oxigen

Oxigen是一个用Rust实现的并行遗传算法库。这个名字来源于将OXIgenación（Rust翻译为西班牙语）和GENetic合并。

Oxigen提供以下功能

• 快速且并行的遗传算法实现（它可以在几秒钟内解决N皇后问题，N=255）。有关基准测试，请参阅此文件的基准测试部分。
• 可根据世代内置的常数、线性或二次函数自定义突变和选择率（您可以通过MutationRate和SelectionRate特质实现自己的函数）。
• 可自定义个体的年龄不适应性，内置无不适应性、线性或不适应性以及按个体世代设置的阈值二次不适应性（您可以通过Age特质实现自己的年龄函数）。
• 内置的Roulette、Tournaments和Cup选择函数（您可以通过Selection特质实现自己的选择函数）。
• 内置的SingleCrossPoint、MultiCrossPoint和UniformCross交叉函数（您可以通过Crossover特质实现自己的交叉函数）。
• 许多内置的生存压力函数。您可以通过SurvivalPressure特质实现自己的生存压力函数。
• 内置的Niches PopulationRefitness函数。您可以通过PopulationRefitness特质实现自己的种群再适应函数。
• 内置的SolutionFound、Generation和Progress以及更多停止标准（您可以通过StopCriterion特质实现自己的停止标准）。
• Genotype特质用于定义遗传算法的基因型。以下限制下，任何结构都可以实现Genotype特质
  • 它有一个iter函数，返回一个对其基因的Iter迭代器。
  • 它有一个 into_iter 函数，该函数消费个体并返回其基因的 use std::vec::IntoIter。
  • 它有一个 from_iter 函数，用于从迭代器设置基因。
  • 它实现了 Display、Clone、Send 和 Sync。
  • 它有函数来生成随机个体、突变个体、获取个体的 fitness 以及判断个体是否是问题的 is_solution。
• 个体的 fitness 被缓存，以避免不必要的重新计算（如果您的 fitness 函数是随机的，并且您需要在每一代中重新计算 fitness，则可以通过 .cache_fitness(false) 禁用此功能）。
• 进度统计信息可以配置为每经过一定代数后打印到文件。
• 具有其 fitness 的种群个体可以配置为每经过一定代数后打印到文件。
• 可以在遗传算法执行中插入特定的初始个体。
• 可以使用上一代的种群作为初始种群来恢复遗传执行。
• 通过在 fitness 函数中执行小的遗传算法重新执行，可以实现共同进化。

2 版本和 1 版本之间的差异

• Oxigen 2 更加灵活，因为任何包含 Vec 的 struct 都可以实现 Genotype。在 1 版本中，这是不可能的，因为 Genotype 必须实现 FromIterator。在 2 版本中，已添加一个 from_iter 函数。
• Oxigen 2 修复了问题 #3（内置枚举中的 'Cuadratic' 已被替换为 'Quadratic'）。在 1 版本中没有修复，以避免破坏接口。
• Genotype 中的 fix 函数返回一个布尔值，以指定个体是否已被更改以重新计算其 fitness。
• 每一代得到的解决方案数量现在是使用新的 distance 函数的 Genotype 中不同解决方案的数量。
• u16 类型在 StopCriterion、MutationRate 和 SelectionRate 特性中已被 usize 替换。
• 已添加 PopulationRefitness 特性，以可选地比较种群中的个体并重新调整它们的 fitness。已添加内置的 Niches PopulationRefitness 函数。
• SurvivalPressure 特性已被重新定义，现在它通过杀死个体而不是返回要删除的索引来操作。它还接收一个包含当前代父母和子代的对列表。
• 已添加许多内置的 SurvivalPressure 函数，如 Overpouplation、CompetitiveOverpopulation、DeterministicOverpopulation、ChildrenFightParents、ChildrenFightMostsimilar 等。
• 这两个新增功能允许在不同的搜索空间区域中搜索不同的解决方案，以避免局部次优解并找到不同的解决方案。
• 其他一些小的改进。

新版本 2.1 中的新增功能

可选功能 global_cache 添加了一个 HashMap，用于保存整个执行期间每个个体的评估。

此缓存适用于评估每个个体代价高昂的情况，它补充了之前版本中已存在的基于个体的缓存（如果个体已经被评估，则不会重新评估，除非cache_fitness设置为false）。换句话说，这个全局缓存保存了与之前已评估的个体相同的新的个体的评估。

请注意，全局缓存并不总是更好的选择，因为如果适应度函数成本低，获取和插入缓存的成本可能比它还高。还要考虑到全局缓存会增加RAM的使用量。

要启用全局缓存，请在您的项目的Cargo.toml中添加global_cache特性，并将cache_fitness（默认始终为true）和global_cache（当启用global_cache时默认为true）属性设置为true。Cargo.toml的示例

[dependencies]
oxigen = { version="^2.1", features=["global_cache"] }

用法

在您的Cargo.toml文件中添加oxigen依赖项

[dependencies]
oxigen = "^2"

要使用oxigen，请使用use oxigen::prelude::*并在一个GeneticExecution实例上调用run方法，覆盖默认的超参数和函数以符合您的需求

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();

要查看完整的示例，请访问nqueens-oxigen示例。

有关更多信息，请访问文档。

恢复先前的执行

从版本1.1.0开始，遗传算法执行返回最后一代的种群，新的遗传执行接受一个初始种群。这允许恢复先前的执行，同时也使得协同进化成为可能，因为可以在适应度函数中启动少量遗传算法的重新执行。

在下面的示例中，启动了一个10000代的执行，并在找到解决方案后，以不同的速率恢复执行。

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();

构建

要构建oxigen，使用cargo就像使用任何Rust项目一样

• cargo build以调试模式构建。
• cargo build --release以优化模式构建。

要运行基准测试，您需要一个nightly Rust编译器。取消注释// #![feature(test)]和// mod benchmarks;从lib.rs，然后可以使用cargo bench运行基准测试。

基准测试

以下基准测试已创建以衡量遗传算法函数的性能

running 25 tests
test benchmarks::bench_cross_multi_point_255inds                                                           ... bench:     348,371 ns/iter (+/- 10,506)
test benchmarks::bench_cross_single_point_255inds                                                          ... bench:     113,986 ns/iter (+/- 10,657)
test benchmarks::bench_cross_uniform_255inds                                                               ... bench:      88,426 ns/iter (+/- 2,302)
test benchmarks::bench_distance_255                                                                        ... bench:      20,715 ns/iter (+/- 1,648)
test benchmarks::bench_fitness_1024inds                                                                    ... bench:     377,344 ns/iter (+/- 8,617)
test benchmarks::bench_fitness_age_1024inds                                                                ... bench:      31,360 ns/iter (+/- 1,204)
test benchmarks::bench_fitness_age_not_cached_1024inds                                                     ... bench:     395,056 ns/iter (+/- 24,407)
test benchmarks::bench_fitness_global_cache_1024inds                                                       ... bench:     340,087 ns/iter (+/- 28,889)
test benchmarks::bench_fitness_not_cached_1024inds                                                         ... bench:     373,966 ns/iter (+/- 60,244)
test benchmarks::bench_get_fitnesses_1024inds                                                              ... bench:      18,951 ns/iter (+/- 868)
test benchmarks::bench_get_solutions_1024inds                                                              ... bench:      30,133 ns/iter (+/- 1,612)
test benchmarks::bench_mutation_1024inds                                                                   ... bench:          13 ns/iter (+/- 0)
test benchmarks::bench_selection_cup_255inds                                                               ... bench:     344,873 ns/iter (+/- 40,519)
test benchmarks::bench_selection_roulette_256inds                                                          ... bench:     140,994 ns/iter (+/- 1,294)
test benchmarks::bench_selection_tournaments_256inds                                                       ... bench:     420,272 ns/iter (+/- 49,178)
test benchmarks::bench_survival_pressure_children_fight_most_similar_255inds                               ... bench:  14,948,961 ns/iter (+/- 989,864)
test benchmarks::bench_survival_pressure_children_fight_parents_255inds                                    ... bench:     108,691 ns/iter (+/- 157)
test benchmarks::bench_survival_pressure_children_replace_most_similar_255inds                             ... bench:  14,935,080 ns/iter (+/- 1,221,611)
test benchmarks::bench_survival_pressure_children_replace_parents_255inds                                  ... bench:     167,392 ns/iter (+/- 15,839)
test benchmarks::bench_survival_pressure_children_replace_parents_and_the_rest_most_similar_255inds        ... bench: 737,347,573 ns/iter (+/- 16,773,890)
test benchmarks::bench_survival_pressure_children_replace_parents_and_the_rest_random_most_similar_255inds ... bench:   7,757,258 ns/iter (+/- 612,047)
test benchmarks::bench_survival_pressure_competitive_overpopulation_255inds                                ... bench:  10,727,219 ns/iter (+/- 770,681)
test benchmarks::bench_survival_pressure_deterministic_overpopulation_255inds                              ... bench:     173,745 ns/iter (+/- 609)
test benchmarks::bench_survival_pressure_overpopulation_255inds                                            ... bench:  10,710,336 ns/iter (+/- 657,369)
test benchmarks::bench_survival_pressure_worst_255inds                                                     ... bench:      20,318 ns/iter (+/- 298)
test benchmarks::bench_update_progress_1024inds                                                            ... bench:       7,424 ns/iter (+/- 273)

这些基准测试在Intel Core i7 6700K、16 GB DDR4和512 GB三星950 Pro NVMe SSD（格式为ext4）的Fedora 30系统上，使用Linux内核5.2.9执行。

不同适应度基准测试之间性能差异的解释如下

• bench_fitness 测量缓存执行清理每个基准迭代后的适应度性能。这种清理是比未缓存基准慢一些的原因。
• bench_fitness_age 测量在所有基准迭代中缓存适应度的性能，因此它非常快。
• 未缓存的基准测量未缓存执行的性能，在最后一种情况下，有1代个体，所以性能相似，但比必须应用年龄不适应性的基准慢一点。
• 函数 children_fight_most_similar 和 children_replace_most_similar 需要调用距离函数 c * p 次，其中 c 是孩子的数量，p 是种群的大小（基准中分别是255和1024）。
• 函数 overpopulation 和 competitive_overpopulation 与 children_replace_most_similar 和 children_fight_most_similar 类似，只是它们只与种群中的 m 个个体进行比较（m 大于孩子的数量，小于种群的大小，基准中为768）。因此，与 children_replace_most_similar 和 children_fight_most_similar 相比，这些基准中有3/4的比较是在这些基准中完成的。
• children_replace_parents_and_the_rest_random_most_similar 与 children_replace_parents 类似，但在之后，选择随机个体与种群中最相似个体进行战斗，直到种群大小恢复到原始种群大小。这意味着在每一代中，根据重复的父母，在整个种群中进行0到254次随机选择和距离计算。
• children_replace_parents_and_the_rest_most_similar 与前面的函数类似，但它搜索种群中最相似个体的对，这意味着有 p² 次距离函数调用（基准中有 2²⁰ 次）。

贡献

我们绝对欢迎和鼓励贡献！贡献的形式有很多。你可以

1. 作为一个 问题 提交功能请求或错误报告。
2. 作为一个 问题 请求改进文档。
3. 对需要反馈的问题进行评论。
4. 通过 拉取请求 贡献代码，提交你的PR之前不要忘记运行 cargo fmt！

我们旨在保持Rocket的代码质量处于最高水平。这意味着你贡献的任何代码都必须是

• 注释：公共项目 必须 进行注释。
• 文档：公开项目 必须 有 rustdoc 注释，如有适用，还应包含示例。
• 样式：尽可能使用 rustfmt 对你的代码进行格式化。
• 简单：你的代码应该尽可能简单地完成其任务。
• 测试：如果可能，你应该为添加的任何功能添加（并通过）令人信服的测试。
• 聚焦：你的代码应该只做它应该做的事情，不做其他任何事情。

请注意，除非你明确声明，否则你提交给 oxigen 的任何贡献都将根据 MIT 许可证和 Apache 许可证 2.0 双重许可，不附加任何额外条款或条件。

参考

Pozo, M.M. "Oxigen: 用 Rust 编写的快速、并行、可扩展和自适应遗传算法库"。

Bibtex

@misc{
  title={Oxigen: Fast, parallel, extensible and adaptable genetic algorithm library written in Rust},
  author={Pozo M.M.},
  howpublised = "\url{https://github.com/Martin1887/oxigen}"
}

许可证

oxigen 根据 Mozilla 公共许可证 2.0 许可。