基于改進蟻群算法的靜態(tài)路徑規(guī)劃研究

李 偉

（鹽城工業(yè)職業(yè)技術學院 江蘇 鹽城 224005）

0 引言

伴隨著機器人技術快速發(fā)展，移動機器人廣泛應用于制造業(yè)、建筑業(yè)、物流、危險工作環(huán)境等領域[1]，路徑規(guī)劃問題作為移動機器人研究領域中的重要問題開始受到關注，路徑規(guī)劃是指機器人在其工作空間內(nèi)自行規(guī)劃出最優(yōu)或較優(yōu)的安全路徑。常用算法可分為兩類，一類是基本算法，主要有Dijkstra算法[2]、A*算法[3]、勢場法[4]等；另外一類是群智能算法，典型代表有：蟻群算法[5]、遺傳算法[6]、粒子群算法[7]等。在前述算法中，蟻群算法以其行為規(guī)則簡單、分布式并行計算、易與其他算法結合等優(yōu)點在路徑規(guī)劃領域得到應用，此外在TSP、調(diào)度等領域也得到成功應用，但是蟻群算法也存在尋優(yōu)能力不平衡、易陷入局部最優(yōu)等問題。為改善現(xiàn)有蟻群算法性能，不少學者提出了優(yōu)化方法，裴振兵等[8]提出在蟻群搜索路徑過程中，將啟發(fā)因子與期望啟發(fā)因子建立互鎖關系并設計前述兩參數(shù)的動態(tài)自適應調(diào)整，提高了算法的收斂速度與搜索效率；張原藝等[9]為提高算法的搜索能力，設計了一種基于多步長的改進蟻群算法，利用每次迭代得到最優(yōu)路徑來引導搜索確定多步長的移動路徑，此外還設計有安全判別機制；高茂源等[10]從優(yōu)化信息素的角度來優(yōu)化蟻群算法，針對初始信息素匱乏不足的問題，提出增加額外信息素在起點與終點的連線上，此外還改良了信息素濃度的揮發(fā)公式，實驗結果表明改進算法提高了收斂速度與性能；張毅等[11]基于柵格法建模并通過限制沿對角方向上移動來提高算法的搜索效率，此外針對轉彎耗時較長設計了轉彎影響因子來節(jié)約機器人過轉時間。

由上述文獻及參考蟻群算法的研究現(xiàn)狀可知，針對蟻群算法的尋優(yōu)能力不平衡、易陷入局部最優(yōu)等問題有進一步研究的必要。本文提出了一種改進蟻群算法：首先，利用柵格法進行靜態(tài)環(huán)境建模；其次，優(yōu)化信息素更新策略，信息素更新中引入保底機制并設計隨迭代次數(shù)變化而變化的信息素強度，降低算法陷入停滯收斂與局部最優(yōu)情況；再次，對狀態(tài)轉移概率進行改進，引入反向學習來擴大算法選擇路徑范圍，提高算法搜索效率與尋優(yōu)能力；最后，在MATLAB中對改進蟻群算法進行了仿真驗證。

1 相關知識

1.1 環(huán)境建模

本文主要研究靜態(tài)環(huán)境下路徑規(guī)劃，此時移動機器人所處工作環(huán)境中的障礙物均為靜態(tài)狀態(tài)，考慮到柵格法相較于幾何法和拓撲圖法更易構建環(huán)境模型，本文選擇柵格法，其工作原理是將待建模環(huán)境進行二值化替代，“1”代表障礙物柵格即不可通行柵格、“0”代表非障礙物柵格即可通行柵格，一個15×15的柵格地圖如圖1（a）所示，黑色柵格代表不可通行柵格、白色柵格代表可通行柵格，同時圖中可見機器人在非邊緣柵格有8個方向可移動、邊緣非頂角柵格有5個方向可移動、頂角柵格有3個方向可移動。

1.2 蟻群算法

蟻群算法是群智能算法的一種，該算法[12]模擬的是蟻群中的螞蟻覓食行為即蟻群的螞蟻尋找巢穴至食物源間的便利路徑，螞蟻可以釋放信息素在自己所經(jīng)的路徑與此同時螞蟻亦可感知路徑中信息素濃度，螞蟻會向信息素濃度較高的路徑移動，由此便形成一種正反饋現(xiàn)象：有多條路徑可從居住地到食物所在地，較短路徑上的螞蟻往返花費時間相應較短由此較短路徑上信息素濃度會增加、會引導更多螞蟻選擇較短路徑；與此對應的較長路徑情況則相反，最終螞蟻會找出最優(yōu)或較優(yōu)路徑。

在t時刻螞蟻k從節(jié)點i到節(jié)點j由轉移概率(t)來決定，式（1）為(t)的計算公式。

式中：τij(t)為t時刻路徑(i,j)間的信息素濃度，ηij(t)為t時刻路徑(i,j)間的啟發(fā)函數(shù)，α、β為啟發(fā)因子、期望啟發(fā)因子，allowk為可轉移的領域節(jié)點集合。

伴隨著時間的變化，路徑上的信息素會因螞蟻的不斷經(jīng)過而出現(xiàn)信息素累積情況，與此同時也有揮發(fā)引起信息素減少情況，因此有必要對信息素進行更新操作，算法完成一次迭代后更新信息素如式（2）～式（4）所示：

式中：ρ為揮發(fā)系數(shù)，1-ρ為持久系數(shù)；Δτij為在完成本次循環(huán)后路徑(i,j)間的信息素變化量；Δ為第k只螞蟻完成本次循環(huán)后留在路徑(i,j)間的信息素量；Q為常數(shù)，代表信息素強度值；Lk為k只螞蟻完成本次循環(huán)中所走路徑的總長度。

2 基于改進蟻群算法的路徑規(guī)劃

2.1 限定信息素區(qū)間

由1.2節(jié)蟻群算法介紹可知，螞蟻會向信息素濃度較高的路徑移動即螞蟻會選擇較優(yōu)的路徑，如果其他路徑?jīng)]有螞蟻經(jīng)過即代表無信息素新增，相應地原有信息素也在不斷揮發(fā)中會降低至零，此時算法中的候選路徑會趨于單一，易引發(fā)算法的停滯收斂情況[13-14]。為避免算法運行中出現(xiàn)上述情況，本文引入保底機制即τ有最低限制值，具體做法為：τmin＜τ，保證算法在迭代中的信息素高于最低限制值，此時較差的路徑也有信息素存在從而候選路徑會維持多樣化，這樣算法不易陷入停滯收斂。

2.2 動態(tài)信息素強度值設計

由式（4）可知，蟻群算法完成一次循環(huán)后釋放的Q為常數(shù)即為一個定值，算法經(jīng)過多次迭代循環(huán)后路徑上信息素量會不斷積累，此時算法易陷入局部最優(yōu)，針對性設計隨迭代次數(shù)變化而變化信息素強度值即算法中后期的Q相應動態(tài)降低，具體公式如下：

由式（5）可知，中前期定值Q保證了不降低算法的搜索能力的同時中后期動態(tài)變化Q能夠有效降低算法陷入局部最優(yōu)的可能性。

2.3 反向轉移概率設計

蟻群算法存在正反饋機制，每次信息素更新時最優(yōu)或較優(yōu)路徑得益于螞蟻往返花費時間較短從而信息素濃度增加，信息素濃度增加會吸引后續(xù)迭代螞蟻選擇上述路徑，這一正反饋機制可以讓候選路徑出現(xiàn)分化，引導蟻群選擇最優(yōu)路徑，但是一旦算法初始得到的“最優(yōu)路徑”為較優(yōu)或者次優(yōu)路徑，此時由于正反饋機制的存在，算法易陷入局部最優(yōu)，所以有必要擴大算法選擇路徑范圍。反向學習（opposition-basedlearning，OBL）[15]目前廣泛應用于各類算法改進中，其主要思想是在當前解的基礎上得到反向解并同時考慮當前解及反向解。反向學習定義：若在D維空間x=(x1,x2,...,xD)上存在一個點，且xi∈[a i,bi]，則反向點xi*=a i+bi-xi,i∈[1,D]。本文在計算轉移概率時引入反向學習來擴大算法選擇路徑范圍，反向信息素τij計算如下：

式中，Lgbest為完成Tc次循環(huán)后的最優(yōu)路徑長度。

特別地，由于算法首次迭代未完成前沒有獲得Lgbest故完成首次迭代后的反向信息素參考信息素τij(0)設定。此時t時刻螞蟻k從節(jié)點i到節(jié)點j由轉移概率new(t)來決定：

式中，λc為反向概率，當隨機數(shù)λ≤λc時，執(zhí)行反向學習轉移概率，反之執(zhí)行原轉移概率。

2.4 相關參數(shù)選取

下面對蟻群算法中部分參數(shù)選取進行介紹，主要包括：ρ、α、β、m、Tmax。揮發(fā)系數(shù)ρ，信息素指引蟻群搜索的方向，伴隨著算法迭代，各節(jié)點上的信息素將逐漸揮發(fā)，揮發(fā)情況由信息素揮發(fā)系數(shù)決定，由此可見信息素揮發(fā)系數(shù)直接影響算法收斂速度和尋優(yōu)能力，ρ增大代表信息素揮發(fā)情況明顯，此時難以保證算法的搜索能力；ρ減小代表信息素揮發(fā)情況不明顯，此時保證了算法搜索能力，但與之相應地會影響算法的收斂速度，綜上ρ的選取應適中，本文設置ρ為0.3。啟發(fā)因子α、期望啟發(fā)因子β，α代表信息素濃度對蟻群的指示作用，其值決定了螞蟻選擇之前路徑的概率大小；β代表路徑相關信息對蟻群的影響，其值決定了算法的搜索效率，本文設置分別為1、7。螞蟻數(shù)量m，蟻群算法中的蟻群數(shù)量應適中，如果蟻群規(guī)模過大，此時會造成信息素趨于一致，最優(yōu)或較優(yōu)路徑無法被確定；如果蟻群規(guī)模過小，算法易出現(xiàn)早熟的情況，也難以確定最優(yōu)或較優(yōu)路徑，本文選取適中的螞蟻數(shù)量，設置為50。最大迭代次數(shù)Tmax的選取應參考算法的實際收斂曲線合理確定，如果最大迭代次數(shù)設置過大，此時算法已收斂并獲取最優(yōu)路徑長度，后續(xù)迭代無意義；如果最大迭代次數(shù)設置過小，算法尚未收斂、未獲取最優(yōu)路徑長度，即算法結束時所得結果不準確，本文參考算法實際運行情況，設置Tmax為50。

2.5 算法應用步驟

本文所設計的改進蟻群算法應用于靜態(tài)工作環(huán)境下移動機器人路徑規(guī)劃的具體應用步驟如下：

步驟1 基于柵格法對機器人工作環(huán)境建模；

步驟2 初始化蟻群算法中的相關參數(shù)；

步驟4 記錄完成本次迭代后的最佳路徑并根據(jù)式（2）～式（6）完成信息素更新；

步驟5 通過對當前迭代次數(shù)Tc與最大迭代次數(shù)Tmax進行比較，若達到則輸出結果，否則返回執(zhí)行步驟3。

3 實驗與分析

為驗證本文所設計的改進蟻群算法在移動機器人靜態(tài)工作環(huán)境下的路徑規(guī)劃表現(xiàn)，在15×15與20×20的兩組柵格環(huán)境下分別對蟻群算法與本文算法進行10次仿真驗證，起始點和終點分別設置在柵格地圖的左上與右下方，相關參數(shù)設置見2.4節(jié)。15×15柵格地圖中的障礙覆蓋率為25%即工作環(huán)境中25%柵格為不可通行柵格、剩余柵格可通行，兩算法所得路徑如圖1（a）所示，可得兩算法都可收斂獲得長度一致的最優(yōu)路徑，兩算法所得路徑軌跡的轉折點均為8個。20×20柵格地圖在15×15基礎上擴大地圖柵格數(shù)并合理設置障礙，兩算法所得路徑如圖1（b）、1（c）所示，兩算法所得路徑軌跡的轉折點均為6個但蟻群算法在接近終點時路線非最優(yōu)選擇，在局部最優(yōu)處收斂，沒有得到長度最短的路徑，本文算法所得路徑曲線流暢，所得路徑更短。因此本文算法相較于蟻群算法有著更好的表現(xiàn)，尋優(yōu)能力好且不易陷入局部最優(yōu)。

4 結語

在移動機器人靜態(tài)工作環(huán)境中，本文針對蟻群算法應用于路徑規(guī)劃問題時存在的尋優(yōu)能力不平衡、易陷入局部最優(yōu)等不足，在柵格地圖中提出了一種改進蟻群算法，引入限定信息素區(qū)間并設計動態(tài)信息素強度值來優(yōu)化信息素更新策略，降低算法陷入停滯收斂與局部最優(yōu)；設計含反向學習的轉移概率來提高算法的搜索能力、避免陷入局部最優(yōu)。實驗結果表明，改進蟻群算法相較于蟻群算法提高了尋優(yōu)能力且不易陷入局部最優(yōu)。