參數α、β和ρ自適應調整的快速蟻群算法

尤海龍，魯照權

（合肥工業大學 智能制造研究院，合肥 230009）

0 引言

蟻群算法是由意大利學者Dorigo M等于1991年在法國巴黎召開的第一屆歐洲人工生命會議（European Conference on Artificial Lif，ECAL）上最早提出的[1]。蟻群算法遵循螞蟻搜尋食物的過程，螞蟻在尋找食物的路程中留下信息素，隨著時間的累計，最短路徑上的信息素濃度高于其他路徑，這使得后來的螞蟻有更大的概率選擇該條路徑，是一個正反饋過程。蟻群算法的優點包括分布式并行計算機制、易與其他方法相結合、具有較強的魯棒性等[2]。隨著智能機器人的興起，蟻群算法也被大量使用在機器人路徑尋優中。由于機器人行走的實時性，使得要在盡可能短的時間內尋找到最優路徑，蟻群算法收斂速度慢的問題顯得尤為突出。針對此問題，國內外很多學者對蟻群算法做出了多次改進。改進的方法主要有改變信息素更新策略，僅更新最優路徑上的信息素[3]。在全局信息素的基礎上加入局部信息素更新[4]避免局部最優。將蟻群算法與其他算法相結合，如與遺傳算法相結合[5]加入交叉算子和變異算子，增加了解的全局性；與免疫算法相結合，加入免疫算子，加快了算法的收斂性[6]。對蟻群算法中的參數進行改進，使其成為自適應參數[7]。

文中首先引入一般蟻群算法的數學模型，對蟻群算法的各個參數所起的作用進行介紹，之后根據其作用提出相應的自適應模型。接著使用MATLAB對傳統蟻群算法與改進后的蟻群算法進行對比，通過實驗結果驗證了改進蟻群算法相對于傳統蟻群算法收斂速度有了顯著提高。最后，進行進一步總結與分析。

1 傳統蟻群算法

螞蟻k（k=1,2,3...,m）在移動過程中，選擇從初始點下一步可以到達的節點，根據每個節點路徑上的信息素求出前往每個節點的概率，并使用輪盤賭法[8]選取下一步的初始點。以表示螞蟻從i節點到j節點的概率：

其中τij（t）表示弧（i，j）上信息素的濃度，ηij（i，j）表示與弧（i，j）相關聯的啟發式信息；tabuk為禁忌表，用來記錄螞蟻已走過的節點，避免螞蟻“回頭”；N為能夠選擇的所有節點；α為信息素啟發因子，反映了τij（t）在蟻群搜索中的重要性；β為期望啟發因子，反映了下一節點的位置在蟻群搜索中的重要性，且β越大，狀態轉移概率越接近貪心規則[9]。

一般情況下， ηij（i，j）按式(2)計算：

dij表示i節點到j節點的距離。由式(2)可知，dij越小，則ηij（i，j）越大，也就越大，被螞蟻選擇的概率就越大。在螞蟻k到達目的地后，要對路徑上殘留信息素進行更新，這種更新類似人類的記憶功能，在新的信息素增加的同時，舊的信息素也在不斷揮發，被“忘記”。根據此原理，τij(t+1)時刻信息素的濃度相對于τij(t)時刻信息素的更新按照式(3)、式(4)處理：

ρ表示信息素揮發系數， 則（1-ρ）表示信息素殘留因子，為了防止路徑上信息素無限積累，ρ的取值范圍為ρ∈[0，1]；Δτij(t)表示本次循環中路徑(i，j)上的信息素增量，初始時刻表示第 k只螞蟻在本次循環中留在路徑（i，j）上的信息量，由式(5)求得：

Lk為第k只螞蟻在本次循環中所走過的路徑長度，Q為信息素強度。

2 改進蟻群算法

與傳統蟻群算法相比，文中在兩個方面對蟻群算法進行了改進：1）將α（信息啟發因子）和β（期望啟發因子）改為動態自適應參數，隨著迭代次數的改變相應的做出變化。2）將ρ（信息素揮發系數）設置為閾值函數。

2.1 α和β的自適應變化

傳統蟻群算法中α和β通常取值為[1，9]中某個固定值。α過大，會使路徑上信息素影響權值過大，使得螞蟻易進入局部最優解。α過小，則螞蟻行走的隨機性又太強，收斂速度太慢。β的取值影響與α相似[10]。α和β過大或者過小都容易導致蟻群算法的搜索陷入局部最優或者陷入隨機而無法找到最優解[11]。取最短路徑下的運行時間為研究對象，對α和β的最佳取值進行研究。蟻群算法中的其他參數分別取值為：迭代總數K=50，每代出動螞蟻總數M=80，信息素揮發系數ρ=0.7。多次改變α和β的取值，得到路徑長度、運算時間與迭代次數的變化如表1和表2所示。觀察變化趨勢，可以得出在求取最短路徑的問題上，α和β的最佳取值范圍分別為[2～4]和[7～9]。

通過分析和多次仿真實驗可知，在迭代初期，各條路徑信息素濃度差別不大，此時與弧相關聯的啟發式信息η為影響螞蟻選擇路徑的主要因素，因此α的值應較小，β的值應較大。隨著迭代的不斷進行，最短路徑上的信息素濃度逐漸高于其他路徑，此時信息素濃度在路徑選擇中占據主導地位，α的值應相應增加，β的值則較小。到了迭代的后期，部分路徑上信息素濃度已遠高于其他路徑，為了防止由于信息素積累陷入局部最優，此時應減小信息素濃度在路徑選擇中所占的比重，即α再次變小，β的值則相應增加[12]。同時，適當增大α和β的取值范圍，可使蟻群尋得路徑解空間范圍變大，有助于尋找全局最優解[13]。因此本文中α取值為[1～4]，β取值為[6～9]。

表1 α取值對性能的影響

表2 β取值對性能的影響

通過以上分析可知，α和β隨著迭代次數的改變呈現階梯型變化，為了能夠更平滑的完成權重系數的改變，本文分別對α和β的取值采用正弦函數和余弦函數的方式，如式(6)、式(7)所示：

式中，k表示當前迭代次數，K表示迭代總次數；本文取式(6)中A=3、B=1、ε=1而式(7)中C=3、D=6、θ=1。也可按需求適當調整。

2.2 ρ信息素揮發系數函數

在信息素的積累過程中，信息素揮發系數占有重要作用。若ρ過大，會降低算法的全局搜索能力；若ρ過小，則收斂速度會降低[14]。將蟻群算法中的其他參數分別取值為：迭代總數K=50，每代出動螞蟻總數M=80，α=1，β=7。ρ的取值變化與算法性能的關系如表3所示。

表3 ρ的取值與算法性能的關系

根據分析可知，算法開始時路徑上信息素濃度較低，此時ρ應相應取大，使得螞蟻可以更快的找到較優路徑，加快算法收斂速度；隨著路徑上信息素濃度的不斷積累，為了避免陷入局部最優丟失算法的全局搜索能力，ρ的取值應相應減小。為了使算法的全局搜索能力和收斂速度在動態平衡中得到最大程度的優化，本文選用閾值函數對ρ進行動態調整，使其隨著迭代次數的改變而改變，ρ的取值為[0.5,0.9]，取式(8)：

式中ψ為常數項，λ為改變因子，k為當前迭代次數，K為總迭代次數。選擇合適的值，使ρ的取值在[0.5,0.9]中隨著迭代的進行而動態減小。本文中ψ=1.82，λ=1。

3 實驗

3.1 二維地圖的建立及相關參數設置

為了驗證本文中算法的有效性，使用matlab2014創建二維靜態柵格地圖如圖1所示。圖中黑色柵格表示障礙物，白色柵格表示可選擇的節點。

圖1 柵格法靜態二維地圖

柵格的編號首先通過序號法從第一行依次編號，如第一行和第二行的障礙物的序號為N={2，14，15，19，20}。螞蟻所取的節點為每個柵格的中心，可通過式(9)換算為直角坐標系坐標：

其中N為序列號，M是地圖中柵格的列數，mod( )為求余函數，ceil( )為取整函數。

3.2 算法步驟

1）使用柵格法建立機器人尋找最優路徑的地圖。

2）輸入初始的信息素矩陣，選擇初始點和終點并且設置各種參數。算法的相關參數設置為：迭代總次數K=100，每代螞蟻總數M=80，信息素強度系數Q=1。改進前α、β與ρ分別取1、7和0.7，改進后根據式(6)、式(7)、式(8)設置。文獻[15]中的ρ按式(9)設置。

ξ∈(0,1)為揮發因子調節系數；ρmin為ρ的最小值。

3）選擇從初始點下一步可以到達的節點，根據每個節點的信息素求出前往每個節點的概率，并利用式(1)的輪盤賭法選取下一步初始點。

4）更新路徑及路徑長度。

5）重復步驟3）、4），直到螞蟻到達終點或因進入陷阱而死亡。

6）重復步驟3）、4）、5），直到這一代的M只螞蟻全部遍歷。

7）根據式(3)、式(4)更新信息素矩陣。

8）重復步驟3）～7），直到第K代螞蟻迭代結束。

3.3 算法實現與比較

建立一個20×20的二維靜態地圖，多次改變障礙物位置，統計傳統蟻群算法和本文改進后蟻群算法找到最優路徑所需的迭代次數。如圖2所示，某次實驗下傳統蟻法。

圖2 蟻群算法下的最優路徑

文獻[15]蟻群算法和本文改進后的蟻群算法找到的最優路徑相同。在此前提下，三種蟻群算法所需的迭代次數則分布如圖3、圖4、圖5所示。

圖3 改進前的迭代次數

圖4 文獻[15]的迭代次數

圖5 本文的迭代次數

改變障礙物位置，迭代總次數選為各算法求得最優路徑所需迭代數的次數五倍以保證結果穩定。進行多次實驗，在所得最優路徑相同的前提下，三種蟻群算法的迭代次數及運算時間如圖6、圖7所示。

圖6 各算法迭代數

圖7 各算法運算時間

由圖可知，本文改進后的蟻群算法在得到相同最優解的前提下，能夠有效的減少迭代次數。由于求得最優

【】【】解所需迭代次數的減小，使得算法在設定總迭代數時可以大幅減小，從而使得算法的總運行時間相應減小，實現了蟻群算法的快速尋路。

4 結論

蟻群算法作為機器人路徑避障中的重要方法，如何解決其收斂速度慢的問題以應對實時路況一直是蟻群算法研究的重要方向。本文提出的改進蟻群算法，是對蟻群算法的三個主要參數做了改進，使得它們在算法的不同過程中所做出的影響發生最合適的變化，在避免陷入局部最優的同時加快了收斂速度，并經過仿真實驗完成了驗證。

[1]T Stützle,M López-Ibáez.Parameter Adaptation in Ant Colony Optimization[M].Springer Be-rlin Heidelberg,2011,6(1):23-8.

[2]李士勇.蟻群算法及其應用[M].哈爾濱工業大學出版社.2004,28(1):42-45.

[3]HH Hoos,MAX-MIN Ant system[M].Elsevier Science Publishers B. V.,2000,16(9):889-914.

[4]孟祥萍,片兆宇.基于方向信息素協調的蟻群算法[J].控制與決策.2013(5):782-786.

[5]李冬妮,賈曉宇.基于蟻群算法和遺傳規劃的跨單元調度方法[J].北京理工大學學報,2017,37(7):704-7102.

[6]周文明.基于智能算法的移動機器人路徑規劃研究[D].南京理工大學.2016.

[7]ZM Lai，GD Guo.Ant Colony Optimization Based on Self-Adaption Threshold for Path Planning[J].Computer Systems &Applications,2014.

[8]郁磊.matlab智能算法30個案例分析[M].北京航空航天大學出版社.2015.

[9]DP Du,YR Zu Greedy. Strategy Based Self-adaption Ant Colony Algorithm for 0/1 Knapsack Problem[M].Springer Netherlands.2015,331:663-670.

[10]魏星,李燕.蟻群算法中參數優化及其仿真研究[J].制造業自動化,2015(10):33-35.

[11]王越,葉秋冬.蟻群算法在求解最短路徑問題上的改進策略[J].計算機工程與應用,2012,48(13):35-38.

[12]T Zhu,G Dong.Research for the Path Planning of the Agricultural Robot Based on the Improved Ant Colony Algorithm[J].Journal of Agricultural Mechanization Research,2016.

[13]DE JACKSON,M HOLCMBE,FLW RA-TNIEKS.Trail geometry gives polarity to ant foraging networks[J].Nature,2004,432(7019):907-909.

[14]鐘娟,趙彥強,孫富康,等.基于混合蟻群算法的物流配送路徑問題[J].合肥工業大學學報(自然科學版),2009,32(5):686-688.

[15]申鉉京,劉陽陽,等.求解TSP問題的快速蟻群算法[J].吉林大學學報（工學版）2013,43(1):147-151.