一种基于多目标克隆进化算法的大规模武器‑目标分配方法

摘要

本发明提供了一种基于多目标克隆进化算法的大规模武器‑目标分配方法，属于计算机仿真与方法优化技术领域，首先根据武器的数量生成多个初始子种群，并计算所有子种群的pareto最优解，用这些最优解构成优势种群；其次，算法采用克隆机制对优势种群中的所有个体进行克隆，形成多个新的子种群；然后，算法给出了三种特殊的进化算子，并用这三种进化算子对个体进行进化。本发明针对大规模武器‑目标分配问题，设计了相应的进化算子和进化方法，能够有效解决大规模武器‑目标分配问题，能够在大规模武器和目标的环境下，得到完整的pareto最优解，具备较好的收敛效果。

说明书

技术领域

本发明属于计算机仿真与方法优化技术领域，涉及一种多目标大规模武器-目标分配方法，可用于在有大量武器和大量敌方目标的环境下，计算出多个优化目标下的武器对目标的资源分配方案。

背景技术

武器-目标分配(Weapon Target Assignment，WTA)问题又称火力分配，是根据当前环境，结合我方武器数量及特点，为武器分配最优的攻击目标，以达到所希望的效能最大的过程。通过武器-目标分配，能够为指挥人员提供合理的武器攻击方案，辅助指挥人员做出决策。武器-目标分配方法一个典型的应用是民航机场或广场等区域的反无人机系统。随着未来无人机的普及，小型民用无人机将会变得越来越多，城市人流密集区域将会出现大量的无人机(主要用于摄像摄影或运输等)。为了维护区域的安全和秩序，反无人机系统能够采用电磁干扰或者捕捉网等方式实施无人机的拦截。但是，随着未来无人机数量的增多，传统人为分配武器目标的方法将不再适用，因此如何在有大量无人机的环境下合理的分配反无人机系统的武器具有重要的意义。

传统的求解武器-目标分配的方法大多是针对单个优化目标进行设计的，例如论文《编队防空火力分配建模及其优化方法研究》(阮旻智,李庆民,刘天华.编队防空火力分配建模及其优化方法研究.兵工学报,2010,31(11):1525-1529.)、《基于混合粒子群算法的多平台多武器火力分配研究》(陈华东,王树宗,王航宇.基于混合粒子群算法的多平台多武器火力分配研究.系统工程与电子技术,2008,30(5):880-883.)以及《基于量子分布估计算法的火力分配问题研究》(张毅,杨秀霞,周绍磊.基于量子分布估计算法的火力分配问题研究.电光与控制,2013(12):18-21.)。这些论文使用的武器-目标分配模型都是将武器的毁伤效能作为优化目标，属于单目标优化问题。发明专利《一种基于差分进化算法解决武器-目标分配问题的方法》(授权公告号CN 103336885B)采用的武器-目标分配模型不仅考虑到武器的毁伤效能还考虑了资源的优先级，但是该模型通过加权的方法将武器的毁伤效能和资源的优先级综合成一个目标函数，其仍然属于单目标优化问题。

多目标优化方法能够同时优化多个指标，可以从多个指标的角度提供多种解决方案，是近年来的研究的热点。求解基于多目标优化的武器-目标分配问题能够为指挥人员提供更全面的武器-目标分配方案。论文《火力分配多目标规划模型的改进MOPSO算法》(刘晓,刘忠,侯文姝,等.火力分配多目标规划模型的改进MOPSO算法.系统工程与电子技术,2013,35(2):326-330.)利用多目标粒子群算法(MOPSO)求解多目标火力分配问题，采用对敌毁伤概率以及所使用的火力单元数作为优化指标。论文《基于分解进化多目标优化算法的火力分配问题》(张滢,杨任农,左家亮,等.基于分解进化多目标优化算法的火力分配问题.系统工程与电子技术,2014,36(12):2435-2441.)采用了基于分解进化多目标优化算法(MOEA/D)求解火力分配问题。发明专利申请《一种基于改进多目标蛙跳算法的协同空战火力分配方法》(申请公开号CN 103425840A)采用了一种基于自适应网格法的多目标量子蛙跳算法来求解火力分配问题。这些论文和发明专利申请虽然能够解决多目标武器-目标分配问题，但是其算法模型都是基于小规模的武器和目标数量(武器数量少于50)进行的设计，在大规模的武器-目标问题下(武器数量超过50)这些方法并不能收敛得到完整的Pareto最优解，无法适用于大规模的武器-目标分配问题。

发明内容

为了克服现有技术的不足，本发明提供一种基于多目标克隆进化算法的大规模武器-目标分配方法，给多目标大规模武器-目标分配问题提供一种合理可行的解决方案。

本发明解决其技术问题所采用的技术方案是：一种基于多目标克隆进化算法的大规模武器-目标分配方法，包括步骤如下：

步骤1，输入武器、目标相关信息，包括：武器数量W，目标数量M，武器平台P＝[p₁,…,p_platform]，p_platform表示第platform个武器平台，各平台武器数量Pnum＝[pnum₁,…pnum_platform]，pnum_platform表示第platform个武器平台包含的武器数量，目标威胁度Th＝[th₁,…,th_M]，th_M表示第M个目标的威胁度，武器平台对目标的毁伤概率表示第platform个武器平台对第M个目标的毁伤概率；子种群的种群大小subpopsize，算法最大迭代次数maxstep，当前迭代次数step＝1；

步骤2，采用整数编码方式作为个体编码规则，个体的可编码位数与武器数量W相等，个体的编码code表示成code＝[c₁,…,c_W]，c₁,…,c_W∈[0,M]且c₁,…,c_W均为自然数；建立W个规模为subpopsize的子种群，并将所有子种群中的每个个体的编码code的全部可编码位c₁,…,c_W都赋值为0；对第一个子种群中的所有个体，分别随机选择其编码中的一个编码位，再随机从(0,M]中选择一个整数Rand，将Rand赋值给该编码位；对第二个子种群中的所有个体，分别随机选择其编码中的二个编码位，随机从(0,M]中选择二个整数Rand₁,Rand₂，将Rand₁,Rand₂分别赋值给这两个编码位；以此类推，对第W个子种群中的所有个体，对其全部W个编码位，随机从(0,M]中选择W个整数Rand₁,Rand₂，…Rand_W，将Rand₁,Rand₂，…Rand_W分别赋值给W编码位；

步骤3，将武器对敌毁伤概率f以及所使用的武器数量g作为两个适应度评价指标，所使用的武器-目标分配多目标优化模型如下：

其中d_ij表示第i种武器平台的一个武器对第j个敌方来袭目标的毁伤概率，一种武器平台只有一种武器；多种武器平台可攻击同一目标，各武器平台可同时攻击多个目标；设决策矩阵为[x_ij]_platform×M，才第i个武器平台攻击第j个目标，当第i个武器平台攻击第j个目标时x_ij取值为1，其他取值为0；

步骤4，取每个子种群中，具有最大的对敌毁伤概率f的个体，组合构成优势种群nondominatedpop；设第u个子种群中具有最大的对敌毁伤概率f的个体为bestindividual_u，u∈[1,W]，则优势种群

步骤5，判断当前迭代次数step是否等于最大迭代次数maxstep，若step＝maxstep则停止算法，输出当前优势种群nondominatedpop；若step≠maxstep则进入步骤6；

步骤6，对优势种群nondominatedpop中的每个个体进行规模为subpopsize的克隆操作，得到W个新的子种群newpop₁,…,newpop_W，newpop₁中包含subpopsize个bestindividual₁，newpop_W中包含subpopsize个bestindividual_W；

步骤7，对子种群newpop₁,…,newpop_W进行进化，具体方法如下：

依次取子种群newpop₁中的一个个体，以相等的概率选择三种进化算子中的一个对该个体执行进化；依次对子种群newpop₂,…,newpop_W执行进化；设当前需执行进化的个体为temppop，则三种进化算子的执行方式具体如下：

1)目标更换算子TCoperator执行方式如下：

1.1)随机选取个体temppop中的一个非零编码位，记为temp₁；

1.2)随机生成一个正整数TC，TC∈(0,M]；

1.3)如果TC与temp₁的值相等，则返回步骤1.2；如果TC与temp₁的值不相等，则继续执行；

1.4)用TC替换temp₁的值；

2)武器更换算子WCoperator执行方式如下：

2.1)随机选取个体temppop中的一个非零编码位，记为temp₂；

2.2)确定temp₂所属的武器平台，记该武器平台为tempplatform₁；

2.3)随机再选取个体temppop中的一个编码位，记为temp₃；

2.4)确定temp₃所属的武器平台，记该武器平台为tempplatform₂；

2.5)如果tempplatform₁＝tempplatform₂，则返回步骤2.3；否则继续执行下一步；

2.6)将编码位temp₂的值与编码位temp₃的值进行交换；

3)武器目标更换算子WTCoperator执行方式如下：

3.1)如果个体temppop没有值为零的编码位则不执行任何操作；如果个体temppop有值为零的编码位则执行下一步；

3.2)随机选择个体temppop的一个值为零的编码为，记为temp₄；

3.3)确定temp₄所属的武器平台，记该武器平台为tempplatform₃；

3.4)随机选取个体temppop中的一个非零编码位，记为temp₅；

3.5)确定temp₅所属的武器平台，记该武器平台为tempplatform₄；

3.6)如果tempplatform₃＝tempplatform₄，则返回步骤3.2)；否则继续执行下一步；

3.7)将编码位temp₄的值与编码位temp₅的值进行交换；

3.8)随机生成一个正整数TC，TC∈(0,M]；

3.9)如果TC与temp₄的值相等，则返回步骤3.8)；如果TC与temp₄的值不相等，则继续执行下一步；

3.10)用TC替换temp₄的值；

步骤8，计算当前进化后所有子种群的pareto最优解，并用所有子种群的pareto最优解构成优势种群nondominatedpop；同时使得step加1，返回步骤5。

所述子种群的种群大小subpopsize取[10,30]间的整数；算法最大迭代次数maxstep取[30,70]间的整数。

本发明的有益效果是：针对大规模武器-目标分配问题的特点，设计了一种克隆进化计算方法，提出了三种求解大规模武器-目标分配问题的进化算子和优势种群克隆机制。本发明设计的克隆进化计算方法能够有效解决多目标大规模武器-目标分配问题，设计的三种进化算子具有很强的武器-目标分配方案可行解搜索能力。同时本发明采用了多子种群的策略，按照武器的数量生成子种群，能够全面的搜索武器-目标分配方案的可行解，在具有大规模武器和目标的环境下能够得到完整的pareto最优解，同时具备较好的收敛性。

附图说明

图1为算法的编码方式示意图

图2为克隆操作原理示意图

图3为实例1独立运行30次的IGD值的统计盒图

图4为本发明算法在实例2下的pareto最优解

图5为本发明的实现方法流程图

具体实施方式

下面结合附图和实施例对本发明进一步说明，本发明包括但不仅限于下述实施例。

本发明按照图5所示的流程图实施如下步骤：

步骤1：输入武器、目标相关信息，确定算法相关参数。具体内容如下：

输入武器数量W；目标数量M；武器平台P＝[p₁,…,p_platform]，platform表示平台的数量，P_platform表示第platform个武器平台，其余类似；各平台武器数量Pnum＝[pnum₁,…pnum_platform]，pnum_platform表示第platform个武器平台包含的武器数量，其余类似，满足目标威胁度Th＝[th₁,…,th_M]，th_M表示第M个目标的威胁度，其余类似，满足武器平台对目标的毁伤概率D，D可以表示为：

式中d_platformM表示第platform个武器平台对第M个目标的毁伤概率，其余类似。

输入子种群的种群大小subpopsize，为了保持算法的求解性能subpopsize不宜过大或者过小，subpopsize可取[10,30]间的整数；算法最大迭代次数maxstep，为了保证算法性能，maxstep可取[30,70]间的整数；当前迭代次数step＝1。

步骤2：根据个体编码规则和武器数量，生成多个初始子种群，具体内容如下：

2.1个体编码规则如下：采用整数编码方式，个体的可编码位数与武器数量W相等，个体的编码code可表示成code＝[c₁,…,c_W]，c₁,…,c_W∈[0,M]且c₁,…,c_W均为自然数。个体编码规则具体如图1所示。由图1可见个体的编码根据武器平台顺序排列，第1个武器平台的武器排在前面，接下来是第2个武器平台的武器，以此类推，最终所有W个武器组成个体的编码。

2.2子种群初始化方法如下：首先建立W个规模为subpopsize的子种群，并将所有子种群中的每个个体的编码code的全部可编码位赋值为0，即将c₁,…,c_W都赋值为0。然后，对第一个子种群中的所有个体，分别随机选择其编码中的一个编码位，随机从(0,M]中选择一个整数Rand，将Rand赋值给该编码位。接下来，对第二个子种群中的所有个体，分别随机选择其编码中的二个编码位，随机从(0,M]中选择二个整数Rand₁,Rand₂，将Rand₁,Rand₂分别赋值给这两个编码位。最后，按照以上方法以此类推，一直到第W个子种群，对第W个子种群中的所有个体，对其全部W个编码位，随机从(0,M]中选择W个整数Rand₁,Rand₂，…Rand_W，将Rand₁,Rand₂，…Rand_W分别赋值给W编码位。

步骤3：根据武器-目标分配多目标优化模型以及相关武器和目标信息，计算所有个体的适应度函数fitness，fitness由武器对敌毁伤概率f以及所使用的武器数量g两个适应度评价指标构成，即fitness＝[f,g]，具体计算方法如下：

将武器对敌毁伤概率f以及所使用的武器数量g作为两个适应度评价指标，所使用的武器-目标分配多目标优化模型如下：

其中d_ij表示第i种武器平台的一个武器对第j个敌方来袭目标的毁伤概率，一种武器平台只有一种武器；多种武器平台可攻击同一目标，各武器平台可同时攻击多个目标；设决策矩阵为[x_ij]_platform×M，x_ij表示第i个武器平台攻击第j个目标，x_ij的表达式如下：

步骤4：计算当前所有子种群的pareto最优解，并用所有子种群的pareto最优解构成优势种群nondominatedpop，具体方法如下：

取每个子种群中，具有最大的对敌毁伤概率f的个体，将所有子种群中的这些个体组合构成优势种群nondominatedpop。设第u个子种群中具有最大的对敌毁伤概率f的个体为bestindividual_u，u∈[1,W]，则优势种群nondominatedpop可表示为如下：

步骤5：判断当前迭代次数step是否等于最大迭代次数maxstep，若step＝maxstep则停止算法，输出当前优势种群nondominatedpop；若step≠maxstep则继续执行下面的步骤。

步骤6：对优势种群nondominatedpop中的每个个体进行规模为subpopsize的克隆操作，得到W个新的子种群，分别记为newpop₁,…,newpop_W，即newpop₁中包含subpopsize个bestindividual₁，newpop_W中包含subpopsize个bestindividual_W，其余类似。克隆操作具体如图2所示。

步骤7：对子种群newpop₁,…,newpop_W进行进化。进化算子共分为三种，第一种为目标更换算子记为TCoperator，第二种为武器更换算子记为WCoperator，第三种为武器目标更换算子记为WTCoperator。进化具体方法如下：

首先取子种群newpop₁中第一个个体，然后以相等的概率选择三种进化算子中的一个，最后利用选择的进化算子对第一个个体执行进化。按照以上步骤对第二个个体到第subpopsize个个体进行，从而完成子种群newpop₁的进化。子种群newpop₂,…,newpop_W的进化方式类似。设当前需执行进化的个体为temppop，则三种进化算子的执行方式具体如下：

2目标更换算子(TCoperator)执行方式如下：

2.1随机选取个体temppop中的一个非零编码位，记为temp₁。

1.2随机生成一个正整数TC，TC∈(0,M]。

1.3如果TC与temp₁的值相等，则返回步骤1.2；如果TC与temp₁的值不相等，则继续执行。

1.4用TC替换temp₁的值。

2武器更换算子(WCoperator)执行方式如下：

2.1随机选取个体temppop中的一个非零编码位，记为temp₂。

2.2确定temp₂所属的武器平台，记该武器平台为tempplatform₁。

2.3随机再选取个体temppop中的一个编码位，记为temp₃。

2.4确定temp₃所属的武器平台，记该武器平台为tempplatform₂。

2.5如果tempplatform₁＝tempplatform₂，则返回步骤2.3；否则继续执行下一步。

2.6将编码位temp₂的值与编码位temp₃的值进行交换。

3武器目标更换算子(WTCoperator)执行方式如下：

3.1如果个体temppop没有值为零的编码位则不执行任何操作；如果个体temppop有值为零的编码位则执行以下步骤。

3.2随机选择个体temppop的一个值为零的编码为，记为temp₄。

3.3确定temp₄所属的武器平台，记该武器平台为tempplatform₃。

3.4随机选取个体temppop中的一个非零编码位，记为temp₅。

3.5确定temp₅所属的武器平台，记该武器平台为tempplatform₄。

3.6如果tempplatform₃＝tempplatform₄，则返回步骤3.2；否则继续执行下一步。

3.7将编码位temp₄的值与编码位temp₅的值进行交换。

3.8随机生成一个正整数TC，TC∈(0,M]。

3.9如果TC与temp₄的值相等，则返回步骤3.8；如果TC与temp₄的值不相等，则继续执行。

3.10用TC替换temp₄的值。

步骤8：计算当前进化后所有子种群的pareto最优解，并用所有子种群的pareto最优解构成优势种群nondominatedpop。同时使得step＝step+1，返回步骤5。

本发明的效果可以通过以下仿真实例进一步说明：

实例1：武器数量8；目标数量4；武器平台有3个；各平台武器数量Pnum＝[3 3 2]；目标威胁度Th＝[0.15 0.36 0.18 0.31]；子种群的种群大小20；算法最大迭代次数50；武器平台对目标的毁伤概率D为：

D＝[0.78 0.76 0.62 0.71；

0.92 0.68 0.59 0.59；

0.86 0.93 0.77 0.69]

为了便于对比算法的收敛性，采用穷举法求出该实例下可行解与pareto最优解，pareto最优解如表1所示。

表1pareto最优解

g1234f0.33480.55490.69350.8315g5678f0.89530.92100.93890.9554

独立运行本发明提出的算法30次，记录每一次最终的优势种群。利用IGD(Invertedgenerational distance)指标来评价算法的性能，IGD指标计算公式如下：

式中Z表示仿真实例问题的真实pareto最优解的集合，Z＝(z₁,z₂,…,z_|Z|)；算法得到的pareto最优解的集合为A，A＝(a₁,a₂,…,a_|A|)，在本发明算法中A即为最终的优势种群。

独立运行本发明算法30次，计算每次运行的最终IGD如表2所示。

表2独立运行30次的IGD值

序号12345678910IGD0.01780.01390.01190.00580.00130.01700.00760.02520.01310.0041序号11121314151617181920IGD0.01840.00650.01200.00530.01170.00570.01540.01700.00630.0048序号21222324252627282930IGD0.00740.01380.02180.02290.020.00920.01350.01650.02050.0178

图3为独立运行30次的IGD值的统计盒图。从图3和表2可以看到，本发明算法具有良好的收敛特性和稳定性，能够较好的逼近多目标武器-目标分配问题的pareto最优解。

实例2：武器数量50；目标数量20；武器平台有10个；各平台武器数量Pnum＝[5 5 5 5 5 5 5 5 5 5]；目标威胁度Th＝[0.02 0.03 0.05 0.08 0.07 0.01 0.09 0.04 0.06 0.05 0.05 0.05 0.03 0.07 0.02 0.08 0.04 0.06 0.01 0.09]；子种群的种群大小20；算法最大迭代次数50；武器平台对目标的毁伤概率D为：

D＝[0.783 0.762 0.627 0.712 0.651 0.794 0.944 0.852 0.969 0.752 0.793 0.851 0.896 0.932 0.686 0.914 0.887 0.751 0.692 0.962；

0.925 0.683 0.591 0.593 0.892 0.756 0.688 0.763 0.788 0.953 0.968 0.863 0.648 0.794 0.814 0.925 0.694 0.832 0.674 0.845；

0.866 0.934 0.772 0.695 0.598 0.897 0.754 0.685 0.763 0.755 0.791 0.857 0.898 0.936 0.688 0.911 0.888 0.754 0.696 0.976；

0.927 0.685 0.599 0.591 0.894 0.598 0.897 0.751 0.686 0.768 0.792 0.854 0.893 0.938 0.684 0.927 0.696 0.835 0.673 0.847；

0.629 0.717 0.654 0.798 0.944 0.859 0.686 0.766 0.751 0.796 0.857 0.895 0.932 0.683 0.928 0.919 0.889 0.756 0.690 0.964；

0.592 0.899 0.593 0.894 0.758 0.753 0.795 0.857 0.892 0.934 0.655 0.749 0.899 0.962 0.943 0.565 0.788 0.817 0.699 0.867；

0.751 0.791 0.858 0.896 0.937 0.896 0.754 0.689 0.763 0.799 0.943 0.853 0.688 0.687 0.927 0.913 0.885 0.758 0.758 0.688；

0.684 0.762 0.757 0.929 0.682 0.595 0.592 0.894 0.936 0.684 0.968 0.949 0.561 0.784 0.816 0.652 0.793 0.943 0.857 0.689；

0.895 0.754 0.686 0.762 0.784 0.687 0.593 0.592 0.894 0.592 0.856 0.896 0.936 0.688 0.924 0.855 0.685 0.685 0.925 0.914；

0.857 0.686 0.765 0.754 0.796 0.789 0.761 0.627 0.717 0.651 0.794 0.811 0.924 0.692 0.831 0.966 0.944 0.563 0.782 0.815]

因为武器-目标分配问题属于NP问题，对于大规模的武器-目标分配问题若采用穷举法求解真实pareto最优解是不现实的，因此在此只说明算法的可行性。

独立运行本发明算法一次，得到pareto最优解如表3所示。

表3本发明算法在实例2下的pareto最优解

g12345678910f0.08660.16100.24680.30840.37480.43290.47230.53980.58790.6263g11121314151617181920f0.66020.70950.74390.77980.79810.83080.84960.84920.87900.8804g21222324252627282930f0.90030.89540.91640.91770.92360.93030.93450.94020.94430.9521g31323334353637383940f0.95670.95760.96120.96630.96640.96770.96960.97240.97430.9792g41424344454647484950f0.97650.97890.98050.98320.98490.98450.98660.98770.98860.9888

图4为本发明算法在实例2下的pareto最优解。由图4可见，本发明算法能够完整的得到大规模武器-目标分配问题的pareto最优解，并且最优解的分布符合真实pareto最优解的分布规律，因此本发明算法能够有效解决大规模武器-目标分配问题。