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

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

（東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長春 130117）

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

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

（東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長春 130117）

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

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

0 引言

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

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

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

1 算法基礎(chǔ)

1.1 蟻群算法

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

1.2 粒子群算法

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

其中：V＝［v1，v2，…，vd］是粒子的速度；X＝［x1，x2，…，xd］是粒子的當(dāng)前位置；rand（）是（0，1）之間的隨機(jī)數(shù)；c1，c2被稱為學(xué)習(xí)因子，用于調(diào)整粒子更新的步長；ω是加權(quán)系數(shù).

1.3 重力搜索算法

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

2 TSP-GPAA算法

2.1 對粒子群算法的改進(jìn)

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

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

2.2 重力搜索算法對參數(shù)的選擇

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

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

表1 α′，β′，α，β，ρ的參數(shù)組合及最優(yōu)路徑

2.3 一種新的TSP-GPAA算法

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

TSP-GPAA算法的步驟

（1）將改進(jìn)的粒子群算法中的參數(shù)α′，β′和改進(jìn)的蟻群算法中的參數(shù)α，β，ρ作為重力搜索算法入口的調(diào)用變量，對其進(jìn)行轉(zhuǎn)化，然后訓(xùn)練產(chǎn)生一組解.

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

（3）利用步驟（2）中得到的粗解調(diào)整改進(jìn)的蟻群算法中信息素的初始分布，運(yùn)用改進(jìn)的蟻群算法求解TSP問題，得到問題的最優(yōu)解.

（4）將步驟（3）運(yùn)行完成后得到的最優(yōu)解作為重力搜索算法的適應(yīng)評價(jià)函數(shù)，根據(jù)適應(yīng)度的大小調(diào)整步驟（1）中的5個(gè)參數(shù)的值.進(jìn)入步驟（2）再次訓(xùn)練，找到最優(yōu)解，從而得出一組參數(shù)的值.

（5）重復(fù)以上的步驟（1），（2），（3），（4），得到10組能夠找到最優(yōu)解的參數(shù).

由于蟻群算法和粒子群算法以及重力搜索算法都是隨機(jī)的算法，每次運(yùn)行的結(jié)果都是不一樣的，所以應(yīng)對這些組合再次用蟻群算法和粒子群算法進(jìn)行訓(xùn)練，從而找到最優(yōu)解及其參數(shù)的最佳組合.

3 模擬實(shí)驗(yàn)及結(jié)果

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

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

4 結(jié)束語

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

［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］ 谷文祥，蘇衛(wèi)華，劉曉龍.構(gòu)建園區(qū)網(wǎng)健壯體系的比較研究［J］.東北師大學(xué)報(bào)：自然科學(xué)版，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

國家自然科學(xué)基金資助項(xiàng)目（61070084，60573067，60803102）.

谷文祥（1947—），男，教授，博士研究生導(dǎo)師，主要從事智能規(guī)劃與規(guī)劃識別、形式語言與自動機(jī)、模糊數(shù)學(xué)及其應(yīng)用研究.

陶 理）