遺傳演算法 - 交叉

本章將討論交叉運算元的含義及其其他模組、用途和優點。

交叉簡介

交叉運算元類似於生物繁殖和生物交叉。在這種方法中，選擇多個父代，並使用父代的遺傳物質產生一個或多個子代。交叉通常以高機率應用於遺傳演算法 – p_c。

交叉運算元

本節將討論一些最常用的交叉運算元。需要注意的是，這些交叉運算元非常通用，遺傳演算法設計者也可以選擇實現特定問題的交叉運算元。

單點交叉

在單點交叉中，選擇一個隨機交叉點，並將兩個父代的尾部交換以獲得新的子代。

多點交叉

多點交叉是一點交叉的推廣，其中交替的片段被交換以獲得新的子代。

均勻交叉

在均勻交叉中，我們不將染色體分成片段，而是分別處理每個基因。在這種方法中，我們實際上為每個染色體拋擲一枚硬幣，以決定它是否包含在子代中。我們也可以使硬幣偏向一個父代，以便子代從該父代獲得更多遺傳物質。

算術重組

這通常用於整數表示，並透過使用以下公式取兩個父代的加權平均值來實現：

• 子代1 = α.x + (1-α).y
• 子代2 = α.x + (1-α).y

顯然，如果 α = 0.5，則兩個子代將相同，如下面的影像所示。

Davis 順序交叉 (OX1)

OX1 用於基於排列的交叉，目的是將有關相對順序的資訊傳遞給子代。其工作原理如下：

• 在父代中建立兩個隨機交叉點，並將第一個父代中它們之間的片段複製到第一個子代。

• 現在，從第二個父代的第二個交叉點開始，將第二個父代中剩餘的未使用數字複製到第一個子代，環繞列表。

• 對第二個子代重複此操作，並反轉父代的角色。

還存在許多其他交叉，例如部分對映交叉 (PMX)、基於順序的交叉 (OX2)、洗牌交叉、環交叉等。