5 重组
遗传算法中的重组有时称为” 交叉”，重组包含了交叉。重组算法是改进遗传算法最 有效的环节，它通过结合交配群体中包含的遗传信息产生新的个体。因为遗传算法中有 二进制编码、实值编码、排列编码、树编码等，因此必须也有与编码方式相适应的不同 的重组算法。
下面介绍几种经典的重组算法：
1) 重组算法的代表——离散重组算法(Discrete recombination)： 离散重组算法在个体间执行变量值的交换，在生成交配个体时，交配个体中每个变 量可以等概率地挑选一个父个体对应变量作为自身的值。其几何特征表现如下，离散重 组产生了父代所在的超立方体的角：
考虑以下两个个体，每个个体有3 个变量(3 维)： 父个体1：13 24 5 父个体2：124 3 24 生成的子个体可以是：124 24 24。
2) 实数值重组(Real valued recombination)： 实值重组算法可以实现对变量为实数值的个体的重组，它包括中间重组、线性重 组、扩展线性重组等。
2.1) 中间重组： 中间重组是一种仅适用于实数变量个体的重组算法。这里后代的变量值是在父辈变 量的区间上选择的。生成子代个体的公式如下：
其中，αi 是[-d， 1 + d] 之间的随机数，它是一个随机均匀选择的比例因子。
参数d 的值代表可能产生的后代的区域大小。d = 0 表示后代的变量值的区域大小
与父代是一样的，此时称为”(标准的) 中间重组”。但是，由于后代的大多数变量不是在
可能区域的边界上生成的，因此变量所覆盖的面积有可能会越来越小。因此，仅用d = 0
的标准中间重组就会发生这种变量空间收缩现象。因此，通过设置更大的d 值可以防止
这种现象。一般设置d = 0:25，此时可以在统计学上保证后代的变量值的范围不会缩小。
如图所示：
例如父个体为： 父个体1：0.4 1.2 -0.3 父个体2：0.2 0.7 0.6 生成的子个体可以是：0.3 0.9 0.4。 中间重组能够稍微超出父代所在的超立方体的边界，如图所示：
2.2) 线性重组： 线性重组类似与中间重组。产生子代个体的公式如下：
对比中间重组可见，线性重组只有一个 ，即所有个体的 是一样的。并且α同样是[-d; 1 + d] 之间的随机数，代表随机均匀选择的比例因子。
对于d 的解析跟中间重组是一样的。 线性重组产生的后代，其变量是在父代所在的直线上，如图所示：
另外还有扩展线性重组，其详细介绍可以参见[Müh94]。
3) 离散值重组(Discrete valued recombination)： 离散值重组的概念和方法跟实值重组类似，只不过在算法执行的过程中要限制个体基因均为整数值。
4) 值互换重组——交叉(Values exchanged recombination——crossover)： 这种重组方式就是两个父代个体交换染色体片段产生新个体的过程，因此也称为交 叉操作。 交叉操作中，个体的染色体编码可以是实值、也可以是二进制，比如： [0 1 0 1 1 1 0 1] 和[1.1 2.0 3.4 2.7 1.6] 这些类型的染色体都可以进行交叉操作，一般 更多地用在二进制或格雷码编码的个体中。 交叉有分单点、双点和多点交叉。它们是根据交叉点的数量分类的。其中多点交叉 的示意图如下：
此外还有均匀交叉、洗牌交叉，这里就不一一赘述了。 这里要介绍一下” 减少代理” 交叉：
4.1) 减少代理交叉(Crossover with reduced surrogate)： 上面的交叉算法的交叉结果可能会产生和父代性状一样的个体，如果在遗传算法中 想让交叉得到的子代中更多的个体拥有与父代个体不一样的性状，这时就可以用减少代 理的交叉算法。 减少代理交叉算法尽可能地产生全新性状的个体，这是通过限制交叉点的位置来实 现的——控制交叉点只出现在父代两个交叉个体的基因值不同的地方。
4.2) 匹配交叉(matched crossover)： 对于排列编码的个体，染色体中每个变量的值都是独一无二的。这意味着不能使用 上面所述的交叉算法。匹配交叉算法通过计算父代两个交叉个体中互相呈现中心对称的 基因片段来设置交叉点，再进行基因片段互换。