基于遺傳-模擬退火的蟻群算法求解TSP問題

徐 勝，馬小軍，錢 海，王震宇

(南京工業(yè)大學 電氣工程與控制科學學院，南京 211800)

?

基于遺傳-模擬退火的蟻群算法求解TSP問題

徐 勝，馬小軍，錢 海，王震宇

(南京工業(yè)大學 電氣工程與控制科學學院，南京 211800)

傳統(tǒng)的蟻群算法具有收斂性好、魯棒性強等優(yōu)點，但在解決旅行商(TSP)問題方面存在收斂時間長，容易出現(xiàn)停滯等問題;為了提高傳統(tǒng)蟻群算法的解的質(zhì)量，本文提出了基于遺傳-模擬退火的蟻群算法(G-SAACO)，將遺傳算法和模擬退火算法引入蟻群算法中;其方法是在傳統(tǒng)蟻群算法中引入遺傳算法的變異與交叉策略來得到候選解，增加解的多樣性;同時引進模擬退火算法機制，使得在高溫時以較高概率選擇候選集中比較差的解加入最新集，溫度控制上加入了回火機制，進一步提高解的質(zhì)量;為了檢驗改進的蟻群算法，隨機選用了TSPLIB中的部分城市進行仿真，結(jié)果與傳統(tǒng)蟻群算法、模擬退火蟻群算法、遺傳蟻群算法相比，算法具有較強的發(fā)現(xiàn)較好解的能力，同時增強了平均值的穩(wěn)定性。

傳統(tǒng)蟻群算法；遺傳算法；模擬退火；旅行商問題

0 引言

在20世紀50年代中期，人們從生物行為和生物進化的機理中獲得啟發(fā)，提出了各種用來解決優(yōu)化問題的方法，如遺傳算法、禁忌搜索、模擬退火、進化策略等。20世紀90年代，意大利學者Dorigo等人通過觀察螞蟻覓食的行為提出了蟻群算法(ACO)[1]。蟻群算法利用了蟻群覓食的正反饋原理，具有收斂性好、魯棒性強、并行性好等優(yōu)點，使得其在解決TSP問題方面優(yōu)于模擬退火算法、禁忌算法、遺傳算法等智能算法[2-3]。但同時也存在收斂時間長，容易出現(xiàn)停滯等問題。文獻[4]中張曉婧等人提出的模擬退火蟻群算法在求解Job-Shop問題時，雖然提高了算法的收斂速度，但導致了早熟現(xiàn)象。文獻[5]中江新姿等人提出的求解旅行商問題的模擬退火蟻群算法，在一定程度避免了早熟現(xiàn)象，但收斂速度變慢了。

本文將遺傳算法和模擬退火算法引入蟻群算法中，在對原有算法改進的基礎(chǔ)上，提出了一種基于遺傳-模擬退火的蟻群算法。此算法利用遺傳算法對蟻群算法得到的解進行交叉變異操作，從而獲得新解，把蟻群算法的解和遺傳算法的解組合成候選集，擴大了解的范圍，并在一定程度上避免了早熟現(xiàn)象。同時結(jié)合模擬退火算法機制，使得在高溫時能夠以較高的概率選擇候選集中比較差的解加入最新集，增加了解的多樣性，很好的防止了早熟現(xiàn)象的發(fā)生；在低溫時較差的解只有很小的概率才會被加入到最新集，這有效地提高了算法的收斂速度。在溫度控制上加入了回火策略，進一步提高解的質(zhì)量。

1 傳統(tǒng)蟻群算法求解TSP問題

1.1 TSP問題描述

設(shè)有n個城市， 為任意兩個城市i，j之間的距離，求經(jīng)過每個城市有且僅有一次的一條路徑M=(M(1)，M(2)，…，M(n))，使得

1.2 傳統(tǒng)蟻群算法的TSP求解

意大利學者M.Dorigo等人發(fā)現(xiàn):螞蟻在運動過程中會在所經(jīng)過的路徑上留下一種稱之為信息素的物質(zhì)，而且它們能夠感知到這種物質(zhì)，并傾向于朝該物質(zhì)強度高的方向移動[6]。因此，由大量螞蟻所組成的集體行為就表現(xiàn)出一種信息正反饋現(xiàn)象:某一路徑越短，那么該條路徑上走過的螞蟻就越多，所留下的信息素的強度自然也就越大，后來者選擇該條路徑的概率也就越大。螞蟻個體之間通過這種信息交流來選擇最短路徑并達到搜索食物的目的。

在旅行商問題中，設(shè)m為螞蟻總數(shù)，表示t時刻位于城市i的螞蟻數(shù)，則。為t時刻邊上信息素的強度，設(shè) (C為常數(shù))。隨著時間的推移，先前的信息素會揮發(fā)，而新的信息素會加入，ρ為信息素保留程度，1-ρ為信息素消逝程度，當m只螞蟻都完成一次循環(huán)后，各邊的信息素按下面公式調(diào)整：

(1)

(2)

表示第k只螞蟻留在路徑ij上的信息素，為此次循環(huán)中邊ij上的信息素增量。

(3)

(4)

Lk為本次循環(huán)后，第k只螞蟻的路徑長度，Q為常數(shù)。

在循環(huán)過程中，由轉(zhuǎn)移概率決定轉(zhuǎn)移方向，表示第k只螞蟻從城市i轉(zhuǎn)移到城市j的概率。

(5)

ηij為邊(i，j)的能見程度，是某種啟發(fā)信息，信息素和能見程度的相對重要性，={0，1，2，3，…，n-1}-tabuk表示允許螞蟻k選擇城市的集合，是螞蟻k的禁忌表，用來記錄螞蟻k已走過的城市，體現(xiàn)了人工螞蟻的記憶性。

傳統(tǒng)蟻群算法解TSP問題的基本步驟。

Step1：迭代步數(shù)nc←0，τij→C(C為常數(shù))，τij←0，將m只螞蟻隨機放在n個頂點上；

Step3：當各螞蟻k完成本次循環(huán)后，計算各只螞蟻的路徑長度Lk，并按照式(1)來更新信息素；

Step4：nc←nc+1；

Step5：如果nc<總迭代步數(shù)，則轉(zhuǎn)步驟2；

Step6：根據(jù)各路徑上信息素的強度，得出最好解。

2 遺傳-模擬退火的蟻群算法

在求解TSP組合優(yōu)化問題時，蟻群算法是在整個可行解內(nèi)進行盲目的隨機搜索全局最優(yōu)解，因此就產(chǎn)生了算法的收斂速度慢、易于停滯等問題，為了很好的克服這些問題。本文對傳統(tǒng)蟻群算法作了一些改進。

2.1 遺傳算法的引入

遺傳算法是以“適者生存”和遺傳變異理論為基礎(chǔ)的一類仿生優(yōu)化算法。本文利用遺傳算法的交叉和變異的策略來改善蟻群算法的解的多樣性。

遺傳算法對蟻群算法得到的解集path1中的解與path1中的最優(yōu)解pbest1按概率交叉操作得到解集path2，然后再對path1中的解按概率進行變異操作獲得解集path3，最后將path1、path2和path3組合成候選集path。

交叉策略：在pbest1中隨機選擇一個交叉區(qū)域，刪除待交叉解中已在pbest1的交叉區(qū)中出現(xiàn)過的城市，將pbest1的交叉區(qū)域加到待交叉解的隨機位置上。例如：pbest1=1，2，3，4，5，6，7，8；交叉區(qū)域為：5 6 7 8；待交叉解為8，7，6，5，4，3，2，1；隨機位置為3，交叉后為：4，3，2，5，6，7，8，1。

變異策略：隨機選擇待變異解的第次和第次訪問的城市，在待變異解中交換這兩次訪問的城市，其他不變。例如：待變異的解為8，7，6，5，4，3，2，1；=1，=4；則變異之后的解為5，7，6，8，4，3，2，1。

2.2 模擬退火算法的引入

2.2.1 模擬退火機制的引入

本文利用模擬退火機制由候選集path生成最新解pathnew，逐個計算候選集中的解，按照下列公式?jīng)Q定候選集中的解是否加入最新集。

(6)

其中：ΔL=Lw-Lwmin，表示候選集中第w個解的路徑長度，表示候選集中最短的路徑長度，T為當前溫度值。若，則將第w個解加到最新集pathnew中；否則在[0，1)之間產(chǎn)生一個隨機數(shù)，若，則第w個解進入最新集pathnew。

由式(6)可知：在高溫時以較高概率選擇候選集中比較差的解加入最新集，增加了解的多樣性，在一定程度在避免了早熟和停滯現(xiàn)象。在低溫時比較差的解只有很小的概率加入最新集中，這樣加快了算法的收斂速度。

2.2.2 回火機制

在完成一次循環(huán)和信息素的更新后，溫度T按照下列式子進行降溫：

(7)

從式(7)可以看出：如果取較小的降溫系數(shù)a，這樣可以加快算法的速度，但很可能算法會陷入局部最優(yōu)。為了克服這個困難，本文運用了回火策略，當溫度T下降到T1時，算法立即溫度T升到T2，同時可以設(shè)定回火次數(shù)G，最大回火次數(shù)Gmax。

回火策略很好的發(fā)揮了模擬退火機制的作用。當溫度T上升到T2時，以較高概率選擇候選集中比較差的解加入最新集，大大減少了落入局部最優(yōu)的風險。

2.3 信息素的更新

2.4 算法的描述

遺傳-模擬退火的蟻群算法的步驟如下。

Step1：初始化算法參數(shù)m,T,T1,T2,a,α,β,ρ,Gmax,Q,Pc,Pm,τij=C,Δτij=0,t=0將所有的螞蟻都放在城市1；

Step2：第k只螞蟻按轉(zhuǎn)移概率移動到j(luò)城市；

Step3：當m只螞蟻都完成了一次循環(huán)，蟻群得到解集path1，path1內(nèi)最優(yōu)解為pbest1；

Step4：解集path1中的解逐個按概率pc與pbest1進行交叉操作，獲得解集path2；

Step5：解集path1中的解逐個按概率pm進行變異操作，得到解集path3；

Step6：解集path1、path2和path3組合成候選集path，記錄當前最優(yōu)解gbest；

Step7：根據(jù)模擬退火機制，按照概率pw來選擇path中的解，生成最新集；

Step8：根據(jù)最新集里的解按照式(1)～式(4)對信息素進行更新；

Step9：T←aT，t←t+1；若T≥T1，則轉(zhuǎn)到Step2；若T

3 算法測試

為了檢驗本文算法，隨機選用了國際上通用的TSP測試庫TSPLIB中a280(280個城市)里的50個城市來進行仿真，并且與傳統(tǒng)蟻群算法、模擬退火蟻群算法、遺傳蟻群算法進行比較。傳統(tǒng)蟻群算法參數(shù)如下：螞蟻數(shù)m=30，信息素保留程度ρ=0.9，信息素的重要程度α=1.5，能見性的重要程度β=2，初始信息素C=100；采用文獻[5]中的模擬退火蟻群算法，初始溫度T=100 000，終止溫度T0=10，降溫系數(shù)a=0.9；采用文獻[8]中的遺傳蟻群算法，染色體數(shù)N=30，交叉概率Pc=0.4，變異概率Pm=0.1；本文算法參數(shù)設(shè)計：m=30，ρ=0.9，α=1.5，β=2，C=100，Q=100 000，a=0.9，T=5 000，T1=100，T2=2 000，Gmax=8，Pc=0.4，Pm=0.1。對各種算法測試50次，結(jié)果如表1所示。圖1是遺傳-模擬退火蟻群算法最好的解，總路程為989.14 km。

從表1中的最好解一列可以看出遺傳-模擬退火蟻群算法具有較強的發(fā)現(xiàn)較好解的能力。觀察他們的平均值可以知道本文算法也具有較好的穩(wěn)定性。

4 結(jié)論

采用傳統(tǒng)算法改進后的遺傳-模擬退火蟻群算法來求解TSP問題能夠獲得比模擬退火算法、標準遺傳算法和傳統(tǒng)蟻群算法都要好的解，而且也增加了解的多樣性和穩(wěn)定性，同時算法的收斂度也得到了一定程度的改善，證明了該算法具有一定的有效性。

表1 3種算法的測試結(jié)果

圖1 用遺傳-模擬退火蟻群算法解TSPa280最好的解

[1]宋志飛.基于蟻群算法的TSP問題研究[D].江西:江西理工大學,2012.

[2]吳華鋒，陳信強，毛奇凰，等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學報,2013,34(4):165-170.

[3]侯文靜，馬永杰，張 燕，等.求解TSP的改進蟻群算法[J].計算機應用研究,2010,27(6): 2087-2089.

[4] 張曉婧，高慧敏.基于模擬退火的蟻群算法求解Job-Shop問題[J].計算機應用與軟件，2008,25(5): 77-79.

[5]江新姿，高 尚，陳建忠.求解旅行商問題的模擬退火蟻群算法[J].計算機工程與設(shè)計,2008,29(6): 1491-1493.

[6] 劉 波,蒙培生.采用基于模擬退火的蟻群算法求解旅行商問題[J].華中科技大學學報(自然科學版), 2009, 37(11): 26-30.

[7] 陳冰梅，樊曉平，周志明，等.求解旅行商問題的Matlab 蟻群仿真研究[J]. 計算機測量與控制,2011,19(4): 990-997.

[8]江君莉，潘 豐.求解TSP的遺傳蟻群融合算法[J].江南大學學報(自然科學版),2012,11(3):253-256.

Genetic-simulated Annealing-based Ant Colony Algorithm for Traveling Salesman Problem

Xu Sheng， Ma Xiaojun， Qian Hai， Wang Zhenyu

(College of Electrical Engineering and Control Science，Nanjing Tech University，Nanjing 211800，China)

The traditional ant colony algorithm has the advantages of good convergence and robustness, but has a long convergence time in solving the problem of TSP. In order to improve the quality of the solution of the traditional ant colony algorithm， G-SAACO is proposed，the genetic algorithm and simulated annealing algorithm are introduced into the ant colony algorithm.. The idea of the algorithm was to introduce the variation and crossover strategy of genetic algorithm into the traditional ant colony algorithm to get the candidate solutions， which increased the diversity of the solution. And introduction of simulated annealing algorithm mechanism made the algorithm have higher probability of selecting poor solutions in a candidate set into the latest set. Besides，In the mechanism of controlling the temperature， the quality of the solutions was improved through backfire strategy. In order to test the improved ant colony algorithm, randomly selected parts of the city of the TSPLIB to simulate.Compared with the standard GA，simulated annealing algorithm and the traditional ant colony algorithm for traveling salesman problem(TSP).The results show that the algorithm has a strong ability to find good solutions, and the stability of the average value is enhanced.

traditional ant colony algorithm；genetic algorithm；simulated annealing；traveling salesman problem

2015-08-28；

2015-11-16。

江蘇省普通高校研究生科研創(chuàng)新計劃項目(SJLX_0334)。

徐 勝(1990-)，男，江蘇常熟人，研究生，主要從事建筑智能化技術(shù)方向的研究。

馬小軍(1956-)，男，江蘇南京人，教授，主要從事建筑智能化技術(shù)，PLC，嵌入式技術(shù)方向的研究。

1671-4598(2016)03-0143-02

10.16526/j.cnki.11-4762/tp.2016.03.039

TP18

A