混合遺傳算法解決單目標旅行商問題的研究

袁成林

（1.廣西大學計算機與電子信息學院，廣西 南寧 530004；2.廣西醫科大學基礎醫學院，廣西 南寧530021）

遺傳算法是一種基于進化策略的優化算法[1]，被廣泛使用在組合優化問題中。但是遺傳算法在解決問題的時候也有諸多不足，首先是在早期的搜索中常常丟失種群的多樣性[2]。在單目標優化中，對于種群的適應性方面的研究很多，多樣性保持方面常常用的手段是小生境方法。其次由于遺傳算法的局部能力差，也有學者采用其他局部搜索算法來構造混合遺傳算法[3]，這些方法對在種群適應性方面是有效的，但是在種群多樣性方面卻不足，對于有的優化問題來說，多樣性保持對搜索最優解有著重要的作用。最后在旅行商問題中普通的交叉算子會破壞要交換的基因片段，針對這個問題本文提出了對應連通子圖交叉(Corresponding Connected Subgraph Crossover,CCSC)，結合LK局部搜索和小生境等操作構造一種基于CCSC的混合遺傳算法(CHGA)。通過幾個實例的計算和對比表明，算法的設計是有效的，求解質量也有較大提高。

1 對應連通子圖交叉

交叉算子是遺傳算法中最重要的部分，既可以使個體發生變化，又能保留父體的優秀基因片段，使種群向著理想的方向進化。對于旅行商問題通常采取自然編碼，即每個基因位對應一個城市的號碼。例如1-2-3-4-5-6表示依次經過城市1到6最后回到1。這種編碼容易理解，效率高。但是在這種編碼方式下普通的交叉算法就不再適用了，因為可能產生沒有意義的個體。圖1中兩條可用路徑經過交叉操作以后，產生的1-1-5-6-3-6路徑是沒有意義的。為了解決這個問題，很多學者提出了適用于TSP的交叉算子，像順序插入法，啟發式交叉等，但是這些算法會打亂交叉片段中的基因位置因而不能保存父體的優秀基因片段。

圖1 普通交叉操作產生的不可用路徑

基于以上分析，本文提出一種新的交叉算子：對應連通子圖交叉(CCSC)。這種交叉方法可以做到嚴格的交叉，即子代的基因都是從父代繼承所得，所有基因片段都可以在兩個父體中找到。CCSC通過合并兩條父體路徑，構造連通圖G。對G中的對應連通子圖進行搜索，然后進行交叉，交叉策略可以是：隨機選擇某個或若干個對應連通子圖進行交換，還可以采用貪婪選擇對每個對應連通子圖進行多次搜索，找到最短個體，這幾種方法時間復雜度都在O(n)之內，本文權衡算法效率和求解效果，決定采用隨機選擇若干個對應連通子圖進行交換的交叉策略。明顯可以看出若對應連通子圖的個數大于等于1，CCSC就可以創造兩個以上的后代個體。若有k個對應連通子圖，則可以產生2k+1-2個個體，減2是因為有兩個個體和父體是相同的。

對應連通子圖：合并兩條父體路徑，構造連通圖G，在G中，刪除兩條父體路徑的重合邊后，得到圖G1，G1的某個連通子圖中的節點在兩條父體中均為連續的基因片段，此連通子圖稱為對應連通子圖。

圖2-2中的a-b-c-d,a-c-b-d和g-h-j-i-k,g-i-h-j-k就是兩對對應連通子圖：

圖2 對應連通子圖示意

尋找對應連通子圖的流程如下：

（1）刪除圖G中兩條路徑重合的邊。

（2）建立隊列Q，把度為1的n個節點放在隊頭，設定計數器K=n。

（3）從隊列的n+1個節點開始進行廣度遍歷，找出所有連通子圖，把遍歷過的點前移，記錄連通子圖結點個數ti，直至所有節點操作完成。

（4）對結點個數ti大于等于3的連通子圖i，對其父體進行檢查如果連通子圖的節點在兩父體中均為連續的基因片段，則該連通子圖為一個對應連通子圖g，記錄g。

（5）如果符合要求的連通子圖都已經搜索就退出程序，否則返回步驟4。

2 混合遺傳算法CHGA的實現

2.1 選擇算子

選擇算子是算法中關鍵的一環，可以選擇優秀個體進入下一代進行交叉和變異操作，本文采用的是輪盤賭法，根據個體的適應度進行選擇，適應度越大個體被選擇的概率就越大，并且可以保留少量適應度較差的個體，增加種群多樣性。

2.2 變異和交叉算子

變異：本文采用兩點隨機交換的變異操作對種群進行擾動，跳出某些局部最優解。

交叉：本文采用第一節提出的對應聯通子圖交叉作為交叉算子。

2.3 小生境操作

經過輪盤賭選擇等操作后，適應度大的個體更容易進入新種群，種群里就會出現很多一樣或者很相似的個體，這樣就會導致算法早熟，結果陷入局部最優解，所以本文引入小生境操作來保持物種多樣性。

具體方法是：假設種群共有n個個體，首先計算個體i(i=1,2…n)和其他個體之間的小生境距離L(i,j)。在對個體i與其他所有個體的小生境距離L(i,j)求和，計算出個體i的小生境排序值循環這個步驟直到計算出所有si。升序排列si后，用隨機產生的個體代替si最高的n個個體，算法的時間復雜度是O(n2)。

其中L(i,j)的求法是，假設TSP共有N個城市，取個體i的第k（k=1,2,3…N）個基因位城市i(k)，在個體j中找到城市i(k)的位置t，對i(k)和j(t)左右兩邊城市號做同或操作∶L(i,j)=i(k+1)⊙j(t+1)+ i(k+1)⊙j(t-1)+ i(k-1)⊙j(t+1)+ i(k-1)⊙j(t-1)。因為 0≤L(i,j)≤2，所以 0≤si≤2n。小生境排序值si越大說明個體i周圍的個體越多。對種群的非精英個體進行小生境操作，起到了保留精英又增加種群多樣性的作用。

2.4 局部搜索

在CHGA中局部搜索算法起著十分重要的作用。它可以使種群迅速向著希望的方向進化。它的另一個作用是使 CHGA算法的第一代開始就能夠找到更多的對應連通子圖，提高算法的效率，本文采用LK算法[4]作為局部搜索。

在本文中局部搜索的另一個作用是使算法的第一代開始就能夠找到等多的對應連通子圖(CCS)，通過實驗測試 CCSC結合局部搜索算法可以產生的對應連通子圖的大致個數，實驗采用TSPLIB中的att532,nrw1379 和 u1817三個算例，用3-OPT，3-OPT和MO-LK算法對50個隨即路徑進行測試，平均實驗結果如表1。通過實驗發現2-OPT與CCSC結合在90%的情況下可以產生可用個體，也就是至少有一對對應連通子圖而，結合3-OPT和LK算法的CCSC產生可用解的概率達到了將近100%。

表1 不同局部搜索找到的對應連通子圖個數

3 算例實驗

3.1 實驗環境

為驗證所設計算法的有效性，基于如下實驗環境進行相關實驗：聯想臺式機，其配置為：

（1）CPU：AMD 64 2X 4400+；

（2）內存：2 G DDR2；

（3）操作系統：Windows XP

程序以 VC++2008編寫及編譯，實驗使用數據取自TSPLIB。算法各參數如表1所示。實驗結果均為運行算法10次后計算得到的平均值、最優值以及最差值。

3.2 實驗參數

表2 混合遺傳算法算法的參數設置

3.3 實驗結果

本文的算例采用 TSPLIB數據庫中的 Att48、Eil51、Eil76、Kroa100、 Ch130 、Tsp225、Ch 150等6個測試對象，每個算例進行20次計算，結果取平均值，并與文獻[5,6]進行了對比。具體數據如下：

表3 混合遺傳算法算法的計算結果

圖3 算例Eil51收斂情況

實驗結果表明，本文所做改進效果明顯。100以內規模的問題每次都可以計算出TSPLAB最優解，而且速度上相比文獻所述也有優勢。100以上問題在 20次實驗中可以計算出TSPLAB最優解，而且平均值的誤差也在1%以內。在下一步工作中，可以著力改善算法的計算速度，并且向更大規模的問題發起挑戰。

[1] Holland John H. Adaptation in natural andartificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[J]. USA: University of Michigan, 1975.

[2] 馬良.旅行推銷員問題的算法綜述[J].數學實踐與認識,2000,32(2):156-165.

[3] 葛繼科,丘玉輝,等.遺傳算法研究綜述[J],計算機應用研究,2008,25(10): 2911-2917.

[4] Helsgaun K. General k-opt submoves for the Lin–Kernighan TSP heuristic[J]. Mathematical Programming Computation, 2009,1(2-3): 119-163.

[5] 孫凱,吳紅星,王浩,丁家棟.蟻群與粒子混合算法求解TSP問題[J].計算機工程與應用,2012,48(34):60-63.

[6] 李哲,夏立,莊浩俊,董紅生.MMAS_EC 算法求解旅行商問題[J].計算機工程與應用,2011,47(9):41-47.