周　凱　姜文志　陳鄧安

(海軍航空工程學(xué)院　煙臺　264001)

?

基于多種群遺傳算法的直升機編隊目標(biāo)分配*

周凱姜文志陳鄧安

(海軍航空工程學(xué)院煙臺264001)

針對多直升機目標(biāo)分配問題,提出了一種基于多種群遺傳算法的多直升機目標(biāo)分配方法。多種群遺傳算法根據(jù)多直升機目標(biāo)分配問題的特點,設(shè)計了競爭算子和遷移算子,加強了個體與群體中最優(yōu)個體進行信息交換,實現(xiàn)多種群的協(xié)同進化的同時有效避免陷入局部最優(yōu),較為顯著地提升了原算法的性能。仿真結(jié)果表明:多種群遺傳算法能夠有效解決多約束條件下多直升機目標(biāo)分配問題,并且算法簡單、靈活,易于實現(xiàn)和擴展。

多直升機協(xié)同; 目標(biāo)分配; 多種群遺傳算法

Class NumberV271.4; TP202

1　引言

直升機所具有的超機動和低空飛行的能力,適宜低空或者超低空作戰(zhàn)。作為打擊地(海)面和超低空中各種目標(biāo)的主要裝備,同時也是支援地(海)面和空中力量的重要保障,其主要作戰(zhàn)方式是對面進行攻擊[1]。在直升機作戰(zhàn)應(yīng)用中,直升機不僅僅以一個獨立的個體存在于戰(zhàn)場,而在大多數(shù)情況下,是以編隊的形式出現(xiàn)。本文在研究直升機編隊對海面多目標(biāo)攻擊問題時,與傳統(tǒng)一對一相比,最顯著的差別就是面對多個敵方目標(biāo)需要根據(jù)我方資源為編隊成員分配目標(biāo),主要考慮多個直升機之間如何進行沖突消解,有效并快速地完成多機多目標(biāo)分配問題[2～3]。

神經(jīng)網(wǎng)絡(luò),蟻群算法,粒子群算法等多種人工智能方法在協(xié)同目標(biāo)分配決策領(lǐng)域有著非常好的應(yīng)用前景。文獻[4]中建立了較為一般化的防空火力分配的數(shù)學(xué)模型,并重新推敲了約束條件,設(shè)計了較為具體合適的遺傳算法,并通過仿真實現(xiàn)了目標(biāo)分配,得到了較優(yōu)的結(jié)果,但數(shù)據(jù)量增大時,有可能出現(xiàn)早熟現(xiàn)象或者求解速度過慢甚至陷入停滯[4]。在傳統(tǒng)算法中嵌入新的機制作為提高算法優(yōu)化性能的一個重要且有效的途徑,開發(fā)和應(yīng)用實踐表明,并行遺傳算法都能不同程度地達到這要求。文獻[5]通過隨機和人為構(gòu)造了種群,獨自進行遺傳操作,考慮到染色體的多樣性,每個處理器都將自己最好的個體傳送個相鄰,相比基本遺傳算法優(yōu)勢明顯,能夠使解空間很好的脫離早熟,得到最優(yōu)解,但當(dāng)規(guī)模擴大,復(fù)雜度增加時,其設(shè)計的遺傳算法求解過程中求解時間較長[5]。為此,通過對復(fù)雜環(huán)境約束下的任務(wù)環(huán)境研究多機多目標(biāo)分配問題分析,同時考慮到對尋優(yōu)能力和快速性的雙重要求,本文使用多種群遺傳算法,在進化過程中增加了較好個體在群體中的傳播,同時降低傳輸數(shù)據(jù)傳輸消耗,提高收斂速度和解的精度[6～8]。適宜應(yīng)用到多機編隊對水面快速目標(biāo)打擊的目標(biāo)分配問題中。

2　直升機編隊作戰(zhàn)問題描述

2.1作戰(zhàn)流程

直升機作戰(zhàn)的基本流程是:收到敵目標(biāo)情報→目標(biāo)探測→數(shù)據(jù)處理(建立敵我態(tài)勢圖)→目標(biāo)分配→方案制定→作戰(zhàn)實施→打擊效果評估,滿足打擊要求則執(zhí)行其他任務(wù),否則重新進行威脅判斷并進行目標(biāo)分配,繼續(xù)打擊。

根據(jù)直升機作戰(zhàn)任務(wù)的流程分析,編隊協(xié)同攻擊的作戰(zhàn)關(guān)系圖如圖1所示。

圖1　編隊作戰(zhàn)關(guān)系圖

2.2作戰(zhàn)收益函數(shù)的構(gòu)造

為了便于目標(biāo)分配后續(xù)的量化計算,首先應(yīng)該確定敵我相對作戰(zhàn)能力。為此,通過以下的我機作戰(zhàn)能力、優(yōu)勢度函數(shù)、快艇作戰(zhàn)能力、目標(biāo)相對價值來確定總的我相對敵作戰(zhàn)收益函數(shù)值。

1) 直升機作戰(zhàn)能力

直升機攻擊能力由航程指數(shù)和武器效能指數(shù)兩部分組成。兩者相加得出的總值。航程指數(shù)是當(dāng)量航程的自然對數(shù),武器效能指數(shù)是當(dāng)量載彈量的自然對數(shù)。主要影響因素最大航程、突防系數(shù)、遠程武器系數(shù)、導(dǎo)航能力系數(shù)和最大載彈量和對地攻擊效率系數(shù)[9]。計算公式如下:

ZF=[ln(N)+ln(M)]ε1ε2

(1)

N=R×Re×Rm×Rn

(2)

M=WB×Pa

(3)

式中N為當(dāng)量航程,M為當(dāng)量載彈量,ε1為電子對抗系數(shù),ε2為探測能力系數(shù),R為最大航程、Re為突防系數(shù)、Rm為遠程武器系數(shù)、Rn為導(dǎo)航能力系數(shù)、WB為最大載彈量和Pa對面攻擊效率系數(shù)由于作戰(zhàn)能力指數(shù)與優(yōu)勢度指數(shù)差距比較大,需要對其進行處理,這里取直升機作戰(zhàn)能力所占比重:

Li=ZFi/max(ZFi) (1≤i≤n)

(4)

2) 直升機優(yōu)勢度分析

直升機在執(zhí)行打擊過程中,編隊成員會耗費自身資源的同時,還會受到來自地面目標(biāo)的攻擊。在打擊過程中,直升機暴露在目標(biāo)區(qū)域內(nèi),直升機能夠成功打擊目標(biāo)不僅與編隊成員的自身狀態(tài)有關(guān),同時與每一架直升機的態(tài)勢有關(guān),如位置、速度與目標(biāo)距離;相對于打擊目標(biāo)的優(yōu)勢越好,則成功摧毀目標(biāo)而保存自己的可能性越大。單純考慮直升機和地面目標(biāo)的毀傷能力是不實際的,只能單純的給出毀傷值的累加。因此,在模型中引入優(yōu)勢函數(shù)S,它主要由相對距離優(yōu)勢Dij、相對速度優(yōu)勢Vij和相對角度優(yōu)勢Tij共同決定。理論分析和實戰(zhàn)經(jīng)驗都表明:在具有角度優(yōu)勢的情況下,相對距離越大優(yōu)勢越小;距離越小,距離優(yōu)勢越大[10]。因此,角度優(yōu)勢和距離優(yōu)勢宜處理為相乘關(guān)系:

Sij=β1Vij+β2Dij×Tij

(5)

其中,β1、β2為權(quán)系數(shù)(0≤β1、β2≤1),具體的計算方法可借鑒文獻[1,11]。

3) 快艇作戰(zhàn)能力

將快艇作戰(zhàn)效能作為總目標(biāo),結(jié)合快艇的系統(tǒng)特點,主要由四個方面組成偵查探測能力、作戰(zhàn)指揮能力、武器系統(tǒng)能力、本艇生存能力。

ZM=Ef×Ep×Et×Em

(6)

式中ZM表示快艇作戰(zhàn)能力,Ef表示偵查探測能力指數(shù),Ep表示快艇作戰(zhàn)指揮能力指數(shù),Et表示本艇生存能力指數(shù),Em表示武器系統(tǒng)能力指數(shù)(主要考慮艦炮對直升機的毀傷能力)。

4) 目標(biāo)相對價值評估

導(dǎo)彈快艇目標(biāo)價值評估主要來源于上一級指揮信息,主要考慮到導(dǎo)彈快艇對艦艇編隊成員的威脅,選用以下幾個因素來描述武器系統(tǒng)能力:導(dǎo)彈射程因素Rp;制導(dǎo)能力Gp;殺傷能力系數(shù)Yp;數(shù)量指數(shù)N[12]。因此,水面快艇對艦船的威脅指數(shù)計算模型可表示為

(7)

同時指揮艦更傾向于具有成功打擊目標(biāo)能力的直升機去攻擊敵快艇解除威脅,構(gòu)造期望權(quán)重矩陣Wij,目標(biāo)相對價值Qij為

Qij=Wij×Edj

最后,直升機得到的相對于目標(biāo)的作戰(zhàn)能力效益值為

Fij=α1(LiSij/ZMj)+α2Qij

(8)

其中,α1、α2為權(quán)系數(shù)(0≤α1、α2≤1)。

則總的作戰(zhàn)能力效益值為

(9)

3　多種群遺傳算法目標(biāo)分配研究

3.1目標(biāo)分配的數(shù)學(xué)模型

基于作戰(zhàn)效益函數(shù),可構(gòu)造直升機編隊目標(biāo)分配問題模型如下:

(10)

相應(yīng)的約束條件:

目標(biāo)分配時,每個目標(biāo)均須分配一架直升機對其進行打擊,即

對編隊中的每一架直升機,至少給其分配一個地面目標(biāo),即

由于單架直升機配置的武器數(shù)量有限,且為保證直升機在目標(biāo)區(qū)域內(nèi)滯留的時間不至于過長,要求每架直升機攻擊的目標(biāo)的個數(shù)不能超過某個值[13],記各架直升機可攻擊的目標(biāo)的最大個數(shù)所組成的向量B=[b1b2…bn-1],則有

3.2單種群遺傳算法

遺傳算法(Genetic Algorithm,GA)是一種進化算法,通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿,來完成對問題最優(yōu)解的自適應(yīng)搜索過程[14]。遺傳算法是通過給解向量編碼、形成初始種群,然后用變異、交叉重組、自然選擇等算子,進行反復(fù)迭代,最終求得最優(yōu)解。GA算法的主要步驟如下:

1) 構(gòu)造染色體

遺傳算法編碼方式采用二進制編碼,利用長度為n×m的一維數(shù)組來表示矩陣Xn×m該數(shù)組可平均分成m段,每段都表示每一直升機所分配的目標(biāo)的情況,1表示該目標(biāo)被分配到此直升飛機去攻擊,0表示該目標(biāo)沒有被分配到此直升飛機。

2) 個體適應(yīng)度評價

3) 遺傳算子

選擇操作主要建立在對個體的適應(yīng)度進行評價的基礎(chǔ)之上。操作的主要目的是為了避免基因缺失、提高全局收斂性和計算效率。最常用的選擇算子是基本遺傳算法中的比例算子。交叉運算是遺傳算法中產(chǎn)生新個體的主要操作過程,它以某一概率相互交換某兩個個體之間的部分染色體。其具體操作過程是:先對群體進行隨機配對;其次隨機設(shè)置交叉點位置,其中的數(shù)字表示交叉點設(shè)置在該基因座之后;最后再相互交換配對染色體之間的部分基因。變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進行改變,它也是產(chǎn)生新個體的一種操作方法,首先確定出各個個體的基因變異位置,然后按照某一概率將變異點的原有基因支取反。

群體規(guī)模和遺傳控制參數(shù)的設(shè)定均對GA算法的優(yōu)化性能有較大的影響。當(dāng)群體規(guī)模較小時,群體中的多樣性程度降低,個體競爭性比較弱,隨著進化的進行,群體很快趨于單一化,交叉操作產(chǎn)生新個體的作用漸趨消失,群體的更新只靠變異操作來維持,群體很快終止進化;當(dāng)群體規(guī)模取值較大時,勢必造成計算量的增加。遺傳控制參數(shù)的設(shè)定涉及GA算法全局搜索和局部搜索能力的均衡,不恰當(dāng)?shù)脑O(shè)定很容易產(chǎn)生早熟、局部尋優(yōu)能力較差等現(xiàn)象。

3.3多種群遺傳算法

為了克服基本遺傳算法所存在的上述問題,避免算法陷入局部最優(yōu)解,引入多種群遺傳算法進行改進,通過遷移算子[15]進行聯(lián)系,實現(xiàn)多種群的協(xié)同進化,綜合結(jié)果獲取最優(yōu)解。由于控制參數(shù)的設(shè)定在很大程度上影響算法的性能,各個種群取不同的控制參數(shù),通過多個設(shè)有不同控制參數(shù)的種群協(xié)同進化,同時兼顧了算法的全局搜索和局部搜索。同時借助遷移算子把相對獨立的種群聯(lián)系起來,在進化過程中,把最優(yōu)個體定期地引入其他種群,實現(xiàn)了種群之間的信息交互,保證了種群的多樣性。個體自身進化修正策略的引入,各個個體分別與周邊個體進行競爭與合作操作,在保留自身原本有用信息的基礎(chǔ)上吸收最優(yōu)鄰居個體的有益信息,以實現(xiàn)有益信息在種群中的流動[16]。精華種群是在進化的每一代,通過人工選擇算子選出其他種群的最優(yōu)個體放入精華種群加以保存。算法結(jié)構(gòu)圖如圖2所示。

圖2　多種群遺傳算法結(jié)構(gòu)圖

3.4多種群算法描述

步驟1:遺傳代數(shù)計數(shù)器初始化:gen←0,種群數(shù)目:MP。

步驟2:隨機初始化群P1(t),P2(t),…,PMP(t)。

步驟3:分組計算各Pi(t)(i=1,2,…,MP)中個體的適應(yīng)度。

由變異算子進行變異操作:

P?i(t)←Mutate[P″i(t)]

步驟5:交叉和變異采用如下公式隨機產(chǎn)生,從而保證MP個種群在不同的控制參數(shù)下協(xié)同進化在同步進化分組計算各P?i(t)(i=1,2,…,MP)中個體的適應(yīng)度。

Pc=0.7+(0.9-0.7)*rand(MP,1)

Pm=0.001+(0.05-0.001)*rand(MP,1)

步驟6:通過遷移算子immigrant把目標(biāo)種群最劣的個體替換為源種群最優(yōu)種群。

步驟7:人工選擇算子將各種群最優(yōu)個體存入精華種群。

步驟8:根據(jù)競爭算子,由周邊個體進行競爭與合作操作,并記錄更新各自適應(yīng)度。假設(shè)Q?ik(t)為第i個種群個體P?ik(t)的幾個鄰居中擁有最大適應(yīng)值的個體,P?ik(t)在解空間的位置根據(jù)

P?ik(t)′=Q?ik(t)+rand(-1,1)(Q?ik(t)-P?ik(t))

i=1,2,…,MP

進行調(diào)整。k為每個種群中的個體數(shù)。

步驟9:終止條件判斷:若不滿足條件,則gen←gen+1,轉(zhuǎn)向步驟4;若滿足終止條件,則:輸出優(yōu)化結(jié)果,算法結(jié)束。

3.5實例驗證

為了測試算法的性能,以直升機編隊對海面敵快艇進行打擊的目標(biāo)分配問題為研究對象進行仿真實驗。想定直升機編隊共有5架直升機,面臨敵5個水面目標(biāo),這5個目標(biāo)對編隊的威脅程度和收益值各不相同。根據(jù)直升機作戰(zhàn)收益定義,計算得到直升機作戰(zhàn)能力的相對比重如表1所示。優(yōu)勢度以及水面目標(biāo)參數(shù)見表2～表4。

表1　直升機作戰(zhàn)能力

表2　直升機相對于目標(biāo)的優(yōu)勢度

表3　快艇作戰(zhàn)能力

表4　目標(biāo)相對價值

取種群規(guī)模N=5,種群數(shù)量MP=5,保持最優(yōu)值代數(shù)MAXGEN=30,交叉和變異概率分別在(0.7～0.9)和(0.001～0.05)隨機取得的,而基本遺傳算法采用種群規(guī)模25,進化代數(shù)30,交叉和變異分別為0.9和0.05控制參數(shù)。通過Matlab進行仿真驗證,最優(yōu)目標(biāo)分配方案對應(yīng)的最大收益值為:8.7766,對應(yīng)的自變量取值:25431,即分配矩陣為

對比仿真結(jié)果,可以看出兩種算法,均能收斂到最優(yōu)的目標(biāo)函數(shù),但本文提出的多種群遺傳算法收斂速度比基本遺傳算法要快,平均在第6次迭代時達到最大收益值,而基本遺傳算法需要13次迭代,如圖3所示。雖然該算法融入新的機制在時間消耗方面有所增多,但在權(quán)衡尋優(yōu)效率與尋優(yōu)結(jié)果精度的基礎(chǔ)上,本文提出的多種群遺傳算法應(yīng)用到目標(biāo)分配在計算效率上有優(yōu)勢。

圖3　兩種算法的收斂速度比較

4　結(jié)語

本文首先分析了直升機作戰(zhàn)過程,結(jié)合影響直升機對地作戰(zhàn)的主要因素,建立了相應(yīng)的數(shù)學(xué)模型,利用具有自適應(yīng)全局搜索能力的遺傳算法來解決直升機編隊目標(biāo)分配問題。針對遺傳算法局部搜索能力弱的缺點,引入多種群遺傳算法能夠更快地尋求到全局最優(yōu)值,從而提高了遺傳算法的收斂速度和解的精度。算法實例表明,基于多種群遺傳算法搜索能力好,收斂速度快,能夠保證直升機對水面快速目標(biāo)的打擊。

[1] 麻士東,龔光紅,等.目標(biāo)分配的蟻群_模擬退火算法及其改進[J].系統(tǒng)工程與電子技術(shù),2011,33(5):1183-1186.

MA Shidong, GONG Guanghong, et al. Hybrid srtatagy with ant colony and simulated annealing algorithm and its improvement in target assignment[J]. Systems Engineering and Electronics,2011,33(5):1183-1186.

[2] 浦鵬,張金春,孫喜菁.多機協(xié)同多目標(biāo)分配戰(zhàn)術(shù)決策研究[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù),2007(2):57-61.

PU Peng, ZHANG Jinchun, SUN Xijing. The study of tactical decision of multi-target distribution in cooperative air combat[J]. Tactical Missile Technology March,2007(2):57-61.

[3] Liu Y F, Zhang A. Cooperative task assignment method of manned/unmanned aerial vehicle formation[J]. Systems Engineering and Electronics,2010,32(3):584-588.

[4] 季大琴.艦艇編隊防空火力基于遺傳算法的分配方案[J].軍事運籌與系統(tǒng)工程,2007,21(1):37-40.

JI Daqin. Warship fomation air defense weapon-target assignment based on genetic algorithm[J]. Militrary Operations Research and Systems Engineering,2007,21(1):37-40.

[5] 季大琴,宋劍,范婷婷.基于并行遺傳算法的艦艇編隊防空火力分配方案[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報,2011,27(1):58-60.

JI Daqin, SONG Jian, FAN Tingting. Warship fomation air defense weapon-target assignment based on parallel genetic algorithm[J]. Natural Seiences Journal of Harbin Normal University,2011,27(1):58-60.

[6] Min C P, Shen L C. Hybrid genetic algorithem and constraint handling formultiple UCAV mission assigning[J]. Control and Decision,2006,21(7):781-786.

[7] Ye W, Zhu A H, Pan C P, et al. Cooperation mission assignment algorithm for multi-UCAV[J]. Systems Engineering and Electronics,2010,32(1):104-108.

[8] 任少偉,賀正洪,劉進忙.基于改進遺傳算法的防空火力優(yōu)化分配方法[J].火力控制與指揮,2004,29(3):81-84.

REN Shaowei, HE Zhenghong, LIU Jinmang. The optimized distribution Method of the anti-air fire based on the improved genetic algorithm[J]. Fire Control & Command Control,2004,29(3):81-84.

[9] 宋筆鋒,劉曉東,等.作戰(zhàn)飛機方案和關(guān)鍵技術(shù)的決策理論與方法[M].北京:國防工業(yè)出版社,2010:60-65.

SONG Bifeng, LIU Xiaodong, et al. Combat aircraft scheme and technology of decsion theory and method[M]. Beijng: National Defence Industry Press,2010:60-65.

[10] 王宏論.多機空戰(zhàn)模擬系統(tǒng)研究[D].西安:西北工業(yè)大學(xué),1995:25-35.

WANG Honglun. Research on simulation system of air combat[D]. Xi’an: Northwestern Polytechnical University,1995:25-35.

[11] 王強,丁全心,張安,等.多機協(xié)同對地攻擊目標(biāo)分配算法[J].系統(tǒng)工程與電子技術(shù),2012,34(7):1400-1405.

WANG Qiang, DING Quanxin, ZHANG An, et al. Target allocation algorithm for multi-cooperative air-groubd attack[J]. Systems Engineering and Electronics,2012,34(7):1400-1405.

[12] 甄濤,王平均,張新民.地地導(dǎo)彈武器作戰(zhàn)效能評估方法[M].北京:國防工業(yè)出版社,2005:52-54.

ZHEN Tao, WANG Pingjun, ZHANG Xinmin. Missile combat effectiveness evaluation method[M]. Beijng: National Defence Industry Press,2005:52-54.

[13] 曾國貴,姜長生.武裝直升機空戰(zhàn)關(guān)鍵技術(shù)問題研究[J].直升機技術(shù),2002(3):29-32.

ZENG Guogui, JIANG Changsheng. Research of Key Technical Problems About Attack Helicopter Air-combat[J]. Helicopter Technique,2002(3):29-32.

[14] 梁旭,黃明.現(xiàn)代智能優(yōu)化算法及其應(yīng)用[M].北京:電子工業(yè)出版社,2012:35-43.

LIANG Xu, HUANG Ming. Modern intelligent optimization algorithm and application[M]. Beijing: Electronic Industry Press,2012:35-43.

[15] 史峰,王輝,等.MATLAB智能算法[M].北京:北京航空航天大學(xué)出版社,2011:69-70.

SHI Feng, WANG Hui. MATLAB intelligence algorithm[M]. Beijing: Beijing University of Aeronautics and Astronautics Press,2011:69-70.

[16] Zhao B, Guo C X, Cao Y J. A multiagent-based particle swarm optimization approach for optimal reactive power dispatch[J]. IEEE Transactions on Power Systems,2005,20(2):1070-1078.

Target Assignment of the Helicopter Fleet Based on Multiple Population Genetic Algorithm

ZHOU KaiJIANG WenzhiCHEN Dengan

(Naval Aeronautical and Astronautical University, Yantai264001)

A multiple population genetic algorithm(MPGA) was put forward for multi-helicopter cooperation target assignment problem. In the algorithm, adopting immigration operator and competition operator was applied so as to make the MPGA more suitable for multi-helicopter cooperation target assignment problem. Aiming at the shorting of premature and poor resulted from pure GA, the algorithm performance was enhance observably by enhancing interactive between individual and superior individual and achieve carrying out being in conjunction with of various populations evolution. The simulated results show that the MPGA algorithm can solve multi-helicopter cooperation target assignment effectively, which was simple, flexible and easy to implement and expand.

multi-helicopter cooperation, multiple population genetic algorithm, target assignment

2016年3月17日,

2016年4月21日

周凱,男,碩士研究生,研究方向:計算機應(yīng)用。姜文志,男,教授,博士生導(dǎo)師,研究方向:計算機應(yīng)用、武器裝備與作戰(zhàn)指揮一體化。陳鄧安,男,副教授,研究方向:兵種戰(zhàn)術(shù)指揮。

V271.4; TP202DOI:10.3969/j.issn.1672-9722.2016.09.015