改進(jìn)蟻群算法在解決TSP問(wèn)題中的應(yīng)用

李 雪，王 雷

(安徽工程大學(xué) 機(jī)械與汽車工程學(xué)院，安徽 蕪湖 241000)

旅行商問(wèn)題(Traveling Salesman Problem，TSP)是典型的組合優(yōu)化問(wèn)題，在實(shí)際應(yīng)用中具有重要作用，比如在飛機(jī)的航線設(shè)定、物流配送、集成電路的整體布局、車輛路徑等領(lǐng)域已經(jīng)得到了廣泛應(yīng)用，因此研究旅行商問(wèn)題具有重要意義。為解決旅行商問(wèn)題，國(guó)內(nèi)外學(xué)者提出了很多算法，如遺傳算法、粒子群算法、蟻群算法等智能算法[1-3]，其中蟻群算法在解決旅行商問(wèn)題中具有較強(qiáng)的優(yōu)勢(shì)。蟻群算法是由意大利學(xué)者Dorigo M首先提出的，該算法是一種啟發(fā)式算法也是仿生進(jìn)化算法，通過(guò)對(duì)螞蟻覓食時(shí)的行為進(jìn)行模仿來(lái)尋找一條從初始點(diǎn)到終點(diǎn)的最優(yōu)路徑。但是蟻群算法也具有許多缺陷，如收斂速度慢、易陷入局部最優(yōu)解等問(wèn)題[4]。目前國(guó)內(nèi)外許多學(xué)者在解決TSP問(wèn)題提出了許多優(yōu)化方案，文獻(xiàn)[5]中提出了一種改進(jìn)的遺傳算法，引入貪心算法以及選擇操作來(lái)解決旅行商問(wèn)題，有效地解決了傳統(tǒng)遺傳算法的易陷入局部最優(yōu)解問(wèn)題，文獻(xiàn)[6]通過(guò)將遺傳算法和模擬退火算法相結(jié)合的方式來(lái)找到TSP最優(yōu)解，文獻(xiàn)[7]引入對(duì)數(shù)遞減的權(quán)重對(duì)螢火蟲(chóng)算法的位置進(jìn)行更新，同時(shí)結(jié)合了遺傳算法的選擇、交叉以及變異等操作來(lái)提高算法的搜索能力，利用改進(jìn)的螢火蟲(chóng)算法求解TSP問(wèn)題。文獻(xiàn)[8]設(shè)計(jì)了一種自適應(yīng)局部調(diào)整算子和全局隨機(jī)策略的布谷鳥(niǎo)算法來(lái)求解TSP最優(yōu)解。文獻(xiàn)[9]通過(guò)對(duì)IGT算法進(jìn)行改進(jìn)，引入原有映射算子、Inver-over算子和求異算子來(lái)求解TSP問(wèn)題。

針對(duì)以上問(wèn)題以及國(guó)內(nèi)外學(xué)者提出來(lái)的解決方案可以看到利用改進(jìn)的算法在TSP問(wèn)題上仍然需要進(jìn)一步優(yōu)化，尤其是在解決收斂速度以及局部最優(yōu)解等問(wèn)題上。本文中使用的改進(jìn)算法是基于傳統(tǒng)蟻群算法的基礎(chǔ)上進(jìn)行改進(jìn)，首先通過(guò)自適應(yīng)改變揮發(fā)系數(shù)來(lái)使初始時(shí)刻的蟻群搜索能力加強(qiáng)、范圍擴(kuò)大、避免陷入局部最優(yōu)解、提高其魯棒性，其次將輪盤(pán)賭算子利用到狀態(tài)轉(zhuǎn)移規(guī)則中，有效地提高了解的質(zhì)量和算法的收斂速度，最后通過(guò)精英選擇操作，有效地提高了算法的全局搜索效率和收斂速度。以上改進(jìn)的蟻群算法對(duì)不同時(shí)刻的信息素都有著全局掌控能力，為提高收斂速度和避免局部最優(yōu)解提供了保證。最后利用改進(jìn)的蟻群算法(Improved Ant Colony Optimization，IACO)來(lái)解決TSP問(wèn)題，并且完成了仿真實(shí)驗(yàn)，相比其他的改進(jìn)算法的實(shí)驗(yàn)結(jié)果可以證明本文的改進(jìn)蟻群算法的可行性和優(yōu)越性。

1 改進(jìn)蟻群算法

1.1 自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ

蟻群算法在運(yùn)行過(guò)程中會(huì)受到許多因素的影響，本文所提到的動(dòng)態(tài)調(diào)整參數(shù)ρ來(lái)解決算法在運(yùn)行過(guò)程中收斂速度慢、易陷入局部最優(yōu)解等問(wèn)題。當(dāng)揮發(fā)系數(shù)ρ設(shè)置比較大時(shí)，之前螞蟻?zhàn)哌^(guò)的路徑被再次選擇的機(jī)會(huì)就會(huì)加大，過(guò)小時(shí)會(huì)提高全局搜索能力導(dǎo)致收斂速度降低。于是初始時(shí)刻將參數(shù)ρ設(shè)置為最大值，雖然以前搜索路徑被再次選擇可能性加大，但是信息正反饋占主導(dǎo)作用。

本文對(duì)參數(shù)ρmin設(shè)置為0.1，C為隨機(jī)常數(shù)，ρ的自適應(yīng)調(diào)整公式如下：

(1)

1.2 多型狀態(tài)轉(zhuǎn)移概率的融合

輪盤(pán)賭算法在遺傳算法中經(jīng)常使用，于是將輪盤(pán)算子應(yīng)用到城市轉(zhuǎn)移狀態(tài)規(guī)則中，適應(yīng)度越大，該個(gè)體被選中的概率也就越大，對(duì)于解的質(zhì)量有很大提高，也有助于提高算法的收斂速度。

(2)

1.3 精英選擇較優(yōu)路徑信息素更新

當(dāng)全部螞蟻都完成一次路徑搜索以后，按每個(gè)螞蟻行走路徑的長(zhǎng)短進(jìn)行排序(L1≤L2≤L3≤…≤Lm)，每只螞蟻對(duì)信息素更新的貢獻(xiàn)根據(jù)該螞蟻的排序進(jìn)行加權(quán)，加權(quán)值記為φ。更新公式(3)、(4)和(5)如下：

τijt+1=1-ρτijt+Δτijt

(3)

(4)

(5)

1.4 較優(yōu)路徑節(jié)點(diǎn)交叉操作

如果蟻群在每次迭代后無(wú)法獲得最優(yōu)解時(shí)，則認(rèn)為蟻群算法可能處于停滯狀態(tài)，陷入局部最優(yōu)解，因此通過(guò)對(duì)來(lái)自不同節(jié)點(diǎn)的路徑進(jìn)行交叉操作來(lái)獲得最新路徑，如下圖所示，改進(jìn)算法的全局搜索效率得到了顯著增強(qiáng)。

圖1 節(jié)點(diǎn)交叉操作

2 IACO求解旅行商問(wèn)題

TSP(旅行商問(wèn)題)是一個(gè)組合優(yōu)化問(wèn)題，可以通過(guò)數(shù)學(xué)模型簡(jiǎn)單的描述為：假設(shè)有n個(gè)城市，可用1，2，…，n來(lái)表示每個(gè)城市，每?jī)蓚€(gè)城市i和j之間的距離為dij且已知，每個(gè)城市恰好被遍訪一次且剛好是一條閉合回路，其中回路路徑總長(zhǎng)度最短。其數(shù)學(xué)模型表達(dá)如下：

(6)

(7)

(8)

(9)

式中：n為城市數(shù)量，式(6)為目標(biāo)函數(shù)，式(7)和式(8)表示經(jīng)過(guò)每個(gè)城市且只有一次，式(9)表示無(wú)子回路解的產(chǎn)生。

IACO解決TSP問(wèn)題步驟可表示如下：

Step 1 初始化螞蟻參數(shù)，將起始禁忌表tabuk設(shè)為空集。

Step 2 采用公式(1)來(lái)設(shè)定初始值C進(jìn)而自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ。

Step 3 采用公式(2)來(lái)按照新?tīng)顟B(tài)轉(zhuǎn)移概率選擇下一個(gè)節(jié)點(diǎn)加入禁忌表。

Step 4 判斷螞蟻是否周游結(jié)束，如果周游結(jié)束則螞蟻k=k+1，否則返回到Step3步驟。

Step 5 判斷螞蟻k是否等于M，是則進(jìn)行下一步驟，否則返回到步驟Step 2。

Step 6 計(jì)算路徑長(zhǎng)度Lφ并對(duì)其排序，然后采用公式(3)、公式(4)、公式(5)進(jìn)行信息素更新。

Step 7 判斷是否滿足結(jié)束條件，是則結(jié)束輸出結(jié)果，否則進(jìn)行較優(yōu)路徑節(jié)點(diǎn)交叉操作，然后判斷是否滿足結(jié)束條件，是則輸出結(jié)果，否則返回到步驟Step 1，直至循環(huán)結(jié)束。

具體算法流程圖如圖2所示。

圖2 改進(jìn)蟻群算法流程圖

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文改進(jìn)的蟻群算法的可行性，將本文算法應(yīng)用在多組TSP案例中，同時(shí)和傳統(tǒng)的蟻群算法和其他學(xué)者改進(jìn)的蟻群算法做一個(gè)比較來(lái)證明本文改進(jìn)的蟻群算法的優(yōu)越性。實(shí)驗(yàn)環(huán)境是在windows7操作平臺(tái)上運(yùn)行MATLAB2016a軟件將GA、HA、IGA、ACO和IACO進(jìn)行比較。算法的參數(shù)設(shè)置為：蟻群總數(shù)M=50，常量C=0.9，參數(shù)α=1.5，β=7，信息素常量Q=10，最大迭代次數(shù)Nmax=100。仿真結(jié)果分別如圖3-圖6所示。

圖3 Att48優(yōu)化實(shí)例

圖4 Eil51優(yōu)化實(shí)例

圖5 Berlin52優(yōu)化實(shí)例

圖6 Pr76優(yōu)化實(shí)例

表1 實(shí)驗(yàn)結(jié)果對(duì)比

如圖3～圖6所示，本文通過(guò)對(duì)比文獻(xiàn)[10]中四個(gè)案例Att48、Eil51、Berlin52、Pr76，分別采用GA、HA、IGA、ACO和IACO求解TSP問(wèn)題，結(jié)果如表1所示。從表1可以看出本文的IACO在求解TSP問(wèn)題平均最優(yōu)值上和最優(yōu)解更加相近，證明了本文IACO的有效性和可行性。

圖7 kroA100優(yōu)化實(shí)例

圖8 pr152優(yōu)化實(shí)例

為了更好證明本文改進(jìn)算法的有效性，將IACO與ACO做了如下對(duì)比，將兩種算法分別在kroA100和pr152中運(yùn)行，結(jié)果分別如圖7-圖8所示。IACO在案例kroA100和pr152中得到的解明顯比ACO更加接近最優(yōu)解。在案例kroA100中ACO的平均偏差在7.7%，IACO的平均偏差在2.3%，在求解精度方面IACO較ACO有70%的提高。在案例pr152中ACO的平均偏差在10.2%，IACO的平均偏差在7.6%，在精度方面IACO較ACO有26%的提高，有效地證明了IACO的可行性。

4 結(jié)論

為解決傳統(tǒng)蟻群算法在收斂速度慢、易陷于局部最優(yōu)解等問(wèn)題，本文提出一種改進(jìn)的蟻群算法(IACO)，首先通過(guò)自適應(yīng)改變揮發(fā)系數(shù)來(lái)使初始時(shí)刻的蟻群搜索能力加強(qiáng)、范圍擴(kuò)大，避免陷入局部最優(yōu)解；其次將輪盤(pán)賭算子利用到狀態(tài)轉(zhuǎn)移規(guī)則中，有效地提高了解的質(zhì)量和算法的收斂速度；最后通過(guò)精英選擇操作，有效地提高了算法的全局搜索效率和收斂速度。在解決TSP問(wèn)題上，通過(guò)對(duì)比文獻(xiàn)可以得到本文IACO在尋優(yōu)能力上得到了提高，有效地避免了出現(xiàn)重復(fù)回路的現(xiàn)象，在與其他算法的比較中可以發(fā)現(xiàn)本文算法在解決TSP問(wèn)題上具有優(yōu)越性和有效性。