oxigen

Oxigen是一个用Rust实现的并行遗传算法库。这个名字来源于将“OXI”dación（Rust翻译成西班牙语）和“GEN”etic合并。

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。
• 现在每一代得到的解决方案的数量是使用 Genotype 的新 distance 函数得到的不同解决方案的数量。
• u16 类型已更改为 usize，在 StopCriterion、MutationRate 和 SelectionRate 特性中。
• 已添加 PopulationRefitness 特性，以可选地比较种群中的个体，重新调整它们的 fitness。已添加内置的 Niches PopulationRefitness 函数。
• SurvivalPressure 特性已被重新定义，现在它杀死个体而不是返回要删除的索引。它还接收一个包含代中父母和子代对的列表。
• 已添加许多内置的 SurvivalPressure 函数，如 Overpouplation、CompetitiveOverpopulation、DeterministicOverpopulation、ChildrenFightParents、ChildrenFightMostsimilar 等。
• 这两个新增功能允许在搜索空间的各个区域中搜索不同的解决方案，以避免局部次优解并找到不同的解决方案。
• 其他一些小的改进。

用法

在您的 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 以优化模式构建。

要运行基准测试，您需要一个 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_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_not_cached_fitness_1024inds                                                         ... bench:     373,966 ns/iter (+/- 60,244)
test benchmarks::bench_not_cached_fitness_age_1024inds                                                     ... bench:     395,056 ns/iter (+/- 24,407)
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. 提交一个功能请求或错误报告作为一个 issue。
2. 以 issue 的形式请求改进文档。
3. 对需要反馈的问题进行评论。
4. 通过 pull requests 贡献代码，提交之前别忘了运行 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 下授权。