基因重组与突变解析

基因重组（recombination），又称为基因交叉（crossover），就是把两个父辈染色体的部分结构加以替换，生成新的个体的操作。通过这种方式，父辈的特征能遗传给子代，子代应该能够部分或者全部地继承父辈的结构特征和优良基因，更适应环境。

重组操作还可以分为无性重组、有性重组、多亲重组三种。无性重组是指子代由一个父辈染色体产生，有性重组是指子代由两个父辈产生，多亲重组指子代由两个以上父辈产生。

突变（mutation），也称变异，是指产生新的染色体，表现出新的性状。在生物界中，在基因复制过程中出现突变的概率一般是很小的，也可能会产生一些不利的因素，但也有可能会改进已有的特征或产生新的特征。在遗传算法中，变异就是将染色体编码中的一部分按照一个较小的概率进行随机变化，其目的是维持群体的多样性，为选择和重组过程中可能丢失的遗传基因进行修复和补充。变异概率Pm一般都不大，常取0.005左右。

重组和突变是遗传算法中的两个基本操作，它们对遗传算法性能的影响很大。重组和突变算子的类型和实现方式与编码相关，同时也与所求解的问题有关。不同的编码方式对应着不同的重组和突变方法。

二进制编码和值编码的重组方式相似，它们常用的重组方式有：

（1）单点重组（single point crossover）。

单点重组是指在染色体编码串中随机设置一个重组点，编码串中从开始到重组点来自一个父辈，剩下的来自另一个父辈，如图5.3所示。

图5.3　单点重组

（2）两点/多点重组（two/multiple points crossover）。

两点/多点重组和单点重组类似，所不同的是它选择两个或多个重组点，以间隔交换的方式分别从两个父辈复制部分基因。图5.4所示为二进制编码染色体使用三点重组的示例。

图5.4　三点重组

（3）均匀重组（uniform crossover）。

均匀重组是指两个父辈个体的每个基因座上的基因都以相同的概率进行交换，从而形成两个新子代。(www.xing528.com)

（4）运算重组（arithmetic crossover）。

运算重组是指两个父辈间的基因通过执行一些运算来产生子代。如图5.5所示，两个二进制编码的染色体执行与运算重组。

图5.5　与运算重组

两个实数值之间的运算，常按式（5.1）进行：

其中，α是比例因子，由在［-d，1+d］区间均匀分布的随机数产生，一般取d=0.25。通常将适应度值更好的设为father2，α越大代表着子代越像father2，α越小代表着子代越偏向father1。

对于二进制编码的突变操作，通常是在完成重组后，随机选一个位点进行取反。对于值编码，如果是实数值编码，则重组后，通常随机选一些值加或减一个很小的数字。

如果染色体用的是排列编码法，常采用单点重组，并且在选择了重组点后，从开始到重组点这一段的值从一个父辈复制到字节中，剩下的值则扫描另一个父辈，按照其在另一个父辈的顺序加到子节点中。

例5.1　已知排列编码的两个染色体A和B分别为（1，2，3，4，5，6，7，8，9）、（4 5 3 6 8 9 7 2 1），如果在第6个基因座发生重组，请写出子代染色体的编码。

解　重组点在第6个基因座，如果从染色体A选5个，则子代染色体编码为（1，2，3，4，5，6，8，9，7）；如果先从染色体B选5个，则子代染色体编码为（4，5，3，6，8，1，2，7，9）。

排列编码中发生突变，是指顺序发生变化，通常是随机选两个数交换位置。在例5.1中，如果重组后的子代（1，2，3，4，5，6，8，9，7）发生突变，随机选两个数交换位置，比如2和9交换位置，则突变后的染色体编码为（1，9，3，4，5，6，8，2，7）。

对于树编码的染色体，在重组点处将父辈染色体分成两段，通过交换重组点下方部分来创建子代，如图5.6所示。树编码的染色体发生基因突变，通常指树节点的内容发生了改变。

图5.6　树编码染色体重组