分布式遗传模拟退火算法的火力打击目标分配优化

吴坤鸿，詹世贤

（1.解放军73630部队，福州　350002；2.军事科学院军事运筹分析研究所，北京　100091）



分布式遗传模拟退火算法的火力打击目标分配优化

吴坤鸿1，2，詹世贤1

（1.解放军73630部队，福州350002；2.军事科学院军事运筹分析研究所，北京100091）

摘要：根据火力打击规则，建立了多目标函数的目标分配模型，提出了分布式遗传模拟退火算法对模型进行求解。分布式遗传模拟退火算法基于经典遗传算法进行改进：将单目标串行搜索方式变成多目标分布式搜索方式，适用于多目标寻优问题求解；采用保留最优个体和轮盘赌相结合的方式进行个体选择，在交叉算子中引入模拟退火算法，使用自适应变异概率，较好地保持算法广度和深度搜索平衡。最后，通过仿真实验验证了算法的有效性和可靠性。

关键词：火力打击目标分配，多目标优化，遗传算法，模拟退火算法

0　引言

火力打击目标分配是作战筹划的关键环节，其结果直接影响到打击火力体系整体效能的发挥，对作战进程推进和战局走向起到关键性作用。在火力目标分配研究领域，许多学者将智能启发式的遗传算法引入目标分配优化，取得了不少研究成果［1-6］。遗传算法具有运算全局寻优强、收敛速度快等优点，能够实现在复杂问题空间中进行鲁棒搜索。但是，采用经典遗传算法又存在迭代时间长、容易陷入局部最优等问题，因此，对遗传算法的改进成为目标分配研究的热点。如文献［7］在遗传算法中引入模拟退火算法，增强了全局收敛性，但此文献只研究了单目标优化问题；文献［8］采用并列选择遗传算法求解舰艇编队武器分配的双目标优化问题，但没有给出适应值分配机制，无法在种群交叉和变异中体现个体适应度影响。

针对目前遗传算法解决火力目标分配多目标优化存在的不足，本文以火力打击目标分配为研究对象，建立了多目标优化模型，对遗传算法进行了一定的改进，提出了分布式遗传模拟退火算法，能够有效求解火力打击目标分配的多目标优化问题。

1火力打击目标分配模型

火力打击目标分配应考虑如何充分发挥火力体系的整体打击优势，目标是尽量使得整体打击效果最大，受敌威胁程度最小，同时弹药消耗总量最低。据此，建立以下多目标函数：

其中，f1（x）、f2（x）、f3（x）分别代表打击效果、威胁程度和弹药消耗；xij={0，1}表示火力分配结果，xij=1表示第i个火力分配给第j个目标，xij=0表示不分配；wij表示第i个火力单位对第j个目标打击的毁伤效果指标；pij∈［0，1］表示第i个火力单位对第j个目标打击的命中概率；tj表示第j个目标的威胁值；uij表示第i个火力单位对第j个目标打击的产生弹药消耗系数。

为适当简化，对模型作如下约束：

2遗传算法和模拟退火算法介绍

2.1遗传算法

遗传算法（GA）是美国Holland［9］教授提出，是基于生物进化论以及基因遗传理论的随机搜索算法，其主要原理是先构建一定数量的初始种群，而后通过交叉和变异操作产生下一代种群，并根据个体的适应值对种群进行优胜劣汰，直到最后出现最优个体。该算法鲁棒性强，具有较强的全局搜索能力，适用于求解问题空间比较复杂的目标规划问题，但存在容易过早收敛陷入局部最优问题。

2.2模拟退火算法

模拟退火算法（SA）由Metropolis等提出，是利用迭代求解策略的一种随机寻优算法，其出发点是基于固体退火过程与一般组合优化问题之间的相似性。根据Metropolis准则，若新出现的个体适应度比当前个体好，则使用该新个体替代当前个体，否则，将以一定概率保留新个体。如此，随着退火过程的进行和温度的降低，非可行解被接受的概率逐渐变小。由于模拟退火算法能够在一定程度上避免出现局部最优解，因此，它在组合优化问题中得到广泛应用［10-11］。

3分布式遗传模拟退火算法设计

火力打击目标分配属于多目标优化问题，即指挥员在进行火力分配决策时需要综合权衡多种指标，但这些指标往往相互冲突，理论上不存在同时满足多目标最优的解。因此，提出分布式遗传模拟退火算法，具备一定的多目标同时寻优能力，支持指挥员根据决策偏好选出的近似最优分配方案。

分布式遗传模拟退火算法的设计基于遗传进化原理，即在各自环境中得到进化的优秀子种群合并后，会产生对多个环境适应度都较高的下一代。其主要过程是：首先将初始群体按目标函数个数划分出相应的子种群，各个子种群朝各自目标展开分布式寻优搜索，由此选择产生适应度高的子代；然后将新子代个体全部合并成新种群，在交叉时引入模拟退火算法，增强局部搜索能力，使用自适应变异操作以扩大全局搜索能力；如此不断地循环，直至算法终止，这样带有潜在最优解的种群能够一代一代地维持下来，最后可求出多目标优化问题的偏好最优解。多目标优化问题的关键是如何根据多个目标函数确定个体的适应度，本文采取子种群分布式各自寻优和合并后分配权重组合寻优的方法进行处理。算法的基本步骤如下：

3.1编码

编码可以实现遗传空间到问题空间的映射。传统的GA算法编码常用二进制编码，这种编码导致染色体过长且不够直观，不便遗传控制，影响求解速度和精度。为便于清晰地反应火力分配方案，本文采用十进制整数编码方式，根据一个火力只能打击一个目标的约束规则，染色体长度由火力单元总数决定，个体每位基因代表分配给该火力单元的目标编号。如假设海、空、常导3个军种分别有2个～4个不同火力单元对敌方5个目标进行打击，则某染色体编码为［1 3 2 3 5 1 3 4 2］代表一种方案打击：海军火力单元依次打击目标编号为1、3，空军火力单元依次打击目标编号为2、3、5，常规导弹火力单元依次打击目标编号为1、3、4、2。

3.2初始化种群并分组

根据种群规模随机创建初始种群，将种群按照目标函数个数分成相应个数的子种群，以便各子种群能同步展开分布式遗传操作。根据火力打击目标分配模型，需要对3个目标函数进行优化搜索，则可将初始种群分为3个子种群。

3.3选择

选择是从各子种群中选择适应度高的染色体，以待交叉和变异操作产生下一代染色体，以确保优化基因能够保留。传统的算法一般采用轮盘赌选择方式，个体适应度越高被选中的概率越大，但当种群个体比较接近的情况，无法保证适应度值最大的个体以较大的概率被选中。针对此问题，本文采用保留最优个体和轮盘赌相结合的方式进行选择，对最大适应度个体直接选中，其余个体采用轮盘赌方式进行选择复制。

该步骤中，由于采用了分布式选择，将式（1）～式（3）的3个目标函数分别作为3个子种群的选择适应度函数。

3.4合并

将各子种群经选择后产生个体进行合并，形成新的种群，以待交叉和变异操作。

3.5交叉

通过交叉操作可以产生继承父辈基因的新染色体。本文采用单点随机定位的2点间基因互换进行交叉，交叉个体也是采取轮盘法来选择，这样能保证个体适应度越高，被选中的概率越大。

对于交叉运算产生的个体，传统的遗传算法一般直接用子代替换父代个体，容易出现局部过早收敛的问题。因此，本文引入模拟退火算法进行改进：对交叉后的个体，根据其适应度模拟退火过程淘汰父代个体。设个体pi和pj，适应度分别为f（pi）和f（pj），进行交叉操作新个体pi'和pj'，如果适应度f（pi'）＞f（pi），则适应新个体pi'替代pi，否则以概率exp（-（f（pi'）-f（pi））/Tk）保留pi，Tk为当前退火温度，pj和pj'的模拟退火运算类似。

该步骤中，适应度函数由式（1）～式（3）的3个目标函数分配不同权重组合［12］而成，为方便进行最大化计算，对式（2）、式（3）目标函数取倒数处理，具体如下：

式中，α、β、γ分别代表分配给式（1）～式（3）3个目标函数的权重。

3.6变异

变异是以一定概率改变某个或部分基因值以产生新个体，变异基因的位置采用随机法确定。传统遗传算法一般采用固定变异概率，本文为了增大搜索范围同时减少搜索时间，采用可变的自适应概率变异方法:在迭代初期选择较大的变异概率，以保证个体多样性，扩大搜索范围;在迭代末期，采用较小的变异概率，减少破坏群体中原有的最优解可能性，以保证算法尽快收敛。自适应变异概率公式为：

式中，Pk代表第k代变异概率，Pmax、Pmin分别代表最大和最小的变异概率，Kmax代表最大迭代次数。

3.7终止方法

规定算法终止的方法是设定最大迭代次数为K。一旦迭代次数大于K，则停止计算，按照约定集合大小输出当前最优个体集。

图1给出分布式遗传模拟退火算法的基本流程图，该图重点说明算法如何朝多目标进行多方向分布式搜索和模拟退火的过程。

图1　分布式遗传模拟退火算法流程

4仿真实验及结果分析

假设某火力打击行动，共有9种火力打击平台，要对5个目标实施火力打击，火力平台对目标的毁伤效果指标、命中概率、弹药消耗，以及目标威胁程度数据事先已获知，分别如下页表1～表4所示（均已无量纲处理）。

用分布式遗传模拟退火算法求解火力打击目标分配问题，假定：遗传最大迭代次数K为1 500；种群数量N为150，分为3个子种群；初始温度T0＝800 K，冷却系数β=0.95；交叉概率0.8；变异概率为0.04～0.08。

表1　毁伤效果指标（％）

表2　命中概率（％）

表3　弹药消耗（％）

表4　威胁程度（％）

使用Matlab7.1对该算法进行编程实现，在XP SP2、Pentium（R）4、CPU 3.40 GHz、内存0.99 GB的单机环境下运行，使用串行遗传模拟退火算法平均2.8 s实现收敛，而使用本文分布式遗传模拟退火算法平均2 s实现收敛，得到不同目标函数权重下的仿真结果如图2所示，目标分配结果如表5所示。

图2　不同权重时的算法仿真结果

表5　仿真结果数据

图2仿真结果及表5数据表明，当目标函数的权重取不同值时，产生不同火力分配方案。其中，3个不同权重的方案，分配给火力1、4、5、7、8、9的目标是相同，不同之处在于火力2、3、6对目标2、4、5的匹配顺序有所不同，如表5灰色列所示，经分析，该匹配顺序主要取决于指挥员对打击效果、威胁度、弹药消耗3个目标的偏重程度。如比较方案1和方案2，方案1将火力2、3、6对应分配给目标2、4、5，而方案2将火力2、3、6对应分配给目标5、4、2，根据表1～表4先验数据可以发现，方案1能更好地提高整体打击效果，而方案2能最大程度地降低目标威胁度，这与指挥员对两个方案赋予不同权重的期望是一致的。

通过分析仿真结果及数据，得出以下结论：

1）算法具备较好的全局寻优搜索能力，最终实现全局收敛，使用该算法求解火力打击目标分配是有效的。

2）通过对多目标权重的调整，可以获得不同偏好情况下的火力目标分配结果，与先验数据一致，

说明使用该算法进行火力打击目标分配优化是可靠的。

3）算法采用了分布式搜索方法，在选择操作计算方面比串行选择节省了一定时间花销，算法性能较优且相对稳定。

5　结论

火力打击目标分配的目的是在各种作战约束条件下，发挥火力诸元的整体效能优势，寻求火力分配的最佳方案。本文针对火力打击的特点，建立了火力打击目标分配模型，提出的分布式遗传算法模拟退火算法经过仿真验证表明，可以满足多目标优化需要，较好解决了火力目标分配问题中的多目标优化问题。

参考文献:

［1］陶英歌，郭乃林，罗红英.基于遗传算法的目标分配优化模型研究［J］.系统工程与电子技术，2003，25（7）:817-819.

［2］冯杰.遗传算法及其在导弹火力分配上的应用［J］.火力与指挥控制，2004，29（2）:43-45.

［3］罗红英，刘进忙.遗传算法在目标优化分配中的应用［J］.电光与控制，2008，15（3）:18-20.

［4］张晓丰，程红斌，张凤鸣.改进遗传算法的导弹目标分配方法［J］.火力与指挥控制，2007，32（4）:59-61.

［5］郑世明，苗壮，董磊，等.基于云遗传算法的防空火力优化分配［J］.指挥信息系统与技术，2011，2（1）:21-26.

［6］BISHT S.Hybrid genetic-simulated annealing algorithm for optimal weapon allocation in multilayer defence scearion［J］.Defence Science Journal，2004，54（3）:395-405.

［7］狄海进，高璇.遗传模拟退火算法在多目标分配中的应用［J］.指挥信息系统与技术，2012，3（6）:22-24.

［8］牛晓博，赵虎，周国祥.基于并列选择遗传算法的舰艇编队目标分配问题［J］.现代防御技术，2010，38（6）:70-74.

［9］HOLLAND J.Adaptation in natural and artificial systems ［M］.MIT Press，Cambridge，MA，1992.

［10］邢立新，陈涠.联合火力打击任务匹配方法［J］.四川兵工学报，2012，32（3）:39-80.

［11］AYDIN M E，FOGARTY T C.A distributed evolutionary simulated annealing algorithm for combinational optimization problems［J］.Journal of Heuristics，2004，10（3）:269-292.

［12］ZADEH L.Optimality and non-scalar-valued performance criteria［J］.IEEE Transactions on Automatic Control，1963，59（8）:211-218.

Optimization for Target Assignment in Fire Strike Based on Distributed Genetic Simulated Annealing Algorithm

WU Kun-hong1，2，ZHAN Shi-xian1
（1.Unit 73630 of PLA，Fuzhou 350002，China；2.Institute of Military Operation Analysis Research，the Academy of Military Science，Beijing 100091，China）

Abstract：According to the rules of fire strike，a target assignment model is presented，and a Distributed Genetic Simulated Annealing algorithm（DGSA）is applied to resolve this model.DGSA is improved based on classic Genetic Algorithm（GA）as below:the single object serial-searched mode is changed to multiple objects distributed -searched mode，which is fitter for resolving multiobjective optimization; in order to keep a better balance between exploration and exploitation of algorithm，a method by coupling best one preservation and roulette wheel is established for individual selection，and simulated annealing algorithm is combined into crossover operation，and self -adaptive mutation probability is applied.Finally，the efficiency and reliability of DGSA is verified by simulation experiment.

Key words：target assignment in fire strike，multiobjective optimizations，genetic algorithm，simulated annealing algorithm

作者简介：吴坤鸿（1981-），男，福建漳蒲人，博士研究生。研究方向：军事运筹、信息对抗。

收稿日期：2015-03-11修回日期：2015-05-16

文章编号：1002-0640（2016）03-0089-04

中图分类号：E917

文献标识码：A