一種求解TSP問題的混合算法

谷文祥，李向濤，王春穎，李國媛，殷明浩

（東北師范大學計算機科學與信息技術學院，吉林 長春 130117）

一種求解TSP問題的混合算法

谷文祥，李向濤，王春穎，李國媛，殷明浩

（東北師范大學計算機科學與信息技術學院，吉林 長春 130117）

結合粒子群算法、蟻群算法、重力搜索算法提出了一種新的混合算法——TSP-GPAA.該算法將粒子群算法和重力搜索算法加入到蟻群算法中，利用粒子群算法的全局搜索能力解決了蟻群算法的初始信息素匱乏的問題，并且重力搜索算法將粒子群算法和蟻群算法參數進行優化，明顯提高了蟻群算法的優化性能.實驗表明新算法對于解決TSP問題是有效的.

蟻群算法；粒子群算法；重力搜索算法；旅行商問題

0 引言

TSP問題是一個重要的組合優化問題，已經被證明是NP完備的.任何能使該問題的求解得以簡化的方法，都會受到高度的評價和關注.雖然目前存在一些可以精確地求解TSP問題的算法，但針對大規模的TSP問題，這些算法往往不能勝任.為了解決這一問題，研究人員提出了多種智能算法來處理TSP問題，目前被廣泛使用的有遺傳算法［1－3］、人工神經網絡方法［4］、粒子群算法［5－7］、模擬退火算法［8］、蟻群算法［9］等.然而，這些算法大多不盡如人意，容易陷入局部極小或收斂過慢等問題.近些年，研究人員發現幾種智能算法靈活的組合可以為求解TSP提供更好的啟發式信息，并且這類混合算法在處理TSP問題上可以提供更有效的行為和更高的靈活性.鑒于以上的原因，混合的智能算法越來越受到人們的關注.由于混合智能算法的研究還處于起步階段，所以，研究用混合智能算法解決TSP問題是必要的.

蟻群算法是由意大利學者M.Dorgo，V.Maniezzo和A.Colorni于20世紀90年代初提出的一種新型的智能優化算法，已經被應用到TSP問題［10－12］，并且取得一定的效果.它采用了一種正反饋機制，通過信息素的不斷更新，最終收斂于最優解.但是，在算法的初級階段信息素匱乏，導致了求解速度較慢.并且，該算法是典型的概率算法，算法中的參數設定通常是由試驗方法確定，這也導致了算法的優化性能要與人的經驗密切相關，很難達到算法性能最優.

雖然現在有很多文章是采用混合的算法去解決TSP，但是目前還沒有人結合蟻群算法、粒子群算法、重力搜索算法這三種算法解決TSP問題.粒子群算法是一種全局優化算法，雖然在求解組合優化問題的方面稍顯遜色，但是由于初始粒子的隨機分布這一特點，將其用于組合優化問題時，該算法仍具有較強的全局搜索能力和較快的求解速度.另一方面由Rashedi和Hossein提出的重力搜索算法由于其在逼近最優解時速度較快［13］，可以有效對系統的參數進行優化.綜合以上的原因，本文提出了一種結合上述三種算法的混合智能算法：TSP-GPAA.在TSP-GPAA算法中，重力搜索算法用于解決蟻群算法參數和粒子群算法參數的優化，粒子群算法則用于解決蟻群算法初級階段信息素匱乏從而導致求解速度變慢的問題.

1 算法基礎

1.1 蟻群算法

該算法通過模擬螞蟻的覓食行為，找到最優解.螞蟻覓食的時候會在所走過的路徑上留下信息激素，同時信息激素會隨時間而揮發.一條路徑走過的螞蟻越多，留下的信息激素越多；反過來，信息激素濃度高的路徑上會吸引更多的螞蟻.通過這種正向反饋，最終將找到一條最優路徑.為了避免螞蟻兩次走上同一條路徑（非法路徑），為每個螞蟻設置一個禁忌表以記錄它已走過的路徑.

1.2 粒子群算法

在某一個空間中初始化一群隨機的粒子，通過迭代找到最優解.在每一次的迭代中，粒子通過兩個極值來更新自己.第一個就是粒子本身所找到的最優解pBest.另一個極值是整個種群目前找到的最優解gBest.

其中：V＝［v1，v2，…，vd］是粒子的速度；X＝［x1，x2，…，xd］是粒子的當前位置；rand（）是（0，1）之間的隨機數；c1，c2被稱為學習因子，用于調整粒子更新的步長；ω是加權系數.

1.3 重力搜索算法

重力搜索算法（GSA）是由Esmat Rashedi和Hossein Nezamabadi－pour等提出的一種源于對物理學中的策略搜索進行模擬的新的進化技術.初始為一組隨機解，通過迭代搜尋最優值，物體在解空間里隨著最優的物體進行迭代.

2 TSP-GPAA算法

2.1 對粒子群算法的改進

在標準PSO算法的基礎上發展了離散的PSO算法來解決TSP問題［6］.粒子的位置可以定義為序列x＝ ［x1，x2，…，xn，xn＋1］，xi∈E，x1＝xn＋1，當所有xi與xi＋1之間的弧存在 時，速 度定義 為v＝（（i，j）），i，j∈｛1，…，N｝，其中（i，j）是一對置換序列，則速度表示一組置換序列的有序列表.此外，位置與位置之間可以做減法操作，結果為速度；速度與速度間可以做加法操作，結果為速度；位置與速度間可以做加法操作，結果為位置.粒子的位置與位置的加法操作，結果為一組置換序列.速度更新公式為：

其中：α′，β′為隨機數；α′（pBest－X）表示基本交換序中以概率α′保留；同理β′也是類似的作用，⊕為兩個交換序的合并因子.

2.2 重力搜索算法對參數的選擇

在利用蟻群優化求解TSP問題的過程中，參數α，β，ρ是通過實驗確定的，它們對算法性能也有很大的影響.啟發式因子α值的大小實際上反映了路徑信息素的相對重要性.期望啟發式因子β體現了啟發式信息在指導蟻群搜索過程中的相對重要性，其大小反映了在尋優過程中先驗性、確定因素的作用強度.信息素持久因子ρ反映了螞蟻個體之間互相影響的強弱.參數α，β，ρ相互配合對蟻群算法性能的影響和作用是密切的.

在利用重力搜索算法對蟻群算法的α，β，ρ和粒子群算法中的α′，β′訓練的過程中，物體被表示成一個5維實數編碼串，每個物體的位置都是一個潛在的解.將物體的前3維反饋到蟻群系統并按目標函數就可以計算出其適應值，根據適應度的大小衡量解的優劣.將第i個物體的速度也定義為一個5維的向量，記為Vi＝（vi1，vi2，vi3，vi4，vi5），運用重力搜索算法的速度和位置的公式進行更新.

表1 α′，β′，α，β，ρ的參數組合及最優路徑

2.3 一種新的TSP-GPAA算法

粒子群算法比較適合求解連續優化問題，在求解組合優化問題上則顯得遜色一點.但是，由于其初始粒子的隨機分布，使得粒子群算法在解決這類問題時，仍有較強的搜索能力和求解速度.蟻群算法在求解組合優化問題上是優于粒子群算法的，但由于它的信息素開始的時候是一種均勻的分布，使得蟻群算法的早期有著一種盲目性.而重力搜索算法比較適合于解決連續優化問題，我們對兩個算法的參數進行訓練從而使其能夠自適應指導參數的選擇.

TSP-GPAA算法的步驟

（1）將改進的粒子群算法中的參數α′，β′和改進的蟻群算法中的參數α，β，ρ作為重力搜索算法入口的調用變量，對其進行轉化，然后訓練產生一組解.

（2）將這組解的前2維作為粒子群算法的入口參數值，運用改進的粒子群求解TSP問題，迭代n次后，將得到問題的粗解.

（3）利用步驟（2）中得到的粗解調整改進的蟻群算法中信息素的初始分布，運用改進的蟻群算法求解TSP問題，得到問題的最優解.

（4）將步驟（3）運行完成后得到的最優解作為重力搜索算法的適應評價函數，根據適應度的大小調整步驟（1）中的5個參數的值.進入步驟（2）再次訓練，找到最優解，從而得出一組參數的值.

（5）重復以上的步驟（1），（2），（3），（4），得到10組能夠找到最優解的參數.

由于蟻群算法和粒子群算法以及重力搜索算法都是隨機的算法，每次運行的結果都是不一樣的，所以應對這些組合再次用蟻群算法和粒子群算法進行訓練，從而找到最優解及其參數的最佳組合.

3 模擬實驗及結果

為了驗證算法的有效性，以TSP標準庫中的Burma14，Odyssey of ulysses22和oliver30為例，將10次運行得到的α′，β′和α，β，ρ不同的優化組合及優化路徑分別列在同表中.實驗中參數m為城市數，Q＝1 000.見表1.

從表1中可以看出10次模擬實驗中，對于Burma14最短路徑為30.878 5，等于TSP庫中給定的值，Odyssey of ulysses22的最短路徑最優解為75.398 4，最差值為75.543 2，都優于TSP庫中的75.665 1.Oliver30最短路徑最優解為423.740 6，最差值為424.102 0，最優解等于 TSP庫中的423.740 6.

4 結束語

本文提出的TSP-GPAA算法是結合了蟻群算法、粒子群算法、重力搜索算法的一種混合算法.將粒子群算法和重力搜索算法加入到蟻群算法中，解決了蟻群算法的初始信息素匱乏問題，并將參數進行優化，提高了蟻群算法的優化性能.實驗表明所提出的算法對于解決TSP問題是有效的.但由于結合了三種智能算法，其運行的時間較長.并且，我們只對蟻群算法和粒子群算法的部分參數進行選擇，因此參數的選擇還有待進一步的研究.

［1］ FORGEL D，APPLYING B.Evolutionary programming to selected traveling salesman problem［J］.Cybernetics and System，1993，24：27-36.

［2］ GREFENSTETTE J J.Genetic algorithms for the traveling salesman problems［C］／／Proceedings of an International Conference on Genetic Algorithms and Their Applications，Pittsburgh，USA：1985：160-168.

［3］ FEI LIU，GUANGZHOU ZENG.Study of genetic algorithm with reinforcement learning to solve the TSP［J］.Expert Systems with Applications，2009，5：6995-7001.

［4］ ANDISHEH ALIMORADI，ALI MORADZADEH，REZA NADERI，et al.Prediction of geological hazardous zones in front of a tunnel face using TSP-203and artificial neural networks［J］.Tunnelling and Underground Space Technology，2008，11：711-717.

［5］ SHI X H，LIANG Y C，et al.Particle swarm optimization-based algorithms for TSP and generalized TSP［J］.Information Processing Letters，2007，8：169-176.

［6］ 谷文祥，蘇衛華，劉曉龍.構建園區網健壯體系的比較研究［J］.東北師大學報：自然科學版，2010，42（1）：47-52.

［7］ ANGELINE P J.Using selection to improve particle swarm optimization［C］／／IEEE International Conference on Evolutionary Computation，Alaska：Anchorage，1998，5：4-9.

［8］ KLAUS MEER.Simulated annealing versus metropolis for a TSP instance［J］.Information Processing Letters，2007，12：216-219.

［9］ AHMED AL-ANI.Feature subset selection using ant colony optimization［J］.International Journal of Computational Intelligence，2006：53-58.

［10］ WU B，SHI ZZ.An ant colony algorithm based partition algorithm for TSP［J］.Chinese Journal of Computers，2001，24（12）：1328-1333.

［11］ DORIGO M，GAM BARDELLA L.An ant colony algorithm：a cooperative learning approach to the traveling salesman problem［J］.IEEE Trans on Evolutionary Computation，1996（1）：29-41.

［12］ DORIGO M，GAM BARDELLA L L.A study of some properties of ant-Q［C］／／Proc of the 44th Int'1Conf on Parallel Problem Solving from Nature，Berlin：1996：656-665.

［13］ ESMAT RASHEDI，HOSSEIN NEZAMABADI-POUR.GSA：agravitational search algorithm［J］.Information Sciences，2009，7：2232-2248.

A hybrid algorithm for the traveling salesman problem

Gu Wen-xiang，LI Xiang-tao，WANG Chun-ying，LI Guo-yuan，YIN Ming-hao
（College of Computer Science and Information Technology，Northeast Normal University，Changchun 130117，China）

The TSP problem is very important because of its theoretical and practical significance.In this paper，a computationally effective algorithm of combining ACO，PSO and GSA is proposed for solving the TSP problem.In this algorthm，PSO and GSA have been added to ACO.The PSO algorithm solved the shortage problem of the initial pheromone towards ACO.The GSA has been used to choose the Parameters of PSO and ACO.Experimental results show that the proposed algorithm for solving the TSP problem is effective and efficient.

ant colony algorithm；particle swarm optimization；gravitation search algorithm；TSP

TP 301

520·1040

A

1000-1832（2011）03-0060-05

2009-03-07

國家自然科學基金資助項目（61070084，60573067，60803102）.

谷文祥（1947—），男，教授，博士研究生導師，主要從事智能規劃與規劃識別、形式語言與自動機、模糊數學及其應用研究.

陶 理）