如何选择遗传算子：轮盘赌、k-精英与Genitor

选择，也被称为复制（reproduction），是对自然界适者生存机制的模拟。因此，适应值更高的个体应该有更多机会繁衍下一代。在经典的比例选择方式（proportional selection scheme）中，一个适应值为f的个体，应该繁衍出个子代，其中为当前种群的平均适应值。因此，从统计角度来说，适应值在均值以上的个体，子代数量会超过1；而适应值在均值以下的个体，子代数量会小于1。Holland（1992）提出的轮盘赌选择（roulette wheel selection）是最知名的比例选择方式，也是SGA缺省采用的选择方式（Srinivas and Patnaik，1994）。在轮盘赌选择中，选择过程反复执行，执行次数等于种群规模λ，每次为中间种群选出一个个体。每次选择时，个体i的中选概率为：

也可以对轮盘进行改造，在轮盘边缘随机排列所有个体，每个个体占据的面积与其适应值成正比。在轮盘外设置λ个间隔相同的指针。如此，只需要转动一次轮盘，就可以选择出所有中间种群的个体。这一选择机制也被称为随机通用采样（stochastic universal sampling）方式（Whitley，1994）。

比例选择方式存在明显的缺陷。在算法早期，个别特别优秀的个体非常容易控制整个选择过程；而在算法晚期，个体适应值已比较接近，容易出现比例问题（scaling problem），较优个体与较劣个体的中选概率趋近，使得选择过程缺乏效率，接近于随机搜索（Whitley，1989）。因此，可以采用线性排序（linear ranking）选择。将当前种群中的所有个体按照染色体适应值从高到低进行排序，然后根据排序而非适应值进行概率选择。个体i的中选概率为（Back，1994）：

其中，参数η+和η−确定了该线性函数的斜率，一般要求1≤η+≤2，η−=2−η+。当η+=2，η−=0时，最差个体在下一代生存的期望数量为0，最优个体的中选概率远超其他个体中选概率，算法容易早熟收敛；当η+=η−=1时，选择方式退化为完全随机选择。通常，可选择η+=1.1（Back，1994）。

Goldberg等（1989）提出的竞赛选择（tournament selection）可以看作是比例选择和排序选择的组合。在每次选择时，先从当前种群中随机选取q个个体，然后从中选择适应值最高的个体进入中间种群。每次选取的个体数量q称为竞赛规模（tournament size）。常用规模为q=2，这时就被称为二元竞赛（binary tournament）。重复执行上述过程λ次即可产生中间种群。假设将当前种群中的所有个体按染色体适应值从高到低进行排列，那么在竞赛选择方式中，个体i的中选概率为（Back，1994）：

与上述概率选择方式不同，（Back，1994）提出的（μ，λ）和（μ+λ）选择方式来源于进化策略，为确定型选择方式。（μ+λ）选择方式对λ个父代和μ个交叉和变异所得的子代个体进行统一排序，并从中选取μ（μ≤λ）个最好的染色体进入下一代种群。（μ，λ）选择方式则对λ个父代个体进行排序，并从中选取μ个最好的染色体进入中间种群。该选择过程中禁止选取相同的染色体，因此适合于组合优化问题，有助于保证种群的多样性（玄光南、程润伟，2004）。上述选择方法也可以改造成概率型选择：(www.xing528.com)

也可将（μ，λ）选择方式与比例选择方式或排序选择方式进行结合，要求当前种群的前μ个个体按照比例选择方式或排序选择方式进行选择（Back and Hoffmeister，1991）。

此外，在选择过程中也经常用到精英选择（elitist selection），以保证当前种群中的一个或若干个最优个体直接进入下一代种群。当精英个体数量超过1时，则称为k-精英选择（k-elitist selection）。该方法可保证在遗传过程中的最优个体不会被概率型选择方式偶然剔除，以维持遗传算法具有良好的收敛性。

Whitley（1994）提出的Genitor选择方式，则与前述世代选择方式不同，为所谓的稳态选择（steady state selection）方式。Genitor选择采用替换形式，即将父代中的最差个体用子代个体替换。换言之，在Genitor选择方式中，不存在中间种群，每次选取两个父代个体产生一个子代个体，并且立即用子代个体替换当前种群中的最差个体。

Goldberg和Deb（1991）的分析表明，相对于传统的比例选择方式而言，排序选择和竞赛选择更加有效。线性排序选择和二元竞赛选择在效果上相当，但是二元竞赛选择的计算量较小。稳态选择收敛性较好，但容易导致早熟收敛。排序选择和竞赛选择则可以通过引入非线性排序和扩大竞赛规模来提高收敛性能。此外，新种群的构造还可以组合采用不同的选择方式（江瑞等，2001）。