基于帶精英策略遺傳算法的艦艇編隊目標分配*

牛曉博,陳新來,朱飛,方群

(海軍蚌埠士官學校,安徽 蚌埠 233012)

基于帶精英策略遺傳算法的艦艇編隊目標分配*

牛曉博,陳新來,朱飛,方群

(海軍蚌埠士官學校,安徽 蚌埠 233012)

結(jié)合現(xiàn)代海戰(zhàn)海軍編隊作戰(zhàn)樣式及作戰(zhàn)武器的特點，建立了新的艦艇編隊武器分配模型，將艦艇編隊目標分配問題抽象化為多目標優(yōu)化問題，該模型可以在保證我方重點目標得到保護的前提下，達到總體效果最優(yōu)和總體耗損最小。采用帶精英策略的快速非支配進化算法對艦艇編隊目標分配問題進行求解。該算法求得的Pareto最優(yōu)解分布均勻，收斂性和魯棒性好。該算法一次運行可以獲得多個Pareto最優(yōu)解，決策者可以根據(jù)實際戰(zhàn)場環(huán)境選擇最終滿意解，為各目標函數(shù)之間的均衡分析提供了有效的工具。最后，通過仿真及與其他算法的對比證明了模型及算法的有效性。

艦艇編隊；目標分配；帶精英策略的快速非支配進化算法；多目標優(yōu)化

0 引言

目標分配是艦艇編隊進行區(qū)域作戰(zhàn)的核心內(nèi)容，構(gòu)建科學合理的目標分配模型及尋找相應(yīng)的求解方法成為研究熱點。解決武器目標分配問題(weapon-target assignment,WTA)的方法是將其歸結(jié)為一個純整數(shù)規(guī)劃問題，理論上講，這類問題的解總可以通過枚舉的方法找到。這意味著以枚舉為基礎(chǔ)發(fā)展進來的分枝定界法、割平面法等傳統(tǒng)方法具有普遍性。但將武器目標分配問題抽象為純整數(shù)規(guī)劃問題采用傳統(tǒng)方法求解，計算時間一般為輸入數(shù)據(jù)量的指數(shù)函數(shù)。隨著戰(zhàn)爭復雜性的增加，戰(zhàn)場目標空前復雜，計算時間會迅速增加到現(xiàn)代計算工具難以承受的地步。現(xiàn)代海戰(zhàn)中艦艇以編隊形式進行作戰(zhàn)成為主要作戰(zhàn)樣式，艦艇的武器裝備也由單通道發(fā)展到多通道，因此艦艇編隊目標分配問題具有自身顯著的特點。對WTA問題的的研究集中在模型研究以及模型的算法研究2個方面。文章針對海戰(zhàn)場艦艇編隊作戰(zhàn)及艦艇作戰(zhàn)武器的特點，建立了新的目標分配模型，采用改進的NSGA算法，即帶精英策略的快速非支配遺傳算法解決艦艇編隊目標分配問題。

1 問題的描述

以往解決目標分配問題，大多通過加權(quán)相加轉(zhuǎn)化為單目標最優(yōu)化問題[1-4]。這樣的目標分配模型可能得到這樣的解，我方火力打擊敵方使我方可以獲得較大收益，但我方也損失慘重，出現(xiàn)兩敗俱傷的局面。在現(xiàn)代戰(zhàn)爭條件下，不僅要打擊敵方目標更要保存自己的實力。因此，目標火力分配問題不僅要使我方的效益最大，對我方重點目標保護最大，我方耗損最小等因素。艦艇編隊作戰(zhàn)更是如此，這樣目標分配問題便抽象為多目標優(yōu)化問題。

1.1 艦艇編隊目標分配問題

紅方m個艦艇組成的編隊(m個火力單元組成的火力單元集)對藍方n批目標進行攔擊。由于目前武器系統(tǒng)采用多通道技術(shù)，因此，一個火力單元可以對多批目標進行射擊。假設(shè)目標分配之前，紅方艦艇編隊每一個火力單元的火力指數(shù)，對藍方各目標的攻擊有利程度，藍方各批目標的價值、目標的威脅度已經(jīng)經(jīng)過評估和排序，并且各火力單元的彈藥儲備量是充足的。如何進行目標分配以充分發(fā)揮紅方的火力優(yōu)勢以達到最佳的作戰(zhàn)效果，就是艦艇編隊目標分配問題。

1.2 艦艇編隊目標分配原則

艦艇編隊目標分配模型需要綜合考慮各因素以達到全局最優(yōu)并不應(yīng)局限于單目標最優(yōu)[5]。目標分配時應(yīng)能充分發(fā)揮各火力單元的整體協(xié)調(diào)優(yōu)勢，尋求對敵方打擊效果最大，己方重點目標保護度最大并且耗損最小等。因此，可以考慮艦艇編隊目標分配方案滿足以下基本原則：

(1) 對敵方目標打擊最大；

(2) 對我方重要目標的保護度最大；

(3) 我方打擊敵方耗損最小。

對該問題進行數(shù)學建模，可將艦艇編隊WTA問題建模為如下多目標優(yōu)化問題：

(1)

(2)

2 遺傳算法求解目標分配問題

S.P.Lloyd(1986)等人證明了WTA問題是NP完全問題[6]，要求其最優(yōu)解必須采用完全枚舉法，所需要的時間將隨著問題規(guī)模的增加而呈指數(shù)增長，WTA問題本身的數(shù)學性質(zhì)表明，求解WTA問題的最優(yōu)解是不現(xiàn)實的，只能求其滿意解或次優(yōu)解。WTA問題算法研究內(nèi)容主要有傳統(tǒng)算法(包括隱枚舉法、分支定界法、割平面法、動態(tài)規(guī)劃法等)、智能算法(包括禁忌搜索算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法及遺傳算法等)、混合算法等。

遺傳算法用于求解WTA問題，可以較快收斂到目標值。傳統(tǒng)遺傳算法并不能很好解決多目標優(yōu)化問題，它只是簡單將多目標按權(quán)值合成，本質(zhì)上仍然是求解單目標優(yōu)化問題。近年來，多目標進化算法領(lǐng)域出現(xiàn)了許多新的算法[7-10],由于可以在一個進化代中得到多個不同的Pareto優(yōu)化解，多目標進化算法在多個目標優(yōu)化領(lǐng)域已成為一個新的研究熱點。文獻[11]提出非支配遺傳算法NSGA(non-dominated sorting genetic algorithm)，把非支配排序的概念引入多目標優(yōu)化領(lǐng)域，在很多方面得到了應(yīng)用，并取得了較好的效果。但NSGA存在計算復雜性高，缺乏精英策略，需要特別指出共享半徑等問題。采用帶精英策略的快速非支配遺傳算法解決艦艇編隊WTA問題根據(jù)非支配關(guān)系和擁擠度排序選擇適應(yīng)度最高的個體組成父輩群體，可以不用指定共享半徑，而NSGA中共享半徑的指定是困難的。通過算例可以看到，該算法可以得到分布更加均勻的Pareto最優(yōu)解。

2.1 帶精英策略的快速非支配遺傳算法

帶精英策略的快速非支配遺傳算法的基本思想為：首先，隨機產(chǎn)生規(guī)模為N的初始種群，非支配排序后通過遺傳算法的選擇、交叉和變異3個基本操作得到第1代子代種群；其次，從第2代開始，將父代種群與子代種群合并，進行快速非支配排序，同時，對每個非支配層的個體進行擁擠度計算，根據(jù)非支配關(guān)系，以及個體的擁擠度選取合適的個體，組成新的父代種群；最后，通過遺傳算法基本操作產(chǎn)生新的子代種群；依次類推，直到滿足程序結(jié)束的條件。帶精英策略的快速非支配遺傳算法的流程圖如圖1。

圖1 FENSGA流程圖Fig.1 Flow chart of FENSGA

(1) 快速非支配排序

在快速非支配排序方法中，對每一個個體需要計算兩個參數(shù)。群體中支配個體i的個體的數(shù)量ni和被個體i所支配的個體的集合Si

設(shè)群體集合為P，快速非支配排序的偽代碼如下：

For eachp∈P

For eachq∈P

Ifp

Else ifq

np=np+1

Ifnp=0,then

i=1

WhileF1≠φ

H=φ

For eachp∈Fi

For eachq∈Si

nq=nq-1

Ifnq=0,then

H=H∪{q}

i=i+1

Fi=H

在Fi中的個體具有非支配序i。

(2) 擁擠度計算

擁擠度的計算能夠確保算法能收斂到一個均勻分布的Pareto曲面。需要對Fi中的每一個個體，計算擁擠度。

擁擠度計算的偽代碼如下：

Initializationid(d)=0

For each objective function m

i=sort(i,m)

令邊緣個體id(d1)=∞，id(dn)=∞

Fork=2 to (n-1)

End for

End for

其中，id(k).m為第k個個體的第m個目標函數(shù)值。

由此可見，擁擠度是通過計算與指定個體相鄰的兩個個體間目標函數(shù)的距離來評估種群在指定個體處的密集程度，這個距離越大，表示在該個體處種群的分布越稀疏，越有利于保持種群的多樣性、防止個體在局部堆積[12]。基于擁擠度的選擇方法可自動調(diào)整小生境，使計算結(jié)果在目標空間比較均勻地散布，具有較好的魯棒性。由于邊緣個體的擁擠度被定義為無窮，因此邊緣個體經(jīng)常被選擇。

(3) 適應(yīng)度排序

經(jīng)過非支配排序和擁擠度計算，群體中每個個體i都有兩個屬性：非支配序ir和擁擠度id。

則定義適應(yīng)度關(guān)系≥n為：i≥nj，如果irjd，表示如果2個個體的非支配序不同，序號低的個體適應(yīng)度高；如果兩個個體在同一非支配序，周圍不擁擠的個體適應(yīng)度高。

2.2 帶精英策略的快速非支配遺傳算法求解艦艇編隊目標分配問題

(1) 編碼生成

編碼可以實現(xiàn)問題空間(候選解空間)向遺傳空間的映射[13]。FENSGA解決武器分配問題染色體采用十進制編碼，染色體的長度由按目標批次編號順序排列的火力單元分配編號，表示一種可能的分配方案。即編碼向量F，F(xiàn)(i)=j,1≤i≤n,1≤j≤m,表示第j個火力單元用于對目標i進行射擊。

(2) 初始群體確定

根據(jù)艦艇編隊目標分配問題模型可以發(fā)現(xiàn)，并不是所有隨機生成的個體都是有效的。根據(jù)約束條件式(2)可知，分配方案需要滿足給某一個火力單元分配的目標總數(shù)應(yīng)小于該火力單元的武器通道數(shù)。因此，需要對每個隨機生成的個體進行判斷，若可以滿足約束條件，則該個體為有效個體。

(3) 適應(yīng)度評估

首先用約束條件對染色體進行初步篩選，令不滿足約束條件的染色體適應(yīng)度為0，然后通過目標函數(shù)對選出的染色體進一步篩選。FENSGA的快速非支配排序和擁擠度算子避免了多目標函數(shù)在選擇上優(yōu)先級的確定。

(4) 選擇

根據(jù)快速非支配排序的結(jié)果和擁擠度算子的大小，用錦標賽的方法進行選擇。即隨機地在群體中選擇k個個體進行比較，適應(yīng)度值最好的個體將被選擇作為生成下一代的父輩，常用二元錦標賽選取，即k=2。這種選擇方式也使得適應(yīng)度較好的個體有較大的生存機會，它只將適應(yīng)度值的相對值作為選擇標準，而與適應(yīng)度值的絕對大小不成直接比例，能夠避免超級個體的影響，在一定程度上避免過早收斂現(xiàn)象和停滯現(xiàn)象的產(chǎn)生。

經(jīng)過錦標賽選擇產(chǎn)生子代個體，將子代個體與父輩個體合并，根據(jù)快速非支配排序和擁擠度算子，選出最優(yōu)的N個個體。

(5) 交叉

對通過選擇的群體，進行概率為Pc的交叉。交叉分兩個步驟：隨機配對、隨機設(shè)定交叉處。交叉可以使配對的兩個個體交換部分信息。例如艦艇編隊目標分配問題中2個配對個體為：P1=2335|47561，P2=1223|54767，其中豎線后面為交叉部分。則交叉后的子代個體為：C1=2335|54767，C2=1223|47561。

(6) 變異

求解目標分配問題時采用自適應(yīng)變異概率，自適應(yīng)變異概率可以減少破壞群體中原有的最優(yōu)解的概率，當算法接近最優(yōu)解時，防止過高的變異概率使最優(yōu)解破壞[14]。

自適應(yīng)變異概率公式為

(3)

式中：Pm為變異概率；fmax為群體中目標函數(shù)最大值；favg為群體目標函數(shù)平均值；f為要變異的個體目標函數(shù)值；Pm1，Pm2為常數(shù)，可取Pm1=0.2，Pm2=0.1。

變異函數(shù)為

(4)

(5)

其中，rk為(0,1)之間的隨機值；ηm為變異常數(shù)，文中取ηm=20。

(7) 算法的終止

FENSGA解決目標分配問題時由于很難找到一個關(guān)于種群中最優(yōu)個體的指標，因此，F(xiàn)ENSGA解決目標分配問題采用設(shè)定代數(shù)的方法來終止遺傳算法的運行。

3 應(yīng)用實例及結(jié)果分析

3.1 應(yīng)用實例

為驗證模型的合理性及算法的可行性，仿真實例選用海軍某次演習中，在某海域的作戰(zhàn)單位進行目標分配。紅方有8艘艦艇組成的艦艇編隊，藍方有15批目標，其中1～5批為水面目標，6～12批為空中目標，13～15批為水下目標。目標分配任務(wù)為為每條艦艇進行目標分配。紅方第2艘艦艇為編隊旗艦，需要重點保護。分配結(jié)果要使紅方打擊藍方的效益最大、對重點保護的第2艘艦艇的保護度最大同時紅方耗損最小；各種數(shù)據(jù)由歷史經(jīng)驗或艦艇指控系統(tǒng)通過解算得到，數(shù)據(jù)最后匯總至編隊旗艦，在旗艦進行目標分配解算，并將最終結(jié)果分發(fā)至相應(yīng)艦艇(由于涉及的各種數(shù)據(jù)矩陣比較龐大，數(shù)據(jù)不在文章中給出)。

3.2 結(jié)果分析

根據(jù)算法設(shè)計，編寫了帶精英策略快速非支配進化算法、并列選擇遺傳算法、目標函數(shù)按權(quán)值相加采用單目標優(yōu)化遺傳算法解決WTA問題的Matlab程序，在Intel Pentimum Dual E2140，1.6 GHz，2.0 GB的計算機上對上述實例進行仿真。運行200代，通過計算得到的Pareto面如圖2a)，b)，c)所示。

圖2 采用不同方法得到的Pareto面(迭代200次)Fig.2 Pareto surface obtained by different algorithms (iteration 200 times)

通過不同方法得到的Pareto面的比較可以看出，F(xiàn)ENSGA能夠比較容易達到每個目標的極值點，其余2種遺傳算法不能對每個函數(shù)均等對待。同時，從迭代了200次的圖象各個點的位置關(guān)系可以看到，F(xiàn)ENSGA的所有點幾乎落在Pareto面上，而其余2種遺傳算法得到的圖象點非常分散，無論如何調(diào)整視角都不能使它們落在同一個面上。

從另一個角度比較3種方法的效果，圖3所示為3個目標函數(shù)的每代平均值比較。通過比較發(fā)現(xiàn)FENSGA在目標函數(shù)1(收益函數(shù))和目標函數(shù)2(保護度函數(shù))上明顯具有優(yōu)勢，在目標函數(shù)3(耗損函數(shù))上FENSGA與并列選擇遺傳算法大致相當，并列選擇遺傳算法稍好，但FENSGA算法的總體趨勢是上升的，而權(quán)值相加遺傳算法上升速度和最終結(jié)果都要優(yōu)于其余2種算法。權(quán)值相加遺傳算法雖然在目標函數(shù)3上可以取得非常好的值，但在目標函數(shù)1和目標函數(shù)2上甚至出現(xiàn)了下降趨勢，這是因為權(quán)值相加將多目標極值問題簡化為單目標。將多個目標函數(shù)混在一起考慮，最優(yōu)解必然趨向于權(quán)值大或上升速度快的目標函數(shù)，其他函數(shù)則會被忽略。這在艦艇編隊目標分配問題上害處是非常大的，因為這樣會造成作戰(zhàn)目的的偏移，從本例講就是目標函數(shù)1和目標函數(shù)2被忽略，僅達目標函數(shù)3。即僅達到作戰(zhàn)耗損最小，而根本沒有考慮我方收益和對我方重點目標的保護作用。圖3d)為采用3種方法得到的目標函數(shù)之和比較圖，通過對比可以看到總體效果并列選擇遺傳算法和FENSGA算法大致相當，而權(quán)值相加遺傳算法得到的結(jié)果要明顯高于其他兩種方法，這是因為權(quán)值相加得到的最優(yōu)解偏重于其中某個權(quán)值比較大或上升比較快的目標函數(shù)，并沒有起到多目標優(yōu)化的作用。

圖3 各目標函數(shù)均值隨迭代次數(shù)的變化曲線Fig.3 Iterative curve of each goal function (iteration 200 times)

通過以上分析可以看到無論從最優(yōu)解的分布還是從各目標函數(shù)每代最優(yōu)解的比較來看，帶精英策略的快速非支配遺傳算法都可以比較好的解決新的艦艇編隊目標分配問題。從函數(shù)曲線的上升速率來看帶精英策略的快速非支配遺傳算法能夠在較小的迭代次數(shù)下得到較好的解，時效性強。

4 結(jié)束語

針對艦艇編隊目標分配問題和現(xiàn)代武器系統(tǒng)的特點，建立了新的目標分配模型。將傳統(tǒng)的單目標優(yōu)化變?yōu)槎嗄繕藘?yōu)化，使目標分配結(jié)果達到既能使得打擊對方目標獲得盡可能大的收益，又可以保護我方重點目標，同時耗損最小。針對建立的艦艇編隊目標分配模型，采用帶精英策略的快速非支配遺傳算法設(shè)計，提出了快速非支配排序、錦標賽選擇相結(jié)合的選擇方法，并采用自適應(yīng)變異概率，可以較好的完成艦艇編隊目標分配問題的求解，解決了以往目標分配問題采用單目標優(yōu)化的局限性。

[1] 曹奇英，何張兵.WTA問題的遺傳算法研究[J].控制理論與應(yīng)用，2001，18(1)：76-79. CAO Qi-ying,HE Zhang-bing.A Genetic Algorithm of Solving WTA Problem[J]. Control Theory & Applications,2001,18(1):76-79.

[2] 劉以安，陳松燦，王士同.分解協(xié)調(diào)法在武器目標分配問題中的應(yīng)用研究[J].應(yīng)用科學學報，2006，24(3)：262-264. LIU Yi-an, CHEN Song-can, WANG Shi-tong. Decomposition Coordination in Weapon Target Assignment Problems[J]. Journal of Applied Sciences,2006,24(3):262-264.

[3] 楊申林，王延璋，許建平.遺傳算法在多目標分配中的應(yīng)用[J].軍事運籌與系統(tǒng)工程，2007，21(1)：37-40. YANG Shen-lin,WANG Yan-zhang,XU Jian-ping. The Application of The Genetic Algorithm of in Multi-Targets Allocation[J]. Military Operations Research and Systems Engineering,2007,21(1):37-40.

[4] 羅紅英，劉進忙.遺傳算法在目標優(yōu)化分配中的應(yīng)用[J].電光與控制，2008，15(3)：18-20. LUO Hong-ying,LIU Jin-mang. Application of Genetic Algorithm Optimum Target Assignment[J]. Electronics Optics & Control,2008,15(3):18-20.

[5] ADAM J, HEBERT. The Baghdad Strikes[J]. Air Force Magazine, 2003,3(1):1-24.

[6] Lloyd S P, H S W. Weapons Allocation is NP-complete[C]∥Proceedings of the IEEE Summer Simulation Conference, Reno, Nevada，1986:127-132.

[7] SRINIVAS N, DEB K. Multiobjective Function Optimization Using Nondominated Sorting Genetic Algorithms[J]. Evolutionary Computation, 1995,2(3):221-225.

[8] FONSECA C M, FLEMING P J. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization[C]∥In:Forrest S. Proceedings of the Fifth International Conference on Genetic Algorithms.SanMateo:Morgan Kauffman,1993:416-420.

[9] HORN J, NAFPLOITIS N, GOLDBERG D E. A niched Pareto Genetic Algorithm for Multiobjective Optimization[C]∥Michalewicz. Z editor, Porceedings of the First IEEE Conference on Evolutionary Computation. Piscataway:IEEE Service Center,1994:82-94.

[10] ZITZLER E, THIELE L. Multiobjective Optimization Using Evolutionary Algorithms-A Compararive Case Study[C]∥Parallel Problem Solving from Nature V.Berlin,1998:292-301.

[11] DEB K. Multiobjective Genetic Algorithms:Provlem difficulties and Constructin of Test Functions[J].Evolutionary Computation,1999,7(3):205-213.

[12] 李棟學，劉茂.NSGAII在應(yīng)急物資儲備庫選址中的應(yīng)用[J].工業(yè)安全與環(huán)保，2009，35(3)：2-3. LI Dong-xue, LIU Mao. Application of NSGA II in Emergency Material Storage Layeet Optimization[J]. Industrial Safety and Environmental Protection,2009,35(3):2-3.

[13] 邢文訓，謝金星.現(xiàn)代優(yōu)化計算方法[M].北京：清華大學出版社，2005. XING Wen-xun,XIE Jin-xing. Modern Optimize Algorithms[M].BeiJing:Tsinghua University Press,2005.

[14] 王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002. WANG Xiao-ping,CAO Li-ming. Genetic Algorithm——Theory、Applications and Software Implementation[M].Xi’an:Xi’an Jiaotong University Press,2002.

Weapon-Target Assignment Problem in the Warship Fleet Based on Non-Dominated Sorting Genetic Algorithm

NIU Xiao-bo， CHEN Xin-lai,ZHU Fei, FANG Qun

(Bengbu Naval Petty Officer Academy,Anhui Bengbu 233012, China)

Based on the characteristics of modern naval formation and characteristics of weapons, a new weapon-target assignment (WTA) model of warship fleet is built. This model can abstract the target assignment of warship fleet into a multi-objects optimization issue. This model can achieve the best overall effect and lowest overall loss. Then the fast and elitist non-dominated sorting genetic algorithm (FENSGA) is applied to resolve this model. The optimal solution of Pareto obtained with the FENSGA is a wide-distributing and good robust solution. One running of the algorithm can achieve multi-Pareto solutions, and the commander can select the best from them according to the actual situation. A simulation is given to prove the validity of this model and the algorithm by comparing with the other algorithms.

warship fleet; weapon-target assignment (WTA); fast and elitist Non-dominated sorting genetic algorithm (FENSGA); multi-objects optimization

2014-06-14；

2014-09-24

牛曉博(1983-)，男，山東濱州人。講師，碩士，主要研究方向為信息融合、決策支持。

通信地址：233012 安徽省蚌埠市海軍蚌埠士官學校信息技術(shù)系指揮自動化教研室 E-mail：chinanxb@163.com

10.3969/j.issn.1009-086x.2015.04.020

E843；E925.6；TP391.9

A

1009-086X(2015)-04-0117-07