遗传算法系列之四:遗传算法的变种

这篇博客介绍遗传算法变种。我们认为，遗传算法的变种可以分为两个类别：有效性变种和应用性变种。有效性变种用于提高遗传算法的性能。应用性变种是遗传算法适用于不同问题形成的，用于扩展遗传算法的应用范围。

有效性变种

有效性变种是人们“变化”了的典型遗传算法，主要用于提高遗传算法各方面的性能。有效性变种的“变”体现在交叉操作、选择操作、参数自适应以及和其他算法的结合。

1. 交叉变种

典型遗传算法选择两条染色体，按照pc的概率决定是否交叉，如果选择交叉则随机选择一点并将这点之后的基因交换。这种交叉方式被称为单点杂交。

交叉操作拥有多种变种。1）多点杂交指定了多个交换点用于父本的基因交换重组，具体的执行过程如下图所示。2）均匀杂交。单点和多点杂交算法存在杂交的染色体中某些部分的基因会被过早地舍弃，这是由于在交换前它们必须确定交换父本染色体交换位前面还是后面的基因，从而对于那些无关的基因段在交换前就已经收敛了。均匀杂交算法（Uniform Crossover）就可以解决上述算法的这种局限性，该算法的主要过程如下：首先随机选择染色体上的交换位；然后随机确定交换的基因是父本染色体上交换位的前部分基因还是后部分还部分基因；最后对父本染色体的基因进行重组从而产生新的下一代个体。3）洗牌杂交。洗牌杂交的最大特点是通常将染色体的中点作为基因的交换点，即从每个父本中取它们一般的基因重组成新的个体。另外针对于实值编码方式，还有离散杂交、中间杂交、线性杂交和扩展线性杂交等算法。

2. 选择策略

轮盘赌算法和锦标赛算法是常见两种选择策略。

2.1. 轮盘赌算法是最简单选择方法。轮盘赌算法有放回地采样出原种群大小的新一代种群，个体

的采样概率如下所示。

(1)

下图是一个轮盘赌算法的示意图。

2.2. 锦标赛算法也是常见的选择方法。锦标赛法从大小为n的种群随机选择k(k小于n)个个体，然后在k个个体中选择适应度最大的个体作为下一代种群的一个个体；反复多次，直到下一代种群有n个个体。

精英保留策略可以认为是选择策略的一部分。精英保留策略是指每次迭代都保留已发现的最优解。这个策略是显而易见的，我们不可能舍弃已发现的最优解，而只使用最后一代种群的最优解。根据上一篇博客，典型遗传算法并不能保证收敛到全局最优解，但采用精英保留策略的典型遗传算法是保证收敛到全局最优解的。虽然这个理论分析没啥卵用，但实际上大家都是这么干的。

3. 多种群并行

在大自然，物种的进化是以多种群的形式进行的。一般来说，一个物种只有一个种群了，意味着这个物种有灭亡的危险。受此启发，人们提出了多种群遗传算法。顾名思义，多种群遗传算法就是保持多个种群同时进化，具体流程如下图所示。多种群遗传算法和遗传算法执行多次的区别在于移民，种群之间会通过移民的方式交换基因。这种移民操作把自然界的杂交优势体现的淋淋尽致啊。

4. 自适应遗传算法

遗传算法有两个参数很重要：交叉概率pc和变异概率pm。针对不同的优化问题，需要反复实验来确定pc和pm，好烦的。而且在遗传算法的不同阶段，我们需要不同的pc和pm。当种群中各个个体适应度趋于一致或者趋于局部最优时，使pc和pm增加；当群体适应度比较分散时，使pc和pm减少。甚至于不同个体也应该有不同的pc和pm。对于适应度高的个体，我们应该减少pc和pm以保护他进入下一代；反之对适应度低的个体，我们应该增加pc和pm让他探索新的天地。

根据上一篇博客介绍的模式定理，遗传算法需要在，选择操作引起的收敛性和变异交叉操作引起的多样性之间取得平衡。Srinivas.M and Patnaik.L.M (1994) 就是为了让遗传算法把这事做得更好，提出来自适应遗传算法的。在论文中，pc和pm的计算公式如下：

5. 混合遗传算法

遗传算法的全局搜索能力强，但局部搜索能力就soso了。这句话怎么理解呢？比如对于一条染色体，遗传算法并不会去看看这条染色体周围局部的染色体适应度怎么样，是否比这条染色体好。遗传算法会通过变异和交叉产生新的染色体，但新产生的染色体可能和旧染色差的很远。因此遗传算法的局部搜索能力差。

梯度法、爬山法和贪心法等算法的局部搜索能力强，运算效率也高。若能够将问题相关的启发知识引入这些算法，这些算法的威力不可小觑。受此启发，人们提出了混合遗传算法，将遗传算法和这些算法结合起来。混合遗传算法的框架是遗传算法的，只是生成新一代种群之后，对每个个体使用局部搜索算法寻找个体周围的局部最优点。

混合遗传算法是很常见的策略。比如遗传算法应用于排序问题，生成新一代种群之后，将个体中相邻两个元素交换次序，如果新的个体适应度更高则保留。这种贪心的变种往往能大幅度提高遗传算法的收敛速率。

应用性变种

应用性变种是遗传算法适用于不同问题形成的，用于扩展遗传算法的应用范围。一般来说，将遗传算法应用在新类型的问题，我们需要设计新的编码方式以及相应的变异交叉操作，或者新的更新迭代方式。下面我们介绍两个常见的问题。

1. 排序问题

排序问题是遗传算法重要的应用领域之一。比如文章开头，我们就将分配问题建模成排序问题。分配问题建模成排序问题并不是很好的方式，有些问题却需要建模成排序问题。我们熟悉的旅行商问题很适合建模成排序问题。旅行商问题：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市；路径的选择目标是要求得的路径路程为所有路径之中的最小值。

排序编码。排序编码为1-n的随机排列，其中第j位基因的值v，表示第v个元素排在第j位。例如I＝[1 3 5 4 2], 表示1排首位，3、5和4紧跟着，2排在最后。

排序变异操作。排序问题的变异操作随机选取个体的两个基因进行交换。我们随机选择个体I=[1 3 5 4 2]中两个基因位，假设选择的基因位是1和3，变异结果I=[5 3 1 4 2]。

排序交叉操作。排序问题的交叉操作可以采用顺序交(0rderCmssover,Ox)。比如我们有两个个体的染色体。

保持中间部分不变。

移走p1中已存在o1中的城市，得到2-1-8-9-3，依次摆到o2中。类似地，可以到到o2。

2. 路径规划问题

路径规划问题也是遗传算法重要的应用领域，之前的文章也有介绍。下图是用栅格表示的机器人路径规划环境，栅格是最简单的路径规划环境表示方法。图中的路线就是机器人的前进路线。

路径规划编码。个体染色体有起始点和终止点，起始点和终止之间是机器人的中间停靠点。上图中的路线可以用下面基因序列表示。 路径规划变异操作。大体思路是先将中间点随机变异，然后检查变异的中间点是否在障碍物内，如果是则选择一个附近位置。下图就是这种变异操作的示意图。

路径规划交叉操作。大体思路是随机选择一个基因位，将这个基因位以及之后的所有基因进行交换。如果产生的路径会进过障碍物，则调整交叉点附近的节点，绕过障碍物。

总体来看，应用性变种都是遗传算法在不同问题变化。由于问题的不同，编码方式、变异操作和交叉操作都需要发生变化。在当年遗传算法火的时候，这是灌水利器啊。应用性变种的变异和交叉操作的一个重要策略是：1）先随机变异和交叉，2）然后根据问题特点，对产生的个体进行和修正。

后记 我写这篇文章的时候，越发觉得自己功底不够。这篇概要性的文章就变成现在这样的流水账。以后慎写这种类型的文章，要写也要多做准备。

参考文献

Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1994, 24(4): 656-667.