如何优化遗传算法中的选择策略？

遗传算法中还有一个很重要的环节，就是选择，也称为复制（reproduction），即从种群中选出作为父代进行交叉重组的染色体。那么，该如何选择呢？根据达尔文的进化论，优胜劣汰，最好的才能适应环境存活下来并繁衍后代。如果用适应度来表示个体对环境的适应能力，那么适应度越强的越容易生存下来。

在遗传算法中，也有类似的适应度函数，也叫评估函数，用来判断群体中的个体的优劣程度。通常，可以直接根据所求问题的目标函数进行评估，而且一般也不需要其他外部信息。比如，对于背包问题，就可以直接用对被挑选物品的价值求和作为适应度函数。再比如，在一些求函数最大值的问题中，就可以将该函数直接作为适应度函数。但有些时候，目标函数并不一定适合直接作为适应度函数，这时需要对目标函数进行转换。

对于适应度函数的设计，一般要求计算应该足够快，因为会被反复使用。另外，适应度函数必须可以定量测量，能够转换目标函数值为相对的适应度值；有时还需要对目标函数进行变换，也称为标定，放大种群中优劣个体之间的差别，增强选优功能。为了将来方便用累加概率等方式进行选择，通常还需要把适应度函数设计成为单值、非负的形式。如果目标函数有约束，则对适应度函数还需要添加惩罚项。

对于一些求最大值的问题，如果目标函数为f（x），则适应度函数F（x）一般可以取为下述三种中的一种：

其中，Cmin为f（x）的最小估计。

其中，c为目标函数界限的保守估计。

相应地，如果是求最小值的问题，则适应度函数F（x）可以取为下述三种中的一种：

其中，Cmax为f（x）的最大估计。

其中，c为目标函数界限的保守估计。

一旦能计算出种群里每个个体的适应度值，就可以进行选择了。然而，选择并不是只挑适应度值高的个体作为双亲，否则就成了确定性优化方法，使种群很快收敛到局部最优解；如果只是随机选择，又体现不出择优选择的优势，导致算法长时间不能收敛，甚至无法收敛。因此，需要找到一个策略，既能使算法较快收敛，又能维持种群的多样性。

按照适者生存的基本原则，我们需要让适应度值高的个体被选中的机会更大，根据适应度值来确定个体被选中的概率。

选择的策略很多，比如轮盘赌选择（roulette wheel selection）、玻尔兹曼选择（Boltzmann selection）、排序选择（rank selection）、联赛选择（tournament selection）、稳态选择（steady state selection）等。下面将介绍一些常用的选择方法。

（1）轮盘赌选择。

就和转轮盘抽奖的游戏一样，将所有的染色体都放在轮盘上，依据其适应度值来决定其在轮盘上占据的范围，如图5.7所示，然后转动转盘来选择用于重组的染色体。这样，适应度值大的染色体被选中的次数就会多了。

图5.7　轮盘赌选择示例

可以用以下算法来模拟轮盘赌选择的过程：

①计算种群中所有染色体适应度值的和S；(www.xing528.com)

②产生一个介于0与S之间的随机数r；

③从第一个染色体的适应度值开始，逐个累加，当累加的和大于r时，停下，返回当前的染色体作为选中的对象。

这个过程就类似模拟转动指针随机选择的过程，圆盘上占面积越大的，被选中的概率也就越大，Python参考代码实现如下：

函数的输入为染色体和对应适应度值的列表，输出为按适应度值大小选中的染色体。函数使用了Python的内建库random，其中random.randint（a，b）用于产生a到b之间的随机整数，random.uniform（a，b）用于产生a到b之间的随机浮点数。

如果使用NumPy包来实现，可以使用np.random.choice（），比如：

其中，fit_value_p用来指定chromosomes中元素的概率，其和应该为1，且与chromosomes的大小相同。

（2）排序选择。

轮盘赌选择策略存在一个问题，就是当适应度值的差别非常大时，比如某个染色体的适应度值占据了轮盘90%以上的面积时，那么其他的染色体将很难有机会被选中。排列序选择通过重新映射适应度值到排序号来解决这个问题，它首先对种群按照适应度值进行排序，然后对每个染色体以排列序号重新分配适应度值，最差的适应度值为1，倒数第二差的为2，依此类推，最好的适应度值将设为N，N为种群染色体的数量。图5.8演示了这种转换关系。

图5.8　排序选择效果演示

通过排序选择进行转换以后，所有染色体就都有机会被选中了，不过这种选择策略会导致收敛变慢。这是因为它大大减少了最佳染色体和其他染色体之间的差异。

（3）稳态选择法。

稳态选择并不算一个特定的选择父代染色体的策略。它的主要思想是染色体的大部分应该存活到下一代，所以每一代中选择一小部分适应度值高的来产生后代，然后用新产生的后代来替换一些适应度值差的染色体。替换的策略一般可以采取以下几种：

①子代的适应度值优于最差的父个体，则子代替换父个体；

②用玻尔兹曼选择来确定是否替换；

③替换整个种群中最差的个体。

（4）精英选择。

在重组和突变的过程中，有着很大的可能性会丢失最好的染色体，精英选择策略就起到了保护这些最佳个体的作用。它首先会将一些最好的染色体先复制到新种群，对于剩下的个体再采用传统的方法进行选择。因为防止了丢失发现的最好解，所以精英选择策略通常可以很快地增强遗传算法的性能。

通常，选择种群数量的2%～5%适应度值最佳的个体，效果最为理想。