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

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

?

基于遺傳-模擬退火的蟻群算法求解TSP問(wèn)題

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

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

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

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

0 引言

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

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

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

1.1 TSP問(wèn)題描述

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

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

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

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

(1)

(2)

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

(3)

(4)

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

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

(5)

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

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

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

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

Step4：nc←nc+1；

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

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

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

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

2.1 遺傳算法的引入

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

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

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

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

2.2 模擬退火算法的引入

2.2.1 模擬退火機(jī)制的引入

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

(6)

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

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

2.2.2 回火機(jī)制

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

(7)

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

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

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)移概率移動(dòng)到j(luò)城市；

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

Step4：解集path1中的解逐個(gè)按概率pc與pbest1進(jìn)行交叉操作，獲得解集path2；

Step5：解集path1中的解逐個(gè)按概率pm進(jìn)行變異操作，得到解集path3；

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

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

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

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

3 算法測(cè)試

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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

[8]江君莉，潘 豐.求解TSP的遺傳蟻群融合算法[J].江南大學(xué)學(xué)報(bào)(自然科學(xué)版),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)新計(jì)劃項(xià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