改進(jìn)的蟻群算法在路徑規(guī)劃問題中的應(yīng)用 ①

代婷婷, 劉 秀, 虎亞楠

(昭通學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,云南 昭通 657000)

0 引 言

路徑規(guī)劃在眾多領(lǐng)域都得到成功的應(yīng)用，常見的包括自主移動消毒、無人機物流配送、類似資源管理和配置問題、通信技術(shù)領(lǐng)域的路由問題等[1-2].事實上，只要能夠拓?fù)錇辄c與線組成的結(jié)構(gòu)形式，且以此結(jié)構(gòu)規(guī)劃的問題都可以通過路徑規(guī)劃的思想進(jìn)行求解[3].因此，研究解決路徑規(guī)劃問題的智能算法是一個熱點問題.蟻群算法在智能算法是比較常用的一種方法，雖然在收斂速度等方面有不足和局限，但是它具有的正反饋性、強魯棒性、并行性等優(yōu)點在機器人路徑規(guī)劃的問題中有優(yōu)勢，并且很多學(xué)者已驗證了蟻群算法在尋找最優(yōu)路徑方面具有較高的速度[4].鑒于此，通過將文獻(xiàn)[5][6]中的改進(jìn)蟻群算法巧妙地柔和得出了另外一種新的改進(jìn)蟻群算法，并且將此方法應(yīng)用于解決機器人路徑規(guī)劃問題得到了很好的效果.

1 相關(guān)理論

1.1 基本蟻群算法

在1992年，作為一種智能優(yōu)化算法的蟻群算法第一次被Marco Dorigo[7-8]在他的博士論文中提出來，其在他的論文中詳細(xì)闡述了這種根據(jù)自然界中螞蟻的搜索食物的路徑行為模擬的進(jìn)化算法的思想和原理，具體模型如下：

設(shè)i為外出覓食螞蟻的出發(fā)點，則其到達(dá)覓食終點j的隨機行進(jìn)概率可表為：

pijk(t)=

(1)

其中，pijk(t)表示螞蟻k從節(jié)點i到節(jié)點j的轉(zhuǎn)移概率；α表示在覓食的路徑上用于刺激后來螞蟻的誘發(fā)因子;β為啟發(fā)式信息對螞蟻行進(jìn)方向的期望誘發(fā)因子；allowedk表示螞蟻在覓食路徑中尚未訪問的節(jié)點集合；將已經(jīng)訪問的節(jié)點集合放如tabuk中.公式(1)表明:蟻覓食過程中很容易被選到的那條是具有較高的信息素濃度并且距離螞蟻很近.每一次每一只螞蟻經(jīng)過某一條路徑后都會馬上按照(2)式和(3)式更新該路徑上的信息素[9].

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

其中，ρ表示隨著時間的變化信息素?fù)]發(fā)的變量；那么1-ρ當(dāng)然表示揮發(fā)后留下來的信息素變量；m表示螞蟻的數(shù)量；Δτij(t)表示節(jié)點i到節(jié)點j的信息素在時間t范圍內(nèi)的變化量大??；Δτijk(t)表示第k只螞蟻從節(jié)點i到j(luò)行走過程中在時間t內(nèi)釋放的信息多少.

1.2 路徑規(guī)劃問題的環(huán)境建模方法

針對機器人的路徑規(guī)劃問題，需要對機器人所處的環(huán)境模擬建模，這樣才可以更方便的研究其路徑的規(guī)劃問題.柵格法環(huán)境建模是一種簡便常見的方法,首先規(guī)定機器人的柵格坐標(biāo)由中心點表示，然后采用坐標(biāo)法和序號法對每一個柵格進(jìn)行標(biāo)記和編號;其次，使用白色表示安全區(qū)域，用彩色表示障礙區(qū)域，這是柵格都具有的屬性.除去曾經(jīng)走過的柵格，機器人可以向安全區(qū)域的任意方向行走[10].

2 改進(jìn)蟻群算法的形成及流程圖

基于普通蟻群算法的原理分析以及結(jié)合相關(guān)參考文獻(xiàn)中方法的分析，發(fā)現(xiàn)不但節(jié)點之間的概率轉(zhuǎn)移能影響最短路徑的計算結(jié)果，而且行走路徑上的信息素濃度的更新對最短路徑的影響也較為明顯.因此將文獻(xiàn)[5]的啟發(fā)函數(shù)改進(jìn)和文獻(xiàn)[6]提出的信息素濃度更新的方案結(jié)合起來構(gòu)成另外一種改進(jìn)蟻群算法.對啟發(fā)函數(shù)進(jìn)行變形，把與最終節(jié)點的距離加入其中，與此同時增加或減少在信息素更新時找到的最優(yōu)和最差解信息素濃度，兩種改變同時進(jìn)行可以提高算法的性能.具體的算法流程如圖1所示：

圖1 改進(jìn)的蟻群算法路程圖

3 實證分析

為驗證改進(jìn)蟻群算法的效果，選用MATLAB2019進(jìn)行仿真實驗，主要的做法是讓機器人處在文獻(xiàn)[5]中的柵格障礙環(huán)境中，讓機器人在該環(huán)境中尋找無碰撞的最短路徑，對于這樣的問題分別使用基本的蟻群算法和改進(jìn)的蟻群算法測試.在實驗的過程中設(shè)定機器人工作的目的是找到一條從起點到終點的沒有碰撞的最短路徑.比較使用兩種算法使機器人在這個尋找最短路徑的過程中，找到最優(yōu)路徑用時最短的方法.通過MATLAB的仿真實驗，圖2、圖3分別表示兩種算法的實驗結(jié)果.

圖2 20×20柵格最優(yōu)路徑

由實驗結(jié)果的圖2可知道基本群算法和改進(jìn)的蟻群算法都尋找到了長度是29.21的最優(yōu)路徑，即兩種算法找到的最優(yōu)路徑相同.盡管兩種算法得到的最優(yōu)路徑是一樣的，然而從實驗結(jié)果的圖3可以看出，這兩種算法所使用的時間是完全不同的，顯然普通的蟻群算法找到最優(yōu)路徑需要18次迭代，而改進(jìn)的蟻群算法用不了那么久的時間，當(dāng)?shù)降谌蔚臅r候就已經(jīng)找到了最優(yōu)路徑.這說明改進(jìn)的蟻群算法收斂速度很快，它的搜索效率較基本蟻群算法有很大的提升，可以在最短時間內(nèi)搜索到最優(yōu)解.

4 結(jié) 論

蟻群算法作為常用的智能優(yōu)化算法，除了最早的在旅行商問題上的應(yīng)用之外，還有很多的其他的優(yōu)化應(yīng)用，尤其是在處理路徑規(guī)劃問題上，此方法的應(yīng)用非常的普遍.因此，通過查閱相關(guān)的資料文獻(xiàn)，本文首先對普通蟻群算法的原理進(jìn)行了詳細(xì)介紹分析了，然后將文獻(xiàn)[5]中改進(jìn)的啟發(fā)因子和文獻(xiàn)[6]中改進(jìn)的信息素更新融合在一起，產(chǎn)生了一種新的改進(jìn)蟻群算法，對形成的新的蟻群算法的具體步驟進(jìn)行了闡述，為了更好地直觀的看出改進(jìn)遺傳算法的優(yōu)勢，選用柵格法對機器人的路徑環(huán)境進(jìn)行模擬建模，建立了20×20柵格障礙環(huán)境，讓機器人在此環(huán)境中找到從起點到終點的一條無碰撞的最短路徑，用MATLAB2019對改進(jìn)蟻群算法和基本的蟻群算法進(jìn)行仿真測試實驗，實驗仿真的結(jié)果表明，雖然改進(jìn)蟻群算法和基本的蟻群算法找到的最優(yōu)路徑相同，長度都是29.21,但是改進(jìn)的蟻群算法比基本蟻群算法能在更短的時間內(nèi)找到最優(yōu)路徑.說明了本文的算法不但可行，而且搜索效率較高.