艦艇編隊(duì)協(xié)同應(yīng)召搜索最優(yōu)路徑規(guī)劃方法

趙 亮,任耀峰,張 獻(xiàn)

(海軍工程大學(xué),湖北 武漢 430033)

?

艦艇編隊(duì)協(xié)同應(yīng)召搜索最優(yōu)路徑規(guī)劃方法

趙 亮,任耀峰,張 獻(xiàn)

(海軍工程大學(xué),湖北 武漢 430033)

針對水面艦艇編隊(duì)協(xié)同應(yīng)召搜索運(yùn)動目標(biāo)問題,建立了同時(shí)優(yōu)化多個搜索者路徑的規(guī)劃模型,并考慮了聲吶有效搜索寬度和舷角對探測能力的影響。根據(jù)規(guī)劃模型,設(shè)計(jì)了一種多種群協(xié)同進(jìn)化自適應(yīng)遺傳算法,利用競爭排除原理引導(dǎo)多個種群同時(shí)進(jìn)化,兼顧了各種群間的差異化和整體的協(xié)調(diào)有序,提高了搜索效率;并在種群內(nèi)部進(jìn)化中通過分類選擇、自適應(yīng)交叉和導(dǎo)向性變異改進(jìn)遺傳操作,保障了優(yōu)勢基因的傳播,加快了收斂速度,動態(tài)調(diào)節(jié)了局部搜索和全局搜索的平衡,避免進(jìn)化陷入局部最優(yōu)。通過對方向未知的運(yùn)動目標(biāo)進(jìn)行協(xié)同搜索的算例仿真,得到了協(xié)同搜索的最優(yōu)路徑,該方法與常規(guī)應(yīng)召搜索方式相比在全局尋優(yōu)和搜索效能上有較大的優(yōu)勢,適用于求解編隊(duì)協(xié)同應(yīng)召反潛搜索問題。

編隊(duì)協(xié)同;應(yīng)召搜索;路徑規(guī)劃;協(xié)同進(jìn)化;自適應(yīng)遺傳算法

編隊(duì)?wèi)?yīng)召反潛搜索[1]作為編隊(duì)反潛搜索的一種常用形式,是在其他兵力的召喚下,前往發(fā)現(xiàn)有敵潛艇活動的海域進(jìn)行的對潛搜索,搜索已被發(fā)現(xiàn)但又失去接觸的潛艇。搜索編隊(duì)通常由2艘以上艦艇組成,采取單橫隊(duì)或人字隊(duì)向丟失點(diǎn)海域進(jìn)行平行搜索,但由于沒有考慮目標(biāo)的運(yùn)動特性,發(fā)現(xiàn)概率不高。因此運(yùn)用計(jì)算技術(shù)和現(xiàn)代搜索理論對編隊(duì)搜索路徑進(jìn)行規(guī)劃,提高艦艇編隊(duì)的搜索效能,具有重要的現(xiàn)實(shí)意義。

對于單搜索者搜索路徑規(guī)劃問題,Kierstead[6]首次將遺傳算法應(yīng)用其中,得到了令人滿意的搜索方案。隨后也有不少研究者通過改進(jìn)遺傳算法來解決此類問題,體現(xiàn)出該方法對于路徑規(guī)劃問題有良好的適應(yīng)性,但對于多搜索者的路徑規(guī)劃問題,遺傳算法缺乏協(xié)同機(jī)制,存在一定的應(yīng)用困難。

本文研究了編隊(duì)?wèi)?yīng)召反潛最優(yōu)搜索路徑規(guī)劃問題。首先對搜索問題進(jìn)行了描述,建立了目標(biāo)的運(yùn)動模型、搜索者的探測和運(yùn)動模型。然后在協(xié)同進(jìn)化算法[14]的基礎(chǔ)上,提出了一種多種群協(xié)同自適應(yīng)遺傳算法(Multiple Coordinated Adaptive Genetic Algorithm,MCAGA),該算法基于環(huán)形傳遞思想,利用種群之間等效距離上的關(guān)系,保持種群之間的差異性進(jìn)化,擴(kuò)大協(xié)同路徑搜索范圍,同時(shí)在種群內(nèi)部采用分類選擇,自適應(yīng)交叉和變異的遺傳操作,動態(tài)調(diào)節(jié)局部尋優(yōu)和全局尋優(yōu)的平衡,提高了整體搜索效率。最后通過仿真分析和方法對比驗(yàn)證了該算法的有效性。

1 搜索問題描述

常規(guī)的編隊(duì)?wèi)?yīng)召搜索問題可以描述成如下形式:在T0時(shí)刻,有情報(bào)顯示在某一海域內(nèi)發(fā)現(xiàn)一水下目標(biāo)在TS點(diǎn)浮出水面并迅速下潛逃離出水點(diǎn)。在T1時(shí)刻位于該海域另一點(diǎn)OS處的艦艇編隊(duì)接到搜索命令后,開始進(jìn)行出航準(zhǔn)備。在T2時(shí)刻編隊(duì)各艦從OS點(diǎn)出發(fā)向TS點(diǎn)機(jī)動,各艦航速為巡航速度VC,編隊(duì)組成密集隊(duì)形,航向?yàn)镺S點(diǎn)到TS點(diǎn)的連線方向。在T3時(shí)刻編隊(duì)到達(dá)FS點(diǎn)組成單橫隊(duì),航向航速不變,艦與艦之間的距離為D,單橫隊(duì)以O(shè)S點(diǎn)到TS點(diǎn)的連線為軸,使編隊(duì)各艦位置成軸對稱布置。在T4時(shí)刻,橫隊(duì)中心到達(dá)開始搜索點(diǎn)ES,此時(shí)編隊(duì)各艦以搜索航速VS開始對潛搜索,搜索點(diǎn)ES為目標(biāo)以最大速度與橫隊(duì)中心相向運(yùn)動的相遇點(diǎn)。當(dāng)編隊(duì)搜索到目標(biāo)或者搜索行動達(dá)到上級要求的搜索時(shí)長TS后,編隊(duì)?wèi)?yīng)召搜索行動完畢。

以3艘艦艇為例,整個過程如圖1所示,但在實(shí)際行動的過程中,由于開始搜索延誤時(shí)間產(chǎn)生的目標(biāo)信息的模糊性,目標(biāo)運(yùn)動要素的不確定性,以及搜索區(qū)域的延伸對搜索資源(時(shí)間、兵力)的依賴性,使得常規(guī)的編隊(duì)搜索效率不高,要獲得較高的發(fā)現(xiàn)概率必須投入大量的時(shí)間和搜索兵力。

圖1 編隊(duì)?wèi)?yīng)招搜索過程圖

針對這個問題,本文采用最優(yōu)搜索路徑規(guī)劃方法,根據(jù)目標(biāo)的運(yùn)動特點(diǎn)來規(guī)劃整個搜索時(shí)長TS內(nèi)的搜索者路徑,使編隊(duì)的搜索路徑能夠較大程度地覆蓋到潛艇的活動區(qū)域,減少重復(fù)搜索,提高搜潛效率。

2 目標(biāo)運(yùn)動模型

在應(yīng)召搜索行動中,水下運(yùn)動目標(biāo)在發(fā)現(xiàn)運(yùn)動要素沒有暴露的情況下,一般仍將繼續(xù)保持原先的運(yùn)動規(guī)律。從T0時(shí)刻開始,目標(biāo)潛入水下遠(yuǎn)離TS點(diǎn)作勻速直線運(yùn)動,航向服從[0,2π]上的均勻分布,速度服從正態(tài)分布[2],通過模擬仿真即可獲得目標(biāo)隨時(shí)間變化的分布情形。

3 搜索者運(yùn)動模型

編隊(duì)在ES點(diǎn)前的路徑為勻速直線運(yùn)動,從ES點(diǎn)開始編隊(duì)進(jìn)入搜索階段,各艦艇根據(jù)機(jī)動能力通常會在一定時(shí)間段內(nèi)保持穩(wěn)定的運(yùn)動方向和速度,每隔一段時(shí)間根據(jù)情況進(jìn)行調(diào)整?，F(xiàn)將航向、航速不變的運(yùn)動過程定義為一個分階段。在搜索階段搜索者搜索路徑的表達(dá)包括以下幾個要素:搜索者起始點(diǎn)SS、搜索階段開始后總搜索時(shí)長TS、運(yùn)動狀態(tài)保持穩(wěn)定的分階段時(shí)長SteptS、各分階段航向θS和航速VS,其中θS∈[0,2π],VS保持不變，如圖2所示。模型忽略各分階段在方向調(diào)整上所消耗的時(shí)間以及由此引起的路徑偏差,只考慮航向變化的情形。

圖2 單個搜索者搜索路徑圖

4 搜索者探測模型

水面艦艇通常裝備有艦殼式聲吶,在實(shí)際問題中,聲吶工作區(qū)域存在盲區(qū),艦艇聲吶的實(shí)際探測能力由聲吶有效搜索寬度w來描述[3,4],聲吶有效搜索寬度公式可近似表示為w=2·r·sinβ,式中r表示聲吶的最大探測距離,β表示聲吶的單舷有效搜索扇面角。編隊(duì)各艦在搜索階段使用聲吶來探測水下目標(biāo),每隔時(shí)間ΔtD進(jìn)行一次探測。

當(dāng)目標(biāo)與搜索者的距離不大于有效搜索寬度w時(shí),探測到目標(biāo)的概率為1,否則為0。在探測過程中,模型不考慮探測信號延遲,在每次的聲吶探測中,搜索者可以立刻得到聲吶所判定的目標(biāo)狀態(tài)信息,且探測模型為二維模型,不考慮目標(biāo)深度對探測的影響，聲吶探測模型如圖3所示。即在任意t時(shí)刻進(jìn)行一次探測,對于任意一個搜索者(Xi,Yi),要能搜索到目標(biāo)(X,Y),需要滿足如下公式:

(1)

圖3 聲吶探測模型

5 編隊(duì)搜索階段的路徑規(guī)劃

5.1 積累探測概率

對于最優(yōu)搜索路徑規(guī)劃問題,需要解決如何合理地分配資源使得搜索效能最大化。本文利用積累探測概率(Cumulative Detection Probability,CDP)來評價(jià)各搜索者路徑的搜索效能[5]。對于任意一個可行的搜索方案ξ,搜索時(shí)長t內(nèi)搜索者的CDP記為FCDP(ξ,t),由于目標(biāo)可通過多次的模擬仿真獲得,所以可采用蒙特卡羅方法[6-8]近似計(jì)算每條搜索路徑的積累探測概率：

(2)

其中NT表示目標(biāo)仿真的總數(shù),ND(t)表示已探測到的目標(biāo)個數(shù)。

5.2 路徑規(guī)劃模型

針對編隊(duì)搜索問題,需要使得編隊(duì)整體對目標(biāo)的積累探測概率最大,將其作為目標(biāo)函數(shù)即可建立編隊(duì)在搜索階段中關(guān)于各艦航向優(yōu)化的路徑規(guī)劃模型：

(3)

式中,X1,X2…Xj…XS代表編隊(duì)中S艘艦艇的路徑方案,決策變量Xj=(xj1,xj2,…,xjN)T表示編隊(duì)中某一艦艇的某一種搜索路徑方案;N表示搜索路徑分階段數(shù);(xj1,xj2,…,xjN)T表示搜索路徑各階段的航向θS;FCDP(X1,X2…Xj…XS,t)表示搜索時(shí)長t內(nèi)編隊(duì)整體的積累探測概率,問題的可行解范圍為:

Ψ={X1,X2…Xj…XS|xji∈[0,2π]}

其中1≤i≤N,1≤j≤S,由于FCDP是t的單調(diào)遞增函數(shù),t取為TS。

6 協(xié)同進(jìn)化自適應(yīng)遺傳算法

進(jìn)化計(jì)算是受大自然中的進(jìn)化現(xiàn)象啟發(fā)而提出來的智能計(jì)算方法,自然界中生物進(jìn)化主要包括相互受益和相互制約兩類機(jī)制,基于達(dá)爾文思想的遺傳算法主要體現(xiàn)的是相互制約的影響,對相互受益的影響體現(xiàn)較少,存在一定的片面性[10],使得該算法主要用來解決單個種群的優(yōu)化問題,而對于多種群存在相互作用關(guān)系的進(jìn)化問題缺乏比較好的解決方法[11]。

協(xié)同進(jìn)化自適應(yīng)遺傳算法(MCAGA)則是在一般進(jìn)化算法的基礎(chǔ)上,考慮種群與種群之間的相互作用,使多個種群向著有利于共同適應(yīng)的方向進(jìn)化,提高所有種群的適應(yīng)能力,提高系統(tǒng)的有序性和多樣性,通過在種群間篩選有利于合作的個體進(jìn)化,有利于整個生態(tài)系統(tǒng)的穩(wěn)定和效能傳遞。

對于編隊(duì)搜索最優(yōu)路徑規(guī)劃過程,可以轉(zhuǎn)化為一個生態(tài)系統(tǒng)里(搜潛編隊(duì))的多種群(每艘艦艇),在合作機(jī)制的作用下,共同進(jìn)化到最優(yōu)的生存狀態(tài),使得整個生態(tài)系統(tǒng)運(yùn)行效率最大的過程。

6.1 個體編碼方案

其中k表示進(jìn)化代數(shù);M表示種群的規(guī)模;S表示編隊(duì)的規(guī)模;θ表示航向的基因編碼;N表示一條搜索路徑的階段數(shù);Gmax表示種群的最大進(jìn)化代數(shù);1≤j≤S,1≤i≤M,1≤b≤N,1≤k≤Gmax。

6.2 種群協(xié)同方式

圖4 環(huán)形傳遞的協(xié)同方式

6.3 信息交互協(xié)同

根據(jù)競爭排除原理[15]思想,在編隊(duì)搜索問題中,需要通過種群之間的信息交互對各搜索者的路徑進(jìn)行差異化處理,減少已探測區(qū)域的重復(fù)搜索,提高搜索資源的利用效率。對于搜索路徑間的相似程度,本文用染色體間的等效距離來衡量。

等效距離為任意兩條搜索時(shí)長相同的路徑上,所有相對應(yīng)探測時(shí)刻點(diǎn)之間距離和的平均值,等效距離越長則路徑的相似度越低,距離越短則路徑的相似度越高。本文利用等效距離將協(xié)同因子ai(t)定義如下:

(4)

其中MDi(t)表示搜索者種群P中搜索時(shí)長為t的個體i與相鄰種群的局部代表個體的等效距離。AMD(P,t)表示整個種群P中的所有個體與相鄰種群的局部代表個體的等效距離和的平均值,每個種群的局部代表個體即為每個進(jìn)化周期初始階段種群中擁有最大染色體適應(yīng)度的個體。

由于不考慮通信延遲,各種群可以迅速獲得相鄰種群的局部代表個體,并與該種群內(nèi)的待評價(jià)個體共同作用,計(jì)算出協(xié)同關(guān)系下的待評價(jià)個體的生存適應(yīng)度,各種群再基于生存適應(yīng)度來完成自身的進(jìn)化過程。

6.4 自適應(yīng)遺傳操作

MCAGA算法的每個運(yùn)算周期內(nèi)除了考慮群體間的關(guān)系進(jìn)行協(xié)同進(jìn)化外,還要考慮種群內(nèi)部的遺傳進(jìn)化。為了克服傳統(tǒng)遺傳算法局部搜索能力差,尋優(yōu)精度不高,收斂速度慢等缺點(diǎn),本文針對搜索問題設(shè)計(jì)了一種改進(jìn)型遺傳操作。首先基于精英保留策略和輪盤賭法改進(jìn)選擇算子,然后通過設(shè)定自適應(yīng)的交叉率Pc和變異率Pm動態(tài)調(diào)節(jié)種群多樣性和收斂性的平衡,并通過兩種變異算子分別作用于種群中的不同個體完成遺傳操作。

6.4.1 分類選擇

設(shè)一個種群的個體數(shù)量為M,每個個體的基因數(shù)為N,選擇后的個體序列標(biāo)記為 (C1,C2,…CM),選擇過程如下:

1) 將父代中生存適應(yīng)度最大的個體放入C1中,不參加交叉變異過程,直接遺傳到下一代。

2) 將父代中生存適應(yīng)度靠前的前l(fā)個精英個體,依次放入(C2,…Cl+1)中,不參加交叉過程,進(jìn)行有指向性的更優(yōu)變異,產(chǎn)生下一代。

3) 將父代的所有個體通過輪盤賭方法依次選出(M-l-1)個個體(當(dāng)遇到最差個體時(shí),放棄重選),將它們放入到(Cl+2,…CM)中,進(jìn)行自適應(yīng)的交叉和變異操作,產(chǎn)生下一代。

6.4.2 自適應(yīng)交叉

6.4.3 更優(yōu)變異和非均勻變異

本文采用兩種不同的變異模式分別作用于分類選擇后的精英個體組和自適應(yīng)交叉后的普通個體組,在方向上引導(dǎo)精英個體更優(yōu)進(jìn)化,同時(shí)加強(qiáng)普通個體的局部尋優(yōu)能力,保證變異的高效性和收斂性。

1) 將選擇操作產(chǎn)生的個體序列(C2,…Cl+1)采用AMGA算法[17]產(chǎn)生變異,利用父代最優(yōu)個體的引導(dǎo)作用,將被操作的個體向父代生存適應(yīng)度最優(yōu)個體的方向?qū)嵤┳儺悺?/p>

6.5MCAGA算法流程

步驟1 從搜索階段開始,每個搜索者初始化搜索時(shí)長為TS的路徑種群,此時(shí)進(jìn)化代數(shù)k=1。

步驟2 評價(jià)各種群中個體的染色體適應(yīng)度,即每個個體的積累探測概率FCDP,每個種群選出染色體適應(yīng)度最大的個體作為局部代表個體。

步驟3 通過環(huán)形傳遞,每個種群結(jié)合相鄰種群的局部代表個體,計(jì)算協(xié)同因子,評價(jià)種群中每個個體的生存適應(yīng)度。

步驟4 種群代數(shù)若達(dá)到設(shè)定的進(jìn)化代數(shù),輸出種群中染色體適應(yīng)度最大的個體所對應(yīng)的積累探測概率和個體的分階段航向,將各種群的最優(yōu)方案組成編隊(duì)的最優(yōu)方案。若未達(dá)到進(jìn)化代數(shù),則各種群繼續(xù)進(jìn)行遺傳操作,進(jìn)入步驟5。

步驟5 每個種群根據(jù)生存適應(yīng)度來評價(jià)個體,進(jìn)行分類選擇自適應(yīng)遺傳操作。

步驟6 各搜索者種群通過遺傳操作得到子代種群,進(jìn)化代數(shù)k=k+1。各搜索者子代種群轉(zhuǎn)至步驟2進(jìn)行操作。

7 模擬仿真及算法實(shí)現(xiàn)

7.1 編隊(duì)搜索算例描述

假設(shè)T0=0時(shí)刻(h),有一水下目標(biāo)在點(diǎn)TS=(100,100)nmile處浮出水面,隨后立即潛入水下離開出水點(diǎn)。目標(biāo)的速度VT(kn)服從正態(tài)分布N(7,1),目標(biāo)的航向θT服從[0,2π]上的均勻分布,通過對目標(biāo)進(jìn)行大量仿真可得到目標(biāo)的運(yùn)動分布，如圖5所示。

圖5 目標(biāo)運(yùn)動分布示意圖

在T1=0.2時(shí)刻,位于點(diǎn)OS=(70,70)處的2艘艦艇接到搜索命令后開始出航準(zhǔn)備,在T2=0.5時(shí)刻編隊(duì)組成密集隊(duì)形進(jìn)入航渡階段,各艦以最大巡航速度VC=20kn向TS點(diǎn)機(jī)動。在T3=1時(shí)刻,編隊(duì)組成單橫隊(duì),艦與艦之間的距離為D=1.5kn。

進(jìn)入搜索階段,各艦均以搜索航速VS=15kn向目標(biāo)可能的逃逸方向搜索,路徑方向不定,根據(jù)搜索任務(wù)要求,各艘艦艇搜索時(shí)長均為TS=15h,在時(shí)刻T5=T4+TS完成搜索行動。編隊(duì)在搜索時(shí)長內(nèi)根據(jù)協(xié)同進(jìn)化自適應(yīng)遺傳算法規(guī)劃各艦的搜索路徑。

7.2 算法實(shí)現(xiàn)與結(jié)果分析

進(jìn)入搜索階段后,對于任意一艘艦艇,搜索航速VS=15kn,搜索時(shí)長TS=15h,搜索路徑分階段時(shí)長SteptS=1h,總階段數(shù)NStep=15。探測方面,由積累探測概率公式計(jì)算探測效能,且探測間隔ΔtD=0.2h。每個搜索者路徑種群的初始化為:每個搜索者均為勻速直線運(yùn)動,路徑航向在初始航向左右各60度的扇面內(nèi)等間隔選取。

設(shè)定算法參數(shù),種群數(shù)S=2,每個種群的規(guī)模M=80,染色體長度N=15,最大進(jìn)化代數(shù)Gmax=60,每次進(jìn)化選出來進(jìn)行更優(yōu)變異的父代精英個體數(shù)l=19。通過30次獨(dú)立的協(xié)同進(jìn)化算法仿真實(shí)驗(yàn),得到的最優(yōu)結(jié)果如圖6所示,編隊(duì)整體積累探測概率為93.82%,其中兩條路徑的角度解為:

θS1=[33.7 2.4 22.2 56.5 70.4 104.6106.3 121.5 140.1 150.9 120.8 103.8 134.9141.9 163.1]

θS2=[38.1 111.4 80.1 33.3 26.8 12.113.5 329.9 323.4 309.3 285.1 322.3 331.9346.6 329.7]

圖6 編隊(duì)(2艘)最優(yōu)搜索路徑

通過對結(jié)果和圖像進(jìn)行分析,可以看出基于MCAGA算法的編隊(duì)路徑規(guī)劃有如下特點(diǎn):

1)根據(jù)搜索者數(shù)量自動匹配不同的搜索路徑,在有限的時(shí)間內(nèi),根據(jù)目標(biāo)的運(yùn)動規(guī)律,盡可能使搜索路徑覆蓋到目標(biāo)所有的運(yùn)動范圍,并減少對相同區(qū)域的重復(fù)搜索。

2)由于目標(biāo)的圓周擴(kuò)散特性,兩條路徑對目標(biāo)可能的擴(kuò)散范圍進(jìn)行了近似對稱地包圍,在搜索初始階段保證了對相向運(yùn)動目標(biāo)的覆蓋,又確保了搜索中段不漏掉可能向兩側(cè)運(yùn)動的目標(biāo),同時(shí)對可能一開始就背離編隊(duì)運(yùn)動的目標(biāo)進(jìn)行了攔截,最后采用近似對數(shù)螺旋線的方式來檢查之前可能遺漏的目標(biāo)。

3)文獻(xiàn)[17]指出,針對此類問題基于遺傳算法的求解路徑近似于對數(shù)螺旋曲線,而且由于目標(biāo)分布的時(shí)空對稱性,對于單搜索者路徑,存在順時(shí)針?biāo)阉骱湍鏁r(shí)針?biāo)阉鲀煞N情況。而本算法對于兩個搜索者路徑的優(yōu)化,正好可以使得兩個搜索者從順時(shí)針和逆時(shí)針方向同時(shí)對目標(biāo)進(jìn)行類似對數(shù)螺旋線的搜索,進(jìn)一步證實(shí)了該方法在求解編隊(duì)搜索問題上的合理性和有效性。

7.3 方法對比與性能驗(yàn)證

對于常規(guī)的編隊(duì)?wèi)?yīng)召搜索,可以通過搜索能力計(jì)算公式[20]來確定編隊(duì)對目標(biāo)的搜索概率,以此方法來對搜索資源進(jìn)行調(diào)整,滿足任務(wù)要求。

(5)

其中U搜索為編隊(duì)的整體搜索能力,T延誤為編隊(duì)開始展開搜索前延誤的時(shí)間,T搜索為編隊(duì)搜索階段所用的時(shí)長,V潛艇為估計(jì)的潛艇最大速度。在保持之前算例相同的參數(shù)設(shè)定條件下,可以得到2艘艦艇在常規(guī)搜索模式下,對目標(biāo)的探測概率為70.34%,當(dāng)在相同時(shí)間內(nèi)組織5艘艦艇進(jìn)行應(yīng)召搜索時(shí),對目標(biāo)的探測概率為91.72%。而采用本文優(yōu)化方法的算例所得到的編隊(duì)搜索路徑,在相同條件下,只需要2艘艦艇便可以達(dá)到常規(guī)方法5艘艦艇同時(shí)搜索的效果,表明該優(yōu)化方法有效提高了搜索效率,降低了對搜索資源的依賴程度。

對于2艘艦艇以上的多艘艦艇編隊(duì)搜潛,運(yùn)用MCAGA算法同樣能得到類似的優(yōu)化效果。通過各30次的獨(dú)立實(shí)驗(yàn),3艘和4艘艦艇優(yōu)化后的路徑整體積累探測概率分別為95.79%和97.43%,由圖7、8可以看出,通過MCAGA算法編隊(duì)各艦的搜索路徑均能夠做到對目標(biāo)運(yùn)動分布區(qū)域的大范圍覆蓋,同時(shí)在一定程度上減少了各搜索路徑之間重復(fù)搜索的區(qū)域。

圖7 編隊(duì)(3艘)最優(yōu)搜索路徑

圖8 編隊(duì)(4艘)最優(yōu)搜索路徑

7.4 不同速度分布目標(biāo)的搜索問題

通過對3艘艦艇和4艘艦艇的搜索路徑圖進(jìn)行分析可以看出,雖然能得到比較高的積累探測概率,但由于目標(biāo)分布的時(shí)空對稱性,編隊(duì)中艦艇路徑還是存在較多的搜索重復(fù)區(qū)域,相比2個搜索者的路徑優(yōu)化效果,3個搜索者和4個搜索者的路徑優(yōu)化效果提升程度并不算太大,對搜索資源的利用并不充分,2個搜索者能夠保證足夠大的搜索效果。

實(shí)際反潛搜索行動中,很多情況下不能準(zhǔn)確判斷目標(biāo)的速度范圍,同時(shí)搜索兵力的探測能力和航行能力也可能不一致,所以對于2艘以上的編隊(duì)?wèi)?yīng)召搜索問題可以采取對目標(biāo)可能的不同速度分布情形分別展開搜索的方法。假設(shè)目標(biāo)可能服從N(12,1)和N(6,1)兩種正態(tài)分布,以4艘艦艇組成搜索編隊(duì),其中2艘搜索能力強(qiáng)速度快,2艘搜索能力弱速度慢,利用MCAGA進(jìn)行路徑規(guī)劃,可以安排編隊(duì)中速度快，探測能力強(qiáng)的艦艇對目標(biāo)速度高的分布區(qū)域進(jìn)行搜索,安排速度慢探測能力弱的艦艇對目標(biāo)速度低的分布區(qū)域進(jìn)行搜索,使搜索路徑與目標(biāo)的速度分布相匹配,在有限的搜索時(shí)長內(nèi)進(jìn)一步提高搜索資源的利用效率。

圖9 編隊(duì)(4艘)分速度段搜索路徑

通過計(jì)算,利用分速度層次搜索的方法,4艘艦艇的整體搜索概率為95.44%。 從搜索路徑圖9可以看出,相比4艘艦艇同時(shí)搜索目標(biāo)的一種速度分布情形,搜索路徑覆蓋的探測區(qū)域進(jìn)一步得到了擴(kuò)大,同時(shí)減少了路徑之間的重復(fù)搜索區(qū)域,并保持了較高的搜索效能,因此編隊(duì)基于MCAGA算法對目標(biāo)的不同速度分布情形分別進(jìn)行反潛搜索的方法,能夠給無法準(zhǔn)確掌握目標(biāo)速度信息的反潛搜索問題提供一種比較合理的思路,有助于編隊(duì)?wèi)?yīng)召反潛搜索方法研究的豐富和發(fā)展。

8 結(jié)束語

本文針對水面艦艇編隊(duì)協(xié)同應(yīng)召搜索運(yùn)動目標(biāo)的最優(yōu)路徑規(guī)劃問題進(jìn)行了研究,根據(jù)種群之間的相互作用和種群內(nèi)部的進(jìn)化關(guān)系,提出了一種多種群協(xié)同進(jìn)化自適應(yīng)遺傳算法。在整體進(jìn)化方面,采用環(huán)形傳遞的協(xié)同方式,保證了各種群進(jìn)化的差異性,增強(qiáng)了種群間的多樣性;在局部進(jìn)化方面,對各種群內(nèi)部采用分類選擇進(jìn)化和自適應(yīng)的交叉變異操作,有針對性地挑選和產(chǎn)生較優(yōu)秀個體,動態(tài)調(diào)節(jié)多樣性和收斂性的平衡,增強(qiáng)了算法的穩(wěn)定性和尋優(yōu)能力。在仿真實(shí)驗(yàn)中運(yùn)用該方法得到了比較合理的編隊(duì)?wèi)?yīng)召搜索方案,提高了編隊(duì)的搜索效能,對多搜索者協(xié)同搜索路徑控制研究具有一定的應(yīng)用價(jià)值和啟發(fā)意義。

[1] 楊日杰，何友，孫明太.航空搜潛裝備搜潛范圍建模與仿真研究[J].系統(tǒng)仿真學(xué)報(bào),2003,15(11):1547-1549

[2] 屈也頻,廖英.潛艇位置散布規(guī)律與搜潛效能評估模型研究[J].系統(tǒng)仿真學(xué)報(bào),2008,20(12):3281-3282.

[3] URICK R. Principles of underwater sound[M]. New York: Mc Graw Hill, 1983.

[4] On sonar performance estimation for separated source and receiver[R]. AD-A068956/2SL.

[5] 瓦格納,邁蘭德,森德.海軍運(yùn)籌分析[M].第3版.姜青山,鄭保華譯.北京:國防工業(yè)出版社, 2008.

[6] Kierstead D P, DelBalzo D R. A genetic algorithm applied to planning search paths in complicated environments[J]. Military Operations Research, 2003, 8(2): 45-59.

[7] Cho J H, Kim J S, Lim J S, et al. Optimal acoustic search path planning for sonar system based on genetic algorithm[J]. International Journal of Offshore and Polar Engineering, 2007, 17 (3): 218-224.

[8] Cho J H, Kim J S. Benchmarking of Optimal Acoustic Search Path Planning[C].∥Proc. of the 19th International Offshore and Polar Engineering Conference, 2009: 620-626.

[9] Goldberg D E. Genetic algorithms in search, optimization and machine learning[M].New York Addison Wasley,1989.

[10]鞏敦衛(wèi).協(xié)同進(jìn)化遺傳算法理論及應(yīng)用[M].北京:科學(xué)出版社,2009.

[11]TU zhen-guo. LuYong. A robust stochastic genetic algorithm for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation,2004,8(5):456-470.

[12]張鵬. 多蜂群協(xié)同進(jìn)化算法及其應(yīng)用研究[D].山東師范大學(xué), 2014.

[13]苗金鳳. 協(xié)同進(jìn)化遺傳算法在多目標(biāo)優(yōu)化中的應(yīng)用研究[D].山東師范大學(xué), 2011.

[14]李碧,郝志峰.協(xié)同進(jìn)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2013.

[15]Lima C F, Goldberg D E, Sastry K. Combining competent crossover and mutation operators: A probabilistic model building approach[C]. Genetic and Evolutionary Computation Conference. 2005: 735-742.

[16]房磊,張煥春,經(jīng)亞枝. 一種模糊自適應(yīng)遺傳算法[J].西南交通大學(xué)學(xué)報(bào),2005,40(1):22-25.

[17]張獻(xiàn),任耀峰,王潤芃等. 基于自適應(yīng)變異遺傳算法的連續(xù)時(shí)空最優(yōu)搜索路徑規(guī)劃[J]. 兵工學(xué)報(bào),2015,36(12):2389-2392.

[18]黃衛(wèi)華,許小勇,范建坤. 實(shí)數(shù)編碼遺傳算法中常用變異算子的Matlab實(shí)現(xiàn)及應(yīng)用[J].輕工科技,2007,23(1):77-78.

[19]李欣. 自適應(yīng)遺傳算法的改進(jìn)與研究[D].南京信息工程大學(xué)，2008.

[20]門金柱,周明,倫九凱. 反潛編隊(duì)?wèi)?yīng)召搜索能力計(jì)算及效果評估[J]. 指揮控制與仿真,2008,30(1):32-34.

The Optimal Path Planning Method for Navy Ships Formation Cooperative Call Antisubmarine Search

ZHAO Liang, REN Yao-feng, ZHANG Xian

(Naval University of Engineering, Wuhan 430033, China)

For navy ships formation cooperative call search problem of moving target, set up and optimize multiple search path planning model, and considering the sonar searching effective width and Angle effect on detecting ability, According to the planning model, we design a genetic algorithm with adaptive population co-evolution, more use of competitive exclusion principle guiding multiple populations, maintain differentiation between the various groups and the overall coordination and orderly, to improve the search efficiency, Through classification and within the population evolution selection, adaptive crossover and targeted mutation improved genetic operation, ensure the spread of dominant genes, and accelerate the convergence speed, dynamically adjust the balance of the global search and local search, avoid evolved into local optimum, Based on the direction of the unknown target motion of collaborative search example simulation, obtained the collaborative search optimal path, compared with conventional call search methods show that the method in terms of global optimization and search efficiency has some advantages, is suitable for solving the formation cooperative call antisubmarine search problem.

formation cooperative; antisubmarine search; path planning; cooperative evolution; adaptive genetic algorithm

2016-11-03

2016-12-07

趙 亮(1987-),男,湖北武漢人,碩士研究生,研究方向?yàn)檐娛孪到y(tǒng)建模與運(yùn)籌決策。 任耀峰(1959-),男,博士,碩士生導(dǎo)師。 張 獻(xiàn)(1990-),男,博士研究生。

1673-3819(2017)02-0024-07

TJ83；E

A

10.3969/j.issn.1673-3819.2017.02.006