基于多目標優化遺傳算法的武器-目標分配

陳 思 胡 濤

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

?

基于多目標優化遺傳算法的武器-目標分配

陳 思1,2胡 濤1

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

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

多目標優化; 遺傳算法; 火力分配; 非劣分層; Pareto集

Class Number TP301.6; TP202

1 引言

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

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

2 WTA數學模型

2.1 WTA問題

(1)

(2)

2.2 多目標優化模型

傳統的WTA單目標優化問題是要求分配方案滿足對敵方來襲目標的毀傷效能指標達到最大,增加用彈量最少的目標函數,從而構成了兩個目標函數的多目標優化模型。

用一定數量的第i類武器攻擊第j個目標的殺傷概率可表示為

pij=1-(1-eij)xij

(3)

則所有n類武器對目標j的毀傷概率pj為

(4)

毀傷效能為

(5)

決策方案中,使用的導彈數目為

(6)

根據目標函數f、g和由WTA三條基本原則構成的約束條件,建立的標準化約束優化問題為

(7)

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

3 改進的NSGA-Ⅱ算法及應用

3.1 多目標優化與Pareto集

多目標優化問題可以用函數f來定義,該函數把決策向量X映射到目標向量Y,其數學描述為

(8)

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

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

在多目標優化問題中,Pareto優化解是最常用的優化概念。它最早由Francis Ysidro Edgeworth在1881年提出而后經Vilfredo Pareto推廣,其定義如下:

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

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

3.2 改進的NSGA-Ⅱ算法

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

用于多目標優化求解的改進NSGA-Ⅱ算法的要點是:

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

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

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

圖1 擁擠距離示意圖

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

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

3.3 算法目標分配應用

本文采用NSGA-Ⅱ算法進行水面艦艇協同防空武器-目標分配優化,其流程圖如圖2所示。基于NSGA-Ⅱ算法的武器-目標分配優化步驟為:

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

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

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

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

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

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

圖2 NSGA-Ⅱ算法武器-目標分配流程圖

4 仿真分析

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

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

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

5 結語

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

[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].系統工程與電子技術,2013,35(10):2121-2127.

[6] 劉曉,劉忠,侯文姝,等.NRIWO算法求解火力分配多目標規劃模型[J].華中科技大學學報(自然科學版),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