oxigen
Oxigen is a parallel genetic algorithm framework implemented in Rust. The name comes from the merge of OXIdación (Rust translated to Spanish) and GENetic.
The changes introduced in each version can be found in CHANGELOG.md.
To migrate between major version check the migration guide (MIGRATE.md).
Oxigen provides the following features:
- Fast and parallel genetic algorithm implementation (it solves the N Queens problem for N=255 in few seconds). For benchmarks view benchmarks section of this file.
- Customizable mutation and selection rates with constant, linear and quadratic functions according to generations built-in (you can implement your own functions via the
MutationRateandSelectionRatetraits). - Customizable age unfitness of individuals, with no unfitness, linear and quadratic unfitness with threshold according to generations of the individual built-in (you can implement your own age functions via the
Agetrait). - Accumulated
Roulette,TournamentsandCupbuilt-in selection functions (you can implement your own selection functions via theSelectiontrait). SingleCrossPoint,MultiCrossPointandUniformCrossbuilt-in crossover functions (you can implement your own crossover function via theCrossovertrait).- Many built-in survival pressure functions. You can implement your own survival pressure functions via the
SurvivalPressuretrait. Nichesbuilt-inPopulationRefitnessfunction. You can implement your own population refitness functions via thePopulationRefitnesstrait.SolutionFound,GenerationandProgressand more built-in stop criteria (you can implement your own stop criteria via theStopCriteriontrait).Genotypetrait to define the genotype of your genetic algorithm. Whatever struct can implement theGenotypetrait under the following restrictions:- It has a
iterfunction that returns ause std::slice::Iterover its genes. - It has a
into_iterfunction that consumes the individual and returns ause std::vec::IntoIterover its genes. - It has a
from_iterfunction that set the genes from an iterator. - It implements
Display,Clone,SendandSync. - It has functions to
generatea random individual, tomutatean individual, to get thefitnessof an individual and to know if and individualis_solutionof the problem.
- It has a
- Individual's fitness is cached to not do unnecessary recomputations (this can be disabled with
.cache_fitness(false)if your fitness function is stochastic and so you need to recompute fitness in each generation). - Progress statistics can be configured to be printed every certain number of generations to a file.
- Population individuals with their fitnesses can be configured to be printed every certain number of generations to a file.
- Specific initial individuals can be inserted in the genetic algorithm execution.
- Genetic executions can be resumed using the population of the last generation as initial population.
- Coevolution is possible executing little genetic algorithm re-executions inside the fitness function.
Optional feature global_cache
The optional feature global_cache adds a HashMap saving the evaluation of each individual in the full execution.
This cache is useful when the evaluation of each individual is expensive, and it complements the individual-based cache already existing in previous versions (if an individual has been evaluated it is not reevaluated unless cache_fitness is false). In other words, this global cache saves the evaluation of new individuals that are equal to another individual that was evaluated before.
Note that the global cache is not always better, since if the fitness function is cheap the cost of getting and inserting into the cache can be more expensive than it. Take also into account the increase of RAM usage of the global cache.
To enable the global cache add the feature global_cache in the Cargo.toml of your project and set to true the cache_fitness (always true by default) and global_cache (true by default when the global_cache is enabled) properties of your GeneticExecution. Example of Cargo.toml:
[dependencies]
oxigen = { version="2.1", features=["global_cache"] }
Usage
In your Cargo.toml file add the oxigen dependency. Oxigen follows the semver specification for the names of the versions, so major version changes will never break the existent API and the last version should always be used. If a minimum version is required specify that minor version to include that version and all minor versions bigger than it.
[dependencies]
oxigen = "2"
To use oxigen use oxigen::prelude::* and call the run method over a GeneticExecution instance overwriting the default hyperparameters and functions following your needs:
let n_queens: u8 = std::env::args()
.nth(1)
.expect("Enter a number between 4 and 255 as argument")
.parse()
.expect("Enter a number between 4 and 255 as argument");
let progress_log = File::create("progress.csv").expect("Error creating progress log file");
let population_log = File::create("population.txt").expect("Error creating population log file");
let log2 = (f64::from(n_queens) * 4_f64).log2().ceil();
let population_size = 2_i32.pow(log2 as u32) as usize;
let (solutions, generation, progress) = GeneticExecution::<u8, QueensBoard>::new()
.population_size(population_size)
.genotype_size(n_queens as u8)
.mutation_rate(Box::new(MutationRates::Linear(SlopeParams {
start: f64::from(n_queens) / (8_f64 + 2_f64 * log2) / 100_f64,
bound: 0.005,
coefficient: -0.0002,
})))
.selection_rate(Box::new(SelectionRates::Linear(SlopeParams {
start: log2 - 2_f64,
bound: log2 / 1.5,
coefficient: -0.0005,
})))
.select_function(Box::new(SelectionFunctions::Cup))
.age_function(Box::new(AgeFunctions::Quadratic(
AgeThreshold(50),
AgeSlope(1_f64),
)))
.progress_log(20, progress_log)
.population_log(2000, population_log)
.run();
For a full example visit the nqueens-oxigen example.
For more information visit the documentation.
Resuming a previous execution
Since version 1.1.0, genetic algorithm executions return the population of the last generation and new genetic executions accept a initial population. This permits to resume previous executions and it also enables coevolution, since little genetic algorithm re-executions can be launched in the fitness function.
In the following example a execution with 10000 generations is launched and after it is resumed until finding a solution with different rates.
let n_queens: u8 = std::env::args()
.nth(1)
.expect("Enter a number between 4 and 255 as argument")
.parse()
.expect("Enter a number between 4 and 255 as argument");
let progress_log = File::create("progress.csv").expect("Error creating progress log file");
let population_log = File::create("population.txt").expect("Error creating population log file");
let log2 = (f64::from(n_queens) * 4_f64).log2().ceil();
let population_size = 2_i32.pow(log2 as u32) as usize;
let (_solutions, _generation, _progress, population) = GeneticExecution::<u8, QueensBoard>::new()
.population_size(population_size)
.genotype_size(n_queens as u8)
.mutation_rate(Box::new(MutationRates::Linear(SlopeParams {
start: f64::from(n_queens) / (8_f64 + 2_f64 * log2) / 100_f64,
bound: 0.005,
coefficient: -0.0002,
})))
.selection_rate(Box::new(SelectionRates::Linear(SlopeParams {
start: log2 - 2_f64,
bound: log2 / 1.5,
coefficient: -0.0005,
})))
.select_function(Box::new(SelectionFunctions::Cup))
.age_function(Box::new(AgeFunctions::Quadratic(
AgeThreshold(50),
AgeSlope(1_f64),
)))
.stop_criterion(Box::new(StopCriteria::Generation(10000)))
.run();
let (solutions, generation, progress, _population) = GeneticExecution::<u8, QueensBoard>::new()
.population_size(population_size)
.genotype_size(n_queens as u8)
.mutation_rate(Box::new(MutationRates::Linear(SlopeParams {
start: f64::from(n_queens) / (8_f64 + 4_f64 * log2) / 100_f64,
bound: 0.005,
coefficient: -0.0002,
})))
.selection_rate(Box::new(SelectionRates::Linear(SlopeParams {
start: log2 - 4_f64,
bound: log2 / 1.5,
coefficient: -0.0005,
})))
.select_function(Box::new(SelectionFunctions::Cup))
.age_function(Box::new(AgeFunctions::Quadratic(
AgeThreshold(50),
AgeSlope(1_f64),
)))
.population(population)
.progress_log(20, progress_log)
.population_log(2000, population_log)
.run();
Building
To build oxigen, use cargo like for any Rust project:
cargo buildto build in debug mode.cargo build --releaseto build with optimizations.
Due to a bug in cargo workspaces with optional features errors appear building from the root folder (see #12, #19), but building inside each project works flawlessly.
To run benchmarks, you will need a nightly Rust compiler. Uncomment the lines // #![feature(test)] and // mod benchmarks; from lib.rs and then benchmarks can be run using cargo bench --jobs 1 --all-features.
Benchmarks
The following benchmarks have been created to measure the genetic algorithm functions performance:
running 29 tests
test benchmarks::bench_cross_multi_point_255inds ... bench: 895,332 ns/iter (+/- 34,409)
test benchmarks::bench_cross_single_point_255inds ... bench: 227,517 ns/iter (+/- 4,802)
test benchmarks::bench_cross_uniform_255inds ... bench: 304,957 ns/iter (+/- 9,421)
test benchmarks::bench_distance_255 ... bench: 41,669 ns/iter (+/- 45)
test benchmarks::bench_fitness_1024inds ... bench: 14,260 ns/iter (+/- 3,789)
test benchmarks::bench_fitness_age_1024inds ... bench: 32,495 ns/iter (+/- 5,705)
test benchmarks::bench_fitness_age_not_cached_1024inds ... bench: 581,263 ns/iter (+/- 3,988)
test benchmarks::bench_fitness_global_cache_1024inds ... bench: 343,314 ns/iter (+/- 25,763)
test benchmarks::bench_fitness_not_cached_1024inds ... bench: 554,870 ns/iter (+/- 32,916)
test benchmarks::bench_generation_run_tournaments_1024inds ... bench: 4,202,844 ns/iter (+/- 111,604)
test benchmarks::bench_get_fitnesses_1024inds ... bench: 777 ns/iter (+/- 17)
test benchmarks::bench_get_solutions_1024inds ... bench: 2,126 ns/iter (+/- 7)
test benchmarks::bench_mutation_1024inds ... bench: 1,553,265 ns/iter (+/- 23,022)
test benchmarks::bench_refitness_niches_1024inds ... bench: 29,616 ns/iter (+/- 783)
test benchmarks::bench_refitness_none_1024inds ... bench: 29,756 ns/iter (+/- 3,576)
test benchmarks::bench_selection_cup_255inds ... bench: 357,611 ns/iter (+/- 37,254)
test benchmarks::bench_selection_roulette_256inds ... bench: 141,654 ns/iter (+/- 1,338)
test benchmarks::bench_selection_tournaments_256inds ... bench: 616,907 ns/iter (+/- 50,645)
test benchmarks::bench_survival_pressure_children_fight_most_similar_255inds ... bench: 17,748,382 ns/iter (+/- 762,602)
test benchmarks::bench_survival_pressure_children_fight_parents_255inds ... bench: 139,405 ns/iter (+/- 2,267)
test benchmarks::bench_survival_pressure_children_replace_most_similar_255inds ... bench: 17,716,416 ns/iter (+/- 739,662)
test benchmarks::bench_survival_pressure_children_replace_parents_255inds ... bench: 202,788 ns/iter (+/- 18,250)
test benchmarks::bench_survival_pressure_children_replace_parents_and_the_rest_most_similar_255inds ... bench: 1,387,504,266 ns/iter (+/- 45,914,604)
test benchmarks::bench_survival_pressure_children_replace_parents_and_the_rest_random_most_similar_255inds ... bench: 9,389,378 ns/iter (+/- 1,224,136)
test benchmarks::bench_survival_pressure_competitive_overpopulation_255inds ... bench: 12,803,024 ns/iter (+/- 1,946,079)
test benchmarks::bench_survival_pressure_deterministic_overpopulation_255inds ... bench: 220,667 ns/iter (+/- 2,790)
test benchmarks::bench_survival_pressure_overpopulation_255inds ... bench: 12,243,512 ns/iter (+/- 726,154)
test benchmarks::bench_survival_pressure_worst_255inds ... bench: 20,339 ns/iter (+/- 1,113)
test benchmarks::bench_update_progress_1024inds ... bench: 7,595 ns/iter (+/- 378)
These benchmarks have been executed in a Intel Core i7 6700K with 16 GB of DDR4 and a 1024 GB Samsung 970 Evo Plus NVMe SSD in ext4 format in Fedora 33 with Linux kernel 5.9.16.
The difference of performance among the different fitness benchmarks have the following explanations:
bench_fitnessmeasures the performance of a cached execution without cleaning the fitnesses after each bench iteration. This cleaning was not done in previous versions of this README and so it was higher.bench_mutationwas very much faster in previous versions of this README because an error in the benchmark (empty population).bench_fitness_agemeasures the performance with fitness cached in all bench iterations, so it is slightly slower.- Not cached benchmarks measure the performance of not cached executions, with 1 generation individuals in the last case, so the performance is similar but a bit slower for the benchmark that must apply age unfitness.
- The
children_fight_most_similarandchildren_replace_most_similarfunctions have to call the distance functionc * ptimes, wherecis the number of children andpis the size of the population (255 and 1024 respectively in the benchmarks). - The
overpopulationandcompetitive_overpopulationfunctions are similar tochildren_replace_most_similarandchildren_fight_most_similarexcept to they are compared only withmindividuals of the population (mis bigger than the number of children and smaller than the population size, 768 in the benchmarks). Therefore, 3/4 of the comparisons are done in these benchmarks compared tochildren_replace_most_similarandchildren_fight_most_similar. children_replace_parents_and_the_rest_random_most_similaris similar tochildren_replace_parentsbut, after it, random individuals are chosen to fight against the most similar individual in the population until the population size is the original population size. This means between 0 and 254 times random choosing and distance computation over the entire population in function of the repeated parents in each generation.children_replace_parents_and_the_rest_most_similaris like the previous function but it searches the pairs of most similar individuals in the population, which means p2 distance function calls (220 in the benchmark).
Contributing
Contributions are absolutely, positively welcome and encouraged! Contributions come in many forms. You could:
- Submit a feature request or bug report as an issue.
- Ask for improved documentation as an issue.
- Comment on issues that require feedback.
- Contribute code via pull requests.
We aim to keep Oxigen's code quality at the highest level. This means that any code you contribute must be:
- Commented: Public items must be commented.
- Documented: Exposed items must have rustdoc comments with examples, if applicable.
- Styled: Your code should be
rustfmt'd when possible. - Simple: Your code should accomplish its task as simply and idiomatically as possible.
- Tested: You should add (and pass) convincing tests for any functionality you add when it is possible.
- Focused: Your code should do what it's supposed to do and nothing more.
Note that unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in Oxigen by you shall be licensed under Mozilla Public License 2.0.
Reference
Pozo, Martín "Oxigen: Fast, parallel, extensible and adaptable genetic algorithms framework written in Rust".
Bibtex
@misc{
title={Oxigen: Fast, parallel, extensible and adaptable genetic algorithms framework written in Rust},
author={Pozo, Martín},
howpublised = "\url{https://github.com/Martin1887/oxigen}"
}
License
Oxigen is licensed under Mozilla Public License 2.0.
95 Dec 26, 2022
110 Dec 21, 2022
29 Aug 9, 2022
3 Jan 18, 2023
2 Jan 27, 2022
74 Dec 27, 2022
8 Oct 1, 2022
4 Aug 15, 2021
17 Mar 22, 2022
16 Dec 21, 2022
42 Nov 8, 2022
3 Jan 21, 2022
1.2k Dec 26, 2022
95 Jan 1, 2023
1 Dec 1, 2021
327 Dec 19, 2022
30 Nov 24, 2022
483 Dec 22, 2022
12 Nov 3, 2022