基于微分進(jìn)化-蟻群優(yōu)化算法的潛航器航路規(guī)劃

【信息科學(xué)與控制工程】

基于微分進(jìn)化-蟻群優(yōu)化算法的潛航器航路規(guī)劃

高永琪，張毅

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

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

關(guān)鍵詞：航路規(guī)劃；蟻群算法；微分進(jìn)化；潛航器

收稿日期：2014-04-25

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

doi:10.11809/scbgxb2015.01.028

中圖分類號：TP301

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

本文引用格式：高永琪，張毅.基于微分進(jìn)化-蟻群優(yōu)化算法的潛航器航路規(guī)劃[J].四川兵工學(xué)報(bào)，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

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

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

1潛航器航路規(guī)劃問題

1.1航路規(guī)劃性能指標(biāo)

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

最小威脅代價(jià)性能指標(biāo)為

(1)

最小能耗代價(jià)性能指標(biāo)為

(2)

則潛航器航路規(guī)劃的總性能指標(biāo)為

minJ=gJt+(1-g)Jf

(3)

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

1.2威脅代價(jià)

當(dāng)潛航器沿路徑Lij航行時(shí)，N個威脅源對其產(chǎn)生的總威脅代價(jià)為

(4)

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

(5)

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

圖1　航路威脅示意圖

2微分進(jìn)化-蟻群優(yōu)化算法

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

2.1信息素

按照式(6)計(jì)算螞蟻mk從節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移概率

(6)

式(6)中：τj(t)為t時(shí)刻節(jié)點(diǎn)j上的信息素強(qiáng)度；ηj(t)為t時(shí)刻的啟發(fā)式函數(shù)；α和β分別為信息素和啟發(fā)式函數(shù)的影響系數(shù)；allowedmk為螞蟻mk當(dāng)前的可行域。這里啟發(fā)式信息設(shè)置為航路的總性能指標(biāo)J。

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

(7)

2.2交叉算子

將螞蟻分為若干相互獨(dú)立的子群，子群數(shù)量記為ns。每個子群釋放在路徑上的信息素記為Γ={τi},i=1,2,…,ns。對于各螞蟻?zhàn)尤寒?dāng)前的信息素，按照式(8)產(chǎn)生變異后的信息素分布

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

(8)

式中：τr1、τr2、τr3是在所有的螞蟻?zhàn)尤褐须S機(jī)選出的三個信息素矩陣，并且r1≠r2≠r3。F是加權(quán)系數(shù)，表示兩個信息素矩陣差別的放大倍數(shù)。由此可知，當(dāng)τr2、τr3之間的差向量較小時(shí)，意味著各子群的信息素收斂于最佳的信息素分布。

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

(9)

(10)

2.3選擇算子

每個子群中的螞蟻按照其信息素矩陣τi計(jì)算螞蟻轉(zhuǎn)移概率，得到最優(yōu)路徑的總性能指標(biāo)Jτ-min，并將其定義為信息素τi的適應(yīng)度值。信息素的選擇操作可表示為

(11)

2.4算法實(shí)現(xiàn)步驟

微分進(jìn)化-蟻群優(yōu)化混合算法針對潛航器最優(yōu)航路規(guī)劃的運(yùn)算步驟如下：

1) 參數(shù)初始化。對算法最大迭代次數(shù)Loop_max，螞蟻數(shù)量M，參數(shù)α、β、ρ，微分進(jìn)化算法參數(shù)F、CR，螞蟻?zhàn)尤簲?shù)量ns等參數(shù)進(jìn)行設(shè)置，并將初始信息素τ0設(shè)置為一個常數(shù)；

2) 令迭代次數(shù)t=1，對各子群中的螞蟻按照式(6)的轉(zhuǎn)移概率進(jìn)行路徑構(gòu)造，直到到達(dá)終點(diǎn)，當(dāng)所有螞蟻完成一遍路徑構(gòu)造后，按式(7)進(jìn)行信息素更新；

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

4) 令t=t+1，各螞蟻按信息素τi進(jìn)行路徑構(gòu)造，并選出最小代價(jià)Jτ-min；

5) 各螞蟻再按信息素μi進(jìn)行路徑構(gòu)造，并選出最小代價(jià)記為Jμ-min；

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

9) 返回到步驟2)，直到t≥Loop_max時(shí)，算法結(jié)束并輸出最優(yōu)計(jì)算結(jié)果。

3仿真研究

為驗(yàn)證所提出的混合算法的有效性，利用Matlab7.0對該算法進(jìn)行仿真實(shí)驗(yàn)。建立簡易的模擬地圖，設(shè)定潛航器的起點(diǎn)坐標(biāo)為(0,0)，終點(diǎn)坐標(biāo)為(100,100)，考慮了敵方的威脅區(qū)后，戰(zhàn)場環(huán)境設(shè)置如表1所示。

表1　環(huán)境設(shè)置

蟻群優(yōu)化算法的參數(shù)和微分進(jìn)化-蟻群優(yōu)化混合算法的參數(shù)設(shè)置為相同的值，如表2所示。

表2　參數(shù)取值

仿真結(jié)果如圖2和圖3所示。

圖2　規(guī)劃航路

圖3　收斂曲線

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

4結(jié)束語

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

參考文獻(xiàn)：

[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ìn)化算法的盲源分離[J].海軍工程大學(xué)學(xué)報(bào)，2012，24(5):12-17.

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

[6]高曼，劉以安，張強(qiáng).優(yōu)化蟻群算法在反艦導(dǎo)彈航路規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2012，32(9):2530-2533.

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

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

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

(責(zé)任編輯楊繼森)