常用的选择策略及其特点

选择是从当前群体中选择能够产生后代的一些个体的过程。遗传算法的基本原理就是达尔文的自然选择原理，选择是遗传算法的推动力。选择策略对算法性能的影响会起到举足轻重的作用，不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。较大的选择压力使最优个体具有较高的复制数目，从而使算法收敛速度较快，但也容易出现过早收敛现象。相对而言，较小的选择压力一般能使群体保持足够的多样性，从而增大了算法收敛到全局最优的概率，但算法的收敛速度较慢。一般来说，算法的初始阶段宜采用较低的选择压力，这有利于扩展搜索空间；而在算法的终止阶段宜采用较高的选择压力，这有利于找到最好的解域，这样选择就能将遗传搜索引向最优解。

下面讨论几种常用的选择策略。

1.基于适应值比例的选择

基于适应值比例的选择是最基本的选择方法，在该方法中，每个个体被选择的期望值与该个体的适应值的大小成比例。这种选择方法体现了生物进化过程中“适者生存，优胜劣汰”的思想，保证了优良基因可遗传给下一代个体。

在这种选择方法中，首先根据当前群体中个体的适应值，按式（2-28）计算出每个个体的选择概率：

式中，fi 是群体中第i个个体的适应值，N 是群体规模。然后根据计算出来的选择概率进行选择。不同的具体选择过程，导致了不同的基于适应值比例的选择方法。

下面介绍几种常见的基于适应值比例的选择方法。

1）繁殖池选择

繁殖池选择根据计算出来的选择概率，按照式（2-29）计算每个个体的繁殖量Ni：

这里Round（x）表示与x 距离最小的整数。

计算出每个个体的繁殖量后，我们即可将它们分别复制Ni 个以生成一个临时群体，即繁殖池。再通过在繁殖池中随机地抽取成对个体进行交配，所产生的后代将取代当前群体形成下一代种群。显然，个体复制到繁殖池的数目越大，则它被选择进行交配的可能性就越大，而对于Ni=0的个体，它们将被淘汰出整个演化过程。

在实现算法时需要注意的是，繁殖池中个体的数目不一定正好等于N。

2）轮盘赌选择

轮盘赌选择是遗传算法中用得最多的选择策略之一。轮盘赌选择根据所计算的每个个体的选择概率，将一个赌轮划分为n 个扇形，其中第i 个扇形面积的大小与第i 个个体的适应值成比例。然后转动赌轮N 次，每次选择一个个体，其具体选择过程在第二章第一节中已经介绍，在此不再赘述。

轮盘赌选择策略不同于繁殖池选择之处是：群体中的每个个体在轮盘赌选择策略下，都有被选择的机会，而在繁殖池选择策略下，具有较小适应值的个体将被剥夺生存的权利。

例2-9 假定当前种群中有10个个体，分别用1，2，…，10表示，其适应值和选择概率如表2-6所示。

表2-6　种群中个体适应值及选择概率

若在轮盘赌选择中，所产生的10个随机数为：0.96，0.05，0.45，0.20，0.21，0.49，0.71，0.67，0.31，0.26，那么所选择的10个个体为：9，1，3，2，2，4，5，5，2，2。

从例2-9中可以看出，个体9被选择了1次。若使用繁殖池选择，则由于个体9的繁殖量N9=Round（p9·N）=Round（0.04×10）=0，所以个体9不会被选择。

3）随机遍历抽样

在轮盘赌选择方法中，适应值大的个体被选择的概率较大，因而可能出现被选择的个体仅为少数几个适应值较大的个体的情况，这有可能导致算法过早收敛到局部最优。随机遍历抽样是为了防止这种现象的发生，减少随机误差。随机遍历抽样首先构造一个赌轮，构造方法与轮盘赌选择中的方法相同，按图2-8所示放置N 个指针，任何两个指针之间的夹角相等，然后转动赌轮一次，当赌轮停止转动后，将N 个指针所指向的N 个个体选择出来。

图2-8　赌轮示意图

随机遍历抽样过程的实现如下：

其中rand（）生成[0，1）上的一个随机数，ek=pop_size×pk。

易知，用随机遍历抽样所选择的个体i的个数ni 满足下列不等式：

例2-10 假定当前种群中有10个个体，分别用1，2，…，10表示，其适应值和选择概率如表2-6所示。

表2-6　种群中个体适应值及选择概率

若算法中所产生的随机数为ptr=0.23，那么所选择的10个个体为：1，1，2，2，3，4，5，5，7，8。

4）Boltzmann选择

Boltzmann选择实际上是一种适应值调节策略。在Boltzmann选择中，选择概率由式（2-31）计算：

式中，T 是一个控制参数。当T 取较大值时，具有较小的选择压力，即适应值的相对比例变小，当取较小值时，具有较大的选择压力，即适应值的相对比例变大。当用上式计算出个体的选择概率后，再用轮盘赌方法进行父体的选择。

2.基于排名的选择

使用基于适应值比例的选择策略常常会出现过早收敛和停滞现象。避免这些现象的方法之一是使用基于排名的选择（Ranking Selection）策略。这种策略首先根据个体适应值的大小对个体进行排序，然后根据个体的次序对每个个体分配选择概率，所指定的概率仅依赖于个体的次序，而与个体的绝对适应值无关。有了选择概率，我们就可以用轮盘赌选择策略选择父体了。这种策略可以在群体中个体的适应值变化较大时，减少选择压力，而当群体中个体适应值变化较小时，保持选择压力。(www.xing528.com)

1）线性排名选择

线性排名选择最初是由J.E.Baker提出来的，其目的是为了克服基于适应值比例的选择策略的不足之处。在线性排名选择中，先将群体中的个体按照其适应值从小到大排序为x1，x2，…，xN，即x1 是适应值最小的个体，xN 是适应值最大的个体，然后按照某个关于个体排名的线性函数来分配每个个体的选择概率。有许多不同的线性函数可以用来计算个体的选择概率，下面是一种常用的选择概率分配方法，具体地说，个体xi 的选择概率为：

2）指数排名选择

指数排名选择与线性排名选择类似，先将群体中的个体按照其适应值从小到大排序为x1，x2，…，xN，然后按照式（2-33）分配个体的选择概率为：

式中，c ∈（0，1]，是一个预先指定的常数。

所以式（2-33）又可写为：

同样，有许多不同的指数函数可以用来分配指数排名选择中个体的选择概率。例如，Michalewicz Z提出将群体中的个体按照适应值从小到大排序为x1，x2，…，xN，然后用式（2-36）分配个体的选择概率：

式中，q 是一个常数，表示最好个体的选择概率。

当然，也可以用其他的非线性函数来分配选择概率pi，只要满足以下条件即可：

（1）若群体P={x1，x2，…，xN}，个体适应值为f（x1）≤f（x2）≤… ≤f（xN），则分配的选择概率pi 满足p1 ≤p2 ≤… ≤pN。

3.基于局部竞争的选择

基于适应值比例的选择和基于排名的选择都是根据个体的适应值在种群中所占的比例或排名位置来确定选择概率，然后再根据选择概率进行选择。所以，这两种选择策略在群体规模很大时，其额外计算量（如计算总体适应值或排序）也相当大，而基于局部竞争选择机制的选择策略则能在一定程度上避免这些问题。

1）锦标赛选择

在锦标赛选择中，从群体中随机地选择k 个个体进行比较，适应值最大的个体将被选择作为生成下一代的父体，这个过程反复进行N 次。参数k 称为竞争规模，通常取k=2。

2）Boltzmann锦标赛选择