改進的蟻群遺傳算法求解旅行商問題

龍艷群，王蕾蕾（西安建筑科技大學 信息與控制工程學院，西安 710055）

改進的蟻群遺傳算法求解旅行商問題

龍艷群，王蕾蕾
（西安建筑科技大學 信息與控制工程學院，西安 710055）

針對遺傳算法收斂速度過慢的問題，將蟻群算法與遺傳算法相結合，應用于求解旅行商問題，同時對兩種算法求解旅行商問題的結果進行模擬與對比分析，實驗結果表明結合算法可以有效地解決旅行商問題，在求解效率和求解質量上都取得了很好的效果。

遺傳算法；蟻群遺傳結合算法；旅行商問題

1　前言

20世紀70年代以來，人工智能的應用研究得到了迅速的發展，其中關于智能優化算法的研究與應用越來越多，遺傳和蟻群作為兩種比較流行的算法，都具有各自的優勢，本文主要研究在對比兩種算法性能優勢與不足的基礎上，采用兩種算法相結合來解決旅行商問題，從而避免單一算法的缺點。通過實驗數據仿真表明，將蟻群與遺傳算法相結合可以更有效地解決旅行商問題。

2　旅行商問題（TSP）模型

“旅行商問題”也被稱為“旅行推銷員問題”，指一名推銷員要拜訪多個地點時，如何找到拜訪多個地點的最短路徑。求其最短路徑可以用數學模型表示：

假設路徑R=（c0，c1，…，cn-1），滿足 f（R）的值最小，則路徑R就是所求的路徑。

其中ci為城市號，i=（0，1，2，…，n-1）。d（ci，cj）表示城市ci到城市cj的距離。

2.1遺傳算法求解TSP

遺傳算法 （GA）是由美國Michignan大學的Holland于20世紀60年代提出的，其主要原理是以自然選擇和遺傳進化論為基礎，模擬生物界的遺傳規律，對種群中的個體不斷進化，達到產生更優秀種群的目的。

該算法主要特點是：具有自組織、自適應和自學習性，良好的全局優化性和穩健性，較強的魯棒性，易于和其他算法結合，計算過程簡單，操作性強。但存在早熟、收斂速度過慢等缺點。

2.2蟻群遺傳結合算法求解TSP

通過將遺傳算法與蟻群算法結合，形成一種全局優化算法，使得遺傳算法和其他算法取長補短，有效提高了算法的收斂速度，并且還能防止早熟收斂，改進的結合算法的具體實現是，利用蟻群算法經過一次螞蟻全局循環，得到一個較優解集，再將所獲得的優解集作為遺傳算法的初始種群，加快遺傳算法的收斂速度，減少遺傳算法的尋優次數，提高算法的執行效率。

（1）初始化蟻群算法的信息啟發式因子α=1，期望值啟發式因子β=2，信息素揮發系數ρ=0.1，信息素強度Q=100，其中路徑初始信息量為1，初始時刻為0。

（2）初始化螞蟻的位置，將m只螞蟻隨機分配到n個城市中。

（3）根據式（2）計算螞蟻k的狀態轉移概率，即選擇下一個城市概率。

（4）將新加入的城市移動到螞蟻k的禁忌表中，更新禁忌表。

（5）重復步驟（3）、（4），分別求出每只螞蟻遍歷一次的路徑。

（6）將步驟（1）至（5）得到的m只螞蟻的遍歷的路徑作為遺傳算法的初始種群。

（7）初始化遺傳算法的交叉概率pc，變異概率 pm以及最大迭代次數的值。

（8）若i大于最大迭代次數，則結束循環，比較每次循環最短路徑，得到算法的最優解。

下面通過實例來驗證比較兩種算法求解TSP問題的實驗結果。

表1　Oliver 30數據對比結果

通過以上實例數據的仿真對比分析，可以看出結合算法具有更好的優化性能。

圖1　結合算法求解Oliver 30的最優路徑

3　結語

本文采用的改進的蟻群遺傳結合算法，通過蟻群算法迭代獲得一個較優解集，作為遺傳算法的初始種群，然后采用遺傳算法尋求最優解。實驗仿真表明，結合算法在解決 TSP問題上具有較快的收斂速度和較強的全局尋優能力。

主要參考文獻

［1］王超學，孔月萍，董麗麗.智能優化算法與應用［M］.西安：西北大學出版社，2012，9（1）.

［2］于瑩瑩，陳燕，李桃迎.改進的蟻群遺傳算法求解旅行商問題［J］.計算機仿真，2013（11）：30-11.

10.3969/j.issn.1673-0194.2016.17.103

TP312

A

1673-0194（2016）17-0184-02

2016-07-19其解決TSP問題的流程說明：