基于改進蟻群算法的全局路徑規劃研究與仿真

燕紫君，吳明芬*

?

基于改進蟻群算法的全局路徑規劃研究與仿真

燕紫君，吳明芬*

(五邑大學計算機學院 江門 529020）

路徑規劃是指在有障礙物的工作環境中，尋找一條從給定起點到終點的適當路徑，使運動過程中能安全、無碰的繞過所有障礙物。目前針對路徑規劃的算法較多，本文主要針對傳統蟻群算法在二維路徑規劃中易陷于局部最優解，最終導致搜索過早停滯等問題，提出了一種改進的蟻群算法。該改進的算法主要以全局最優為出發點，通過引入終點對啟發因子的影響，在鄰接點和終點的共同作用下對啟發因子函數的重新構建，有效地解決了傳統蟻群算法在處理全局路徑規劃中帶來的問題。采用MAKLINK圖論理論建立二維空間模型，應用MATLAB作為編碼的軟件工具來對傳統的蟻群算法和改進的蟻群算法在路徑規劃中進行仿真驗證，實驗結果表明改進的蟻群算法有更好的性能。

全局路徑規劃；蟻群算法；啟發因子；MAKLINK圖論理論

引言

路徑規劃是指在有障礙物的工作環境中，尋找一條從給定起點到終點的適當運動路徑，使在運動過程中的物體能安全、無碰的繞過所有障礙物。考慮到實際環境復雜多變,如何迅速的策劃一個有效的最優的路徑變得異常顯著。目前國內外研究者們針對該問題已經提出了多種解決方法，比如神經網絡算法[1]、人工勢場法[2]等，神經網絡算法具有較強的學習能力，但是當路徑中的障礙物變多，且為動態時，就要不斷的調整閾值；人工勢場法的優勢在于實時控制，但容易陷入局部最優解而停止運動。蟻群算法的提出為解決這一問題提供了新的思路。從金純等人的《礦井中多機器人搜救系統路徑規劃》[3]、Rong Wang等人的《Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm》[4]、張琦等的《基于改進蟻群算法的移動機器人路徑規劃》[5]等文獻中可知，蟻群算法在解決這一問題中有著較強的優越性，但還是存在收斂于局部次優解的問題，為了克服這些的問題，本文提出了一種改進的蟻群算法，該算法主要是通過引入終點對啟發因子的影響，在鄰接點和終點的共同作用下對啟發因子函數的重新構建，有效地解決了傳統蟻群算法在處理全局路徑規劃中帶來的問題。

1 傳統的蟻群算法

蟻群算法是一種模擬螞蟻搜索食物的算法，它于90年代由M.Dorigo[6]等人提出，該算法一經提出便成為了智能領域一種主要的算法。該算法在解決優化問題的基本步驟是：螞蟻行走路徑被看作問題的可行優化路徑，整個螞蟻所在的路徑構成了解空間的優化問題。釋放的信息素在短路徑會超過其它路徑，隨著時間的推移，更多的螞蟻會選擇這些較短的路徑。最終螞蟻在積極的反饋作用下將專注于最好的路徑。

在t時刻，螞蟻k從節點i選擇下一個要走的節點j必須要依據概率轉換公式，如公式（1）、公式（2）和公式（3）所示

（2）

（3）

信息素初始化時通常將每條路徑上的值都設置為一固定的常數。在對于信息素的更新策略方面有局部信息素更新方式和全局信息素更新方式，局部信息素更新方式指螞蟻選完下一路徑后立即更新該路徑上的信息素；全局信息素更新方式是所有螞蟻選擇完下一個節點后，對信息素進行更新。為了更好的得到全局最優路徑，本文選擇全局信息素更新方式。其公式如公式（4）所示。

2 改進的蟻群算法

由于在解決機器人全局路徑規劃時傳統的蟻群算法存在收斂于局部次優解而導致搜索的過早停滯問題，為了克服在全局路徑規劃中蟻群算法中存在的這些的問題，下面提出了一種改進的蟻群算法。

2.1 環境建模

本文利用MAKLINK圖論理論[7]建立一個二維空間模型， MAKLINK線定義為兩個障礙物之間不與障礙物相交的頂點之間的連線,以及障礙物頂點與邊界相交的連線[8]。典型的MAKLINK圖如圖1所示。在MAKLINK圖上存在一條自由連接線，連接線中的點依次為,連接部分MAKLINK線中的點加上起點和終點就構成了規劃路徑。

Fig. 1 The two-dimension MIKLINK model

在MAKLINK模型中規劃最短路徑的主要思路是：首先利用MAKLINK圖建立路徑規劃二維空間模型，然后根據dijkstra算法[6]（單源最短路徑算法）來對最短路徑初始化，初始化各參數，采用蟻群算法搜索路徑，更新路徑上的信息素。假設得到的路徑為，其中表示第條連接線上的第個等分點。

2.2 蟻群算法的改進

下面使用全局式啟發因子示意圖來更詳細的對此改進的公式進行描述，如圖2所示，在最短路徑規劃中已經得知了起點和終點，所以目標就是在起點和終點之間找一條最短路徑。所以當螞蟻選擇下一個城市時，如果是基于傳統蟻群算法，會傾向于選擇節點，但改進的蟻群算法會從全局考慮，更傾向于選擇節點。由兩點之間線段最短可知改進的啟發因子函數中引入了可以得到更短的規劃路徑。由于兩邊之和大于第三邊，所以改進以后的啟發因子函數，更加考慮全局，可以從一定程度上避免局部最優解。

Fig. 2 The stimulating factor function .

為了說明該改進的有效性，舉個簡單的例子來說明。如圖3表示一個普通路網圖，要分別用傳統蟻群算法和改進蟻群算法在起點S到終點T之間規劃出一條合理的路徑。

Fig. 3 Ordinary road network diagram

Fig. 4 Traditional ant colony algorithm in network planning

Fig. 5 Improved ant colony algorithm in network planning

在圖4和圖5紅色加粗路徑代表規劃的路徑，由于邊(2,3)+邊（2,6）>邊(3,6),所以兩種方法中改進的蟻群算法具有更加優越的性質。

3 實驗仿真及結果分析

由于不同的參數設置會對實驗結果產生較大的影響，所以本文在經過對多個參數值進行實驗仿真后選取出比較好的一組參數，對于公式（4）中的參數進行初始化即信息素重要度，啟發式因子重要度，信息素揮發因子，螞蟻的數量，迭代次數c=500。。

步驟一：描繪二維路徑中的障礙物，描述起點和終點，初始化鏈路的端點。從而構建一個MAKLINK圖。

步驟三：使用dijkstra算法產生一條初始化的最優路徑，將其經過的連接線存儲在列表中，并使用公式（6）和（7）來將鏈路分離出多個等分點。

根據上訴步驟編寫了相應的MATLAB程序進行仿真，改進的蟻群算法和原始的蟻群算法得到的路徑如圖6所示，其中紅色的線代表的是傳統蟻群算法規劃的路徑，藍色的線代表了改進的蟻群算法。傳統的蟻群算法得到的路徑長度為212km，改進的蟻群算法得到的規劃路徑長度為109km，反映了改進的蟻群算法能夠找到更優的路徑。圖7為兩種蟻群算法的迭代次數和路徑總長度的示意圖，從該圖中可以看出改進的蟻群算法能夠更加快速的找到一條更優的全局規劃路徑而且在迭代中更加穩定。以上證明了改進的蟻群算法的有效性。

Fig. 6 Two kinds of ant colony algorithm contrast figure on planning path

Fig. 7 Two kinds of ant colony algorithm contrast figure on total length of path and iteration

圖7 兩種蟻群算法的迭代次數和路徑總長度

4 結論

本文通過應用改進的啟發因子提出了一種改進的蟻群算法，更好的解決了傳統蟻群算法在解決最短路徑規劃中改進的蟻群算法收斂速度慢、易限于局部最優解等問題。通過MAKLINK圖論建模和MATLAB仿真可知較傳統的蟻群算法該方法能夠更好的解決全局路徑規劃問題。

雖然該算法在此環境下有較好的應用，但本文的建模環境比較單一，只有障礙物的阻礙，在實際應用中會有各種因素來影響路徑的規劃，這時要考慮到多種因素，這也是作者以后要研究要考慮的問題。

[1] 黃磊. 基于神經網絡的移動機器人路徑規劃研究[D]. 武漢理工大學, 2008

[2] 于振中, 閆繼宏, 趙杰. 改進人工勢場法的移動機器人路徑規劃[J]. 哈爾濱工業大學學報, 2010(01): 50-55.

[3] 金純, 王升剛, 尹遠陽. 礦井中多機器人搜救系統路徑規劃[J]. 機床與液壓, 2014, 42(15): 10-14.

[4] Rong Wang, Hong Jiang. Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm [J]. Advances in Pure Mathematics, 2015(5): 571-578.

[5] 張琦, 馬家辰, 謝瑋. 基于改進蟻群算法的移動機器人路徑規劃[J].東北大學學報( 自然科學版), 2013, 34(11): 1521-1524.

[6] Dorigo, M. and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem”, IEEE Transaction on Evolutionary Computation, Vol.1, No1. pp 53-66, 1997.

[7] 史峰, 王輝, 郁磊等.MATLAB智能算法30個案例分析[M].北京：北京航天航空大學出版社, 2011, 7.

[8] 王云飛. 基于蟻群算法的武警巡邏路徑優化問題研究[D]. 國防科學技術大學, 2014.

Research and Simulate of Global Path Planning Based on Improved Ant Colony Algorithm

YAN Zijun, WU Mingfen*

(College of Computer Science , Wuyi University, Jiangmen，529020)

Path planning is to find a proper path from a given starting point to the end point in a work environment with obstacles, and it makes the object in motion process safety without touching obstacles. At present, there are many kinds of algorithm to solve the issue of path planning. In this paper, we focus on the shortage of traditional Ant Colony algorithm, causing issues of premature and search stalled. When it is applied to solve the problem of robot path planning, an improved Ant Colony algorithm has been put forward, and the improved algorithm set global optimization as original intention. By introducing the end point effect on the stimulating factor, we rebuild the stimulating factor function under the joint of adjacent point and end point, and through this method we can deal with the matters that traditional algorithm brings effectively. As the result, we use MAKLINK to build a two-dimensional space model, and use the MATLAB as a coding tool to simulate the traditional ant colony algorithm and the improved ant colony algorithm in path planning. The result shows that the improved Ant Colony algorithm has better performance.

global path planning; Ant Colony algorithm; stimulating factor function; MAKLINK graph theory

10.19551/j.cnki.issn1672-9129.2017.01.02

TP391.9

A

1672-9129(2017)01-0006-04

2017-02-01；

2017-02-10。

國家自然科學基金(11271040，11361027)；廣東省教育廳重大項目(2014KZDXM055)；廣東省科技廳項目(2016A070708002，2015A070706001，2014A070708005)資助。

吳明芬，廣東省江門市五邑大學計算機學院(529020)，E-mail：mfwu@sina.com