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

1.安徽工程大學電氣工程學院，安徽蕪湖,241000；

2.安徽科技學院動物與科學學院，安徽滁州,233100

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

王學梅1，陳其工1，王 正2

1.安徽工程大學電氣工程學院，安徽蕪湖,241000；

2.安徽科技學院動物與科學學院，安徽滁州,233100

對基于蟻群算法移動機器路徑規(guī)劃的因素進行分析研究，建立環(huán)境柵格圖模型。每一步路徑的選擇概率由狀態(tài)轉移概率公式確定，用遺傳算法控制優(yōu)勢路徑的數(shù)目以避免算法陷入局部最優(yōu)值。路徑上的信息素濃度更新用信息素更新法則進行調整，通過信息素放大機制對信息素濃度值進行適當倍數(shù)的放大，用粒子群算法對以上算法涉及到的重要參數(shù)進行優(yōu)化和選擇。仿真結果圖清晰地顯示改進后的蟻群算法在移動機器人路徑規(guī)劃上的效率和適應能力都有了明顯的改善。

改進蟻群算法；移動機器人；路徑規(guī)劃；信息素；粒子群算法

近年來，隨著機器人研究的不斷發(fā)展，移動機器人路徑規(guī)劃技術也取得了長足進步，學者們提出了多種路徑規(guī)劃算法，如神經(jīng)網(wǎng)絡法、人工勢場法、遺傳算法、粒子群優(yōu)化算法等。但路徑規(guī)劃的核心思想?yún)s始終如一，那就是尋找一條從起始點到目標點的最優(yōu)路徑，這其中包括用時最短、路徑最短、避開所有障礙物且通過必須要經(jīng)過的指定點[1-4]。

針對傳統(tǒng)蟻群算法機器人路徑規(guī)劃出現(xiàn)的問題，本文通過信息素放大機制成功解決了蟻群算法自身收斂速度慢問題；同時，為了克服由于搜索機制導致算法容易陷入局部最優(yōu)的困境，也將遺傳算法融入其中。由于粒子群算法(Particlc Swarm Optimization，簡稱PSO)能很好地對參數(shù)進行優(yōu)化，因此，將其加入到改進蟻群算法中，以進一步確保算法的穩(wěn)定性和優(yōu)越性，最終完成路徑規(guī)劃研究和仿真實驗。

1 蟻群算法的改進

人們通過觀察研究發(fā)現(xiàn)，螞蟻的覓食工作是分工協(xié)作、合理有序的，彼此間通過自身散發(fā)出的信息素進行交流，且在走過的路徑上留下這種物質作為標記。某一路徑上通過的螞蟻越多，留下的信息素的濃度也就越高(忽略揮發(fā)掉的部分)，在有限的區(qū)域范圍內螞蟻彼此間能感覺到這種化學物質，并且哪里的信息素濃度高就自覺地向那個方向移動，因此，信息素濃度越高的路徑，被選擇的概率也就越大。群體中的個體之間就是這樣通過信息素相互交流，最終探索到一條從蟻穴到食物源的最短的路徑而獲取食物[5-6]。

1.1 路徑選擇概率公式

蟻群算法中狀態(tài)轉移概率公式定義為:

(1)

式中，α和β分別表示τij(t)和ηij(t)對整個概率影響的大小； τij(t)表示t時刻路徑i與路徑j上殘留的信息素濃度，ηij(t)表示后續(xù)柵格點的啟發(fā)信息強度函數(shù)；allowedα表示螞蟻k下一步可以選擇的柵格號組成的集合。

與此同時，后續(xù)柵格的概率選擇公式ηij(t)為：

其中，dij表示從路徑i到路徑j的距離。

由于自然狀態(tài)下群體中螞蟻搜索到的各路徑上信息素濃度差異很小，導致算法的搜索效率低下，收斂速度慢[7]，效果不盡人意。

1.2 用遺傳算法避免蟻群算法陷入局部最優(yōu)

由于蟻群算法自身的缺陷，使得算法容易陷入局部最優(yōu)，本文采用遺傳算法中的輪盤算法[8]來避免蟻群算法陷入局部最優(yōu)值。按照群體中每一個體對環(huán)境適應能力的大小，以不同的概率向下一代進行復制。具體操作過程如下：

步驟1根據(jù)適應度函數(shù)：

其中，n代表螞蟻在模擬環(huán)境中所經(jīng)過的路徑上所包含的柵格數(shù)目，每個螞蟻個體所經(jīng)過的路徑長度用字母d表示。依次計算出群體內每個個體的適應值，得相應的累計值為Hi，最后一個累計值為Hn；

步驟2得出均勻分布的適應度隨機數(shù)W∈[0，Hn];

步驟3依次用Hi與步驟2中產生的隨機數(shù)W進行比較，若Hi≥W，則i被選為復制對象；若Hi≤W，則i被刪除；

步驟4重復步驟2和步驟3，直到所需要的個體數(shù)目被復制滿為止。

通過輪盤算法對個體適應值的篩選，使算法的早熟問題得到了很好的解決。為了使算法優(yōu)勢更加明顯，用上一代種群中適應度大的個體來代替新種群中適應度小的個體，增加了新種群中優(yōu)勢路徑的數(shù)目,顯著提高了算法的效率及全局最優(yōu)解的搜索概率。

2 粒子群算法對參數(shù)的優(yōu)化

設M為信息素濃度放大倍數(shù)，信息素濃度和啟發(fā)函數(shù)對轉移概率的影響程度分別用α和β表示，信息素揮發(fā)系數(shù)為ρ，啟發(fā)系數(shù)為ε。顯然最能影響算法性能的因素是參數(shù)的選取,而人們通常根據(jù)經(jīng)驗選取參數(shù)值，這樣就使得算法具有很強的主觀性，導致算法容易陷入局部最優(yōu)；由于粒子群算法搜索速度快、效率高、算法簡單，適合于實值型處理，因此選擇其對改進蟻群算法的重要參數(shù)進行優(yōu)化選擇。

2.1 粒子群優(yōu)化群算法

粒子群優(yōu)化算法是由電子工程學博士R.Eberhart和社會心理學博士J.Kennedy受自然界鳥類尋找食物的自然現(xiàn)象的啟發(fā)于1995年發(fā)表的兩篇論文中提出的。由于PSO算法對非線性多峰值問題和沒有特殊方法可用或者使用特殊方法也得不到滿意結果的問題有很好的應用前景，因此PSO已廣泛應用于調度、組合優(yōu)化、信號處理、數(shù)據(jù)挖掘等現(xiàn)代化應用領域。

定義算法在Q維的空間搜索，參與搜索的粒子數(shù)為m，粒子l在某一時刻它的位置和速度分別記為xl和vl則：

xl=(xl1,…,xlq,…,xIQ)

vl=(vl1,…,vlq,…,vIQ)

其中，1≤l≤m,1≤q≤Q。

在解空間中，pl=(pl1,pl2,…,pIQ)表示粒子l所經(jīng)歷的最好位置，群體中適應度最好的粒子g的位置記為pg=(pg1,pg2,…,pgQ)，則粒子群的進化方程式為：

(2)

(3)

其中，w為慣性衡量值；c1和c2為影響機器人自適應學習功能的參數(shù)；r1和r2為常數(shù)，且取值范圍為0≤r1≤1，0≤r2≤1；k為遍歷搜索的次數(shù)。粒子的位置用字母X表示，且其變化范圍為X∈[Xmin,Xmax]；速度用字母V表示，其變化范圍記為V∈[Vmin,Vmax],若由式(2)和式(3)計算出的值超過了這個范圍，則設置其為邊界值。

2.2 對參數(shù)進行優(yōu)化

改進蟻群算法的相關參數(shù)用粒子群算法進行優(yōu)化選擇的具體操作步驟如下：

步驟1參數(shù)初始化。對遍歷搜索次數(shù)最大值kmax，慣性衡量值w，粒子個數(shù)m，影響機器人自適應學習功能的參數(shù)c1和c2進行初始化。

步驟2當前粒子群的位置信息用改進蟻群算法中放大后的信息素濃度值和啟發(fā)函數(shù)表示，起始位置和初速度在位置可變范圍內隨機選取。

步驟3將當前群體中適應度最好的粒子的位置和本次循環(huán)中每個粒子在解集中的最好位置求出。

步驟4粒子群中每個粒子i的速度Vi按(2)式進行更新。若Vi小于Vmin，則Vi為Vmin；若Vi大于Vmin，則Vi為Vmax。

步驟5粒子群中每個粒子i的位置Xi按式(3)對其進行更新。若Xi小于Xmin，則Xi為Xmin；若Xi大于Xmin，則Xi為Xmax。

3 用改進的蟻群算法對機器人動態(tài)路徑進行規(guī)劃

在用蟻群算法尋找機器人工作環(huán)境中最優(yōu)路徑的過程中，如果傳感器檢測到機器人將與環(huán)境中移動的障礙物相碰，機器人則選擇離動態(tài)障礙物最近的安全柵格作為新的移動路徑。根據(jù)傳感器探測反饋的環(huán)境信息，確定動態(tài)障礙物在模擬環(huán)境空間中的運動范圍，在避開障礙物的前提下，機器人循著信息素濃度高的路徑前進[9]。用粒子群算法對改進蟻群算法中的重要參數(shù)的最優(yōu)組合進行確定，基于以上對算法的改進，新路徑規(guī)劃的操作步驟如下：

步驟1初始化參數(shù)。對最大迭代次數(shù)Kmax、種群個數(shù)為Nnum、信息素濃度放大倍數(shù)M進行初始化；S和E分別為算法的起點和終點，設Nnum只螞蟻的起始位置全部在起始點S，且起始時每條路徑上的信息素濃度都為0。

步驟2螞蟻下一步到達的柵格根據(jù)自適應啟發(fā)函數(shù)確定。

步驟3在螞蟻k到達終點E后，按信息素更新公式對路徑上的信息素進行更新。

步驟4合理選擇和調整放大倍數(shù)M，對更新后的信息素濃度按放大倍數(shù)M進行放大。

步驟5對循環(huán)次數(shù)進行判斷。若循環(huán)次數(shù)已達到最大值，則將當前群體中用時最短的路徑柵格的序號和長度輸出；否則返回起點S，程序轉步驟2。

步驟6機器人在沿著通過以上步驟搜索到的最優(yōu)路徑前進時，如果傳感器檢測到將與環(huán)境中的動態(tài)障礙物相撞，則機器人調整前進方向后沿著信息素濃度大的柵格重新探索到一條避開動態(tài)障礙物的路徑，否則，機器人一直走到指定目標點，終止算法。

4 仿真實驗與分析

改進后蟻群算法[10]性能的仿真實驗在Matlab軟件中進行。工作環(huán)境的柵格圖是長為20個柵格、寬也為20個柵格正方形，每個小柵格的面積為10×10個單位，定義傳統(tǒng)蟻群算法中螞蟻數(shù)和最大循環(huán)次數(shù)分別25和200。用于對改進蟻群算法的重要參數(shù)進行優(yōu)化粒子群算法中粒子數(shù)為30，循環(huán)次數(shù)的最大值為100，慣性衡量值w為0.65，影響機器人自適應學習功能的參數(shù)c1和c2都選為1.5，放大倍數(shù)M=3。

仿真圖中，坐標系以X軸向右為正方向，Y軸向上為正方向，假設動態(tài)障礙物為正方形物塊，且其長和寬都為10個單位。

由圖1和圖2的仿真實驗結果可以看出，改進的蟻群算法減少了搜索的盲目性，縮短了搜索時間，提升了算法的性能。

5 結束語

路徑規(guī)劃一直是機器人研究領域的關鍵性問題之一，如何找到一條快速、高效、便捷、安全性能高的路徑，一直是機器人研究工作者們的愿望。傳統(tǒng)蟻群算法是受螞蟻覓食一步步探索路徑的啟示抽象得到的，因此算法的搜索效率低下且容易陷入局部最優(yōu)。本文通過對信息素濃度值進行適當倍數(shù)的放大，擴大了不同路徑上信息素濃度的差距，有效地提高了搜索速度。考慮到這樣容易導致算法陷入局部最優(yōu)的值，采用遺傳算法進行優(yōu)化，適當選擇遺傳算子，從而提高了新種群中的合適的路徑數(shù)目，成功避免了算法陷入局部最優(yōu)且提高了算法的收斂速度。仿真實驗結果表明，該路徑規(guī)劃方法是可行的，且效果明顯。

[1]付濤，王大鎮(zhèn)，弓清忠，等．改進神經(jīng)網(wǎng)絡自適應滑模控制的機器人軌跡跟蹤控制[J]．大連理工大學學報，2014(5)：523-530

[2]殷路，尹怡欣．基于動態(tài)人工勢場法的路徑規(guī)劃仿真研究[J]．系統(tǒng)仿真學報，2009，21(11)：3325-3328

[3]浦定超.基于遺傳算法的移動機器人路徑規(guī)劃的研究[D].合肥：合肥工業(yè)大學電器與自動化工程學院，2010:16-28

[4]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J].農業(yè)機械學報，2014,45(6):53-56[5]楊學峰．蟻群算法求解TSP問題的研究[D]．長春：吉林大學計算機科學與技術學院，2010：14-16

[6]楊沛，古德祥．蟻群的信息系統(tǒng)[J]．昆蟲知識，2001，38(1)：23-25

[7]Gutjahr W J.A graph-based ant system and its convergence[J].Future Generation Computer Systems,2000,16(8):873-888

[8]崔建軍．基于遺傳算法的移動機器人路徑規(guī)劃研究[D]．西安：西安科技大學電氣與控制工程學院，2010：42-44

[9]郝靳.基于改進的蟻群算法實現(xiàn)的茶樹種植分析系統(tǒng)[D].長春：吉林大學軟件學院，2014：15-23

[10]柳長安，鄢小虎，劉春陽，等．基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J]．電子學報，2011，5(5)：1220-1224

(責任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.03.027

2015-11-15

國家自然科學基金資助項目“網(wǎng)絡控制系統(tǒng)中基于時延在線預測的動態(tài)調度策略研究”(61172131)。

王學梅(1984-)，女，安徽滁州人，在讀碩士研究生，主要研究方向：移動機器人路徑規(guī)劃。

TP18

A

1673-2006(2016)03-0107-04