遗传算法中的变异操作及其多样性保持作用

交叉算子针对染色体进行操作，而变异算子则针对染色体基因进行操作。每个基因具有相同的变异概率pm>0。变异主要是为了保持种群的多样性，防止算法早熟收敛。变异算子显著影响遗传算法的邻域搜索能力。常见的变异算子有以下几种。

反转变异（inversion）：对染色体的某一随机基因片段进行反转，也可以对整个染色体进行反转（Whitley，1994），如图7.4所示。值得注意的是，反转变异只对与基因位置无关的编码方案（position-independent encoding）有效，如果染色体编码是和基因位（locus）相结合的，那么反转之后，由于基因和基因位发生脱节，会导致染色体失效。反转有时候也被看作是和交叉、变异一样的基本遗传算子。

图7.4　反转变异示例

对换变异（swap mutation）：随机选择两个基因进行对换，如图7.5所示。与反转变异类似，对换变异也存在可行性问题，不一定适合于所有的编码方案。

图7.5　对换变异示例

也可以针对特定的优化问题设计基于邻域搜索的变异算子（local searchbased mutation）。例如，将上述对换变异后得到的染色体看作原染色体的邻居，则一个染色体的邻域（neighborhood）可定义为该染色体经过一次对换变异所产生的所有染色体的集合（玄光南、程润伟，2004）。例如，图7.6显示了某一染色体在选中一个支点后的基于对换变异的邻域。

图7.6　基于对换变异的邻域示例(www.xing528.com)

在上述邻域中，如果某一染色体的适应值优于所有其他染色体，则该染色体为局部最优解（local optimum），并成为变异染色体。显然，邻域存在规模问题。如果限定一个较小的邻域，则搜索速度较快，但局部最优解的质量可能较差；如果扩大邻域规模，局部最优解的质量可能得到提高，但搜索计算量也会随之增加。

均匀变异（uniform mutation）：假设是对染色体的第j个基因进行操作，则在其定义区间[LBj，UBj]中按照均匀分布随机取值替代原先的值。也可以事先确定一个较小的变异域以提高搜索效率。

非均匀变异（non-uniform mutation）：非均匀变异的目的在于，在遗传算法的早期扩大搜索空间，而在后期则进行局域搜索。可以设计如下的非均匀变异算子（Michalewicz，1996）：

其中，vj为变异前基因j的取值，为变异后的赋值；ζ为等于0或1的随机数；g表示当前种群世代数；函数Δ（g，x）返回区间[0，x]内的一个值，并且保证随着g的增加，函数值接近0的概率上升。函数Δ（g，x）定义如下：

其中，γ是区间[0，1]内的随机值，GEN是遗传算法种群世代数的上限，而b是用于控制分布均匀程度的参数，一般取值2～5。

此外，还有高斯变异、柯西变异、多项式变异等（文诗华等，2009）。