蟻群算法在解決TSP問題中的應(yīng)用

陳靈佳

文章首先對(duì)蟻群算法與TSP問題進(jìn)行簡(jiǎn)要介紹，在此基礎(chǔ)上對(duì)蟻群算法在解決TSP問題中的應(yīng)用進(jìn)行論述。期望通過本文的研究能夠?qū)SP問題的解決有所幫助。

【關(guān)鍵詞】蟻群算法 TSP問題 最優(yōu)解

1 蟻群算法與TSP問題簡(jiǎn)介

1.1 蟻群算法

蟻群算法是一種隨機(jī)的、概率搜索算法，它是目前求解復(fù)雜組合優(yōu)化問題較為有效的手段之一，借助信息反饋機(jī)制，能夠進(jìn)一步加快算法的進(jìn)化，從而更加快速地找到最優(yōu)解。蟻群算法可在諸多領(lǐng)域中應(yīng)用，借助該算法能夠求得TSP問題的最短路徑。蟻群尋找最短路徑的過程如圖1所示。

蟻群算法之所以在多個(gè)領(lǐng)域獲得廣泛應(yīng)用，與其自身所具備的諸多優(yōu)點(diǎn)有著密不可分的關(guān)聯(lián)，如自組織性、正負(fù)反饋性、魯棒性、分布式計(jì)算等等，其最為突出的優(yōu)點(diǎn)是能夠與其它算法結(jié)合使用。但是在應(yīng)用實(shí)踐中發(fā)現(xiàn)，雖然蟻群算法的優(yōu)點(diǎn)較多，其也或多或少地存在一定的不足，如搜索時(shí)間較長(zhǎng)，規(guī)模越大時(shí)間越長(zhǎng)；容易出現(xiàn)停滯現(xiàn)象等等。

1.2 TSP問題

TSP是旅行商的英文縮寫形式，這一術(shù)語最早出現(xiàn)于1932年，在1948年時(shí)，美國(guó)蘭德公司（RAND）引入了TSP，由此使得TSP廣為人知。從數(shù)學(xué)領(lǐng)域的角度上講，TSP問題是NP-完備組合優(yōu)化問題，這是一個(gè)看似簡(jiǎn)單實(shí)則需要天文數(shù)字計(jì)算能力方可獲得最優(yōu)解的過程，其適用于搜索算法解決不了的復(fù)雜與非線性問題。

2 蟻群算法在解決TSP問題中的應(yīng)用

2.1 蟻群算法的改進(jìn)

（1）大量的實(shí)驗(yàn)結(jié)果表明，標(biāo)準(zhǔn)蟻群算法在TSP問題的求解中，很容易陷入局部最優(yōu)解。這是因?yàn)?，蟻群的轉(zhuǎn)移主要是由各條路徑上的信息素濃度及城市間的距離來引導(dǎo)的，信息素濃度最強(qiáng)的路徑是蟻群的首選目標(biāo)，該路徑與最優(yōu)路徑極為接近。然而，各個(gè)路徑上初始信息素的濃度全部相同，因此，蟻群在對(duì)第一條路徑進(jìn)行創(chuàng)建時(shí)，主要依賴于城市間的距離信息，這樣一來很難確保蟻群創(chuàng)建的路徑是最優(yōu)路徑，如果以此為基礎(chǔ)，那么信息素便會(huì)在該局部最優(yōu)路徑上越積累越多，其上的信息素濃度將會(huì)超過其它路徑，從而造成全部螞蟻都會(huì)集中于該路徑之上，由此便會(huì)造成停滯現(xiàn)象，不但會(huì)使搜索的時(shí)間增長(zhǎng)，而且所求得的解也無法達(dá)到理想中的效果。

（2）由于本文研究的是利用蟻群算法來解決TSP問題，所以對(duì)蟻群算法的改進(jìn)應(yīng)當(dāng)以此為依據(jù)，具體的改進(jìn)方法如下：對(duì)于初始的TSP而言，利用蟻群算法求取最優(yōu)解時(shí)，應(yīng)考慮的首要問題是預(yù)處理環(huán)節(jié)，可采用近鄰法建立一個(gè)初始游歷，并對(duì)信息素的初始值進(jìn)行計(jì)算；利用Ant-Q Systems算法，基于隨機(jī)性和確定性相結(jié)合的策略，在搜索的過程中，對(duì)狀態(tài)轉(zhuǎn)移概率進(jìn)行調(diào)整；對(duì)信息素的更新可使用在線單步更新信息素與離線全局更新信息素相結(jié)合的方法予以實(shí)現(xiàn)。

2.2 改進(jìn)蟻群算法在TSP求解中的應(yīng)用

2.2.1 對(duì)算法進(jìn)行初始化

對(duì)所有城市的坐標(biāo)進(jìn)行獲取，以此為依據(jù)，對(duì)距離矩陣Distmatrix進(jìn)行計(jì)算，同時(shí)對(duì)隨機(jī)發(fā)生器狀態(tài)進(jìn)行初始化，并以隨機(jī)的形式從n個(gè)城市中選出初始的出發(fā)城市，并將該城市設(shè)定為：

p（1）=round（Ncities*rang+0.5），其中的Ncities代表城市的數(shù)目。

通過最近鄰法創(chuàng)建一個(gè)初始游歷，并對(duì)距離矩陣進(jìn)行更新，同步計(jì)算出距離總長(zhǎng)度len在此基礎(chǔ)上對(duì)信息素的初始值Q0進(jìn)行設(shè)定，即Q0=1/（Ncities*len）。

2.2.2 算法循環(huán)

Step1：對(duì)相關(guān)參數(shù)進(jìn)行初始化，令NC（循環(huán)初始迭代）=1，MaxNC（最大循環(huán)次數(shù)）=5000，A（信息素因子）=1，B（啟發(fā)信息因子）=2，P1（局部揮發(fā)系數(shù)）=P2（全局揮發(fā)系數(shù)）=0.1，M（蟻群數(shù)量）=10，R0（選擇概率）=0.9。

Step2：將初始化信息素矩陣進(jìn)行設(shè)定為：

Pheromone=Q0*ones（Ncities，Ncities）

同時(shí)將啟發(fā)信息矩陣設(shè)定為：

Heuristic=1./DistMatrix

在將初始化允許矩陣設(shè)定為：allow0=repmat（1：Ncities，M，1）

該矩陣的初始值設(shè)為0，最后將M置于Ncities個(gè)元素上。

Step3：設(shè)循環(huán)計(jì)數(shù)器NC=NC+1。

Step4：設(shè)螞蟻禁忌表索引號(hào)AK=1，螞蟻的數(shù)目=AK+1。

Step5：螞蟻個(gè)體按照Ant-Q Systems算法提出的狀態(tài)轉(zhuǎn)移概率，選擇下個(gè)城市j并前進(jìn)。

Step6：對(duì)允許矩陣進(jìn)行更新，使其變?yōu)閍llow（AK，j）=0，即將螞蟻所選城市標(biāo)號(hào)在該矩陣中對(duì)應(yīng)位置的值重新設(shè)定為0。

Step7：如果螞蟻為遍歷集合C中的所有元素，即AK

Step8：對(duì)每只螞蟻找到的路徑長(zhǎng)度進(jìn)行計(jì)算，并對(duì)最優(yōu)的路徑長(zhǎng)度及其對(duì)應(yīng)的遍歷順序進(jìn)行保存，記錄并找到最優(yōu)解的螞蟻的搜索軌跡。

Step9：若NC≥MaxNC，則整個(gè)循環(huán)過程結(jié)束，如果未達(dá)到這一要求，則清空禁忌表，并跳轉(zhuǎn)至Step3，直至達(dá)到要求為止。

2.2.3 算法輸出

先將全局最優(yōu)解的軌跡變化圖繪制出來，然后再繪制出全局最優(yōu)解的路線圖，最后將最優(yōu)的遍歷順序、最優(yōu)的遍歷結(jié)果以及總體運(yùn)行時(shí)間輸出，便可完成對(duì)TSP問題的求解。

3 結(jié)論

綜上所述，蟻群算法以其自身諸多的優(yōu)點(diǎn)在多個(gè)領(lǐng)域中獲得了廣泛應(yīng)用，但標(biāo)準(zhǔn)蟻群算法的搜索時(shí)間較長(zhǎng)，并且容易出現(xiàn)停滯現(xiàn)象。對(duì)此，本文提出一種改進(jìn)的蟻群算法，并對(duì)其在TSP問題解決中的應(yīng)用進(jìn)行分析。經(jīng)過改進(jìn)之后，不但縮短了搜索時(shí)間，而且停滯問題也隨之消除。

參考文獻(xiàn)

[1]杜鵬楨，唐振民，孫研.一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解[J].控制與決策，2014（10）：85-88.

[2]扈華，王冬青.蟻群算法解決TSP問題圖形化軟件設(shè)計(jì)[J].電腦編程技巧與維護(hù)，2014（10）：98-100.

[3]徐勝，馬小軍，錢海.基于遺傳-模擬退火的蟻群算法求解TSP問題[J].計(jì)算機(jī)測(cè)量與控制，2016（03）：125-127.

作者單位

同濟(jì)大學(xué) 上海市 201804