改进的多目标粒子群优化算法及其在弹药维修任务调配中的应用

王 琦， 穆希辉， 吕晓明， 江劲勇

(1. 63908部队， 河北 石家庄 050000; 2. 66440部队， 河北 石家庄 050052)

改进的多目标粒子群优化算法及其在弹药维修任务调配中的应用

王 琦1,2， 穆希辉1， 吕晓明1， 江劲勇1

(1. 63908部队， 河北 石家庄 050000; 2. 66440部队， 河北 石家庄 050052)

针对多目标粒子群算法多样性不好、收敛精度不高等问题，提出了一种改进的多目标粒子群优化算法。该算法设计了一种基于聚类算法的全局引导策略，并对初始惯性权值进行了非线性递减的自适应调整。结合现阶段我军弹药维修任务调配中的实际问题，构建了弹药维修任务调配多目标优化模型。通过算例求解和MATLAB仿真，验证了该算法的Pareto解集具有更好的多样性和收敛性，为我军弹药维修的定量决策提供了参考。

多目标粒子群优化算法；弹药维修决策；多目标模型；聚类算法

长期以来,我军对弹药维修工作的重视程度不高，尤其是针对当前弹药种类多、型号杂、维修单位能力参差不齐等问题，缺乏全局统筹和科学调配，导致维修效率不高，维修资源浪费严重，影响部队的战备和训练。因此，必须综合考虑维修能力、维修效率等因素，科学调配弹药维修任务，实现维修资源的合理配置。

弹药维修任务的调配属于多目标优化问题。目前，解决多目标优化问题的算法比较多，主要有：NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm Ⅱ)、SPEA2(Strength Pareto Evolutionary Algorithm 2)、PAES (Pareto Archived Evolutionary Strategy)、PESA (Pareto Evelope-based Seletion Algorithm)、多目标粒子群(Multi-Objective Particle Swarm Optimization, MOPSO)等算法[1]。其中，MOPSO算法因其计算简便、参数设置方便、收敛速度快等特点而备受研究者的青睐[2-6]。由于多目标优化问题无法得到全局最优的唯一解，只是存在一个Pareto非支配解集，因此，需要通过全局最优引导使整个种群向Pareto解集收敛。然而，已有的全局引导策略往往存在解集多样性不好、收敛精度不高等问题。为此，本文设计了一种基于聚类算法的全局引导策略，并对初始惯性权值w的变化方式进行改进，对解集进行优化。

1 改进的MOPSO算法

1.1 MOPSO算法流程

MOPSO算法的流程如图1所示。其中：1)初始化种群时将对每个粒子的速度和位置随机赋值，设种群规模为P，总进化代数为N，初始惯性权值为w；2)搜索和更新全局最优粒子gbest时，采用相应的全局引导策略对粒子的搜索轨迹进行引导；3)对初始惯性权值w进行调整，以改变粒子在不同时间段的飞行搜索速度；4)第i个粒子的速度和位置的更新公式分别为

vid(t+1)=wvid(t)+c1r1(pbestid-xid(t))+

c2r2(gbestid-xid(t)),

(1)

xid(t+1)=xid(t)+vid(t+1)。

(2)

式中:c1、c2为学习因子；r1、r2为[0, 1]内的随机数；d为空间的维数。

图1 MOPSO算法的流程

1.2 改进的全局最优引导策略

目前，运用较为广泛的全局最优引导策略主要有自适应网格法和拥挤距离法。其中：自适应网格法的网格数目确定难度较大，计算过程中会由于网格过大而影响收敛速度；拥挤距离法仅从局部区域选择全局最优引导，不能兼顾全局信息，易陷入局部最优。

本文设计了一种基于聚类算法的全局引导策略，其基本思路是：根据粒子的位置，把档案集(Archive)中的粒子按“类中心与粒子之间欧氏距离最小”的原则分为M类(M与Archive的容量成正比)，通过计算选出每类中的代表粒子，然后再从各类的代表粒子中随机选出一个作为最优引导粒子。由于空间中的任意区域无论粒子密度的大小，其都会形成1个类，因此稀疏区域的粒子被选为全局最优引导粒子的概率大大增加。这样，就可在充分考虑非支配前端上所有粒子分布的情况下，增加解集的多样性。具体引导步骤如下：

1) 设Archive中有种群B={x1,x2,…,xa}，xi为B中的第i个粒子，从B中任意选取m(m

1.3 初始惯性权值w的改进

初始惯性权值w的调整通常采用线性递减策略[7]。由于粒子群(Particle Swarm Optimization,PSO)算法的搜索过程较复杂，线性递减策略会使w在较大或较小值时均得不到充足的停留时间，减弱了对搜索过程的优化作用。若在整个搜索过程前期，w能较长时间保持较大值，则有利于提高全局搜索速度；若在后期能较长时间保持较小值，则有利于提高局部搜索精度。因此，本文采用自适应非线性递减策略来改进w，即

(3)

式中：T为当前的进化代数。

由此可知:w的取值分布为由2个抛物线组合而成的反“S”型曲线,且在曲线的前区和后区部分其速度递减较慢，而在中区部分其速度递减相对较快。

2 弹药维修任务调配多目标模型

当前，我军主要采用总部、军区、基层3级弹药维修体制。其中，总部弹药修理厂和军区弹药修配站是承担弹药修理任务的主体，基层仓库的弹药检修所仅进行一些简单的弹药维护和保养工作，因此本文不考虑对基层级分配修理任务。另外，根据不同弹种的工作原理和维修工作的相似性，运用故障树分析(Failure Tree Analysis , FTA)和故障模式影响分析(Failure Mode and Effect Analysis, FMEA)方法，将其分为轻武器类、后装炮弹类、迫击炮弹类、火箭弹类等多个维修种类。

影响弹药维修效果的因素较多，但其关键因素主要有：1)在战时，弹药的快速供应保障需求对维修的时效性提出了较高要求；2)在平时，大部分弹药处于长期贮存状态，需要保持较高的可靠性；3)由于国防经费的限制，弹药维修时应尽量节约维修经费的开支等。

因此，本文以影响弹药维修效果较大的因素，即维修时间T、维修费用C、维修可靠性R为优化目标，分别建立如下目标函数：

式中:p为全军承担修理任务的总部和军区级维修机构数；q为待修弹药种类数；tij、xij、cij、rij分别为维修机构i对第j类弹药的维修时间、维修任务、维修费用和维修可靠性。

在弹药维修任务调配决策中，要充分考虑各弹药维修机构的实际维修能力和维修经费，使各维修机构既保持一定的维修任务来加强其自身建设，又能顺利完成其承担的维修任务。因此，设置如下约束条件：

1)xij≤aij(∀i∈[1,p],∀j∈[1,q])，aij为维修机构i对第j类弹药的维修能力(年度最大维修量)；

4) 0

3 算例与仿真分析

3.1 参数设置

设某年参与弹药维修任务的维修机构数p=5；待修弹药种类数q=4；维修机构i的年度最大可支配经费Bi=[200,320,400,240,280];各类弹药的数量Mi=[16,20,12,24];维修机构i对第j类弹药的维修维修时间Tij、维修费用Cij、维修可靠性Rij和维修能力Aij分别为

初始化种群规模P=100；进化代数N=1 000；外部档案A=100；初始惯性权值的wmax=0.9，wmin=0.4；学习因子c1=c2=2.0；聚类值M=8。

3.2 算法性能比较与分析

选择4个有代表性的测试函数KUR、ZDT1、ZDT3、ZDT6，以收敛性指标GD(Generational Distance)和多样性指标SP(Space)为评价指标，评价次数为20 000次，每个函数的实验均重复50次以排除干扰因素的影响，对改进前后的MOPSO算法[8]及NSGA-Ⅱ算法[9]的性能进行比较，结果如表1、2所示。

表1 各算法收敛性指标GD比较

表2 各算法多样性指标SP比较

由表1可见：1)改进的MOPSO算法在ZDT1、ZDT3、ZDT6测试函数中的收敛性能均优于其他2种算法，但在测试函数KUR中，其GD均值与其他2种方法差别不大，收敛性能较为接近；2)改进的MOPSO算法的GD方差值均小于其他2种算法，表明其收敛稳定性最好。

由表2可见：改进的MOPSO算法的多样性能在4个测试函数中均优于其他2种算法，稳定性也好。

3.3 仿真及其结果分析

结合弹药维修任务调配多目标模型，运用MATLAB对改进MOPSO算法进行求解，可得其Pareto解集分布如图2所示，其部分最优解集如表3所示。

图2 改进MOPSO算法的Pareto解集分布

表3 改进MOPSO算法的部分Pareto最优解集

对于Pareto解集，在实际中往往需要从中选出若干个满意解。本文根据总部年度弹药维修任务的具体要求进行选取，如：为了最大限度节约维修经费开支，可选择表3中的方案7；战时弹药需求量大，需要快速补给弹药，且维修后的弹药主要用于短期使用，则可选择方案2。另外，也可运用“基于模糊集理论的最佳折中方案”[10]，通过建立反映满意程度的隶属度函数来选取满意解。

4 结论

本文提出了一种基于聚类算法的全局引导策略和惯性权值非线性递减策略相结合的改进MOPSO算法；结合我军弹药维修决策现状，构建了弹药维修任务调配多目标模型，并运用算法对模型进行求解。通过算例及仿真验证了该算法的优越性及对该类问题的良好求解能力，在我军弹药维修任务调配的定量决策工作中起到重要作用。然而，本文并未考虑由于弹药贮存地不同而给送修过程带来的影响，这也是下一步工作需继续深入研究的问题。

[1] 凌海风.面向装备保障的多准则决策相关方法和技术研究[D].南京：南京大学，2011.

[2] Jumaat S A, Musirin I, Othman M M, et al. MOPSO Approach for FACTS Device Installation in Power System[C]∥Proceedings of IEEE 7th International Power Engineering and Optimization Conference. USA: IEEE, 2013: 564-569.

[3] Pang X, Rybarcyk L J. Multi-objective Particle Swarm and Genetic Algorithm for the Optimization of the LANSCE Linac Operation[J].Nuclear Instruments & Methods in Physics Research, 2014,741(3): 124-129.

[4] 刘晓，刘忠，侯文姝,等.火力分配多目标规划模型的改进MOPSO算法[J].系统工程与电子技术，2013,35(2):326-330.

[5] 刘勇，贾庆轩，陈钢，等.基于多目标粒子群优化算法的自由漂浮空间机器人负载最大化轨迹优化[J].机器人，2014,36(4):402-410.

[6] Li W X, Zhou Q, Zhu Y, et al. An Improved MOPSO with a Crowding Distance Based External Archive Maintenance Strategy[C]∥Proceedings of 3rd International Conference on Swarm Intelligence.Germany: Springer Verlag, 2012: 74-82.

[7] 刘宝宁，章卫国，聂瑞.一种改进混沌MOPSO算法及其在飞控系统中的应用[J].计算机测量与控制,2012,20(8):2149-2151.

[8] Coello C A, Pulido G T, Lechuga M S. Handling Multiple Objectives with Particle Swarm Optimization[J]. IEEE Trans Evol Comput,2004,3(3): 256-279.

[9] Deb K, Pratao A, Agarwal S, et al. A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation, 2002,6(2): 182-197.

[10] 颜楠楠，傅正财.基于多目标粒子群优化算法的UPFC协调控制[J].电力系统保护与控制，2010,38(8):43-48.

(责任编辑: 王生凤)

Improved Multi-Objective Particle Swarm Optimization Algorithm and Its Application in Ammunition Maintenance Task Allocation

WANG Qi1，2, MU Xi-hui1, LÜ Xiao-ming1, JIANG Jin-yong1

(1. Troop No. 63908 of PLA, Shijiazhuang 050000, China; 2. Troop No.66440 of PLA, Shijiazhuang 050052, China)

An improved method is proposed against the shortcomings of poor diversity and weak convergence accuracy in multi-objective particle swarm optimization algorithm. The algorithm devises a global guidance selection strategy based on clustering algorithm and makes self-adaption of inertia weight non-linear decreasing. The multi-objective optimization model of ammunition maintenance task allocation is built according to the problems of army ammunition maintenance task allocation. Through examples solution and MATLAB simulation, it is proved that the improved algorithm has a better diversity and convergence in the Pareto solution set, which provides references for quantitative decisions of army ammunition maintenance.

multi-objective particle swarm optimization algorithm; ammunition maintenance decision; multi-objective model; clustering algorithm

1672-1497(2015)05-0014-04

2015-06-15

王 琦(1985-)，男，硕士研究生。

E92

A

10.3969/j.issn.1672-1497.2015.05.004