基于改進蟻群算法的無人機路徑規(guī)劃*

陳禮琪

（上海理工大學(xué)光電信息與計算機工程學(xué)院 上海 200093）

1 引言

隨著科學(xué)技術(shù)的發(fā)展，無人機因其可飛行，可探索未知領(lǐng)域等優(yōu)點被廣泛地應(yīng)用。在各個行業(yè)中。但是無人機在飛行過程中也會遇到障礙物，在目標搜尋中，需要避開所在的障礙物，同時需要最短的距離。

目前有很多對于無人機路徑規(guī)劃的智能算法，比如：遺傳算法［1］，粒子群算法［2］，人工勢場算法［3］，蟻群算法［7~16］，免疫算法［4］，混合組搜索優(yōu)化器算法［5］，以及A*算法［6］等。蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法，模擬了一種基于蟻群間協(xié)作的仿生智能優(yōu)化算法。最初是應(yīng)用在TSP 旅行商最優(yōu)路線的規(guī)劃。后來逐漸應(yīng)用在路徑規(guī)劃，可以實現(xiàn)二維以及三維的路徑規(guī)劃。文獻［7］借鑒了狼群分配的原則對蟻群算法進行了優(yōu)化，通過柔和路徑曲線達到減小路徑的目的。文獻［8］在蟻群算法的基礎(chǔ)上增加了智能增益算法，可以有效地跳出局部最優(yōu)，收斂速度明顯加快，但是對于路徑的優(yōu)化并不是很明顯。文獻［9］是在蟻群算法的基礎(chǔ)上提出了一種新型的算法，增加了懲罰策略，改變了蟻群算法的模型。文獻［10］提出雙蟻群算法，同時增加了遺傳算法，定期進行信息交換。文獻［11］提出基于A*算法和蟻群算法結(jié)合的算法。文獻［12］通過路徑代價計算方法，并使用改進的多目標蟻群算法對路徑進行優(yōu)化選擇。文獻［13］是通過一種改進信息素更新規(guī)則的蟻群算法。文獻［14］傳統(tǒng)蟻群算法的局部收斂問題采用全局與局部信息素互補衰減法，來高效完成蟻群算法尋優(yōu)問題。文獻［15］在路徑搜索時引入了一種雙向搜索機制，對選擇方法進行改進。文獻［16］通過調(diào)整信息素揮發(fā)因子大小，提出了一種適用于路徑規(guī)劃的自適應(yīng)蟻群算法。

本文提出一種改進的蟻群算法，在借鑒了文獻［8］的基礎(chǔ)上，增加了轉(zhuǎn)移概率，并對最優(yōu)路徑的信息素增強。最后通過實驗表明，算法能夠搜尋到更短的路徑，而且加快了收斂速度，減少了迭代次數(shù)。

2 基本算法

2.1 柵格法

本文采用柵格法模擬靜態(tài)環(huán)境，作為移動空間模型。在靜態(tài)環(huán)境中，假設(shè)障礙物的大小和位置都是已知的。

在柵格網(wǎng)中，隨機生成一個環(huán)境，其中白色表示可行區(qū)域，黑色表示障礙物。在柵格網(wǎng)規(guī)劃一個起點和終點，然后隨機分布障礙物，無人機運行軌跡必須避開障礙物到達終點，并且尋找出最佳路徑。同時，對柵格網(wǎng)進行坐標點的建立，每一格網(wǎng)格都對應(yīng)一個坐標點。網(wǎng)格的編號從左往右，從下往上都是逐漸增大。假設(shè)小方格的邊長為a，橫坐標一共有X 個方格，縱坐標一共有Y 個方格，i 為方格的編號，我們可以通過下列式子求得每個編號所對應(yīng)的坐標點：

圖1 是無人機可以飛行的八個方向，它的每一步都是從一個網(wǎng)格的中心到另一個相鄰網(wǎng)格的中心，所以無人機飛行時運動的步長為a或者 2a。

圖1 無人機飛行方向

2.2 傳統(tǒng)蟻群算法

蟻群算法一直被用來解決路徑規(guī)劃問題，然而蟻群算法的關(guān)鍵部分是在信息素矩陣的更新。更新的結(jié)果直接導(dǎo)致蟻群算法的最優(yōu)路線。每一代螞蟻行走的路線表示待優(yōu)化的可行解，蟻群行走的所有路徑就構(gòu)成了解空間，在每一代每一只螞蟻行走的時候都會釋放一種信息素。隨著時間的推進，每一代螞蟻走過的相同路徑的信息素就會越來越高，那么就有更大的可能性選擇信息素較高的路徑，從而能找出更優(yōu)路線。

2.3 轉(zhuǎn)移概率

傳統(tǒng)的蟻群算法的轉(zhuǎn)移概率為

上式α表示的是信息素重要程度因子，β表示啟發(fā)函數(shù)重要程度因子，Jk(i)表示第k 只螞蟻從位置i到可行路徑點的集合，τij(t)表示在t 時刻從位置i到j(luò)的信息素，ηij(t)是在t時刻啟發(fā)因子，它的值為t時刻位置i到j(luò)的距離的倒數(shù)：

在現(xiàn)實世界中，隨著時間的推移，螞蟻釋放的信息素會逐漸蒸發(fā)。它有助于螞蟻在選擇的時候能找到更好的路徑。對下一代的螞蟻尋找路徑的時候有著很好的指導(dǎo)作用。信息素的更新公式如下：

式中ρ是信息素揮發(fā)因子，范圍在0~1之間。

Lk表示的是第k 只螞蟻走過的總路程。Q 表示信息素釋放總量。

3 算法改進

3.1 轉(zhuǎn)移概率改進

考慮到為了增加有效螞蟻，盡可能減少螞蟻陷入死區(qū)間，在轉(zhuǎn)移概率上進行了改進，添加了選擇下一個節(jié)點的可行點的分析，可將轉(zhuǎn)移概率公式改進為下列公式：

allowij(t)是螞蟻選擇的下一節(jié)點可行節(jié)點的個數(shù)。具體情況如圖2所示。

圖2 路徑選擇分析

從圖2 中，無人機當面對有死區(qū)的時候，通過下一個節(jié)點的可行節(jié)點的個數(shù)，優(yōu)先選擇可行節(jié)點多的方向。這樣可以避免產(chǎn)生過多的無效螞蟻。

3.2 信息素改進

傳統(tǒng)的蟻群算法在每一代搜索路徑的時候可能會丟失最佳路徑。改進的蟻群算法將每一代的螞蟻最佳路徑與歷史的最佳路徑進行比較，如果當代的最佳路徑比歷史最佳路徑長度更短。則保持當代螞蟻的路徑。否則，將歷史最優(yōu)路徑替換到當代最遠路徑。每條路徑上的信息素可以更改為如下公式：

在第二方面所提出的基于增益算法中，通過消除需要穿越障礙物周圍所有的路徑來獲得能量減少。通過這一原理，可以將信息素更新公式改寫為

在迄今為止找到的最佳路徑上添加新的信息素，通過減少障礙物周圍所有路徑的能量計算，實現(xiàn)更快的尋路。本文利用了標準正態(tài)分布函數(shù)作為信息素的增益，通過下列公式可以得到信息素增益：

其中Xcurrent表示無人機當前的位置，Xdestination表示無人機的終點，Xinitial表示無人機的起點。

增益值呈標準正態(tài)分布函數(shù)，增益可以是正的，也可以是負的，如果增益為正，螞蟻將往目標點的方向移動，如果增益是負的，那么螞蟻將會遠離目標點。當螞蟻到達當前節(jié)點的時候，搜索下一個要訪問的節(jié)點，那么會優(yōu)先選擇離目標點近的節(jié)點作為下一個要訪問的節(jié)點。

圖3 中，A 表示無人機起點，B 為目標點，X1 表示前一個位置節(jié)點，X2 表示無人機當前的節(jié)點。如果X2到B點的歐式距離小于X1到B點的歐式距離，則增益，將與當前信息素數(shù)量增加，否則按照等式中給出的方法減去。

圖3 增益分析圖

3.3 算法流程

1）環(huán)境建模，設(shè)立初始化參數(shù)，設(shè)立初始點和目標點。

2）初始化螞蟻種群。

3）螞蟻從初始點轉(zhuǎn)移，通過生成的轉(zhuǎn)移概率以及輪盤賭法選擇轉(zhuǎn)移的點，同時將上一節(jié)點接入禁忌表中。

4）保存這一代每只螞蟻走的路徑以及總長度。并與歷史最短路徑進行比較，如果當前最短路徑長度大于歷史最短路徑，將歷史最短路徑替換到當代最遠路徑。

5）利用提出改進方法更新信息素。

6）判斷是否達到最大迭代次數(shù)，若達到最大迭代次數(shù)，停止循環(huán)，否則，繼續(xù)循環(huán)。

7）輸出結(jié)果。

4 實驗仿真

4.1 參數(shù)設(shè)定

本實驗在Windows10 系統(tǒng)的Matlab 軟件下不同的環(huán)境進行仿真。設(shè)每條路徑的初始濃度為8，小方格的邊長為1m。迭代次數(shù)為100，種群大小M為50。表1列出了算法的內(nèi)部初始值參數(shù)設(shè)置。

表1 初始參數(shù)設(shè)定

4.2 仿真結(jié)果

本次20*20的簡單環(huán)境和30*30的復(fù)雜環(huán)境是隨機生成的。

4.2.1 測試一

從圖4~圖6可以看出，改進后的算法收斂速度明顯加快，更能尋到更短的路徑，有較好的穩(wěn)定性。

圖4 20*20傳統(tǒng)蟻群算法路徑規(guī)劃圖

圖6 20*20收斂比較

4.2.2 測試二

從圖7~圖9 可以看出，在更為復(fù)雜的環(huán)境下，傳統(tǒng)蟻群算法明顯出現(xiàn)了大量的折回路線，相比之下，改進后的算法能尋到更短的路徑，收斂速度也明顯加快。

圖5 20*20改進蟻群算法路徑規(guī)劃圖

圖7 30*30傳統(tǒng)蟻群算法路徑規(guī)劃圖

圖8 30*30改進蟻群算法路徑規(guī)劃圖

圖9 30*30收斂比較

4.3 數(shù)據(jù)分析

本實驗在隨機選擇轉(zhuǎn)移點時采用的是輪盤賭法，根據(jù)Matlab隨機生成的數(shù)值決定了選擇下一個節(jié)點。因此具有一定的隨機性，為了避免路徑規(guī)劃中存在一定的偶然性，本實驗進行多次實驗，對數(shù)據(jù)取平均值。得到表2和表3。

從表2 和表3 可以看出，本文算法不管在20*20的環(huán)境還是30*30的環(huán)境下，得到的路徑長度都是小于傳統(tǒng)的蟻群算法，而且收斂速度快。本文通過改變轉(zhuǎn)移概率及朝著最優(yōu)方向不斷優(yōu)化信息素的方法，通過仿真實驗可以看出有著明顯的優(yōu)越性。也更能找到最優(yōu)路徑。收斂也更加穩(wěn)定。算法有著一定的提升。

表2 20*20改進算法和傳統(tǒng)算法性能評估

表3 30*30改進算法和傳統(tǒng)算法性能評估

5 結(jié)語

蟻群算法是一種具有正反饋機制的智能算法，主要內(nèi)容包括路徑的構(gòu)建和信息素的更新。本文主要以傳統(tǒng)蟻群算法所存在的缺點提出一種改進的算法。對于轉(zhuǎn)移概率的改進，可以有效避免螞蟻陷入死區(qū)間。再利用增益函數(shù)，對節(jié)點進行距離判斷，來增加或減少當前路徑的信息素。算法再Matlab 中實現(xiàn)，實驗結(jié)果表明改進的算法在路徑收斂速度以及尋找最佳路徑方面表現(xiàn)較好。

但是本文只考慮了靜態(tài)環(huán)境，動態(tài)障礙物并沒有涉及，有著一定的局限性。