基于微分進化-蟻群優化算法的潛航器航路規劃

【信息科學與控制工程】

基于微分進化-蟻群優化算法的潛航器航路規劃

高永琪，張毅

(海軍工程大學 兵器工程系，武漢430033)

摘要：航路規劃是包括新型巡航魚雷和誘餌、遠程布雷系統等潛航器完成指定任務的關鍵技術之一；為了解決蟻群優化算法在航路規劃時存在的容易陷入局部最優、收斂速度慢等問題，引入了微分進化原理，對蟻群優化算法進行了改進，提出了微分進化-蟻群優化混合算法；該算法將微分進化的隨機偏差擾動產生新個體的思想融入到蟻群優化算法中，對蟻群算法的信息素進行優化；最后以潛航器航路規劃問題為實例，對改進后的混合算法進行了仿真研究；結果表明：提出的混合算法不僅能夠得到更好的解，還能顯著地提高算法的收斂速度。

關鍵詞：航路規劃；蟻群算法；微分進化；潛航器

收稿日期：2014-04-25

作者簡介：高永琪(1968—)，男，博士，副教授，主要從事導航制導與控制研究。

doi:10.11809/scbgxb2015.01.028

中圖分類號：TP301

文章編號：1006-0707(2015)01-0099-04

本文引用格式：高永琪，張毅.基于微分進化-蟻群優化算法的潛航器航路規劃[J].四川兵工學報，2015(1):99-101.

Citationformat:GAOYong-qi,ZHANGYi.DifferentialEvolution—UUVRoutePlanningBasedonAntColonyOptimizationAlgorithm[J].JournalofSichuanOrdnance,2015(1):99-101.

DifferentialEvolution—UUVRoutePlanning

BasedonAntColonyOptimizationAlgorithm

GAOYong-qi,ZHANGYi

(DepartmentofWeaponryEngineering,NavalUniversityofEngineering,LPA,Wuhan430033,China)

Abstract:Route planning is one of the key technologies for underwater unmanned vehicle (UUV) to complete appointed task. In order to solve some defects of the ant colony optimization such as easily to fall into local optimum and slowly to converge, we put forward differential evolutions--ant colony optimization algorithm which is an improved ant colony algorithm. The new algorithm added random deviation to optimize the pheromone of ant colony algorithm and to improve the convergence speed. The simulation experiments with the improved ant colony optimization about UUV route planning were conducted. The results show that the new algorithm is not only able to get a better solution, but also can significantly improve the convergence speed.

Keywords:routeplanning;antcolonyalgorithm;differentialevolution;UUV

由于新概念巡航魚雷和誘餌、遠程布雷系統等新型潛航器的航行時間長、距離遠，因而航路規劃是其完成任務的關鍵技術之一。意大利學者MarcoDorigo通過模擬自然界中螞蟻群體的覓食行為于1991年提出的蟻群算法[1,2]可用于航路規劃中。該算法采用正反饋和分布式并行計算機制，具有很強的自學習能力和較好的魯棒性，易于和其他算法相結合。但是基本蟻群優化算法在解決復雜優化問題時搜索時間長，收斂速度慢，并容易陷入局部最優。

受到達爾文“優勝劣汰、適者生存”的自然進化原理的啟發，美國學者Storn和Price于1997年提出了模擬自然進化按概率演進的微分進化算法[3]。微分進化算法與其他進化算法相比，在解決復雜的全局優化問題方面的性能更加突出，過程也更加簡單，并且該算法在收斂速度和穩定性方面都比其他幾種隨機算法要好[4-5]。因此本文將微分進化的隨機偏差擾動產生新個體的思想融入到蟻群優化算法中，提出了基于微分進化-蟻群優化的混合算法，并將該混合算法運用于潛航器的航路規劃中，通過仿真研究取得了良好的效果，驗證了該算法的可行性和有效性。

1潛航器航路規劃問題

1.1航路規劃性能指標

潛航器航路規劃是指在特定約束條件下，尋找一條從出發點到目標點，并且滿足某種特定指標的最優航路[6]。具體來說，就是在綜合考慮潛航器能源消耗(如電池能量)、到達時間、敵方威脅(如敵方布雷區)及航行區域地形(如水下地形的可導航性)等前提下，為潛航器規劃出一條最優或者是最能滿足要求以完成指定任務的航路。在所有航路規劃的性能指標中，安全性能指標和能源性能指標最為重要，即威脅代價最小性能指標和能耗代價最小性能指標。

最小威脅代價性能指標為

(1)

最小能耗代價性能指標為

(2)

則潛航器航路規劃的總性能指標為

minJ=gJt+(1-g)Jf

(3)

L為規劃航路的長度；ωt表示航路上各點的威脅代價；ωf表示航路上各點的能耗代價，它們都是航路長度的函數；g∈[0,1]，表示安全性能與能源性能指標的權衡系數，其值可根據潛航器所執行任務的實際情況而定，如果潛航器任務重視航行時的安全性，則g選擇較大的值，如果任務更多需要考慮潛航器的續航力，則g選擇較小的值。由于潛航器能耗代價與航程成正比，為簡化起見，仿真中取ωf恒等于1，因而Jf=L。

1.2威脅代價

當潛航器沿路徑Lij航行時，N個威脅源對其產生的總威脅代價為

(4)

為了簡化計算，如圖1所示，把每條航路邊分為10段，取其中的5個奇數點來計算這條邊所受到的威脅代價，若威脅點到該邊的距離在威脅半徑之內，則按式(5)計算其威脅代價[7]

(5)

式(5)中：Lij為邊ij的長度；d0.i,k表示該條邊上的i/10分點距第k個威脅源中心的距離(i=1,3,5,7,9)；tk為第k個威脅源的威脅等級(圖1)。

圖1　航路威脅示意圖

2微分進化-蟻群優化算法

由于蟻群優化算法存在容易陷入局部最優和收斂速度慢等不足，本文將微分進化原理中的隨機偏差擾動產生新個體的思想融入到蟻群優化算法中，對螞蟻留下的信息素進行優化，以期在航路規劃過程中得到更好的信息素分布，從而獲得更優的路徑。通過對模擬地圖進行直角網格劃分，由當前點搜尋到下一個相鄰點，直到搜尋到規劃航路的終點，便形成連接起點和終點的規劃航路。網格圖中算法的數據結構是以當前點為中心的九宮圖，共有8個相鄰點，下一個點必須從以其為中心構成的8個點中選擇，同時借鑒文獻[8]設置可行域，其中網格大小d需根據實際問題規模進行合理設置。

2.1信息素

按照式(6)計算螞蟻mk從節點i到節點j的轉移概率

(6)

式(6)中：τj(t)為t時刻節點j上的信息素強度；ηj(t)為t時刻的啟發式函數；α和β分別為信息素和啟發式函數的影響系數；allowedmk為螞蟻mk當前的可行域。這里啟發式信息設置為航路的總性能指標J。

在螞蟻構建航路的過程中，每完成一次迭代后，按式(7)對當前所構建的航路進行信息素的更新

(7)

2.2交叉算子

將螞蟻分為若干相互獨立的子群，子群數量記為ns。每個子群釋放在路徑上的信息素記為Γ={τi},i=1,2,…,ns。對于各螞蟻子群當前的信息素，按照式(8)產生變異后的信息素分布

νi=τr1+F(τr2-τr3)i=1,2,…,ns

(8)

式中：τr1、τr2、τr3是在所有的螞蟻子群中隨機選出的三個信息素矩陣，并且r1≠r2≠r3。F是加權系數，表示兩個信息素矩陣差別的放大倍數。由此可知，當τr2、τr3之間的差向量較小時，意味著各子群的信息素收斂于最佳的信息素分布。

再利用微分進化算法的交叉操作，通過變異信息素分布νi和當前的目標信息素τi的結合以提高路徑上信息素的多樣性，以擴大螞蟻的搜索范圍。改進算法利用式(9)和式(10) 生成新的信息素矩陣：

(9)

(10)

2.3選擇算子

每個子群中的螞蟻按照其信息素矩陣τi計算螞蟻轉移概率，得到最優路徑的總性能指標Jτ-min，并將其定義為信息素τi的適應度值。信息素的選擇操作可表示為

(11)

2.4算法實現步驟

微分進化-蟻群優化混合算法針對潛航器最優航路規劃的運算步驟如下：

1) 參數初始化。對算法最大迭代次數Loop_max，螞蟻數量M，參數α、β、ρ，微分進化算法參數F、CR，螞蟻子群數量ns等參數進行設置，并將初始信息素τ0設置為一個常數；

2) 令迭代次數t=1，對各子群中的螞蟻按照式(6)的轉移概率進行路徑構造，直到到達終點，當所有螞蟻完成一遍路徑構造后，按式(7)進行信息素更新；

3) 對各子群按式(8)進行變異操作，再按式(10)進行交叉操作，產生信息素矩陣μi；

4) 令t=t+1，各螞蟻按信息素τi進行路徑構造，并選出最小代價Jτ-min；

5) 各螞蟻再按信息素μi進行路徑構造，并選出最小代價記為Jμ-min；

8) 對信息素進行更新。如果螞蟻選擇τi，則按照第4)步路徑構造過程進行信息素更新；如果螞蟻選擇μi，則按照第5)步路徑構造過程進行信息素更新；

9) 返回到步驟2)，直到t≥Loop_max時，算法結束并輸出最優計算結果。

3仿真研究

為驗證所提出的混合算法的有效性，利用Matlab7.0對該算法進行仿真實驗。建立簡易的模擬地圖，設定潛航器的起點坐標為(0,0)，終點坐標為(100,100)，考慮了敵方的威脅區后，戰場環境設置如表1所示。

表1　環境設置

蟻群優化算法的參數和微分進化-蟻群優化混合算法的參數設置為相同的值，如表2所示。

表2　參數取值

仿真結果如圖2和圖3所示。

圖2　規劃航路

圖3　收斂曲線

由圖2和圖3的仿真結果對比可知，微分進化-蟻群優化混合算法相對于蟻群優化算法不僅能夠得到更優解(蟻群算法和混合算法都能避開威脅區，但混合算法的綜合代價值更小)，而且其收斂速度也明顯加快(蟻群算法收斂時迭代次數大約需要180次，而混合算法只需要90次左右)。

4結束語

針對潛航器最優航路規劃問題，引入微分進化原理對蟻群優化算法進行了改進，提出了微分進化-蟻群優化混合算法，并用新的算法詳細闡述了潛航器航路優化搜索問題，給出了算法的具體流程，最后進行了仿真驗證。仿真結果表明：微分進化-蟻群優化混合算法比基本蟻群優化算法在潛航器航路規劃中能夠得到更優的結果和更快的收斂速度。

參考文獻：

[1]DorigoM,GambardellaLM.AntColonySystem:ACooperativeLearningApproachtotheTravelingSalesmanProblem[J].IEEETransactionsonEvolutionaryComputation(S1089-778X),1997,1(1):53-66.

[2]MarcoDorigo,ThomasStützle.AntColonyOptimization[M].Brussels:MIT,2004.

[3]StornR，PriceK.Differentialevolution-asimpleandefficientheuristicforforglobaloptimizationovercontinuousspaces[J].JournalofGlobalOptimization，1997,11(4)：341-359.

[4]柯維，張永祥，呂博.基于微分進化算法的盲源分離[J].海軍工程大學學報，2012，24(5):12-17.

[5]蘇海軍，楊煜普，王宇嘉.微分進化算法的研究綜述[J].系統工程與電子技術，2008，30(9):1793-1797.

[6]高曼，劉以安，張強.優化蟻群算法在反艦導彈航路規劃中的應用[J].計算機應用，2012，32(9):2530-2533.

[7]段海濱，張祥銀，徐春芳等.仿生智能計算[M].北京：科學出版社，20011.

[8]張毅，高永琪，牛興江．基于蟻群優化算法的水下航路規劃[J]．魚雷技術，2013，21(4)：272-276.

[9]劉志強，雷宇曜，陽再清. 基于元胞螞蟻算法的防空靶機航路規劃研究[J].兵工自動化，2014(5):4-6.

(責任編輯楊繼森)