基于改進(jìn)蟻群算法的全局路徑規(guī)劃研究與仿真

燕紫君，吳明芬*

?

基于改進(jìn)蟻群算法的全局路徑規(guī)劃研究與仿真

燕紫君，吳明芬*

(五邑大學(xué)計(jì)算機(jī)學(xué)院 江門(mén) 529020）

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

全局路徑規(guī)劃；蟻群算法；啟發(fā)因子；MAKLINK圖論理論

引言

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

1 傳統(tǒng)的蟻群算法

蟻群算法是一種模擬螞蟻搜索食物的算法，它于90年代由M.Dorigo[6]等人提出，該算法一經(jīng)提出便成為了智能領(lǐng)域一種主要的算法。該算法在解決優(yōu)化問(wèn)題的基本步驟是：螞蟻行走路徑被看作問(wèn)題的可行優(yōu)化路徑，整個(gè)螞蟻所在的路徑構(gòu)成了解空間的優(yōu)化問(wèn)題。釋放的信息素在短路徑會(huì)超過(guò)其它路徑，隨著時(shí)間的推移，更多的螞蟻會(huì)選擇這些較短的路徑。最終螞蟻在積極的反饋?zhàn)饔孟聦?zhuān)注于最好的路徑。

在t時(shí)刻，螞蟻k從節(jié)點(diǎn)i選擇下一個(gè)要走的節(jié)點(diǎn)j必須要依據(jù)概率轉(zhuǎn)換公式，如公式（1）、公式（2）和公式（3）所示

（2）

（3）

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

2 改進(jìn)的蟻群算法

由于在解決機(jī)器人全局路徑規(guī)劃時(shí)傳統(tǒng)的蟻群算法存在收斂于局部次優(yōu)解而導(dǎo)致搜索的過(guò)早停滯問(wèn)題，為了克服在全局路徑規(guī)劃中蟻群算法中存在的這些的問(wèn)題，下面提出了一種改進(jìn)的蟻群算法。

2.1 環(huán)境建模

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

Fig. 1 The two-dimension MIKLINK model

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

2.2 蟻群算法的改進(jìn)

下面使用全局式啟發(fā)因子示意圖來(lái)更詳細(xì)的對(duì)此改進(jìn)的公式進(jìn)行描述，如圖2所示，在最短路徑規(guī)劃中已經(jīng)得知了起點(diǎn)和終點(diǎn)，所以目標(biāo)就是在起點(diǎn)和終點(diǎn)之間找一條最短路徑。所以當(dāng)螞蟻選擇下一個(gè)城市時(shí)，如果是基于傳統(tǒng)蟻群算法，會(huì)傾向于選擇節(jié)點(diǎn)，但改進(jìn)的蟻群算法會(huì)從全局考慮，更傾向于選擇節(jié)點(diǎn)。由兩點(diǎn)之間線段最短可知改進(jìn)的啟發(fā)因子函數(shù)中引入了可以得到更短的規(guī)劃路徑。由于兩邊之和大于第三邊，所以改進(jìn)以后的啟發(fā)因子函數(shù)，更加考慮全局，可以從一定程度上避免局部最優(yōu)解。

Fig. 2 The stimulating factor function .

為了說(shuō)明該改進(jìn)的有效性，舉個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明。如圖3表示一個(gè)普通路網(wǎng)圖，要分別用傳統(tǒng)蟻群算法和改進(jìn)蟻群算法在起點(diǎn)S到終點(diǎn)T之間規(guī)劃出一條合理的路徑。

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紅色加粗路徑代表規(guī)劃的路徑，由于邊(2,3)+邊（2,6）>邊(3,6),所以兩種方法中改進(jìn)的蟻群算法具有更加優(yōu)越的性質(zhì)。

3 實(shí)驗(yàn)仿真及結(jié)果分析

由于不同的參數(shù)設(shè)置會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生較大的影響，所以本文在經(jīng)過(guò)對(duì)多個(gè)參數(shù)值進(jìn)行實(shí)驗(yàn)仿真后選取出比較好的一組參數(shù)，對(duì)于公式（4）中的參數(shù)進(jìn)行初始化即信息素重要度，啟發(fā)式因子重要度，信息素?fù)]發(fā)因子，螞蟻的數(shù)量，迭代次數(shù)c=500。。

步驟一：描繪二維路徑中的障礙物，描述起點(diǎn)和終點(diǎn)，初始化鏈路的端點(diǎn)。從而構(gòu)建一個(gè)MAKLINK圖。

步驟三：使用dijkstra算法產(chǎn)生一條初始化的最優(yōu)路徑，將其經(jīng)過(guò)的連接線存儲(chǔ)在列表中，并使用公式（6）和（7）來(lái)將鏈路分離出多個(gè)等分點(diǎn)。

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

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 兩種蟻群算法的迭代次數(shù)和路徑總長(zhǎng)度

4 結(jié)論

本文通過(guò)應(yīng)用改進(jìn)的啟發(fā)因子提出了一種改進(jìn)的蟻群算法，更好的解決了傳統(tǒng)蟻群算法在解決最短路徑規(guī)劃中改進(jìn)的蟻群算法收斂速度慢、易限于局部最優(yōu)解等問(wèn)題。通過(guò)MAKLINK圖論建模和MATLAB仿真可知較傳統(tǒng)的蟻群算法該方法能夠更好的解決全局路徑規(guī)劃問(wèn)題。

雖然該算法在此環(huán)境下有較好的應(yīng)用，但本文的建模環(huán)境比較單一，只有障礙物的阻礙，在實(shí)際應(yīng)用中會(huì)有各種因素來(lái)影響路徑的規(guī)劃，這時(shí)要考慮到多種因素，這也是作者以后要研究要考慮的問(wèn)題。

[1] 黃磊. 基于神經(jīng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人路徑規(guī)劃研究[D]. 武漢理工大學(xué), 2008

[2] 于振中, 閆繼宏, 趙杰. 改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2010(01): 50-55.

[3] 金純, 王升剛, 尹遠(yuǎn)陽(yáng). 礦井中多機(jī)器人搜救系統(tǒng)路徑規(guī)劃[J]. 機(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ìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].東北大學(xué)學(xué)報(bào)( 自然科學(xué)版), 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個(gè)案例分析[M].北京：北京航天航空大學(xué)出版社, 2011, 7.

[8] 王云飛. 基于蟻群算法的武警巡邏路徑優(yōu)化問(wèn)題研究[D]. 國(guó)防科學(xué)技術(shù)大學(xué), 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。

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

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