基于改進蟻群算法的水下無人機路徑規劃研究

楊海清,蘆 斌

(浙江工業大學 信息工程學院，杭州 310014)

0 引言

隨著現代計算機信息科學的不斷發展,人工智能和海洋大數據的應用領域也在不斷擴大,無人機的最優路徑選擇和規劃成了其重要的組成部分。我國擁有漫長的海岸線和包括內海在內的四百多平方公里的水域,所以水下無人機與海洋的資源開發綜合利用的問題也已經變得越來越亟待解決。水下無人機已經成為了對海洋資源的開發綜合利用的重要技術工具，在面對這種復雜多變的海洋生態環境時,目前的水下無人機在最優路徑規劃上依然是個重要課題，很多算法在路徑規劃上的效果并不令人滿意,很難得到較好的結果[1-2]。

蟻群算法針對水下無人機路徑規劃方面有著非常好的效果，擁有不錯的魯棒性和全局性，但在面對復雜的海洋環境時，往往出現局部最優解、收斂速度慢的不足之處。本文在傳統算法基礎上進行研究，針對傳統算法的不足之處進行改進，建立了基于正態分布的自適應蟻群算法，對添加目標引導素、精英螞蟻體系、更新信息素濃度這3個方向進行改進。進而確定了改進蟻群算法在路徑規劃上的應用步驟，并對其實驗仿真。仿真結果表明，相較于傳統的蟻群算法，經過改進的蟻群算法具有更好的收斂速度，能夠準確求得最優路徑，具有很強的可行性。

1 問題描述

1.1 水下環境建模

面對復雜的水下環境,水下無人機在水下航行過程中也面臨的種種威脅,包括來自洋流、海底火山地震、地質變化及水下動植物帶來的問題[3]。要完成水下無人機的整個航行過程,我們不僅僅需要機器本身擁有更優秀的結構和材料,也需要研究人員設計一套更加完善可靠的規劃方案。

要完成整個水下無人機的路徑規劃方案,就需要先建立起一個高效的水下環境的模型,將復雜的水下環境抽象成為計算機能夠識別的地圖模型,抽象表達的方式能夠使得計算機的計算效率就可以大幅度提升,環境模型建立的好壞會直接導致路徑尋優的成功與否,通過不斷優化水下環境的模型,是整個系統朝著更加安全可靠的方向進行[4-5]。

根據水下環境的圖片運用柵格法對數據進行處理,把水下環境比作成一個二維的平面,然后將這個二維的平面進行分割,劃分成m×n個相同面積的方塊作為小柵格,這樣我們對每個柵格進行了賦值,從而就將復雜的水下環境用簡單的柵格表達出來[6-7]。用白色柵格代表可自由行進的空間,用黑色柵格代表不可行進和障礙物空間，如圖1所示。

圖1 二維環境柵格模型

在進行建立二維環境的模型時,使用這種建模方法最終能否精確獲得所求解的重要因素就是劃分出的柵格的大小,若柵格面積大,整個環境模型的信息保留少,計算機處理速度加快,能有效地避免干擾,能夠快速地求出最優路徑,但是這樣會使得環境中的信息不完整,構建的環境模型模糊,無法準確地進行規劃,容易造成結果錯誤;相反地,若柵格面積分割的特別小,會使得構建的環境模型清晰,但這樣就使得計算機處理速度緩慢,雖然會增大獲得最優路徑的幾率,尋得最優解,但其實時性較差,無法快速地計算出最優的路徑。

1.2 蟻群算法基本原理

螞蟻之間進行信息交流的媒介就是自身分泌的氣味，在螞蟻群運動的過程中,它們往往能夠在其要走過的路上留下分泌物,這種分泌物就能夠引導其他的螞蟻也在這個路徑上行走。當螞蟻在路上遇到障礙物的時候，螞蟻就會以相同概率選擇一個方向，久而久之，每一個通往目標處的路上都會存在著信息素[8-9]。但由于螞蟻在經過的短路徑上,信息素的濃度就會比其他路上的濃度高，當其他螞蟻再進行選擇時，就會更加傾向于信息素濃度大的路線，這樣就會使得后面的螞蟻更多的通過這條路，而其它路上的螞蟻就越來越少[10]。螞蟻覓食的原理如圖2所示。

圖2 蟻群覓食路徑選擇原理圖

蟻群算法在尋找最短路徑時能夠運用正反饋的原理，在最短的路徑上不斷地增大信息素的濃度，這種隨時間連續增大的濃度，可以加快系統的運算速度。而負反饋的加入，就盡可能地避免出現局部最優解，使得整個算法得到一個正確解。

根據蟻群覓食的這些規則，螞蟻在覓食路線上會留下一定量的信息素，后面螞蟻將會根據留下來的信息素的濃度對下一步路線進行選擇，這個狀態可用概率公式表示為：

(1)

(2)

螞蟻每次到達一個節點時，就將這個節點排除在以后的前進目標中，這樣就保證了每個節點只能被選取一次，當所有的節點都被螞蟻排除的時候，螞蟻就相當于對環境地圖的所有能到達的節點都經過，這時就要對這個排除單的目錄重新刷新一次，后續的螞蟻就將繼續進行。每一只螞蟻在所經過的路上也將會留下一定量的信息素，這些信息素將隨著時間慢慢地消失，這就要求合理的控制信息素的濃度，保證螞蟻達到的概率。經過時間n秒后，信息素濃度更新公式如下：

τij(t+n)=(1-p)*τij(t)+Δτij(t),p∈(0,1)

(3)

(4)

其中:ρ表示信息度揮發系數；Δτij表示路徑上留下來的信息素總量；當t=0時，路徑上留下的信息素為0。

信息素的更新有不同的方式，根據方式的不同，下面提供3種計算信息素總量的方法。

螞蟻循環模型:

螞蟻數量模型:

螞蟻密度模型:

通過對比這3種模型的公式，可以看出它們對信息素濃度的計算方法有差別，3種公式的Q表示路徑上信息素的強度，Lk表示螞蟻經過的路線長度[11-12]。螞蟻循環模型中，信息素濃度跟螞蟻在覓食中走過的路線的長度有關；螞蟻數量模型中，信息素濃度與兩節點之間的距離有關系；螞蟻密度模型中，信息素濃度完全取決于信息素的強度這個常量。分析公式可以看出，當信息素強度變大時，得到的信息素濃度也就變大，這樣就會使得蟻群過早地找到一條信息素含量高的路線，這種情況下容易出現局部最優解。由此可見，螞蟻循環模型在解決路徑規劃問題上有更好的優勢，能夠更方便地計算。

2 改進蟻群算法

針對傳統蟻群算法的不足，我們將從以下幾個方面做出改進：

首先是在算法中加入目標引導素。螞蟻在節點移動時更加地具有目的性，更好地提高算法的求解效率，螞蟻能夠在初始階段就開始確定搜索范圍，這樣就可以直接朝著更接近最終目的地的方向尋找最優解，改進后的算法將會顯著提高收斂的速度，減少了不必要的資源消耗。

其次確立精英螞蟻體系。蟻群在路徑尋優時，動態的調整每只螞蟻所帶信息素的量，經過路徑短的螞蟻攜帶信息素的量增大，經過路徑長的螞蟻攜帶信息素的量降低。這樣就能對后面螞蟻起到正反饋作用，增加求得解的數量，有效地避免出現局部最優解。

最后，更新信息素的濃度。傳統蟻群算法時，螞蟻在每條路徑上留下的信息素的量是相同的，這樣就會導致出現多個路徑信息素總濃度相似，容易出現非最優解。這時我們對信息素揮發系數進行動態調整，增加螞蟻所經過路徑的數量，避免陷入局部解的誤區，改進后的算法將會求得更多的解，面對數量大的蟻群時也會求得最優解。

2.1 添加目標引導素

算法在初始搜索階段，由于每條路徑經過的螞蟻數量較少，使得后面螞蟻沒法根據信息素的濃度來判斷下一個節點，這就使得螞蟻隨機的前往其余所有節點，這種盲目的搜索，極大地增加了算法的運算時間，也將會占用更多的資源。我們在改進的算法中添加目標引導素：

(5)

式中，m為蟻群總數量；mk為當前蟻群數量；Ncmax為最大迭代次數；Nc為當前迭代次數；diD為節點i與終點的長度；dij為節點i與節點j的長度。

添加上目標引導素之后，節點之間的移動概率就變為：

(6)

其中:jD和sD為當前節點的引導素和下一個節點的引導素。蟻群搜索初始階段時，各條路線上信息素濃度接近，此時的引導素較小，移動概率就較低，此時蟻群可以不斷地進行搜索，隨著距離終點位置的接近，路線上信息素的濃度相應地增大，引導素也不斷增大，此時螞蟻移動到目標節點的概率增大，降低了蟻群搜索的盲目性。加入引導素的蟻群算法使得螞蟻在節點之間移動時，概率出現差別，離終點越近的節點被螞蟻選擇的可能性更大，這種做法使得算法運行更加高效地、更快速地獲得最優解。

2.2 精英螞蟻體系

螞蟻在節點之間進行移動時，由于開始搜索時路徑經過螞蟻數量較少，留下來的信息素特別低，如果這是后面螞蟻朝著一條不是最優路線的節點移動時，這條非最優路徑的信息素濃度就變大，在正反饋的作用之下，后續螞蟻將會更多的經過這個路線，這時就會出現非最優解。面對這一問題，本文做出精英螞蟻體系，對完成搜索的螞蟻按照其走過路線的長度排序，對走過路線最小的螞蟻所帶有的信息素進行更新，增大其所帶有的信息素量，而這種能夠取得最短路徑的螞蟻被看成為精英螞蟻，越是經過的路線越短，更新后螞蟻所攜帶的信息素的量就越高。更新信息素的公式為：

τij(t+n)=(1-p)τij(t)+Δτij(t,t+n)

(7)

精英螞蟻信息素的增加量為：

(8)

并對節點信息素進行更新為：

(9)

蟻群搜索初始，螞蟻在兩節點i和j之間進行移動時，由于開始搜索時路徑經過螞蟻數量較少，留下來的信息素特別低，如果這是后面螞蟻朝著一條不是最優路線的節點移動時，這條非最優路徑的信息素濃度就變大，在正反饋的作用之下，后續螞蟻將會更多地經過這個路線，這時就會出現非最優解。而加入了精英螞蟻體系，對完成搜索的螞蟻按照其走過路線的長度排序，走過路線最短的螞蟻被看作為精英螞蟻，對精英螞蟻所帶有的信息素進行更新，增大它們所帶有的信息素量，越是經過的路線越短，更新后螞蟻所攜帶的信息素的量就越高，這種搜索方式將會極大地提高算法運算速度，快速得到算法的最優解。

2.3 更新信息素濃度

運用蟻群算法求解時，每只螞蟻會根據每條路徑信息素濃度的正反饋來決定它們的移動路線，信息素的改變將會直接影響整個算法的結果，而每條路徑上信息素的濃度與它們的揮發系數有著直接的聯系。當信息素的揮發系數大時，每條路徑上的信息素濃度低，此時算法能夠迅速收斂，但路徑上信息素消失速度太快，無法求得解，當信息素揮發系數小時，每條路徑留下的信息素濃度較大，這樣會陷入局部最優解的誤區。為了能夠平衡這個關系，對信息素揮發系數進行改造，使其服從正太分布，即蟻群在剛開始搜索時，揮發系數較小，此時能夠在路徑上留下更多的信息素，便于提高初始搜索效率，螞蟻能夠通過正反饋的指引來獲得比較強尋優能力；隨著時間的增加，信息素揮發系數越來越大，這時路徑上所留下來的信息素能夠快速的消失，這樣就可以增大最優解的個數，很好地避免了出現局部最優解；當搜索快要結束時，揮發系數降低，這樣路徑上的信息素濃度就會增加，能夠更好地引導后續的蟻群，起到正反饋作用。

信息素揮發系數滿足正態分布如下：

(10)

其中:k為精英螞蟻的序號。

相較于傳統蟻群算法，利用服從正態分布的信息素揮發系數能夠更好地利用取值的不同大小來實現改進蟻群算法求得更多最優解的目的。利用正態分布的特性，在螞蟻搜索最優解的初始階段，信息素揮發系數小，螞蟻在經過每條路徑時便可以留下更多的信息素，對后面螞蟻做到了更好的引導，隨著搜索的不斷進行，揮發系數慢慢增大，螞蟻在通過每條路徑上的信息素將會快速揮發，這樣螞蟻就能夠達到更多的節點，有效地避免局部最優的現象，能夠增大最終獲得最優解的數量，提高了系統的性能，隨著螞蟻搜索的不斷進行，信息素的揮發系數慢慢減小，螞蟻經過的每條路徑上的信息素濃度就不斷增大，便于螞蟻能夠到達目標，整個路徑尋優就此完成。由此可見，用于服從正態分布的揮發系數具有傳統固定揮發系統所不具備的多種優勢，這種改進的蟻群算法更能夠快速、高效地求出更多的最優解，進一步增加了蟻群算法的魯棒性。

2.4 改進蟻群算法的路徑規劃步驟

通過對蟻群算法的改進，路徑規劃過程也發生了相應的改進，具體步驟如下：

Step1：數學參數初始化。給定路徑的起點坐標和終點坐標，設置蟻群的個數、信息啟發因子、最大迭代的次數、信息素揮發系數等一系列參數

Step2：構建環境模型。運用柵格法將空間模型抽象處理，根據環境信息完成環境模型的構建。

Step3：信息參數初始化。將蟻群的排除表及模型的長度等信息進行初始化，螞蟻從路徑的起點坐標出開始向前行進，根據螞蟻從一個節點到達另一個節點的概率公式來進行尋找，每次到達一處節點都要進行記錄并將此處節點加入排除表，當環境模型中的所有節點都出現在排除表時，蟻群就完成了整個尋優過程。

Step4：信息素更新。蟻群沒完成一次迭代，都要對信息素濃度等參數進行更新。

Step5：判斷是否是局部最優解。若是，則將信息素揮發系數按照正態分布進行改進；否則，繼續進行迭代。

Step6：完成遍歷。將蟻群尋優已完成的次數與最大迭代次數比較，當已完成次數小于最大迭代次數時，繼續完成下一次迭代；反之，迭代完成，蟻群結束下一步尋優。

Step7：輸出。將蟻群算法得到的最優路徑保存。

改進的蟻群算法處理路徑規劃問題的流程如圖3所示。

圖3 改進后的蟻群算法尋優流程圖

算法在處理路徑規劃問題上的編程思路如下：

Begin

建立環境模型的01矩陣。(0表示可行進空間，1表示障礙物空間)

參數初始化，將m只螞蟻放到起點上。

loop

for k=1 to m do//從第1只螞蟻開始，依次置于起點

按概率計算公式(6)計算選擇下一個節點j;

按公式(10)更新節點間的信息素濃度；

if 節點 j是終點D then

全局信息素更新；

記錄起點到終點D之間的距離和路徑；

else 根據公式(6)選擇下一節點

更新全局信息素

if N≥ then

輸出最短路徑和距離

else exit loop

end

3 仿真實驗

為了驗證改良過后的蟻群遺傳算法的全局路徑規劃的性能，將水下環境空間柵格劃分為20*20的柵格坐標系，對傳統蟻群算法和改進后的蟻群算法進行仿真實驗，此次仿真計算機為Intel(R).Core(TM)i5-7300HQ的處理器，Windows10家庭中文版操作系統，仿真軟件為Matlab2016b。

仿真的實驗參數如表1所示。

表1 實驗參數值

仿真結果如圖4、圖5所示。

圖4 傳統蟻群算法路徑圖

圖5 改進后的蟻群算法路徑圖

算法平均迭代次數最大迭代次數最優路徑長度平均路徑長度常規蟻群算法436126.373 927.79改進蟻群算法243425.384 825.61

根據圖4可以看出，傳統的蟻群算法在解決路徑規劃問題上有不錯的優勢，蟻群從起點開始能夠有效躲避路徑上的障礙物到達終點，但在最優解上并不完美。而從圖5可以看到，改進后的算法可以有效地找到最短距離，得到的路徑更短。由表2的數據可看出，改進后的蟻群算法平均迭代次數為24次，比傳統的蟻群算法的43次更少，而且得到的最短路徑也比傳統蟻群算法短了接近一個單位長度，算法響應更加快速。

改良過的蟻群遺傳算法在最短路徑長度、迭代次數及運算時間方面都優于傳統的蟻群算法，有效提升了遺傳算法的收斂速度及管理效率。從以上最優途徑對比可見，傳統式蟻群遺傳算法在搜索初期陷于了局部最優，縱然終究還找到了一條最優途徑，但是途徑品質不及改良后的蟻群遺傳算法。

4 結束語

本文在傳統的蟻群遺傳算法分析模型剖析的基礎上，給出一種改良的蟻群算法，加入目標引導素，將幾個因素綜合考慮，減少了隨機性，構建多參數的優化分析模型。仿真試驗結果顯示，改良的蟻群遺傳算法具備良好的魯棒性，且其收斂到最優解的速度還較快，求解成本低。在下一步的研究中，經不斷改進添加引導素和更新信息素濃度等參數的值，進一步提高算法的收斂速度，保證水下無人機的環境適應能力。