交叉 (遺傳算法)

交叉（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）中淘汰一半（奇数编号），另外一半按照轮盘法进行繁殖，并进行交叉、变异操作

參考條目

• 遺傳算法
• 交叉互換
• 變異
• 雜交
• 收斂 (遺傳算法)