基于K-means信息揮發速率動態調整的改進蟻群算法

，

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

0 引言

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

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

1 改進蟻群算法求解TSP

1.1 信息揮發素率動態調整改進蟻群算法

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

1.1.1 狀態轉移規則

偽隨機比例選擇下一城市

(5)

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

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

(6)

1.1.2 信息素更新規則

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

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

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

(7)

(8)

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

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

(9)

ξ是信息素局部揮發速率。信息揮發素是蟻群系統算法中的一項重要參數。

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

(10)

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

信息揮發速率動態調整改進蟻群算法具體流程如圖1所示。

圖1 改進蟻群算法流程

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

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

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

圖2 輪廓系數

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

采用子區域最近鄰鄰接方法進行類間連接。類間連接所得最優路徑的目標函數為

minZ=∑Zk-∑Si+∑Sj

(13)

Zk為子區域TSP最優路徑長度；Si為子區域連接時的斷開鏈長度；Sj為子區域之間的連接鏈長度。

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

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

表1 改進蟻群算法參數設置

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

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

圖3 eli101聚類子問題求解

圖4 eil101聚類連接示意

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

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

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

(14)

(15)

2 實驗驗證

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

表2 蟻群算法參數設置

表3 改進ACO與ACO測試對比

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

圖7 優化路徑長度對比

圖8 算法運行時間對比

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

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

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

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

3 結束語

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