Lib.rs

› 科学 › Oxigen
#遗传算法 #遗传 #oxigen #算法 #queens

app nqueens-oxigen

使用oxigen解决N皇后问题

由 Martín Pozo 和 2位贡献者 编写

4个稳定版本

使用旧的Rust 2015

2.2.0 2021年1月9日
2.1.0 2020年1月19日
2.0.0 2019年9月28日
1.2.0 2019年1月5日
1.1.0 2018年8月20日

#445 in 科学

MIT/Apache

145KB
3K SLoC

oxigen

Build Status Current Crates.io Version

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

每个版本中引入的更改可以在CHANGELOG.md中找到。

要迁移到主要版本，请查看迁移指南（MIGRATE.md）。

Oxigen提供了以下功能

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

可选功能global_cache

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

此缓存非常有用，因为当每个个体的评估成本很高时，它补充了之前版本中已经存在的基于个体的缓存（如果个体已被评估，除非cache_fitness是false，否则不会重新评估）。换句话说，此全局缓存保存了与之前评估过的个体相等的新个体的评估。

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

要启用全局缓存，请将功能global_cache添加到项目的Cargo.toml中，并将cache_fitness（默认情况下始终为true）和global_cache（当启用global_cache时默认为true）属性设置为true。以下是Cargo.toml的示例：

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

用法

在您的 Cargo.toml 文件中添加 oxigen 依赖项。Oxigen 遵循 semver 规范来命名版本，因此主要版本变更永远不会破坏现有的 API，并且应始终使用最新版本。如果需要指定最小版本，请指定该次要版本以包括该版本及其所有高于该版本的次要版本。

[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 --jobs 1 --all-features 运行基准测试。

基准测试

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

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:      73,370 ns/iter (+/- 9,106)
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)

这些基准测试在 Intel Core i7 6700K、16 GB DDR4 和 1024 GB 三星 970 Evo Plus NVMe SSD（ext4 格式）的 Fedora 33 操作系统、Linux 内核 5.9.16 上执行。

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

  • bench_fitness 测量了缓存执行的性能，而没有在每次基准测试迭代后清理适应度。由于之前的这个 README 版本中没有进行这种清理，所以它更高。
  • bench_mutation 在这个 README 的先前版本中非常快，因为基准测试中存在错误（空种群）。
  • 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 函数与前面的函数类似，但它会在种群中搜索最相似个体的配对，这意味着 p2 距离函数调用（基准测试中为 220）。

贡献

我们绝对欢迎并鼓励贡献！贡献可以有多种形式。你可以

  1. 以 issue 的形式提交功能请求或错误报告。
  2. 以 issue 的形式请求改进文档。
  3. 对需要反馈的问题进行评论。
  4. 通过 pull requests 提交代码。

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

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

请注意，除非你明确说明，否则你提交给 Oxigen 的任何有意为之的贡献将按照 Mozilla Public License 2.0 许可。

参考

Pozo, Martín "Oxigen：使用 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}"
}

许可

Oxigen 根据 Mozilla Public License 2.0 许可。

依赖关系

~2MB
~36K SLoC