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

楊樂 向鳳紅 毛劍琳

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

關鍵詞：蟻群算法；迷宮；路徑優化

DOI：10.11907/rjdk.173093

中圖分類號：TP312

文獻標識碼：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引言

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

本文借鑒已有文獻算法，針對提高路徑搜索時間與減少路徑距離進行了研究。對傳統蟻群算法進行了改進，在時間復雜度以及路徑距離上進行了改進，在解決迷宮路徑問題上取得了很好的結果。

1蟻群算法及改進思想

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

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

本文對蟻群算法作了改進，在螞蟻路徑搜索過程做了幾點調整：

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

（2）在信息素更新方式上采取局部更新和全局動態更新相結合。當搜索出一條沒有比其更短的路徑時，螞蟻會不斷增強該路徑信息素，從而忽視沒有涉及到的節點。隨著時間的積累，很容易導致搜索出的路徑不是最優解。本文在信息素更新基礎上，改變了原有的更新原則：當螞蟻經過該路徑時適當降低該路徑信息素濃度，增加選擇其它更優路徑的概率，從而進行比對，有利于搜索出最優路徑。

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

2迷宮建模

主要利用柵格環境求解最優路徑，根據實際需要構造不同復雜程度的二維地形圖。如圖1所示，用MATLAB構造一個四進四出的二維迷宮地形圖，起點終點可以設置，其中黑色柵格相當于障礙物，迷宮中的圍墻表示不可以通過，白色柵格相當于道路表示可行走通過。要求在移動時只能向周圍白色柵格移動一步，在此基礎上求解出最優路徑。

3算法設計及流程

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

3.1信息素更新

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

信息素更新采用局部更新和全局更新相結合，局部更新信息素添加衰減系數，該點的信息素大小會隨著螞蟻的經過而減小，局部更新的目的是通過減小已經過點的信息素值增加螞蟻未經過點的搜索概率，從而達到全局搜索目的。信息素更新公式為：

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

3.2群搜索策略

螞蟻在當前點選擇下一個點步驟如下：

（1）根據該點周圍環境確定下一節點的可行點集合。

（2）根據啟發函數公式依次計算該點到下一節點內可行點集合的啟發函數值H（t），啟發函數值大小表示下一節點到達終點距離的遠近，有助于快速尋找到最優點。

（3）計算在可行節點內任一點的選擇概率P：

（4）根據各點的選擇概率采用輪盤賭法選擇下一節點。

4實驗仿真

分別采用傳統蟻群算法和改進蟻群算法在跨度為17×17的正方形迷宮中搜索出一條從入口到出口的最佳路徑。路徑規劃起點坐標為（0.5，17），終點坐標為（17，0.5），同時也可以任意設置其它入口與出口坐標，如圖2所示。

4.1仿真結果

分別采用傳統蟻群算法和改進后的蟻群算法進行迷宮從入口到出口的路徑搜索，得出的路徑規劃結果和最優個體適應度變化如圖3、圖4、圖5、圖6所示。

4.2數據結果對比

實驗結果對比見表1。

5結語

本文改進蟻群算法能夠快速搜索出一條從起點到終點的最優路徑，與傳統蟻群算法相比，在運行時間、最短距離、迭代次數、轉折角度及平滑度上都有很大改進。實驗仿真結果證明，改進后的蟻群算法能快速解決二維路徑問題，優于傳統的蟻群算法，能快速搜索出最優路徑。

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

[12]丁建立，陳增強.基于混合螞蟻算法的網絡資源均衡與優化[J].儀器儀表學報，2013，2（32）：592-594.

[13]柴寅.融合柵格法與改進蟻群算法的機器人路徑規劃[D].武漢：武漢科技大學，2016.

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

[15]張賢.基于超聲波測距的多機器人室內定位導航研究[D].哈爾濱：哈爾濱工業大學，2015.

（責任編輯：杜能鋼）