鄭培豪

（四川大學(xué)電子信息學(xué)院，成都610065）

0 引言

遺傳算法（Genetic Algorithm，GA）最初是由J. D.Bagley 在1967 年提出的，該算法是一種基于達(dá)爾文生物自然選擇和遺傳機制的隨機搜索算法，隨著大量學(xué)者多年的研究和發(fā)展，GA 依然成為了無數(shù)著作中使用的最通用的全局優(yōu)化求解方法之一[1]。遺傳算法屬于仿生啟發(fā)式算法，具有良好的擴(kuò)展性、強大的全局搜索能力、容易與其他算法結(jié)合的特點，在旅行商問題、全局優(yōu)化問題、規(guī)劃調(diào)度問題中有這廣泛的應(yīng)用。Ahmed[2]提出了一種新的順序建設(shè)性交叉算子，為TSP生成了高質(zhì)量的解決方案。Nagata 和Soler[3]提出了一種新的非對稱TSP 遺傳算法。Deep 和Adane[4]針對順序交叉算子提出了改進(jìn)的樹形結(jié)構(gòu)。Kumar 等提出了TSP 不同交叉算子的比較分析，并表明部分映射的交叉給出了最短的路徑[5]。Liu[6]提出改進(jìn)的遺傳算法，通過對變異操作進(jìn)行增強突變，在交叉操作中使用異構(gòu)配對選擇代替隨機選擇，最終在解決TSP 問題時其效果優(yōu)于傳統(tǒng)的遺傳算法。葛[7]提出一種染色體擇優(yōu)策略，有效減少了算法陷入局部最優(yōu)的情況。胡[8]結(jié)合了遺傳算法的全局搜索能力和蟻群算法的反饋機制，并驗證了其算法相較于單遺傳算法和蟻群算法有更好的尋優(yōu)能力。Ma[9]最后，基于遺傳算法框架和2-opt 選擇策略，提出了一種混合遺傳算法。仿真結(jié)果表明了該算法的有效性。楊[10]提出了一種改進(jìn)單親遺傳算法進(jìn)行路線優(yōu)化，提高了計算效率。朱[11]對單親遺傳算法進(jìn)行了遞階式編碼相比于普通單親遺傳算法收斂精度提升40%。

1 遺傳算法及經(jīng)典交叉算子

遺傳算法是模擬自然進(jìn)化過程來搜索全局最優(yōu)解的方法。從一組隨機生成的初始解（稱為種群）開始搜索過程。其中每一個在種群內(nèi)的個體都稱為染色體（個體），它可以是多種不同的編碼形式，現(xiàn)實意義代表著問題的一個解。在種群的繁衍過程中染色體會被遺傳到子代中并在遺傳過程中發(fā)生一些變異。在每一代種群中，適應(yīng)度被用來衡量度個體的質(zhì)量。下一代染色體被稱為后代。后代是通過上一代染色體的雜交或變異而形成的。在形成新一代的過程中，將根據(jù)后代適應(yīng)度的大小進(jìn)行篩選，一些適應(yīng)度較小的將被淘汰，以便保持種群規(guī)模不變。適應(yīng)度高的染色體被選擇的概率較高，因此經(jīng)過幾代后，算法收斂到最佳染色體，這可能是問題的最優(yōu)解或次優(yōu)解（算法流程如圖1）。在遺傳算法中，交叉算子和染色體變異是最為重要的兩個遺傳操作，對種群的豐富性、后代合理性有著重要的影響，本文以交叉算子為研究對象，通過對交叉算子的改進(jìn)來提升算法的整體性能。圖1 為遺傳算法流程圖。

圖1 遺傳算法流程圖

（1）部分映射交叉算子：部分映射交叉（Partial-Mapped Crossover，PMX）是由Goldberg 與Lingle 提出的[12]。在父母身上選擇兩個隨機切割點來構(gòu)建后代后，切割點之間的部分、父母一方的字符串被映射到另一方的字符串上，剩余的信息被交換。例如，考慮兩個雙親旅行，在第3 位和第4 位之間隨機有一個切割點，在第6 位和第7 位之間有另一個切割點，如下所示（用“|”標(biāo)記的兩個切割點）：

映射部分位于切割點之間。在這個例子中，映射系統(tǒng)是4?5、5?4 和6?3?，F(xiàn)在，兩個映射部分相互復(fù)制，以生成如下子代：

然后，我們可以（從原始父母那里）為那些沒有沖突的基因直接進(jìn)行填充表示，如下所示：

因此，第一個后代中的第一個×是3，它來自第一個親本，但是3 已經(jīng)在這個后代中，所以我們檢查映射6?3，由此得到：

（2）順序交叉算子。順序交叉（Order Crossover，0X）是由Davis 提出的[13]。它通過選擇父代的一個子代，并保留另一個父代的相對位序來建立后代。例如，考慮以下兩個父母的旅行（隨機地用“|”標(biāo)記兩個切割點）：

后代是以下列方式產(chǎn)生的。首先，這些比特以類似的方式被復(fù)制到后代的切口之間，這就給出了

此后，從一個父代的第二個切割點開始，以相同的順序復(fù)制另一個父代的位，省略現(xiàn)有的位。從第二個切割點開始，第二個父代中的位順序為“2→1→8→7→6→5→4→3”刪除第一個后代中的位4、5 和6 后，新序列為“2→1→8→7→3”該序列從第二個切割點開始放置在第一個后代中：

O1=（873|456|21）。類似地，我們也完成了第二個代：

（3）循環(huán)交叉算子。循環(huán)交叉（Cycle Crossover，CX），首先由Oliver 等人提出[14]。使用這種技術(shù)來創(chuàng)造后代，使得每一個位置的基因都來自父母中的一方：

應(yīng)用CX 技術(shù)后，產(chǎn)生的后代如下：

和他們的父母完全一樣。子代與父代相同在遺傳學(xué)中是不存在的，在算法中將會嚴(yán)重影響種群的豐富性，不利于算法的全局搜索能力。

2 改進(jìn)循環(huán)交叉算子

本文基于循環(huán)交叉算子（CX）提出一種新的交叉算子自適應(yīng)改進(jìn)循環(huán)交叉算子（ICX），其工作原理與CX相似，與此同時，它使用循環(huán)直到最后一位從父母那里產(chǎn)生兩個后代。并且本文提出的ICX 不再是從父代中隨機的選擇基因作為子代第一個基因，本文固定某個父代的第一個基因為本文最初選的基因，也就是說某個父代的第一個基因一定是位于其中一個子代基因序列中的第一位，其中關(guān)于具體父代的選擇我通過判斷父代適應(yīng)度來確定，以適應(yīng)度較大父代的第一個基因作為第一個子代的第一個基因。同時本文參考文獻(xiàn)[15]采用了自適應(yīng)交叉率。以下是其具體的交叉步驟：

第一步：在當(dāng)前交叉率下選擇雙親進(jìn)行交叉操作；

第二步：計算父代適應(yīng)度，將適應(yīng)度較大父代中的一個基因為第一個后代的第一位（假設(shè)是第二個父代）；

第三步：從步驟2 中選擇的基因在第一父代中找到，并選擇相同位置處第二個父代中的基因，再找到第一個父代中該基因的位置，最后，將為第二個父代該位置處的基因，作為第二子代中第一個位置處的基因；

第四步：從步驟3 中選擇的基因在第一個父代中找到，并選擇相同位置處第二個父代中的基因，作為第一個子代中第二個位置處的基因。（注意:對于遺傳給第一個后代的基因，本文選擇兩次移動，對于遺傳給第二個后代的基因，選擇一次移動）；

第五步：往后的每個位置重復(fù)步驟3 和4，直到第一個父代的第一位不再出現(xiàn)在第二個子代中（完成一個周期），過程可能終止；

第六步：如果留下一些基因，并將已經(jīng)遺傳的基因在其兩個父代中的位置省略。對于剩余的位，重復(fù)步驟2、3 和4 以完成該過程。

第七步：比較兩個子代個體的適應(yīng)度，對于適應(yīng)度較小的子代進(jìn)行剔除，更新交叉率。

在文獻(xiàn)[16]中提出了一種交叉算子CX2，也是解決了循環(huán)交叉算子種會產(chǎn)生與父代相同子代的情況，但是沒有對父代中基因的選擇做出規(guī)定，而是隨機選擇一個父代，同時該文獻(xiàn)中的交叉率為固定值。

3 性能測試

為了體現(xiàn)出本文所提出算法相比于經(jīng)典交叉孫子和對比交叉算子CX2 的優(yōu)越性，其中算法參數(shù)的選擇保持和對比CX2 算子試驗中相同的參數(shù)。

（1）實驗一：為了證明算法的一般性，本文選擇TSPLIB（包含了TSP 及其相關(guān)問題的問題庫）中的3 個實例Gr21、Fri26 和Dantzig42 如表1。三者均是對稱旅行商實例且城市節(jié)點數(shù)量不多。

表1

（2）實驗二：為了驗證本文算法在非對稱性旅行商問題和大規(guī)模旅行商問題中的表現(xiàn)，選擇TSPLIB 中7個 非 對 稱 的 旅 行 商 實 例ftv33、ftv38、ft53、ftv170、rbg323、rbg358、kro124p。對于每個實例，保持實驗運行次數(shù)。前三個實例中為算法選擇公共參數(shù)，即種群大小M、最大遺傳代數(shù)G、初始交叉Pc 和突變Pm 概率相同，后四個實例中將種群大小M、最大遺傳代數(shù)G相同。

表2

4 實驗分析

實驗一中，本研究選取了對稱TSP 實例，結(jié)果顯示ICX 相較于其他算子在收斂精度和穩(wěn)定性上仍有提升。尤其在實例Dantzig42 上效果最為顯著，并且ICX的最差值竟然比其他算子的最優(yōu)值還有更加接近精確的最佳值。在最終的效果上，ICX 相比于PMX、OX、CX最優(yōu)值分別提升了46%、43%、40%。ICX 與對比算法CX 在實驗中達(dá)到過精確的最佳值699，而PMX、OX、CX 卻沒有給出過一次最佳值。同時相較于CX2 最差值和平均值本文提出的交叉算子ICX 明顯更優(yōu)。

實驗二中，本研究選用了非對稱TSP 實例，其城市節(jié)點數(shù)量從34 到358，其中Ftv33、Ftv38、Ftv53 在種群大小和最大遺傳代數(shù)上區(qū)別于后面四個實例。實例Ftv53、Ftv170 中，ICX 在最終效果上的提升最為明顯。相比其他三種經(jīng)典交叉算子，ICX 在這兩個實例中最優(yōu)值的提升分別為：18%、21%、20%；52%、58%、50%，相比于對比交叉算子CX2 可以看到越是在城市節(jié)點數(shù)量較多的實例中如，Rbg323、Rbg358、Kro124p 提升最為明顯。值得注意的是，在實例Rbg323 中ICX 的最優(yōu)值反而是略低于OX，平均值低于PMX、OX，而ICX 算子有明顯的改善。同樣在實例Kro124p 中對比算子CX2 的表現(xiàn)是不及PMX 的，但本文提出的交叉算子變現(xiàn)是幾種交叉算子中最好的。

5 結(jié)語

根據(jù)上述對比實驗總結(jié)出，本文所提出的改進(jìn)循環(huán)交叉算子ICX，在絕大數(shù)情況下相比于PMX、OX、CX有著一定的提升，具有一定的適用性?？傮w來說在遺傳算法中使用本文所提出的交叉算子ICX 在大多方面比使用經(jīng)典交叉算子PMX、OX 和CX 交叉算子表現(xiàn)得更好，在針對ft53、dantzig42 和ftv170 實例時，算法效率分別超過20%、70%和100%，同時相較于CX2 本文提出的算法有著更好的泛化性能。總結(jié)得出，本文提出的改進(jìn)循環(huán)交叉算子確實有助于遺傳算法收斂精度的提升，尤其是在城市節(jié)點較多的實例中，本文提出的交叉算子ICX 比CX2 有更加優(yōu)異的表現(xiàn)。