改進(jìn)的多目標(biāo)粒子群優(yōu)化算法及其在彈藥維修任務(wù)調(diào)配中的應(yīng)用

王 琦， 穆希輝， 呂曉明， 江勁勇

(1. 63908部隊(duì)， 河北 石家莊 050000; 2. 66440部隊(duì)， 河北 石家莊 050052)

改進(jìn)的多目標(biāo)粒子群優(yōu)化算法及其在彈藥維修任務(wù)調(diào)配中的應(yīng)用

王 琦1,2， 穆希輝1， 呂曉明1， 江勁勇1

(1. 63908部隊(duì)， 河北 石家莊 050000; 2. 66440部隊(duì)， 河北 石家莊 050052)

針對(duì)多目標(biāo)粒子群算法多樣性不好、收斂精度不高等問題，提出了一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法。該算法設(shè)計(jì)了一種基于聚類算法的全局引導(dǎo)策略，并對(duì)初始慣性權(quán)值進(jìn)行了非線性遞減的自適應(yīng)調(diào)整。結(jié)合現(xiàn)階段我軍彈藥維修任務(wù)調(diào)配中的實(shí)際問題，構(gòu)建了彈藥維修任務(wù)調(diào)配多目標(biāo)優(yōu)化模型。通過算例求解和MATLAB仿真，驗(yàn)證了該算法的Pareto解集具有更好的多樣性和收斂性，為我軍彈藥維修的定量決策提供了參考。

多目標(biāo)粒子群優(yōu)化算法；彈藥維修決策；多目標(biāo)模型；聚類算法

長期以來,我軍對(duì)彈藥維修工作的重視程度不高，尤其是針對(duì)當(dāng)前彈藥種類多、型號(hào)雜、維修單位能力參差不齊等問題，缺乏全局統(tǒng)籌和科學(xué)調(diào)配，導(dǎo)致維修效率不高，維修資源浪費(fèi)嚴(yán)重，影響部隊(duì)的戰(zhàn)備和訓(xùn)練。因此，必須綜合考慮維修能力、維修效率等因素，科學(xué)調(diào)配彈藥維修任務(wù)，實(shí)現(xiàn)維修資源的合理配置。

彈藥維修任務(wù)的調(diào)配屬于多目標(biāo)優(yōu)化問題。目前，解決多目標(biāo)優(yōu)化問題的算法比較多，主要有：NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm Ⅱ)、SPEA2(Strength Pareto Evolutionary Algorithm 2)、PAES (Pareto Archived Evolutionary Strategy)、PESA (Pareto Evelope-based Seletion Algorithm)、多目標(biāo)粒子群(Multi-Objective Particle Swarm Optimization, MOPSO)等算法[1]。其中，MOPSO算法因其計(jì)算簡便、參數(shù)設(shè)置方便、收斂速度快等特點(diǎn)而備受研究者的青睞[2-6]。由于多目標(biāo)優(yōu)化問題無法得到全局最優(yōu)的唯一解，只是存在一個(gè)Pareto非支配解集，因此，需要通過全局最優(yōu)引導(dǎo)使整個(gè)種群向Pareto解集收斂。然而，已有的全局引導(dǎo)策略往往存在解集多樣性不好、收斂精度不高等問題。為此，本文設(shè)計(jì)了一種基于聚類算法的全局引導(dǎo)策略，并對(duì)初始慣性權(quán)值w的變化方式進(jìn)行改進(jìn)，對(duì)解集進(jìn)行優(yōu)化。

1 改進(jìn)的MOPSO算法

1.1 MOPSO算法流程

MOPSO算法的流程如圖1所示。其中：1)初始化種群時(shí)將對(duì)每個(gè)粒子的速度和位置隨機(jī)賦值，設(shè)種群規(guī)模為P，總進(jìn)化代數(shù)為N，初始慣性權(quán)值為w；2)搜索和更新全局最優(yōu)粒子gbest時(shí)，采用相應(yīng)的全局引導(dǎo)策略對(duì)粒子的搜索軌跡進(jìn)行引導(dǎo)；3)對(duì)初始慣性權(quán)值w進(jìn)行調(diào)整，以改變粒子在不同時(shí)間段的飛行搜索速度；4)第i個(gè)粒子的速度和位置的更新公式分別為

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為學(xué)習(xí)因子；r1、r2為[0, 1]內(nèi)的隨機(jī)數(shù)；d為空間的維數(shù)。

圖1 MOPSO算法的流程

1.2 改進(jìn)的全局最優(yōu)引導(dǎo)策略

目前，運(yùn)用較為廣泛的全局最優(yōu)引導(dǎo)策略主要有自適應(yīng)網(wǎng)格法和擁擠距離法。其中：自適應(yīng)網(wǎng)格法的網(wǎng)格數(shù)目確定難度較大，計(jì)算過程中會(huì)由于網(wǎng)格過大而影響收斂速度；擁擠距離法僅從局部區(qū)域選擇全局最優(yōu)引導(dǎo)，不能兼顧全局信息，易陷入局部最優(yōu)。

本文設(shè)計(jì)了一種基于聚類算法的全局引導(dǎo)策略，其基本思路是：根據(jù)粒子的位置，把檔案集(Archive)中的粒子按“類中心與粒子之間歐氏距離最小”的原則分為M類(M與Archive的容量成正比)，通過計(jì)算選出每類中的代表粒子，然后再從各類的代表粒子中隨機(jī)選出一個(gè)作為最優(yōu)引導(dǎo)粒子。由于空間中的任意區(qū)域無論粒子密度的大小，其都會(huì)形成1個(gè)類，因此稀疏區(qū)域的粒子被選為全局最優(yōu)引導(dǎo)粒子的概率大大增加。這樣，就可在充分考慮非支配前端上所有粒子分布的情況下，增加解集的多樣性。具體引導(dǎo)步驟如下：

1) 設(shè)Archive中有種群B={x1,x2,…,xa}，xi為B中的第i個(gè)粒子，從B中任意選取m(m

1.3 初始慣性權(quán)值w的改進(jìn)

初始慣性權(quán)值w的調(diào)整通常采用線性遞減策略[7]。由于粒子群(Particle Swarm Optimization,PSO)算法的搜索過程較復(fù)雜，線性遞減策略會(huì)使w在較大或較小值時(shí)均得不到充足的停留時(shí)間，減弱了對(duì)搜索過程的優(yōu)化作用。若在整個(gè)搜索過程前期，w能較長時(shí)間保持較大值，則有利于提高全局搜索速度；若在后期能較長時(shí)間保持較小值，則有利于提高局部搜索精度。因此，本文采用自適應(yīng)非線性遞減策略來改進(jìn)w，即

(3)

式中：T為當(dāng)前的進(jìn)化代數(shù)。

由此可知:w的取值分布為由2個(gè)拋物線組合而成的反“S”型曲線,且在曲線的前區(qū)和后區(qū)部分其速度遞減較慢，而在中區(qū)部分其速度遞減相對(duì)較快。

2 彈藥維修任務(wù)調(diào)配多目標(biāo)模型

當(dāng)前，我軍主要采用總部、軍區(qū)、基層3級(jí)彈藥維修體制。其中，總部彈藥修理廠和軍區(qū)彈藥修配站是承擔(dān)彈藥修理任務(wù)的主體，基層倉庫的彈藥檢修所僅進(jìn)行一些簡單的彈藥維護(hù)和保養(yǎng)工作，因此本文不考慮對(duì)基層級(jí)分配修理任務(wù)。另外，根據(jù)不同彈種的工作原理和維修工作的相似性，運(yùn)用故障樹分析(Failure Tree Analysis , FTA)和故障模式影響分析(Failure Mode and Effect Analysis, FMEA)方法，將其分為輕武器類、后裝炮彈類、迫擊炮彈類、火箭彈類等多個(gè)維修種類。

影響彈藥維修效果的因素較多，但其關(guān)鍵因素主要有：1)在戰(zhàn)時(shí)，彈藥的快速供應(yīng)保障需求對(duì)維修的時(shí)效性提出了較高要求；2)在平時(shí)，大部分彈藥處于長期貯存狀態(tài)，需要保持較高的可靠性；3)由于國防經(jīng)費(fèi)的限制，彈藥維修時(shí)應(yīng)盡量節(jié)約維修經(jīng)費(fèi)的開支等。

因此，本文以影響彈藥維修效果較大的因素，即維修時(shí)間T、維修費(fèi)用C、維修可靠性R為優(yōu)化目標(biāo)，分別建立如下目標(biāo)函數(shù)：

式中:p為全軍承擔(dān)修理任務(wù)的總部和軍區(qū)級(jí)維修機(jī)構(gòu)數(shù)；q為待修彈藥種類數(shù)；tij、xij、cij、rij分別為維修機(jī)構(gòu)i對(duì)第j類彈藥的維修時(shí)間、維修任務(wù)、維修費(fèi)用和維修可靠性。

在彈藥維修任務(wù)調(diào)配決策中，要充分考慮各彈藥維修機(jī)構(gòu)的實(shí)際維修能力和維修經(jīng)費(fèi)，使各維修機(jī)構(gòu)既保持一定的維修任務(wù)來加強(qiáng)其自身建設(shè)，又能順利完成其承擔(dān)的維修任務(wù)。因此，設(shè)置如下約束條件：

1)xij≤aij(?i∈[1,p],?j∈[1,q])，aij為維修機(jī)構(gòu)i對(duì)第j類彈藥的維修能力(年度最大維修量)；

4) 0

3 算例與仿真分析

3.1 參數(shù)設(shè)置

設(shè)某年參與彈藥維修任務(wù)的維修機(jī)構(gòu)數(shù)p=5；待修彈藥種類數(shù)q=4；維修機(jī)構(gòu)i的年度最大可支配經(jīng)費(fèi)Bi=[200,320,400,240,280];各類彈藥的數(shù)量Mi=[16,20,12,24];維修機(jī)構(gòu)i對(duì)第j類彈藥的維修維修時(shí)間Tij、維修費(fèi)用Cij、維修可靠性Rij和維修能力Aij分別為

初始化種群規(guī)模P=100；進(jìn)化代數(shù)N=1 000；外部檔案A=100；初始慣性權(quán)值的wmax=0.9，wmin=0.4；學(xué)習(xí)因子c1=c2=2.0；聚類值M=8。

3.2 算法性能比較與分析

選擇4個(gè)有代表性的測(cè)試函數(shù)KUR、ZDT1、ZDT3、ZDT6，以收斂性指標(biāo)GD(Generational Distance)和多樣性指標(biāo)SP(Space)為評(píng)價(jià)指標(biāo)，評(píng)價(jià)次數(shù)為20 000次，每個(gè)函數(shù)的實(shí)驗(yàn)均重復(fù)50次以排除干擾因素的影響，對(duì)改進(jìn)前后的MOPSO算法[8]及NSGA-Ⅱ算法[9]的性能進(jìn)行比較，結(jié)果如表1、2所示。

表1 各算法收斂性指標(biāo)GD比較

表2 各算法多樣性指標(biāo)SP比較

由表1可見：1)改進(jìn)的MOPSO算法在ZDT1、ZDT3、ZDT6測(cè)試函數(shù)中的收斂性能均優(yōu)于其他2種算法，但在測(cè)試函數(shù)KUR中，其GD均值與其他2種方法差別不大，收斂性能較為接近；2)改進(jìn)的MOPSO算法的GD方差值均小于其他2種算法，表明其收斂穩(wěn)定性最好。

由表2可見：改進(jìn)的MOPSO算法的多樣性能在4個(gè)測(cè)試函數(shù)中均優(yōu)于其他2種算法，穩(wěn)定性也好。

3.3 仿真及其結(jié)果分析

結(jié)合彈藥維修任務(wù)調(diào)配多目標(biāo)模型，運(yùn)用MATLAB對(duì)改進(jìn)MOPSO算法進(jìn)行求解，可得其Pareto解集分布如圖2所示，其部分最優(yōu)解集如表3所示。

圖2 改進(jìn)MOPSO算法的Pareto解集分布

表3 改進(jìn)MOPSO算法的部分Pareto最優(yōu)解集

對(duì)于Pareto解集，在實(shí)際中往往需要從中選出若干個(gè)滿意解。本文根據(jù)總部年度彈藥維修任務(wù)的具體要求進(jìn)行選取，如：為了最大限度節(jié)約維修經(jīng)費(fèi)開支，可選擇表3中的方案7；戰(zhàn)時(shí)彈藥需求量大，需要快速補(bǔ)給彈藥，且維修后的彈藥主要用于短期使用，則可選擇方案2。另外，也可運(yùn)用“基于模糊集理論的最佳折中方案”[10]，通過建立反映滿意程度的隸屬度函數(shù)來選取滿意解。

4 結(jié)論

本文提出了一種基于聚類算法的全局引導(dǎo)策略和慣性權(quán)值非線性遞減策略相結(jié)合的改進(jìn)MOPSO算法；結(jié)合我軍彈藥維修決策現(xiàn)狀，構(gòu)建了彈藥維修任務(wù)調(diào)配多目標(biāo)模型，并運(yùn)用算法對(duì)模型進(jìn)行求解。通過算例及仿真驗(yàn)證了該算法的優(yōu)越性及對(duì)該類問題的良好求解能力，在我軍彈藥維修任務(wù)調(diào)配的定量決策工作中起到重要作用。然而，本文并未考慮由于彈藥貯存地不同而給送修過程帶來的影響，這也是下一步工作需繼續(xù)深入研究的問題。

[1] 凌海風(fēng).面向裝備保障的多準(zhǔn)則決策相關(guān)方法和技術(shù)研究[D].南京：南京大學(xué)，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] 劉曉，劉忠，侯文姝,等.火力分配多目標(biāo)規(guī)劃模型的改進(jìn)MOPSO算法[J].系統(tǒng)工程與電子技術(shù)，2013,35(2):326-330.

[5] 劉勇，賈慶軒，陳鋼，等.基于多目標(biāo)粒子群優(yōu)化算法的自由漂浮空間機(jī)器人負(fù)載最大化軌跡優(yōu)化[J].機(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] 劉寶寧，章衛(wèi)國，聶瑞.一種改進(jìn)混沌MOPSO算法及其在飛控系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)測(cè)量與控制,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] 顏楠楠，傅正財(cái).基于多目標(biāo)粒子群優(yōu)化算法的UPFC協(xié)調(diào)控制[J].電力系統(tǒng)保護(hù)與控制，2010,38(8):43-48.

(責(zé)任編輯: 王生鳳)

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