移動機器人路徑規(guī)劃的改進蟻群算法

張 儀 趙苗慧 楊 兵 張 彤

（陜西省可控中子源工程技術研究中心，西京學院理學院，陜西 西安710123）

近年來，由于人工智能的飛速發(fā)展，移動機器人的發(fā)展也成為人們討論的熱點，同時路徑規(guī)劃是移動機器人主要討論的焦點。路徑規(guī)劃是指移動機器人在有障礙的環(huán)境中尋找一條無碰撞的路徑[1]。路徑規(guī)劃的智能優(yōu)化算法主要有：遺傳算法、模擬退火算法、粒子群算法、免疫算法等。這些算法在移動機器人路徑規(guī)劃時能取得很好的結果，但面對復雜環(huán)境時依然存在一定的缺陷[2]。

本文將改進的蟻群算法是一種啟發(fā)式的隨機搜索算法。蟻群算法來源于自然界螞蟻尋找食物的過程。該算法主要模擬螞蟻群體覓食的過程，螞蟻在尋找食物的過程中，會在所經(jīng)過的路徑上留下信息素，而在找到食物，且路程較短的路徑上留下較多的信息素，這也給后來尋找食物的螞蟻提供了強有力的方向指引，更多的螞蟻會往信息素濃度高的路徑上走[3]。但傳統(tǒng)的蟻群算法存在收斂速度慢、容易陷入局部最優(yōu)解等問題[4]。本文將根據(jù)傳統(tǒng)蟻群算法所存在的問題提出一種改進蟻群算法。

1 障礙物模型建立

本文將利用柵格法來模擬障礙物環(huán)境，黑格表示障礙物，在矩陣中由1 表示，白格表示可行空間，在矩陣中由0 表示。柵格點標號依據(jù)從左到右，從上到下的順序依次標號。每個標號代表一個柵格點。每個柵格長度定義為1。坐標原點定義為左上點。并建立XOY 坐標系。坐標點（X,Y）和柵格標號G 對應的關系為式（1）和式（2）所示：

式中，G 是柵格點標號，N 是矩陣的行列數(shù)，mod 是進行取余數(shù)操作，ceil 是進行朝正向元素方向取整操作。對移動機器人在柵格中的移動規(guī)定以下準則:（1）移動機器人只能在白格中移動，并將移動機器人作為質(zhì)點。（2）移動機器人每次從每個柵格的中心出發(fā)，每次只能向周圍八個中心移動，每次移動的距離為1 或1.414。向上下左右移動時的距離為1，向左上、左下、右上、右下移動時距離為1.414。

2 蟻群算法

2.1 傳統(tǒng)蟻群算法

2.2 傳統(tǒng)蟻群算法的不足

2.2.1 迭代次數(shù)多。傳統(tǒng)蟻群算法在前期迭代時，每條路徑上的信息素濃度差別不大，就加大了螞蟻尋找最優(yōu)路徑的范圍，需要更多的時間去搜索路徑，直到找到最優(yōu)路徑。

2.2.2 易陷入局部最優(yōu)解。傳統(tǒng)蟻群算法尋找到較優(yōu)路徑時，就會往這條路徑上釋放更多的信息素，從而引來更多的螞蟻在這條路徑上留下信息素，通過正反饋，令較優(yōu)解成為了最佳路徑。

2.2.3 參數(shù)的大小選擇影響算法尋優(yōu)能力。參數(shù)的選擇直接影響算法的尋優(yōu)能力，參數(shù)選擇不當直接影響算法的可行性。

2.3 改進蟻群算法

通過上述分析的不足，對蟻群算法提出以下改進：

2.3.1 解決陷入U 型陷阱問題。當螞蟻陷入U 型陷阱時，螞蟻只能選擇回退，但上一個節(jié)點已經(jīng)無法回退，此螞蟻就陷入了鎖死狀態(tài)。文獻[5]就提出將鎖死的螞蟻丟棄。但此方法并未將螞蟻陷入鎖死時的節(jié)點加入禁忌表，沒有為后來出發(fā)的螞蟻留下有效信息。本文提出一種新的解決方案，當螞蟻陷入鎖死時，將此節(jié)點加入禁忌表中，并將此螞蟻之前路徑上的信息素清零，再令此螞蟻從起始點重新出發(fā)。

2.3.2 設計自適應信息素揮發(fā)因子ρ。信息素揮發(fā)因子ρ 的大小影響著蟻群算法的收斂速度，也影響算法能否找到最優(yōu)路徑。當ρ 過大時，容易導致信息素揮發(fā)過快，減少了較優(yōu)路徑上的信息素含量，從而導致最優(yōu)路徑可能被排除。當ρ 過小時，會使各路徑上信息素含量差別不大，從而導致最優(yōu)路徑不容易被選擇，影響算法的收斂性。本文設計了一種自適應信息素揮發(fā)因子。本設計引入Sigmoid 函數(shù)作為信息素揮發(fā)因子前面的系數(shù)。本設計只引入Sigmoid 函數(shù)大于0 的部分。改進如式（3）所示。

式中，ρ 和N 為程序初始化設定的參數(shù)，信息素揮發(fā)因子和迭代次數(shù)，Nn為進行到第n 次的迭代。

若取N 為100，則ρ 前面的系數(shù)值與迭代次數(shù)N 的曲線關系如圖1 所示。

圖1 迭代次數(shù)和系數(shù)值的關系圖

由圖1 可知該式實現(xiàn)了ρ 的大小隨迭代次數(shù)變化而變化的效果。在迭代初期和末期，ρ 的取值最小，初期時，取值越小有利于螞蟻更容易找見最優(yōu)路勁，末期時，取值越小有利于增快收斂性。當中期取值較大時，能增大信息素的揮發(fā)，若陷入局部最優(yōu)解，就更容易找到更優(yōu)的解，使螞蟻避免陷入局部最優(yōu)解。

3 實驗結果與分析

圖2 傳統(tǒng)蟻群算法路徑規(guī)劃圖

圖3 改進蟻群算法路徑規(guī)劃圖

由圖2 和圖3 對比可知，很直觀地就能看出改進的蟻群算法是有效果的，改進的蟻群算法明顯比傳統(tǒng)蟻群算法少走了許多冤枉路，拐彎次數(shù)也少了好多次。再由圖2 和圖3 對比可知，改進蟻群算法所找到的解比傳統(tǒng)蟻群算法所找到的解要更優(yōu)，所找到的最短路徑長度比傳統(tǒng)的要短11.2%。所用的迭代次數(shù)也比傳統(tǒng)蟻群算法要少。傳統(tǒng)蟻群算法與改進蟻群算法對比數(shù)據(jù)如表1 所示。

表1 傳統(tǒng)蟻群算法與改進蟻群算法性能指標數(shù)據(jù)對比

4 結論

傳統(tǒng)蟻群算法確實存在容易陷入局部最優(yōu)解、無法找到最優(yōu)路徑的問題，基于此問題，設計了一種自適應信息素揮發(fā)因子與舍棄鎖死螞蟻路徑信息素但不舍棄螞蟻的方法處理陷入U型障礙鎖死的問題。通過仿真證明改進蟻群算法可以很好地使蟻群避免陷入局部最優(yōu)解而且能減少迭代次數(shù)，提高算法的效率，效果優(yōu)于傳統(tǒng)蟻群算法。