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

陳 思 胡 濤

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

?

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

陳 思1,2胡 濤1

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

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

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

Class Number TP301.6; TP202

1 引言

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

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

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

2.1 WTA問(wèn)題

(1)

(2)

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

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

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

pij=1-(1-eij)xij

(3)

則所有n類(lèi)武器對(duì)目標(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)化問(wèn)題為

(7)

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

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

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

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

(8)

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

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

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

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

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

3.2 改進(jìn)的NSGA-Ⅱ算法

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

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

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

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

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

圖1 擁擠距離示意圖

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

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

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

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

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

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

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

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

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

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

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

4 仿真分析

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

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

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

5 結(jié)語(yǔ)

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

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

[6] 劉曉,劉忠,侯文姝,等.NRIWO算法求解火力分配多目標(biāo)規(guī)劃模型[J].華中科技大學(xué)學(xué)報(bào)(自然科學(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日 作者簡(jiǎn)介:陳思,女,碩士研究生,研究方向:項(xiàng)目信息管理。

TP301.6; TP202

10.3969/j.issn1672-9730.2015.07.015