楊海清,蘆 斌

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

0 引言

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

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

1 問題描述

1.1 水下環(huán)境建模

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

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

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

圖1 二維環(huán)境柵格模型

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

1.2 蟻群算法基本原理

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

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

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

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

(1)

(2)

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

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

(3)

(4)

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

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

螞蟻循環(huán)模型:

螞蟻數(shù)量模型:

螞蟻密度模型:

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

2 改進蟻群算法

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

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

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

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

2.1 添加目標引導素

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

(5)

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

添加上目標引導素之后，節(jié)點之間的移動概率就變?yōu)椋?/p>

(6)

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

2.2 精英螞蟻體系

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

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

(7)

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

(8)

并對節(jié)點信息素進行更新為：

(9)

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

2.3 更新信息素濃度

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

信息素揮發(fā)系數(shù)滿足正態(tài)分布如下：

(10)

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

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

2.4 改進蟻群算法的路徑規(guī)劃步驟

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

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

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

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

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

Step5：判斷是否是局部最優(yōu)解。若是，則將信息素揮發(fā)系數(shù)按照正態(tài)分布進行改進；否則，繼續(xù)進行迭代。

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

Step7：輸出。將蟻群算法得到的最優(yōu)路徑保存。

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

圖3 改進后的蟻群算法尋優(yōu)流程圖

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

Begin

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

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

loop

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

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

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

if 節(jié)點 j是終點D then

全局信息素更新；

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

else 根據(jù)公式(6)選擇下一節(jié)點

更新全局信息素

if N≥ then

輸出最短路徑和距離

else exit loop

end

3 仿真實驗

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

仿真的實驗參數(shù)如表1所示。

表1 實驗參數(shù)值

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

圖4 傳統(tǒng)蟻群算法路徑圖

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

算法平均迭代次數(shù)最大迭代次數(shù)最優(yōu)路徑長度平均路徑長度常規(guī)蟻群算法436126.373 927.79改進蟻群算法243425.384 825.61

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

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

4 結束語

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