遗传算法中的变异操作及其优化

在自然界中，生物体可能发生某些基因的变异而产生新的个体。同样，在遗传算法中，某些基因座上的基因值可以发生改变。以二值码为例，基因值在变异时取反，即1→0或0→1。

引入变异操作的目的有两个：一是使遗传算法具有局部的随机搜索能力。当遗传算子在接近最优解时，利用变异操作的局部随机搜索能力，加速向最优解收敛；二是使遗传算法维持群体的多样性。特别是在进化过程中，搜索落入某个局部范围而不能摆脱时，通过变异操作，能够跳出局部优化解。显然，当搜索已接近最优解时，若过多地进行变异，也会使最优解的搜索遭到破坏。一般变异操作概率应取较小值。

在遗传算法中，交换操作主要用来增强全局搜索能力，而变异操作则主要用来增强局部搜索能力，这两种操作要配合使用。

以下介绍常用的变异操作。

1）基本变异操作

随机地挑选一个或多个个体，使其中一个或多个基因座的基因值发生改变。以下是一个变异操作的例子。

2）逆转操作(https://www.xing528.com)

逆转操作的基本方法是：在个体码串中随机挑选两个逆转点，在两个逆转点之间，将其基因值以逆转概率pi进行逆向排列。二值码串的逆转操作如下所示：

由上可见，两个逆转点之间的码串1011经逆转操作后，变成了1101。

上述这种逆转操作等效为一种变异操作。但逆转操作的真正目的并不在于变异，而是为了实现重新排序。

在自然界中，有时个体的基因进行重新组合时，并不改变该个体的主要特征，而仅提高该个体的繁殖率。把这种机制应用到遗传算法中，就要求有一种操作，既可对基因进行重新排序，又不改变其适应度值。为此，设计了一种编号的逆转操作。其思想是，将每个基因编号，基因值与编号成固定对应关系，在逆转操作以后，虽然基因座位置改变了，但基因值并不改变，这样其适应度值依然保持与原个体一样。上例经编号对应后，其逆转操作如下：

此时，每个基因都从1～8进行了编号。例如在个体A中第6基因座（编号为6）的基因值是4，经过逆转操作后，第6基因座移到个体A的第3基因座，其编号仍为6，此位置的基因值仍为4。所以个体A＇的适应度值没有改变，但基因的顺序发生了改变。

Goldberg等人将这种逆转操作与交换操作结合起来，形成一种特殊的交换操作（PMX，OX，CX）应用在TSP问题中，效果很好（参见9.6节）。