遗传编程引擎

这个Rust中的遗传编程库是为“带我去月球”研讨会开发的。

目的

遗传编程涉及将特定问题的解决方案表达为抽象语法树（即，作为将解决问题的计算机程序的表示），然后使用遗传操作生成和改进程序种群。希望最终种群会收敛到一组成功解决所提问题的程序。

遗传编程通过进化最初随机生成的种群的后续代来工作。为了创建新一代，我们将对上一代中的个别程序应用3种遗传操作。

遗传操作包括

• 繁殖。我们从当前代中挑选一个程序并将其复制到下一代。通过挑选表现良好的个体，我们希望保持种群的健康水平。
• 变异。我们从当前代中挑选一个程序，对其进行轻微修改，并将其插入到下一代。变异有助于我们摆脱局部最优。
• 交叉。我们挑选两个程序，并将它们的程序拼接在一起。通过使用交叉，我们希望产生比任一父代更好的程序。

您会注意到，所有这些遗传操作都包含“挑选一个个体”的概念。该库提供了锦标赛选择，它挑选N个随机个体，然后从这些N个个体中选择最佳个体。这为更健康的个体提供了更好的选择机会。

变异和交叉在AST节点级别实现。我们将从AST中随机选择一个节点，并用另一个节点（要么是一个随机生成的子树，要么是从另一个父代中随机选择的同一类型的节点）替换它。

如何使用此库

此库提供了进化框架。要使用它，您需要提供

• AST语法。这是可以用于解决方案的节点类型集合，以及子节点可以出现在哪些父节点中。AST节点表示为具有各种情况的枚举。
• 适应度函数。适应度函数将评估特定解决方案的好坏。在实践中，这意味着你需要提供一个函数，该函数遍历抽象语法树（AST）以某种方式评估它，然后将评估结果按数值进行排名。此函数将被最大化。

语法节点

语法节点指定为枚举类型，需要实现一些特定的特性。尽管如此，这些特性实现中的大部分都可以使用宏自动生成。

#[derive(Clone)]
enum Statement {
    IfFoodAhead(Box<Statement>, Box<Statement>),
    Prog2(Box<Statement>, Box<Statement>),
    Prog3(Box<Statement>, Box<Statement>, Box<Statement>),
    Command(Box<Command>)
}

impl_astnode!(Statement, 1,
              int IfFoodAhead(then, els),
              int Prog2(one, two),
              int Prog3(one, two, three),
              leaf Command(cmd));

适应度函数

适应度函数具有以下形状

fn fitness(program: &Program, rng: &mut Rng) -> SomeFitnessStruct

其中 Program 是 AST 的根类型，而 SomeFitnessStruct 是实现了 Fitness 的任何对象。使用该结构来保留你想要在进化后持久化的任何信息（例如，模拟的跟踪）。如果不要求这样做，可以使用 SimpleFitness 对象。

最终，得分在 ScoreCard 对象中提供，其中包含标签和分数。分数可能是负数以表示惩罚。

SimpleFitness::new(vec![
    ("food_eaten", ant.food_eaten as f32),
    ("complexity_penalty", (depth(ant) as f32) * -10.)
])