基于遺傳——蟻群混合算法求解旅行商問題

摘要：作為物流領域中的典型問題，旅行商問題的求解具有十分重要的理論和現實意義。在它的傳統求解方法中，遺傳算法和蟻群算法被廣泛采用，但遺傳算法收斂速度慢，蟻群算法易陷入局部最優，在求解旅行商問題上都有一定的缺陷。本文采用遺傳—蟻群混合算法，充分利用遺傳算法的快速全局搜索能力和蟻群算法的智能性，對旅行商問題求解，并進行了實例仿真。仿真計算結果表明，該算法可以找到最優解或近似最優解，并提高了求解效率。

關鍵詞：旅行商問題；蟻群算法；遺傳—蟻群混合算法；物流

中圖分類號：F253文獻標識碼：A文章編號：1002-3100(2007)04-0128-04

Abstract: As a typical question in logistics field， solution of Traveling Salesman Problem is of both theoretical significance and practical importance. Genetic Algorithms and Ant Colony Algorithms have been adopted extensively in its solving before. But they are not perfect because Genetic Algorithms converges slowly and Ant Colony Algorithms is prone to trap in local optimum. Genetic-Ant Colony Algorithms is used to solve Traveling Salesman Problem in this paper， fully utilizing quick global searching ability of Genetic algorithms intelligence of Ant Colony. Then instance simulation is proposed and the results show that optimum solution or approximate optimum solution can be gotten using the Algorithms and computational efficiency is increased.

Key words: Traveling Salesman Problem; Ant Colony Algorithms; Genetic-Ant Colony Algorithms; logistics

物流與國民經濟及生活的諸多領域密切相關，得到越來越多的重視，甚至被看作是企業“第三利潤的源泉”[1]。因此，作為物流領域中的典型問題，旅行商問題（Traveling Salesman Problem， TSP）的研究具有巨大的經濟意義。

在傳統解決方法中，遺傳算法（Genetic Algorithms，GA）以其快速全局搜索能力在物流領域獲得了廣泛的應用。但遺傳算法在求解到一定程度時，往往作大量的冗余迭代，對于系統中的反饋信息利用不夠，效率較低；蟻群算法也以其較強的魯棒性和智能選擇能力被廣泛應用于旅行商問題（TSP）[2]，分配問題[3]，Job-Shop調度問題[4]。但由于蟻群算法的全局搜索能力較差，易陷入局部最優，很難得到最優解。

本文采用了遺傳—蟻群混合算法，將蟻群算法和遺傳算法的優點有機地結合起來。在初期，用智能蟻搜索到的解替代種群中的較劣個體，提高種群質量，然后按一定的規則進行交叉變異，增加種群的多樣性，從而較快地達到全局最優。最后對典型TSP進行仿真計算，結果表明了該算法的有效性。

1TSP問題的定義

TSP的簡單形象描述如下：給定n個城市，有一個旅行商從某一城市出發，訪問各城市一次且僅有一次后再回到原來出發的城市，要求找出一條最短的巡回路徑。TSP可分為對稱TSP（symmetric traveling salesman problem）和非對稱TSP（asymmetric traveling salesman problem）兩大類，若兩城市往返的距離相同，則為對稱TSP，否則為非對稱TSP。本文研究的是對稱TSP。

2蟻群系統

蟻群系統模型描述如下：現有n個節點，m只螞蟻要搜尋連接每個節點且只經過一次每個節點的最短路徑。設一只螞蟻從一個節點走到下一個節點的時間為1，完成一個完整路徑的時間為n。當m只螞蟻都走完一個完整路徑后，對所有經過的路段進行信息素[5]更新：

3遺傳—蟻群混合算法

與傳統的遺傳算法相比，遺傳—蟻群混合算法有兩點不同：一是由人工智能蟻群的搜索代替了原來完全隨機的編碼；二是選擇操作更具智能化。在該算法中，智能蟻的數據結構和染色體的數據結構是完全一樣的，都用數組來表示，這一點也為實現以上兩點打下了基礎。每只智能蟻（染色體）的結構如圖1所示。

3.1蟻群搜索算法

procedure ant_travel()

begin

把數組visited都置成1；//1表示還沒有訪問過，反之則表示訪問過

把每個螞蟻i都隨機地放在節點j上；

visitedi，j=true；

forint j=0; j

forint i=0; i

按照公式（4）計算p ；

選擇下一個要訪問的節點next；

visitedi， next=true；

endfor

endfor

綜合公式（2）和（3）計算Δτ t；

按照公式（1）更新每條路上的信息量τ ；

end

3.2目標函數

3.3智能選擇

智能選擇是遺傳算法和蟻群算法的結合點，通過智能選擇來實現信息共享。它主要負責智能蟻群和基因之間的信息交換。按照一定的規則，用智能蟻找到的好的個體——目標值較小的個體來代替原來種群中較差的個體——目標值較大的個體。

3.4交叉算子

把節點t放在g中；

do{

x=x-1mod n； y=y+1mod n；//n是結點個數

return g；

end

通過試驗，GSC能有效地消除局部最優，而這正是蟻群算法的缺點之一。

3.5基于局部搜索的變異

為了彌補蟻群算法收斂慢的缺點，使收斂速度加快，擬用基于局部搜索的交換變異方法，如圖3所示。局部搜索通過搜索當前解的鄰域來尋找問題的改進解。染色體的鄰域是通過成對交換產生的染色體集合，對于一對基因，其中一個稱作中心，即它對于給定的鄰域來說是固定的，另一個是隨機選擇的。在一給定的鄰域中，如果一條染色體在適應值上比其它任意染色體都要好，稱其為局部最優。

3.6算法步驟

Step1：初始化各個參數，輸入基礎數據；

Step2：調用蟻群搜索過程ant_travel()；

Step3：計算每只智能蟻的目標值；

Step4：智能選擇；

Step5：局部變異；

Step6：計算每條基因的目標值；

Step7：判斷是否滿足結束條件，如果滿足，則結束，否則轉到Step2。

4模擬仿真

以TSPLIB（http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/）中的gr17，gr21，gr24為例，分別應用遺傳算法，蟻群算法，遺傳—蟻群混合算法進行了仿真。實驗的有關參數如下：在遺傳算法中，種群數量100，進化14 000代，交叉概率0.5，變異概率0.5；在蟻群算法中，α=2，β=2，Q=200，ρ=0.3；在遺傳—蟻群混合算法中，種群數量為40，進化了600代，其它的參數與上面兩種算法相同。每種算法都運行一百次，分別計算這三種算法運行結果的平均值如表1所示及這三種算法運行100次所耗的時間如表2所示。

從表1可以看出，當節點個數比較少的時候，遺傳—蟻群算法找到的路徑的平均長度最短，遺傳算法找到的路徑的平均長度較長，蟻群算法找到的路徑的平均長度最長。但是，隨著節點的增多，蟻群算法的優勢就體現出來了，遺傳一蟻群算法找到的路徑的平均長度最短，而蟻群算法找到的路徑的平均長度較長，遺傳算法找到的路徑的平均長度最長。可見無論節點的多少，遺傳—蟻群算法都能找到較優的解。從表2可以看出遺傳—蟻群混合算法的效率也要明顯高于其它兩種算法。圖4是放映程序針對gr21的算例運行了25次的結果，可以看出蟻群算法每次找到的路徑的波動最小，且絕大部分的值都小于其它兩個算法的值，表明了遺傳—蟻群混合算法的穩定性最好。

5結論

本文為了更好地解決物流領域中的旅行商問題，充分發揮遺傳算法的全局搜索能力和蟻群算法的正反饋能力和協同能力，采用了將遺傳算法融入蟻群算法之中的遺傳—蟻群混合算法進行求解，并且進行了模擬仿真。仿真結果表明，利用遺傳—蟻群混合算法可以找到較好解的能力，大大提高計算效率，計算結果也較為穩定。

參考文獻：

[1] 黃中鼎. 現代物流管理學[M]. 上海：上海財經大學出版社，2004.

[2] Marco Dorigo. Ant algorithms and stigmergy[J]. Future Generation Computer Systems， 2000，16:851-871.

[3]Maniezzo V， Colorni A. An ANTS heuristic for thefrequency assignment problem[J]. Future Generation Computer Systems， 2000，16(8):927-935.

[4] Colorni A， Dorigo M. Ant system for job shopscheduling[J]. Operation Research， 1994，34(1):39-53.

[5] 段海濱. 蟻群算法原理及其應用[M]. 北京：科學出版社，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”