式中,N(π)为第1个目标函数;N(π)为第2个目标函数,以避免造成过度杀伤和火力浪费;Ω为导弹-目标分配空间;导弹集A中导弹Ar攻击敌机Rj为Ar→Rj,对敌机Rj的摧毁概率为 drRj;XrRj为二值函数，如式(2)所示；第1个约束表示毁伤门限[3]以保证分配方案π对目标的最低杀伤； KRj表示第j 个目标的毁伤门限,可根据战场态势等具体任务需要由指挥员制定;第2个约束表示每枚导弹只能攻击1个目标.
2 进化多目标优化算法 2.1 多目标决策理论多目标优化问题(MOPs)指目标函数多于1个且需同时处理的问题.多目标决策与单目标决策最大的不同在于解的寻优用Pareto占优进行度量,即“支配”关系,会同时存在多个Pareto非支配解,构成Pareto最优解集(Pareto-optimal set)[4].为便于后续讨论给出定义如下.定义1 Pareto占优.πA,πB∈Ω是所求多目标函数的两个可行解,称与πB相比,πA是Pareto占优的，当且仅当
定义2 Pareto最优解.一个解π*∈Ω被称为Pareto最优解,当且仅当
Pareto最优解的集合为Pareto最优解集P*.3 Pareto前沿.Pareto最优解集P*中的解对应目标值组成的曲面称为Pareto前沿F*:
2.2 进化多目标优化算法进化多目标优化(EMO)通过在代与代之间维持由潜在解组成的种群来实现全局搜索.这种方法对于搜索Pareto最优解集是非常有效的,一些新颖的多目标优化算法相继提出[7].EMO用基于支配关系的比较机制评价解的优劣,Pareto最优解集需设置一个外部种群保存.此类问题不仅要考虑解的收敛性,还要考虑解分布的均匀性,以保证解的多样性,一般用自适应网格机制[4],将外部种群按照目标函数空间均匀地划分为网格.在删除个体时,含有较多个体的网格中的粒子赋予较高选中概率;在选取个体作为进化种群的全局最优时,含有较少个体的网格中粒子赋予较高概率,基于转盘赌方式进行选择. 3 基于MODPSO-GSA的模型求解文中分别采用多目标离散粒子群优化(MODPSO)、多目标引力搜索算法(MOGSA)及多目标离散粒子群-引力搜索算法MODPSO-GSA实现WTA模型求解. 3.1 基于MODPSO的模型求解求解WTA问题的单目标离散粒子群(DPSO)算法可参见文献[3,8,9].在具体WTA问题上,MODPSO用粒子位置代表一组分配方案,粒子位置矢量为X=[X1,X2,…,XK],K为待分配导弹数量;粒子速度矢量为V=[v1,v2,…,vK] .粒子按式(6)更新速度及位置:
式中,t为迭代次数;c1和c2为学习因子;r1和r2为(0,1)之间的随机数;w为惯性权重; pibest为粒子i搜索到的最优位置; prep为基于转盘赌从外部种群选取的Pareto占优解来引导寻优.3.2 基于MOGSA的模型求解引力搜索算法(GSA)是一种基于万有引力定律寻优的智能优化算法,算法将每个可能解视为在空间中有质量的个体,质量越大代表越优的位置,个体之间基于牛顿定律,通过万有引力作用相互吸引产生运动,引导群体向最优解区域搜索[10].图 1给出了M2,M3,M4均对M1产生引力作用.
 |
| 图 1 个体之间引力相互作用构造合力 F1Fig. 1 Resultant force F1 from other masses |
| 图选项 |
GSA具有良好的全局寻优能力[11,12,13],尚未应用在WTA问题.此处对GSA简略介绍,可参见文献[10].单目标GSA主要步骤如下:1) 初始化.由N个个体组成搜索群体,搜索空间为K维,个体i位置定义为
2) 计算个体质量Mi(t).3) 计算个体j对个体i的引力Fij(t). 4) 计算个体j对个体i的引力加速度aij(t).
其中,Xi表示个体i的位置;Rij(t)表示Xi与Xj之间的欧式距离;ε表示最小门限,防止分母为0;G(t) 表示此时的引力常数,以控制迭代步长.5) 根据牛顿运动定律,计算合力加速度如式(9)所示,控制变量Kbest随时间递减,表示只有前Kbest个适应值最好的个体产生引力,控制算法收敛到最优解;randj为随机数.个体的速度及位置更新如式(10)所示.
6) 若没达到迭代次数,转步骤2);否则停止计算.MOGSA多目标优化改进采用基于支配关系的比较机制和基于自适应网格的外部种群.主要是如何在两个目标函数与个体单一质量之间建立对应关系,此处参考NSGA-II根据个体间非支配关系为个体分级[14]来定义个体质量:定义不被其他个体支配的个体集合rank=1,只被一个个体支配的个体集合定义rank=2,以此类推.如下所示为非支配关系分级伪代码，其中rank=1的个体集合就是Pareto最优解.
对于进化种群中的粒子p定义集合DomSetp存放被该粒子支配的粒子,变量DomedNump记录该粒子被支配的次数.如果一个粒子被支配次数为0,则该粒子rankp=1,该粒子集合记为S1.对于第i等级的粒子集合Si中的粒子p,它所支配的粒子集合DomSetp中的每个粒子q的DomedNumq减1后DomedNumq=0,则说明q只被粒子p支配,粒子q等级为i+1,存入i+1等级的粒子集合Fi+1,以此类推完成非支配分级.3.3 基于MODPSO-GSA的模型求解MODPSO收敛速度快,但易早熟收敛;MOGSA表现出良好的求解空间探索(exploration)能力,但缺乏有效加速机制[13].文中将二者结合,用一种协同进化的形式[15]:将PSO算法速度更新中的“社会(social)部分”(即gbest)与GSA的加速度结合起来,混合算法的速度更新如式(11)所示.
式中,ai(t) 表示MOGSA构造的加速度;VMax表示粒子速度限定;XMin,XMax分别表示位置的最大最小限定;其余变量与式(6)中变量意义相同.在迭代过程中可能会产生“非法”个体,如分配中遗漏敌机或分配过多导弹攻击同一目标.算法中引入局部调整adjustX:对分配方案中超过杀伤概率的目标尝试删除冗余分配;对于未达到毁伤概率的目标尽量弥补,从未分配导弹中选择对于该目标毁伤概率最大的导弹分配给该目标.MOPSOGSA算法结构流程如图 2所示.
 |
| 图 2 MODPSOGSA算法流程图Fig. 2 Procedure of MOPSOGSA |
| 图选项 |
4 算例仿真及分析为验证模型及求解算法有效性,采用文献[3]中算例进行仿真,我方编队由4架战机组成,每架战机挂载4枚导弹;敌机编队由10架飞机组成.各目标的毁伤概率门限可由指挥员进行设定,仿真中KRj均设为0.9.敌机的威胁权重矩阵dRB=[0.6,0.7,0.3,0.5,0.6,0.35,0.65,0.55,0.4,0.75].经评估我导弹对目标的毁伤概率矩阵[3]如式(12)所示.仿真时用文中提出的WTA模型建模,并同时用NSGA-II[16],MODPSO,MOGSA及MODPSO-GSA这4种算法对该算例进行求解.进化种群规模均设置为60,迭代次数为100.NSGA-II中进化种群与外部种群是合一的,采用二元竞赛图选择算子,交叉概率Pc=0.8,变异概率Pm=0.3;MODPSO,MOGSA,MODPSO-GSA的外部种群设置数量门限为10,网格设置为10×10.MODPSO中基本单目标参数设置参见文献[3],MODPSO-GSA采用MODPSO和MOGSA中的参数设置.仿真结果如图 3所示,横坐标E(π)表示目标函数1;纵坐标N(π)表示目标函数2,直线为各算法寻到的Pareto最优解.NSGA-II收敛于寻到的Pareto最优解集;MODPSO寻到的Pareto最优解如图中连线所示,进化种群如图中点集所示;MOGSA迭代后基本收敛到Pareto最优解集;MODPSO-GSA寻到的Pareto最优解集如图中连线所示,进化种群多样性仍较好.由图可知,MODPSO-GSA具备较好的寻优能力且粒子多样性得到了保持.4种算法寻到的Pareto最优解比较如图 4所示,MODPSO-GSA具备最佳寻优性能.
 |
| 图 3 4种算法迭代结束状态Fig. 3 Last states of four algorithms |
| 图选项 |
 |
| 图 4 4种算法迭代结果比较Fig. 4 Overall results of four algorithms |
| 图选项 |
仿真可知:①耗弹量为13和14的分配方案是每种多目标优化算法都能寻到的稳定分配,也是其他WTA算法[1,3]寻到的最优分配,证明了多 目标优化的有效性;②多目标优化算法可一次运行寻得不同耗弹量下的多个最优目标分配方案,达到预设的目标毁伤概率,指挥员可根据空战态势进行分配方案优选,这更符合空战实际情况;③MODPSO-GSA保持了粒子群算法的快速寻优能力,寻优性能是稳定的并优于其他算法.图 5是MODPSO-GSA寻到的4个分配方案及达到的毁伤效果,图中标示了每个分配方案的敌总期望剩余威胁和我方用弹量.4种方案均是可行分配,指挥员可根据不同的战场态势进行决策.
 |
| 图 5 不同耗弹量下的毁伤效果及分配方案Fig. 5 Killing probability and weapon-target assignment (WTA) for varied missiles used |
| 图选项 |
4种多目标优化算法各运行20次取平均性能如表 1所示,MODPSO-GSA具备相对最好的综合性能. 表 1 平均性能对比Table 1 Comparison of average performance
| 算法 | 不同耗弹量下的平均敌方剩余威胁 | 平均时间/s | |||
| 13 | 14 | 15 | 16 | ||
| NSGA-II | 0.348 5 | 0.296 5 | 0.249 2 | 0.206 9 | 56.420 |
| MODPSO | 0.349 0 | 0.296 6 | 0.250 4 | 0.214 8 | 2.249 6 |
| MOGSA | 0.349 7 | 0.296 5 | 0.251 9 | 0.215 0 | 3.153 7 |
| MODPSO-GSA | 0.348 5 | 0.296 5 | 0.248 0 | 0.204 9 | 4.582 1 |
表选项
5 结 论1) 构建多目标决策模型,选取对敌杀伤效果最大和消耗火力资源最小作为决策目标,提出新的目标分配模型,模型具备直观性.2) 提出基于混合离散粒子群-引力搜索的多目标优化算法求解所建多目标决策模型,展现了良好的寻优能力.3) 进化多目标优化的优势在于一次运行可得到多个Pareto最优解,在文中模型可在满足毁伤门限的前提下,寻到多个不同耗弹量下的最优分配方案,指挥员可根据不同空战态势决策优先,具备实战意义.4) 文中所提多目标优化算法属集中式WTA方式,对通信及指控中心依赖性强,当空战态势剧烈变化或通信质量难以保证时仍有待改进.
参考文献
| [1] | 刘传波, 邱志明,吴玲,等.动态武器目标分配问题的研究现状与展望[J].电光与控制,2010,17(11):43-47. Liu C B,Qiu Z M,Wu L,et al.Review on current status and prospect of researches on dynamic weapon target assignment[J].Electronics Optics & Control,2010,17(11):43-47(in Chinese). |
| Cited By in Cnki (16) | |
| [2] | 陈闽. 编队协同作战目标分配建模综述[J].电光与控制,2013,20(9):53-63. Chin M.A survey on modeling of target allocation for formation cooperative combat[J].Electronics Optics & Control,2013,20(9): 53-63(in Chinese). |
| Cited By in Cnki | |
| [3] | 李俨, 董玉娜.基于SA-DPSO混合优化算法的协同空战火力分配[J].航空学报,2010,31(3):626-631. Li Y,Dong Y N.Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat[J].Acta Aeronautica et Astronautica Sinca,2010,31(3): 626-631(in Chinese). |
| Cited By in Cnki (22) | |
| [4] | 公茂果, 焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289. Gong M G,Jiao L C,Yang D D,et al.Evolutionary multi-objective optimization algorithms[J].Journal of Software,2009,20(2): 271-289(in Chinese). |
| Cited By in Cnki (402) | |
| [5] | 岳超源. 决策理论与方法[M].北京:科学出版社,2006:151-169. Yue C Y.Decision theory and methods[M].Beijing:Science Press,2006:151-169(in Chinese). |
| [6] | 段海滨. 蚁群算法原理及其应用[M].北京:科学出版社,2006:312-317. Duan H B.Ant colony algorithms: theory and applications[M].Beijing:Science Press,2006:312-317(in Chinese). |
| [7] | Coello C C, Veldhuizen V D,Lamont G.Evolutionary algorithms for solving multi-objective problems[M].2nd ed.New York:Springer-Verlag,2007:1-10. |
| [8] | 段海滨,张翔银, 徐春芳.仿生智能计算[M].北京:科学出版社,2011:63-85. Duan H B,Zhang X Y,Xu C F.Bio-inspired computing[M].Beijing:Science Press,2011:63-85(in Chinese). |
| [9] | 郭文忠,陈国龙. 离散粒子群优化算法及其应用[M].北京:清华大学出版社,2012:13-16. Guo W Z,Chen G L.Discrete particle swarm optimization algorithm and its application[M].Beijing:Tsinghua University Press,2012:13-16(in Chinese). |
| [10] | Esmat R, Hossein N,Saeid S.GSA: a gravitational search algorithm[J].Information Sciences,2009,179(13):2232-2248. |
| Click to display the text | |
| [11] | 杨晶,黎放, 狄鹏.免疫万有引力搜索算法的研究与仿真[J].兵工学报,2012,33(12):1533-1538. Yang J,Li F,Di P.Research and simulation for the gravitational search algorithms with immunity[J].Acta Armamentarh,2012,33(12):1533-1538(in Chinese). |
| Cited By in Cnki (3) | |
| [12] | 谷文祥,李向涛, 朱磊,等.求解流水线调度问题的万有引力搜索算法[J].智能系统学报,2010,5(5):411-418. Gu W X,Li X T,Zhu L,et al.A gravitational search algorithm for flow shop scheduling[J].CAAI Transactions on Intelligent Systems,2010,5(5):411-418(in Chinese). |
| Cited By in Cnki (10) | |
| [13] | 李沛,段海滨. 基于改进万有引力搜索算法的无人机航路规划[J].中国科学:技术科学,2012,42(10):1130-1136. Li P,Duan H B.Path planning of unmanned aerial vehicle based on improved gravitational search algorithm[J].Scientia Sinica Technologica,2012,42(10):1130-1136(in Chinese). |
| Cited By in Cnki (9) | |
| [14] | Hadi N, Mahdi N,Patrick S.A multi-objective gravitational search algorithm based on non-dominated sorting[J].International Journal of Swarm Intelligence Research,2012,3(3):32-49. |
| Click to display the text | |
| [15] | Seyedali M, Siti Z M H.A new hybrid PSOGSA algorithm for function optimization[C]//International Conference on Computer and Information Application.Piscataway,NJ:IEEE,2010:374-377. |
| Click to display the text | |
| [16] | Kalyanmoy D, Amrit P,Sameer A,et al.A fast elitist multi-objective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197. |
| Click to display the text |
