基于帶精英策略遺傳算法的艦艇編隊(duì)目標(biāo)分配*

牛曉博,陳新來(lái),朱飛,方群

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

基于帶精英策略遺傳算法的艦艇編隊(duì)目標(biāo)分配*

牛曉博,陳新來(lái),朱飛,方群

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

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

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

0 引言

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

1 問(wèn)題的描述

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

1.1 艦艇編隊(duì)目標(biāo)分配問(wèn)題

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

1.2 艦艇編隊(duì)目標(biāo)分配原則

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

(1) 對(duì)敵方目標(biāo)打擊最大；

(2) 對(duì)我方重要目標(biāo)的保護(hù)度最大；

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

對(duì)該問(wèn)題進(jìn)行數(shù)學(xué)建模，可將艦艇編隊(duì)WTA問(wèn)題建模為如下多目標(biāo)優(yōu)化問(wèn)題：

(1)

(2)

2 遺傳算法求解目標(biāo)分配問(wèn)題

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

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

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

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

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

(1) 快速非支配排序

在快速非支配排序方法中，對(duì)每一個(gè)個(gè)體需要計(jì)算兩個(gè)參數(shù)。群體中支配個(gè)體i的個(gè)體的數(shù)量ni和被個(gè)體i所支配的個(gè)體的集合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中的個(gè)體具有非支配序i。

(2) 擁擠度計(jì)算

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

擁擠度計(jì)算的偽代碼如下：

Initializationid(d)=0

For each objective function m

i=sort(i,m)

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

Fork=2 to (n-1)

End for

End for

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

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

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

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

則定義適應(yīng)度關(guān)系≥n為：i≥nj，如果irjd，表示如果2個(gè)個(gè)體的非支配序不同，序號(hào)低的個(gè)體適應(yīng)度高；如果兩個(gè)個(gè)體在同一非支配序，周?chē)粨頂D的個(gè)體適應(yīng)度高。

2.2 帶精英策略的快速非支配遺傳算法求解艦艇編隊(duì)目標(biāo)分配問(wèn)題

(1) 編碼生成

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

(2) 初始群體確定

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

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

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

(4) 選擇

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

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

(5) 交叉

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

(6) 變異

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

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

(3)

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

變異函數(shù)為

(4)

(5)

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

(7) 算法的終止

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

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

3.1 應(yīng)用實(shí)例

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

3.2 結(jié)果分析

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[1] 曹奇英，何張兵.WTA問(wèn)題的遺傳算法研究[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)法在武器目標(biāo)分配問(wèn)題中的應(yīng)用研究[J].應(yīng)用科學(xué)學(xué)報(bào)，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] 楊申林，王延璋，許建平.遺傳算法在多目標(biāo)分配中的應(yīng)用[J].軍事運(yùn)籌與系統(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] 羅紅英，劉進(jìn)忙.遺傳算法在目標(biāo)優(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] 李棟學(xué)，劉茂.NSGAII在應(yīng)急物資儲(chǔ)備庫(kù)選址中的應(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] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京：清華大學(xué)出版社，2005. XING Wen-xun,XIE Jin-xing. Modern Optimize Algorithms[M].BeiJing:Tsinghua University Press,2005.

[14] 王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，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-)，男，山東濱州人。講師，碩士，主要研究方向?yàn)樾畔⑷诤?、決策支持。

通信地址：233012 安徽省蚌埠市海軍蚌埠士官學(xué)校信息技術(shù)系指揮自動(dòng)化教研室 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