陳 思 胡 濤

(1.海軍工程大學(xué) 武漢 430033)(2.中國瑞達投資發(fā)展集團公司 北京 100040)

?

基于多目標(biāo)優(yōu)化遺傳算法的武器-目標(biāo)分配

陳 思1,2胡 濤1

(1.海軍工程大學(xué) 武漢 430033)(2.中國瑞達投資發(fā)展集團公司 北京 100040)

針對武器-目標(biāo)火力分配問題,建立了基于效能最大和用彈量最少的多目標(biāo)優(yōu)化模型?；赑areto集非劣分層思想對遺傳算法進行改進,利用非劣分層遺傳算法處理武器-目標(biāo)分配多目標(biāo)優(yōu)化問題。非劣分層遺傳算法通過對種群內(nèi)的所有個體的多個目標(biāo)函數(shù)進行非劣分層排序來度量個體的適應(yīng)能力,通過遺傳算法實現(xiàn)多樣性進化操作,能夠獲取Pareto最優(yōu)解集,以供決策者參考。仿真試驗表明:該方法能夠獲得滿意的分配結(jié)果,方便快捷地解決多平臺多類型武器-目標(biāo)分配問題。

多目標(biāo)優(yōu)化; 遺傳算法; 火力分配; 非劣分層; Pareto集

Class Number TP301.6; TP202

1 引言

目前大多學(xué)者對于多平臺多武器-多目標(biāo)火力分配(Weapon-Target Assignment,WTA)問題采用單目標(biāo)規(guī)劃方案,將多平臺多武器火力分配的單目標(biāo)規(guī)劃多是以作戰(zhàn)效能最大,即對敵目標(biāo)毀傷效能最大為優(yōu)化的目標(biāo)函數(shù),然后采用線性規(guī)劃類方法以及遺傳算法、蟻群算法、禁忌搜索算法、粒子群優(yōu)化方法等智能算法進行優(yōu)化求解[1～5]。采用單目標(biāo)優(yōu)化分配的結(jié)果在實際作戰(zhàn)應(yīng)用中表現(xiàn)為對敵火力增大到一定程度后,作戰(zhàn)效能改善不明顯,容易造成火力資源的浪費。在作戰(zhàn)效能最大的目標(biāo)函數(shù)基礎(chǔ)上增加了用彈量最少這一目標(biāo)函數(shù),從而形成了多目標(biāo)優(yōu)化問題,這樣可以解決單目標(biāo)優(yōu)化帶來的矛盾[6],這類方法均采用基于Pareto集理論的多目標(biāo)優(yōu)化方法來解決,其特點是在多個目標(biāo)函數(shù)值形成的多維空間內(nèi)進行非劣分層,形成非劣解集,然后根據(jù)決策者的意圖找出最終解[7～9]。

遺傳算法是一種基于自然界生物進化的智能隨機搜索算法,它是由美國Michigan大學(xué)的John Holland與其同事提出的方法。由于簡單易用,魯棒性好,具有強有力的全局搜索能力,且算法簡單、易于編程,目前已經(jīng)成為一種解決許多實際優(yōu)化問題的有效工具[10]。根據(jù)遺傳算法和Pareto集多目標(biāo)優(yōu)化原理,本文研究了非劣分層的多目標(biāo)優(yōu)化遺傳算法,采用Pareto集非劣分層原理,根據(jù)種群中個體的多個目標(biāo)函數(shù)值進行非劣分層,得到非劣解集,從而為決策者提供多種決策方案。文中首先介紹了WTA問題多目標(biāo)優(yōu)化數(shù)學(xué)模型,接著研究了非劣分層的多目標(biāo)優(yōu)化遺傳算法(NSGA-Ⅱ)及其在武器-目標(biāo)分配中的應(yīng)用,最后進行了武器-目標(biāo)分配仿真試驗,從而實現(xiàn)了NSGA-Ⅱ求解WTA問題。

2 WTA數(shù)學(xué)模型

2.1 WTA問題

(1)

(2)

2.2 多目標(biāo)優(yōu)化模型

傳統(tǒng)的WTA單目標(biāo)優(yōu)化問題是要求分配方案滿足對敵方來襲目標(biāo)的毀傷效能指標(biāo)達到最大,增加用彈量最少的目標(biāo)函數(shù),從而構(gòu)成了兩個目標(biāo)函數(shù)的多目標(biāo)優(yōu)化模型。

用一定數(shù)量的第i類武器攻擊第j個目標(biāo)的殺傷概率可表示為

pij=1-(1-eij)xij

(3)

則所有n類武器對目標(biāo)j的毀傷概率pj為

(4)

毀傷效能為

(5)

決策方案中,使用的導(dǎo)彈數(shù)目為

(6)

根據(jù)目標(biāo)函數(shù)f、g和由WTA三條基本原則構(gòu)成的約束條件,建立的標(biāo)準(zhǔn)化約束優(yōu)化問題為

(7)

其中,i=1,2,…,n;j=1,2,…,m。

3 改進的NSGA-Ⅱ算法及應(yīng)用

3.1 多目標(biāo)優(yōu)化與Pareto集

多目標(biāo)優(yōu)化問題可以用函數(shù)f來定義,該函數(shù)把決策向量X映射到目標(biāo)向量Y,其數(shù)學(xué)描述為

(8)

式中,X=(x1,x2,…,xm)由m個決策變量xi構(gòu)成,Y由n個需同時優(yōu)化的目標(biāo)fi(X)構(gòu)成;約束條件g(X)由r個等式、不等式gi(X)≤0構(gòu)成(為方便討論起見,本文的優(yōu)化問題皆為最小化問題)。

多目標(biāo)優(yōu)化問題式(2)中的各目標(biāo)往往處于沖突狀態(tài),因而不存在使所有目標(biāo)同時達到最優(yōu)的絕對最優(yōu)解,只能獲得滿意解,即Pareto解。

在多目標(biāo)優(yōu)化問題中,Pareto優(yōu)化解是最常用的優(yōu)化概念。它最早由Francis Ysidro Edgeworth在1881年提出而后經(jīng)Vilfredo Pareto推廣,其定義如下:

定義3(Pareto最優(yōu)解集):對于給定的多目標(biāo)優(yōu)化問題,設(shè)其定義域為Ω,則其Pareto最優(yōu)集X*,定義為:X*={x∈Ω|?。

對于極小值多目標(biāo)優(yōu)化問題minf(X),Pareto最優(yōu)解定義為:在設(shè)計變量的可行域內(nèi),對于變量X,當(dāng)且僅當(dāng)不存在其他變量X*,在不違背約束的條件下滿足fi(X)≤fi(X*),至少存在一個i使得fi(X)

3.2 改進的NSGA-Ⅱ算法

NSGA-Ⅱ算法是將標(biāo)準(zhǔn)遺傳算法應(yīng)用于多目標(biāo)優(yōu)化問題時進行改進的,其思想是Pareto集非劣分層的方法與遺傳算法相結(jié)合——通過對多目標(biāo)解群體進行逐層分類,得到具有優(yōu)劣關(guān)系的不同非劣層,而最優(yōu)的解構(gòu)成Pareto前端,即第一非劣層。首先在可行解空間初始化種群,種群中每個個體代表了多目標(biāo)優(yōu)化問題的一個潛在解,其適應(yīng)度值由Pareto集非劣分層后每個個體在解空間中的秩來決定;接著進行解種群的Pareto集非劣分層,完成解個體秩的計算和每個非劣層中個體擁擠距離的計算;再執(zhí)行遺傳算法的基本進化操作,主要包括變異、交叉和選擇;然后進行父代種群和子代種群的合并和新一代種群的篩選;篩選出新一代種群后可再進行非劣分層,如此循環(huán)迭代,滿足迭代終止條件后,最優(yōu)的解集就存在于Pareto前端中。

用于多目標(biāo)優(yōu)化求解的改進NSGA-Ⅱ算法的要點是:

1) 種群個體秩的計算:個體的秩的定義是種群中Pareto占優(yōu)個體的數(shù)目rank=R+1;

2) Pareto集非劣分層:種群中相同秩的個體分為一層,稱為非劣層;秩越小則該非劣層優(yōu)勢越大,最優(yōu)非劣層為秩為1的非劣層,即Pareto前端;

3) 擁擠距離計算:擁擠距離是進行同一非劣層中個體的優(yōu)選的基本原則,認為在同等情況下,擁擠距離越大,解的多樣性越大,因此優(yōu)先選擇擁擠距離大的個體。種群中某個個體i的擁擠距離di是一個在個體i周圍不被種群中任何其它的個體所占有的搜索空間的度量。為了估計種群中某個個體i周圍個體的密度,取個體i沿著每個目標(biāo)fm的兩邊的兩個個體(i-1)、(i+1)的水平距離,數(shù)量di作為M個距離之和的估計值,稱之為擁擠距離。如圖1所示,同一個非劣層相鄰的三個個體分別為i、(i-1)、(i+1),則第i個個體的擁擠距離為di=dx+dy。

圖1 擁擠距離示意圖

4) 進化操作:進化操作與標(biāo)準(zhǔn)遺傳算法一樣,交叉過程中采用基因重組的形式產(chǎn)生兩個子個體,選擇過程采用Pareto占優(yōu)的概念,在所產(chǎn)生的兩個個體和父本個體中選擇最優(yōu)的個體,如果兩個個體無差別,則在兩個子個體中隨機選擇一個個體。

5) 種群合并與篩選:子代和父代種群合并后,利用Pareto占優(yōu)的概念選取與父代種群規(guī)模相等的種群,其選擇根據(jù)為Pareto非劣分層層次和個體擁擠距離。

3.3 算法目標(biāo)分配應(yīng)用

本文采用NSGA-Ⅱ算法進行水面艦艇協(xié)同防空武器-目標(biāo)分配優(yōu)化,其流程圖如圖2所示?；贜SGA-Ⅱ算法的武器-目標(biāo)分配優(yōu)化步驟為:

1) 編碼:對于水面艦艇編隊協(xié)同防空的武器-目標(biāo)分配問題,由于每個平臺武器的彈藥數(shù)量為整數(shù),本文采用十進制整數(shù)編碼。具體編碼實施方法是:假定海上艦艇編隊防空預(yù)警探測系統(tǒng)空情顯示有m個敵方目標(biāo),協(xié)同防空多平臺武器有n組武器。采用十進制編碼,每個染色體由按目標(biāo)順序排列的武器編號組成,表示一種可能的分配方案,其中每個基因表示一批目標(biāo)的分配結(jié)果,染色體的長度為m*n。編碼基因的取值范圍在每種武器擁有的導(dǎo)彈數(shù)目總量以內(nèi),不同的基因可取相同的編碼值。例如m取4,n取3,則種群的1個染色體216973480531表示一個火力分配方案,即第一種武器分配給4個目標(biāo)的導(dǎo)彈數(shù)目分別是2,1,6,9,第二種武器分配給4個目標(biāo)的導(dǎo)彈數(shù)目分別是7,3,4,8,第三種武器分配給4個目標(biāo)的導(dǎo)彈數(shù)目分別是0,5,3,1。

2) 初始種群的產(chǎn)生。結(jié)合約束條件生成一個比所需群體規(guī)模要大很多的初始群體,從該群體中再隨機選取適合所要的群體規(guī)模的個體,選擇以后對所選的初始群體進行評價,如果它的最好個體的適應(yīng)度達到了理論適應(yīng)度的0.8左右,則選擇,否則重新生成大規(guī)模的初始群體進行選擇。

3) Pareto集非劣分層:種群中每個解與該種群中所有的其它解進行比較,看是否劣于種群中的其它任意一個解,并記錄個數(shù),根據(jù)個數(shù)進行分層。

4) 進化操作:進化操作即3.2中介紹的標(biāo)準(zhǔn)遺傳算法的變異、交叉和選擇操作。

5) 種群合并與篩選。對整個親代和子代種群執(zhí)行非劣分層,然后再進行種群篩選,選出初始種群規(guī)模大小的種群,具體篩選策略是:從最優(yōu)非劣解開始,接收每層的個體直到填滿所有的種群位置。

6) 迭代次數(shù)加1,返回步驟3),直至達到最大迭代次數(shù)為止,種群中的所有第一非劣層解即構(gòu)成Pareto最優(yōu)解集。

圖2 NSGA-Ⅱ算法武器-目標(biāo)分配流程圖

4 仿真分析

對于優(yōu)化模型本文采用罰函數(shù)法處理其中的約束條件,然后進行求解。

圖3 NSGA-Ⅱ 200次迭代后的種群及Pareto前端

圖3為200次迭代后的種群,紅色曲線串聯(lián)的為Pareto前端,即最優(yōu)非劣解集,其中的每一個解代表一種分配方案,例如,g=33,1-f=0.04的方案,其對應(yīng)的染色體為[0 4 0 0 0 7 7 0 2 0 11 2],即第一種武器分給四個目標(biāo)的導(dǎo)彈數(shù)目分別為0,4,0,0;第二種武器分給四個目標(biāo)的導(dǎo)彈數(shù)目分別為0,7,7,0;第三種武器分給四個目標(biāo)的導(dǎo)彈數(shù)目分別為2,0,11,2。圖3中所示的用改進的NSGA-Ⅱ算法求解的WTA多目標(biāo)優(yōu)化模型得到的非劣解集構(gòu)成的Pareto前沿,較好地維護了Pareto解的分布性與收斂性,體現(xiàn)了增加導(dǎo)彈數(shù)量對射擊效能的影響,便于決策者進行決策。例如,如果決策者要求對敵毀傷概率0.85

5 結(jié)語

針對傳統(tǒng)的單目標(biāo)優(yōu)化效率低,且不容易獲取偏重權(quán)重的缺點,本文結(jié)合遺傳算法和Pareto集多目標(biāo)優(yōu)化方法,將非劣分層多目標(biāo)優(yōu)化遺傳算法NSGA-Ⅱ應(yīng)用到了水面艦艇編隊協(xié)同防空多目標(biāo)優(yōu)化武器-目標(biāo)分配問題,利用多目標(biāo)優(yōu)化遺傳算法搜索能力強、考慮問題全面等特點進行目標(biāo)分配。仿真實驗表明,NSGA-Ⅱ算法結(jié)構(gòu)簡單,易于實現(xiàn),且搜索能力強,可適用于解決較復(fù)雜的或規(guī)模較大的武器-目標(biāo)分配問題。

[1] Lee Z J, Lee C Y, Su S F. An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem[J]. Applied Soft Computing,2002,2(1):39-47.

[2] Lee Z J, Su S F, Lee C Y. Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics[J]. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on,2003,33(1):113-121.

[3] Wacholder E. A neural network-based optimization algorithm for the static weapon-target assignment problem[J]. ORSA Journal on computing,1989,1(4):232-246.

[4] Ahuja R K, Kumar A, Jha K C, et al. Exact and heuristic algorithms for the weapon-target assignment problem[J]. Operations Research,2007,55(6):1136-1146.

[5] 徐克虎,黃大山,王天召.改進的人工免疫算法求解武器-目標(biāo)分配問題[J].系統(tǒng)工程與電子技術(shù),2013,35(10):2121-2127.

[6] 劉曉,劉忠,侯文姝,等.NRIWO算法求解火力分配多目標(biāo)規(guī)劃模型[J].華中科技大學(xué)學(xué)報(自然科學(xué)版),2013,5:13.

[7] Kalyanmoy D. Muilti-objective optimization using evolutionary algorithms[M]. New York: John Wiley & Sons,2001:245-253.

[8] Kundu D, Suresh K, Ghosh S, et al. Muilti-objective optimization with artificial weed colonies[J]. Information Science,2011(181):2441-2454.

[9] Srinivas N, Deb K. Muilti-objective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation,1994,2(3):221-248.

[10] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. Evolutionary Computation, IEEE Transactions on,2002,6(2):182-197.

Weapon-target Assignment with Multi-objective Non-dominated Set Ranking Genetic Algorithm

CHEN Si1,2HU Tao2

(1. Naval University of Engineering, Wuhan 430033) (2. China RIDA Investment and Development Group Corporation, Beijing 100040)

Aiming at solving weapon-target assignment(WTA) problems, a multi-objective optimization model is established based on maximum optimal damage probability and minimum the firepower number. Application the Pareto non-dominated set ranking method, non-dominated set ranking genetic algorithm(NSGA-Ⅱ) is presented to solve the multi-objective optimization WTA problems. The population’s fitness is evaluated by the non-dominated set rank, the diversity evolution operation is evaluated by genetic algorithm(GA). The proposed NSGA-Ⅱ algorithm is simple, perfect performance and can provide Pareto-optimal front to support decision. The simulation experiment gives good WTA result which verifies the correctness and effectiveness of the proposed algorithm.

multi-objective optimization, genetic algorithm, weapon-target assignment, non-dominated set ranking, Pareto set

2015年1月3日,

2015年2月24日 作者簡介:陳思,女,碩士研究生,研究方向:項目信息管理。

TP301.6; TP202

10.3969/j.issn1672-9730.2015.07.015