交叉 (遗传算法)

交叉（crossover）是遗传算法中由遗传学中染色体交叉互换、生物杂交等现象发展来的一个算法过程。

在自然环境中，基因重组对生物的进化起到非常关键的作用，同理，杂交操作也是遗传算法的核心部分。

交叉技术

杂交操作就是将两个父本染色体上的基因进行重新组合分配，从而产生下一代个体的过程，通过杂交可能会将两个父本的优势基因组合在一起，产生适应度更高、更接近最优解的新个体。通常杂交算法和基因的编码方式有关，当前采用最多的是二进制编码方式，二进制编码的主要杂交算法有：

单点杂交

这种杂交方式是当前使用最多的杂交算法。单点杂交的主要过程是：首先在染色体上随机选择一个交换点；然后确定是在交换点前面部分或者后面部分的基因进行交换；最后根据前面的原则将两父本的染色体基因进行交换重组，从而形成了新的个体，即下一代个体。如有两个父本染色体序列10010|111和00101|010，其中“|”表示交换点，按照父本染色体的交换点前部分交换的原则，产生的新得下一代个体的染色体分别是00101|111和10010|010。

多点杂交

多点杂交算法就是指定了多个交换点用于父本的基因交换重组，具体的执行过程与单点杂交算法类似。

均匀杂交

上述的两种杂交算法存在杂交的染色体中某些部分的基因会被过早地舍弃，这是由于在交换前它们必须确定交换父本染色体交换位前面还是后面的基因，从而对于那些无关的基因段在交换前就已经收敛了。均匀杂交算法（Uniform Crossover）就可以解决上述算法的这种局限性，该算法的主要过程如下：首先随机选择染色体上的交换位；然后随机确定交换的基因是父本染色体上交换位的前部分基因还是后部分基因；最后对父本染色体的基因进行重组从而产生新的下一代个体。

洗牌杂交

该杂交算法的最大特点是通常将染色体的中点作为基因的交换点，即从每个父本中取它们一般的基因重组成新的个体。另外针对于实值编码方式，还有离散杂交、中间杂交、线性杂交和扩展线性杂交等算法。

算法

1. 根据交叉概率（Pc, probability of performing crossover），随机选取种群中C对体。
2. 对每对依次进行如下操作
   1. 将所选两个体的染色体分成N份（N≥2），交换其中相互等长的M对（N>M≥1）

算法示例

Pascal

• 下面是最简模型：对于交叉的一对个体的遗传信息，进行取平均操作：

procedure crossover（k:integer）;//交叉过程
   var h:integer;
   begin
     h:=2*k;
     a[h]:=（a[h]+a[h-1]）/2;//数组a中包含了遗传信息，对一对遗传信息进行取平均
     a[h-1]:=a[h];
   end;

//遗传算法其他部分略去，此示例中，亲代（P）中淘汰一半（奇数编号），另外一半按照轮盘法进行繁殖，并进行交叉、变异操作

参考条目

• 遗传算法
• 交叉互换
• 变异
• 杂交
• 收敛 (遗传算法)