基于多目标优化遗传算法的武器-目标分配

陈 思 胡 涛

(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