基于改進(jìn)蟻群算法快速求解迷宮路徑問題研究

楊樂 向鳳紅 毛劍琳

摘要：針對傳統(tǒng)蟻群算法收斂速度慢、搜索時(shí)間長、易陷入局部最優(yōu)等缺點(diǎn)，在其基礎(chǔ)上重新定義信息素更新方式。在搜索路徑上進(jìn)行選擇優(yōu)化處理，對搜索出的最短路徑做平滑優(yōu)化處理，使其能快速有效地搜索出最優(yōu)路徑。在解決迷宮路徑問題上對傳統(tǒng)蟻群算法進(jìn)行了改進(jìn)。仿真實(shí)驗(yàn)對比表明，改進(jìn)后的蟻群算法在求解時(shí)間和距離上都遠(yuǎn)優(yōu)于傳統(tǒng)蟻群算法，能快速有效地求得問題的最優(yōu)解，使解決二維路徑問題得到進(jìn)一步優(yōu)化。

關(guān)鍵詞：蟻群算法；迷宮；路徑優(yōu)化

DOI：10.11907/rjdk.173093

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2018）007-0108-03

Abstract：Inthispapertosolvethemazeroutingproblemofthetraditionalantcolonyalgorithmisimproved，thetraditionalantcolonyalgorithmslowconvergencerateandlongsearchtime，easytofallintolocaloptima，onthebasisofredefiningthepheromoneupdatemethods，theselectionandoptimizationofprocessinginthesearchpath，smoothingoptimizationoftheshortestpathsearch，whichcanquicklyandeffectivelysearchtheoptimalpath.Throughsimulationexperiments，theimprovedantcolonyalgorithmisfarbetterthanthetraditionalantcolonyalgorithminsolvingtheoptimaltimeanddistance，theimprovedantcolonyalgorithmcanobtainmorefastandefficientsolution，afurtheroptimizationinsolvingtheproblemoftwo-dimensionalpath.Toovercomethetraditionalantcolonyalgorithm′sdefaultsofslowconvergencerate，longresearchtimeandgreattendencytolimmittolocaloptimalsolution，weredifinethepheromoneupdatemethod.Thesearchpathisselectivelyoptimizedandtheshortestpathissmoothedtosearchtheoptimalpathquicklyandefficiently.Thetraditionalantcolonyalgorithmonsolvingmazepathisimproved.Thesimulationexperimentsshowthattheimprovedalgorithmcanobtainfasterandmoreeffiecientsolutionsothatthesolutionfortwo-dimensionalpathisoptimized.

KeyWords：antcolonyalgorithm；maze；pathoptimization

0引言

迷宮問題是數(shù)據(jù)圖形領(lǐng)域的經(jīng)典問題[1]。迷宮指道路環(huán)境復(fù)雜，從入口進(jìn)入之后很難找到出口的建筑物[2-3]。迷宮最優(yōu)路徑指從入口到出口距離最短的一條路徑[4]。傳統(tǒng)的蟻群算法搜索迷宮最優(yōu)路徑時(shí)，需要很長的搜索時(shí)間用來生成和更新信息素，輔助螞蟻快速找到終點(diǎn)位置，然而求解速度和所需要的算法空間會隨著迷宮環(huán)境復(fù)雜度的增大而不斷增加[5-6]。文獻(xiàn)[7]對二維空間進(jìn)行環(huán)境建模，采用蟻群算法對機(jī)器人進(jìn)行全局二位路徑搜索；文獻(xiàn)[8]引入一種變異算子，在搜索設(shè)計(jì)和信息素更新方式上進(jìn)行改變，引入逆轉(zhuǎn)變異和插入變異算子，對傳統(tǒng)蟻群算法進(jìn)行了局部優(yōu)化改良；文獻(xiàn)[9]引入精英策略，加入遺傳算法中的排序概念，重新定義一種信息素更新方式，有效改善了蟻群算法求解速度慢的問題，增加了蟻群算法的求解速度和精確度；文獻(xiàn)[10]加入遺傳算法思想，在求解路徑問題上設(shè)計(jì)編碼、適應(yīng)值函數(shù)、遺傳操作，優(yōu)化演化過程中的基因，提高搜索速度，快速解決了二維路徑問題；文獻(xiàn)[11]在蟻群算法中加入了平滑因子，平滑蟻群算法能避開障礙物，有效降低路徑長度，增大了轉(zhuǎn)折角度，路經(jīng)規(guī)劃結(jié)果優(yōu)于傳統(tǒng)蟻群算法。

本文借鑒已有文獻(xiàn)算法，針對提高路徑搜索時(shí)間與減少路徑距離進(jìn)行了研究。對傳統(tǒng)蟻群算法進(jìn)行了改進(jìn)，在時(shí)間復(fù)雜度以及路徑距離上進(jìn)行了改進(jìn)，在解決迷宮路徑問題上取得了很好的結(jié)果。

1蟻群算法及改進(jìn)思想

蟻群算法（AntColonyAlgorithm，ACA）是由意大利學(xué)者M(jìn).Dorigo等[12]于20世紀(jì)90年代提出的一種新的模擬算法，真實(shí)模擬了自然界螞蟻群體的覓食行為，應(yīng)用于交通、通信、化工、電力等領(lǐng)域，成功解決了許多組合優(yōu)化問題[13]。

傳統(tǒng)求解迷宮路徑問題算法一般采用廣度優(yōu)先搜索或深度優(yōu)先搜索，對求得的全部路徑進(jìn)行比較從而得到最優(yōu)路徑，該算法缺點(diǎn)是搜索效率低。隨著人工智能算法研究的不斷深入，涌現(xiàn)出仿生智能算法如遺傳算法、蟻群算法等，相對于傳統(tǒng)算法，在搜索效率上有了很大提高，但結(jié)果往往近似于最優(yōu)解而非最優(yōu)解。

本文對蟻群算法作了改進(jìn)，在螞蟻路徑搜索過程做了幾點(diǎn)調(diào)整：

（1）本文基于柵格環(huán)境求解最優(yōu)路徑。當(dāng)螞蟻所在位置有多條路徑可搜索時(shí)，設(shè)螞蟻當(dāng)前位置為普通節(jié)點(diǎn)。當(dāng)只有一條路徑可以搜索時(shí)，就當(dāng)前螞蟻位置進(jìn)行顏色標(biāo)記。當(dāng)螞蟻所在位置搜索到的路徑是封閉的、只能原路返回時(shí)，設(shè)置當(dāng)前螞蟻釋放的信息激素為零并反饋所處節(jié)點(diǎn)信息素為零，直到返回到的節(jié)點(diǎn)為普通節(jié)點(diǎn)后再進(jìn)行下一節(jié)點(diǎn)搜索。這樣螞蟻在下一輪搜索中就不會選擇這條信息素幾乎為零的道路，大大縮短了螞蟻搜索的時(shí)間，提高了算法運(yùn)行效率。

（2）在信息素更新方式上采取局部更新和全局動態(tài)更新相結(jié)合。當(dāng)搜索出一條沒有比其更短的路徑時(shí)，螞蟻會不斷增強(qiáng)該路徑信息素，從而忽視沒有涉及到的節(jié)點(diǎn)。隨著時(shí)間的積累，很容易導(dǎo)致搜索出的路徑不是最優(yōu)解。本文在信息素更新基礎(chǔ)上，改變了原有的更新原則：當(dāng)螞蟻經(jīng)過該路徑時(shí)適當(dāng)降低該路徑信息素濃度，增加選擇其它更優(yōu)路徑的概率，從而進(jìn)行比對，有利于搜索出最優(yōu)路徑。

（3）對得到的最優(yōu)路徑進(jìn)行優(yōu)化處理。搜索結(jié)束得到一條完整的路徑后，在迷宮中一定會有很多轉(zhuǎn)折次數(shù)，并且轉(zhuǎn)折角度有大有小，對路徑有很大影響。對這些轉(zhuǎn)角作平滑處理，增大轉(zhuǎn)角度數(shù)降低轉(zhuǎn)角次數(shù)以有效降低路徑長度，從而使路徑盡可能顯得平滑，達(dá)到縮短起點(diǎn)到終點(diǎn)距離的目的。

2迷宮建模

主要利用柵格環(huán)境求解最優(yōu)路徑，根據(jù)實(shí)際需要構(gòu)造不同復(fù)雜程度的二維地形圖。如圖1所示，用MATLAB構(gòu)造一個(gè)四進(jìn)四出的二維迷宮地形圖，起點(diǎn)終點(diǎn)可以設(shè)置，其中黑色柵格相當(dāng)于障礙物，迷宮中的圍墻表示不可以通過，白色柵格相當(dāng)于道路表示可行走通過。要求在移動時(shí)只能向周圍白色柵格移動一步，在此基礎(chǔ)上求解出最優(yōu)路徑。

3算法設(shè)計(jì)及流程

基于改進(jìn)蟻群搜索算法流程如下：①初始化參數(shù)，根據(jù)迷宮規(guī)模大小、復(fù)雜程度進(jìn)行抽象環(huán)境建模，確定入口起點(diǎn)、出口終點(diǎn)位置，將所有的螞蟻置于起點(diǎn)；②計(jì)算各可行節(jié)點(diǎn)的啟發(fā)函數(shù)，啟發(fā)函數(shù)值是下一節(jié)點(diǎn)到終點(diǎn)距離的倒數(shù)，采用輪盤賭法選擇下一可行節(jié)點(diǎn)；③當(dāng)螞蟻k移動到下一節(jié)點(diǎn)時(shí)，根據(jù)公式對當(dāng)前節(jié)點(diǎn)進(jìn)行局部信息素更新；④當(dāng)判斷螞蟻進(jìn)入死胡同需要原路返回時(shí)，設(shè)置當(dāng)前節(jié)點(diǎn)信息素為零，并設(shè)置返回節(jié)點(diǎn)中的信息素也為零，直至返回到普通節(jié)點(diǎn)；⑤判斷是否所有螞蟻均到達(dá)終點(diǎn)，若是則進(jìn)行全局信息素更新，若否則返回步驟②繼續(xù)尋優(yōu)；⑥判斷是否達(dá)到最大迭代次數(shù)，若否則轉(zhuǎn)向步驟②繼續(xù)尋優(yōu)，如是則輸出當(dāng)前群體中最短路徑，即求解的最優(yōu)路徑；⑦對搜索求解出來的路徑進(jìn)行最后的優(yōu)化處理。

3.1信息素更新

信息素更新是整個(gè)蟻群算法中最重要的一環(huán)，關(guān)系到能否成功求得最優(yōu)路徑。螞蟻是依靠信息素濃度大小選擇下一節(jié)點(diǎn)的，所以信息素初始化及更新方法在蟻群算法中有著非常重要的意義，改進(jìn)信息素的更新方式也是改進(jìn)蟻群算法的最佳方式。對迷宮的環(huán)境進(jìn)行柵格建模，將整個(gè)搜索空間離散為二維空間上的點(diǎn)，這些點(diǎn)就是蟻群搜索路徑中需要搜索的節(jié)點(diǎn)。因此，每個(gè)點(diǎn)都會對應(yīng)一個(gè)信息素值，用來吸引螞蟻。信息素濃度越高，經(jīng)過該點(diǎn)的可能性越大，每個(gè)點(diǎn)在螞蟻經(jīng)過之后信息素的值都會實(shí)時(shí)更新。

信息素更新采用局部更新和全局更新相結(jié)合，局部更新信息素添加衰減系數(shù)，該點(diǎn)的信息素大小會隨著螞蟻的經(jīng)過而減小，局部更新的目的是通過減小已經(jīng)過點(diǎn)的信息素值增加螞蟻未經(jīng)過點(diǎn)的搜索概率，從而達(dá)到全局搜索目的。信息素更新公式為：

全局更新指所有螞蟻完成從起點(diǎn)到終點(diǎn)的路徑搜索時(shí)，以每只螞蟻搜索路徑的長度作為評價(jià)值進(jìn)行比對，選出最短路徑。路徑越短，該路徑上點(diǎn)的信息素值增加越大。信息素更新公式如下：

3.2群搜索策略

螞蟻在當(dāng)前點(diǎn)選擇下一個(gè)點(diǎn)步驟如下：

（1）根據(jù)該點(diǎn)周圍環(huán)境確定下一節(jié)點(diǎn)的可行點(diǎn)集合。

（2）根據(jù)啟發(fā)函數(shù)公式依次計(jì)算該點(diǎn)到下一節(jié)點(diǎn)內(nèi)可行點(diǎn)集合的啟發(fā)函數(shù)值H（t），啟發(fā)函數(shù)值大小表示下一節(jié)點(diǎn)到達(dá)終點(diǎn)距離的遠(yuǎn)近，有助于快速尋找到最優(yōu)點(diǎn)。

（3）計(jì)算在可行節(jié)點(diǎn)內(nèi)任一點(diǎn)的選擇概率P：

（4）根據(jù)各點(diǎn)的選擇概率采用輪盤賭法選擇下一節(jié)點(diǎn)。

4實(shí)驗(yàn)仿真

分別采用傳統(tǒng)蟻群算法和改進(jìn)蟻群算法在跨度為17×17的正方形迷宮中搜索出一條從入口到出口的最佳路徑。路徑規(guī)劃起點(diǎn)坐標(biāo)為（0.5，17），終點(diǎn)坐標(biāo)為（17，0.5），同時(shí)也可以任意設(shè)置其它入口與出口坐標(biāo)，如圖2所示。

4.1仿真結(jié)果

分別采用傳統(tǒng)蟻群算法和改進(jìn)后的蟻群算法進(jìn)行迷宮從入口到出口的路徑搜索，得出的路徑規(guī)劃結(jié)果和最優(yōu)個(gè)體適應(yīng)度變化如圖3、圖4、圖5、圖6所示。

4.2數(shù)據(jù)結(jié)果對比

實(shí)驗(yàn)結(jié)果對比見表1。

5結(jié)語

本文改進(jìn)蟻群算法能夠快速搜索出一條從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，與傳統(tǒng)蟻群算法相比，在運(yùn)行時(shí)間、最短距離、迭代次數(shù)、轉(zhuǎn)折角度及平滑度上都有很大改進(jìn)。實(shí)驗(yàn)仿真結(jié)果證明，改進(jìn)后的蟻群算法能快速解決二維路徑問題，優(yōu)于傳統(tǒng)的蟻群算法，能快速搜索出最優(yōu)路徑。

參考文獻(xiàn)：

[1]徐守江.迷宮問題的路徑優(yōu)化[J].電腦知識與技術(shù)，2009，5（32）：9045-9046.

[2]燕忠.基于蟻群優(yōu)化算法的若干問題的研究[D].南京：東南大學(xué)，2005.

[3]胡小兵，黃席樾.蟻群算法在迷宮最優(yōu)路徑問題中的應(yīng)用[J].計(jì)算機(jī)仿真，2009，22（4）：115-116.

[4]齊勇，魏志強(qiáng)，殷波.增強(qiáng)蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（1）：54-56.

[5]侯文靜，馬永杰.求解TSP的改進(jìn)蟻群算法[J].計(jì)算機(jī)應(yīng)用研究，2010（6）：2087-2089.

[6]孫東秋.基于八方向跟蹤算法的迷宮問題新解[J].計(jì)算機(jī)應(yīng)用與研究，2015，22（4-2）：267-269.

[7]WENZQ，CAIZX.Globalpathplanningapproachbasedonantcolonyoptimizationalgorithm[EB/OL].http：//www.docin.com/p-1358599085.html.

[8]李向軍，霍艷麗，曾勍煒，等.基于機(jī)器人路徑規(guī)劃的一種變異算子蟻群算法[J].計(jì)算機(jī)仿真，2015，32（2）：364-369.

[9]張家善，王志宏，陳應(yīng)顯.一種基于精英策略的改進(jìn)蟻群算法及應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21（10）：105-108.

[10]石鐵峰.改進(jìn)遺傳算法在移動機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)仿真，2011，2（28）：193-196.

[11]王紅軍，徐軍，趙輝，等.基于平滑蟻群算法的機(jī)器人路徑規(guī)劃[J].燕山大學(xué)學(xué)報(bào)，2017，41（3）：278-282.

[12]丁建立，陳增強(qiáng).基于混合螞蟻算法的網(wǎng)絡(luò)資源均衡與優(yōu)化[J].儀器儀表學(xué)報(bào)，2013，2（32）：592-594.

[13]柴寅.融合柵格法與改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[D].武漢：武漢科技大學(xué)，2016.

[14]LIUJP，XUSH，ZHANGFH，etal.Ahybridgenetic-antcolonyoptimizationalgorithmfortheoptimalpathselection[C].beijing：ResearchcenterofGovermentGIS，2016.

[15]張賢.基于超聲波測距的多機(jī)器人室內(nèi)定位導(dǎo)航研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2015.

（責(zé)任編輯：杜能鋼）