书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第9章目录

9.5　遗传算法，第二部分：选择

选择过程需要评估种群个体的适应度，从而选出更适合繁殖的个体。我们可以将选择过程分为两部分。

1、评估适应度

• 为了让遗传算法有效，我们需要设计一个适应度函数。这个函数会产生一个描述个体适应度的分值。
• 当然，现实世界并不是这么运作的。在现实世界中，生物并没有分值，它们只有两种选择：生存或死亡。
• 但传统遗传算法的最终目的是进化出最佳方案，所以它需要用分值衡量每一种方案的效果。

再一次简化这个问题，假设我们只想进化出单词“cat”。

• 种群中有3个成员：“hut”“car”和“box”。
• “car”有两个正确字符，它的适应度最高。
• “hut”只有一个正确字符，“box”没有正确字符。

• 因此，适应度函数如下：适应度 = 正确字符的数量

  
  
  

  你可能希望看到更复杂的适应度函数，但对于入门学习来说，本例非常合适。

2、创建交配池

• 得到所有个体的适应度后，我们就开始选择合适的个体，并将它们放入交配池。
• 这一步的实现方式有很多种。
• 可以只选择个体中的精英：“哪两个个体的分数是最高的？
  所有后代都将由这两个个体繁殖出来！”在编程实现上，这是最简单的方案，但它不符合多样性原则。
• 如果种群（可能由上千个个体组成）中的两个个体成了唯一的繁殖个体，那么下一代的多样性就会非常低，这会抑制种群的进化过程。
• 也可以扩大交配池中的个体数量——比如，前50%的个体都能繁殖后代，也就是说，如果有1000个个体，那么前500个能繁殖后代。
  这种方案也很容易实现，但不会产生最优的结果。在这种情况下，排名靠前的个体的繁殖机会和排在中间的个体一样。为什么排在第500位的个体有繁殖机会，而排在第501位的个体却没有繁殖机会呢？
• 一种更好的方案是概率方法，我们称为“命运之轮”（又叫作“赌盘”）。

3、命运之轮

我们先看一个简单的例子。假设种群中有5个个体，它们都有自己的适应度分值。

• 首先，我们要单位化这些分值。
  你还记得向量的单位化吗？向量的单位化就是把向量的长度变为1。
  适应度的单位化就是让分值介于0~1，计算它在总适应度中所占的比例。
  我们先把所有元素的适应度相加得到总适应度：
  总适应度 = 3 + 4 + 0.5 + 1.5 + 1 = 10
  再用每个分值除以总适应度，就能得到单位化后的适应度。

  
  

• 下面，我们要开始实现命运之轮。

  
  

• 转动这个轮盘，你会发现B被选中的概率最大，接下来是A，然后是D和E，最后是C。

• 基于概率的选择方法是一种很好的实现方式：
  首先，它保证概率最高的个体有最大的繁殖机会；
  其次，它并不会减弱种群的多样性，和精英选择的方式有所不同，即使是最低分值的个体（C）依然有把基因传给后代的机会。低分值的个体可能有一些非常有用的基因片段，这些片段不能被移除。

• 比如，在“to be or not to be”的进化过程中，可能会出现以下个体。
  A：to be or not to go
  B：to be or not to pi
  C：xxxxxxxxxxxxxxxxbe
  你可以看出，A和B是适应度最高的个体。
  但是它们都不是最优解，因为它们的最后两个字符都不正确。
  尽管C的分值很低，但它最后的基因片段恰好是正确的。
  因此，尽管我们要用A和B产生大部分的后代基因，却仍需要让C有机会参与繁殖过程。