基于K-means信息揮發(fā)速率動態(tài)調整的改進蟻群算法

，

(哈爾濱工業(yè)大學(深圳)，廣東 深圳 518055)

0 引言

旅行商問題屬于NP問題，對于給定N個城市，旅行商需要從某個城市出發(fā)，到達每個城市一次，且最后回到出發(fā)的城市，求解旅行商遍歷所有的城市所需要的最短封閉路線。普遍采用智能啟發(fā)算法求解旅行商問題，常用的有遺傳算法[1-2]、蟻群算法[3-4]、PSO算法[5-6]和神經(jīng)網(wǎng)絡[7]等。雖然參考文獻[8]，文獻[5]，文獻[9]的算法，保證了一定的求解質量，但存在求解時間長的問題。

為了解決蟻群優(yōu)化算法求解時間較長、收斂速度較慢、容易陷入局部最優(yōu)解的缺陷，本文提出了一種基于K-means信息揮發(fā)速率動態(tài)調整的改進蟻群算法。

1 改進蟻群算法求解TSP

1.1 信息揮發(fā)素率動態(tài)調整改進蟻群算法

本文的改進蟻群算法在下一城市的選擇上加入了輪盤賭規(guī)則，信息素的更新采用信息素全局更新規(guī)則和信息素局部更新規(guī)則，引入了信息素自適應動態(tài)調整策略。每只螞蟻選擇下一城市后即對經(jīng)過的這條邊(i,j)進行局部信息素更新。在每輪迭代結束后，僅對最優(yōu)路徑上的信息素進行全局更新。輪盤賭規(guī)則的加入使得蟻群在路徑探索時增加了隨機性，避免陷入局部最優(yōu)。

1.1.1 狀態(tài)轉移規(guī)則

偽隨機比例選擇下一城市

(5)

qo為[0,1]區(qū)間內的一個設定參數(shù)；q為[0,1]區(qū)間內的一個隨機數(shù)。

當產(chǎn)生的隨機數(shù)q≤q0時，螞蟻直接選擇使啟發(fā)式信息的指數(shù)α和信息素量的β指數(shù)乘積最大的作為下一個到達城市；當產(chǎn)生的隨機數(shù)q>q0時，改進算法采用輪盤賭策略，選擇下一城市為j的概率為

(6)

1.1.2 信息素更新規(guī)則

蟻群算法中，每輪迭代時路徑構建完成后，每只螞蟻都可以釋放信息素。在改進算法中，只有最優(yōu)螞蟻才能在路徑構建完成后釋放信息素，信息素更新規(guī)則的改進加強了算法搜索的導向性。在每輪迭代中，當所有螞蟻完成路徑構建后，當前最優(yōu)路徑上的信息素發(fā)生全局更新。信息素全局更新規(guī)則為

τ(i,j)=(1-ρ)·τ(i,j)+

ρ·Δτb(i,j),?(i,j)∈τb

(7)

(8)

ρ為信息素全局揮發(fā)速率；Δτb(i,j)為至今最優(yōu)螞蟻在邊(i,j)釋放的信息素；Cb為至今最優(yōu)螞蟻構建路徑的長度；信息素局部更新規(guī)則為

τ(i,j)=(1-ζ)·τ(i,j)+ξ·τo

(9)

ξ是信息素局部揮發(fā)速率。信息揮發(fā)素是蟻群系統(tǒng)算法中的一項重要參數(shù)。

信息素全局揮發(fā)速率ρ影響蟻群算法的全局搜索能力和收斂速度：當ρ過小時，會使算法的隨機性能和全局搜索能力下降；當ρ過大時，又會使算法的收斂速度降低。因此，需要合理選擇ρ，保證算法在有較好的全局搜索能力的同時能較快收斂。本文的改進蟻群系統(tǒng)算法提出簡單而有效的自適應策略來動態(tài)調整信息揮發(fā)速率ρ，表達式為

(10)

i為當前迭代輪數(shù)；Nmax為最大迭代次數(shù)。初始化時，給全局信息揮發(fā)速率ρ設定較小的值ρ0，這時以前搜索過的路徑被選擇的概率較大，收斂速度比較快。之后隨著迭代次數(shù)增加，逐漸增加ρ至最大值ρmax，信息正反饋的作用被削弱，那些從未被搜索過的路徑上的信息素增加，搜索的隨機性增強，全局搜索能力提高。

信息揮發(fā)速率動態(tài)調整改進蟻群算法具體流程如圖1所示。

圖1 改進蟻群算法流程

1.2 基于K-means的改進蟻群算法

利用蟻群算法求解大規(guī)模TSP問題存在求解時間過長的問題，采用“分而治之”的思想，利用簡單易行的K-means算法，將大規(guī)模TSP分體分解為多個小規(guī)模TSP問題，然后對每個小規(guī)模TSP問題采用上節(jié)提出的改進蟻群算法求解，再將子問題的求解結果進行類間連接，最終得到原大規(guī)模TSP問題的滿意解。

選取TSPlib庫中的eil101作為測試數(shù)據(jù)，數(shù)據(jù)包含了101個城市的坐標。該實例的輪廓系數(shù)隨聚類數(shù)的變化關系如圖2所示。聚類數(shù)K=4時，輪廓系數(shù)最大，即聚類效果最佳。

圖2 輪廓系數(shù)

對每個小規(guī)模TSP問題采用本文提出的信息揮發(fā)速率動態(tài)調整改進蟻群算法求解后，對子問題進行類間的連接。對于子問題，首先求解封閉路徑滿意解，在類間連接時，確定斷開鏈與連接鏈。

采用子區(qū)域最近鄰鄰接方法進行類間連接。類間連接所得最優(yōu)路徑的目標函數(shù)為

minZ=∑Zk-∑Si+∑Sj

(13)

Zk為子區(qū)域TSP最優(yōu)路徑長度；Si為子區(qū)域連接時的斷開鏈長度；Sj為子區(qū)域之間的連接鏈長度。

最近鄰鄰接方法的基本思路如下：確定子區(qū)域的連接順序；將相鄰兩簇距離較近的點作為潛在連接點集；對于每2個相鄰子區(qū)域，在其潛在連接點集中選擇出入度點，確定斷開鏈和連接鏈；由式(10)計算最優(yōu)路徑長度，得到原有大規(guī)模TSP問題的滿意解。

對于TSPlib實例eil101，城市數(shù)為101輪廓系數(shù)最優(yōu)時的聚類個數(shù)為4，因此簇數(shù)設置為4個；每簇的螞蟻個數(shù)設置為與每簇的城市數(shù)相等。其他參數(shù)的設置如表1所示。

表1 改進蟻群算法參數(shù)設置

采用TSPlib庫中eil101實例進行聚類和子問題優(yōu)化路徑求解的結果如圖3所示。

4個子區(qū)域進行類間連接后的優(yōu)化路徑求解結果如圖4所示。采用Berlin52和ch130對改進算法進行測試。改進算法循環(huán)次數(shù)設定為50次。實例Berlin52中有52個城市的坐標數(shù)據(jù)，其最優(yōu)解為7 544.37。采用改進算法求解，得到最短路徑為7 544.37，最長路徑為7 807.57，平均路徑長度為7 604.65。實例ch130中有130個城市的坐標數(shù)據(jù)，其最優(yōu)解為6 110。最短路徑為6 269.15，最長路徑為6 586.33，平均路徑長度為6 383.95。改進算法連續(xù)運行15次后所得的路徑長度結果分別如圖5和圖6所示。

圖3 eli101聚類子問題求解

圖4 eil101聚類連接示意

圖5 改進算法求解Berlin52路徑長度

圖6 改進算法求解ch130路徑長度

算法的平均解和最優(yōu)解相比TSPlib庫中已知的最優(yōu)解的偏差百分比可由式(14)和式(15)得出，自適應信息素調節(jié)的改進蟻群系統(tǒng)算法在Berlin52上測試后得到的偏差百分比分別為 0.799%和0.000%，在ch130上測試后得到的偏差百分比分別為4.484%和2.600%，即

(14)

(15)

2 實驗驗證

將基本蟻群算法ACO與本文改進的蟻群算法進行對比，選擇國際上通用的TSP lib數(shù)據(jù)集中的實例作為測試數(shù)據(jù)?；鞠伻核惴ǖ膮?shù)設置如表2所示。設置螞蟻數(shù)和城市數(shù)相等。對于本文改進的蟻群算法，設置每簇的螞蟻個數(shù)與簇內城市數(shù)相等。其他參數(shù)如表1所示。2種算法均對測試實例重復運行15次，實驗結果如表3所示。其中算法1為本文提出的改進ACO算法，算法2為ACO算法。

表2 蟻群算法參數(shù)設置

表3 改進ACO與ACO測試對比

改進蟻群算法所得到的最優(yōu)解均優(yōu)于蟻群算法如圖7所示。2種算法運行時間對比情況如圖8所示。由圖8可知，隨著城市數(shù)的增加，在求解時間上改進的蟻群算法明顯少于蟻群算法，平均減少約62.9%左右。城市數(shù)達到280時，改進蟻群算法的求解時間相比蟻群算法能減少76.6%。

圖7 優(yōu)化路徑長度對比

圖8 算法運行時間對比

選取TSPlib庫中的ch150實例進行測試。參數(shù)設置城市數(shù)N=150，螞蟻數(shù)量m=150，其他參數(shù)同表1。重復進行5次，得到如圖9所示的路徑長度隨迭代次數(shù)變化的收斂曲線。由圖9可知改進算法在前100次收斂速度較快，在400次左右基本收斂。

圖9 改進蟻群算法的收斂性

蟻群算法的參數(shù)設置同表1。2種算法的收斂性對比如圖10所示。由圖10可知在迭代初期，改進蟻群算法和蟻群算法均能快速收斂，在迭代次數(shù)達到600后，兩者基本收斂，但改進蟻群算法得到的有效解明顯優(yōu)于改進蟻群算法得到的有效解，避免了陷入局部最優(yōu)。

圖10 改進蟻群算法與蟻群算法的收斂性對比

3 結束語

本文提出基于K-means信息揮發(fā)速率動態(tài)調整的改進蟻群算法，通過動態(tài)調整蟻群的信息揮發(fā)速率，避免了蟻群陷入局部最優(yōu)路徑，同時加快了算法收斂。采用分治方法，將大規(guī)模TSP問題分解為數(shù)個子問題，大大減少了求解時間。實驗結果表明，本文提出的改進算法在求解最優(yōu)路徑和求解時間上均優(yōu)于蟻群算法，所得的最優(yōu)路徑長度平均減少約10.0%，求解時間平均降低約62.9%，能較好地適用于求解TSP問題。