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

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

改進的多目標粒子群優(yōu)化算法及其在彈藥維修任務調配中的應用

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

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

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

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

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

彈藥維修任務的調配屬于多目標優(yōu)化問題。目前，解決多目標優(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)、多目標粒子群(Multi-Objective Particle Swarm Optimization, MOPSO)等算法[1]。其中，MOPSO算法因其計算簡便、參數(shù)設置方便、收斂速度快等特點而備受研究者的青睞[2-6]。由于多目標優(yōu)化問題無法得到全局最優(yōu)的唯一解，只是存在一個Pareto非支配解集，因此，需要通過全局最優(yōu)引導使整個種群向Pareto解集收斂。然而，已有的全局引導策略往往存在解集多樣性不好、收斂精度不高等問題。為此，本文設計了一種基于聚類算法的全局引導策略，并對初始慣性權值w的變化方式進行改進，對解集進行優(yōu)化。

1 改進的MOPSO算法

1.1 MOPSO算法流程

MOPSO算法的流程如圖1所示。其中：1)初始化種群時將對每個粒子的速度和位置隨機賦值，設種群規(guī)模為P，總進化代數(shù)為N，初始慣性權值為w；2)搜索和更新全局最優(yōu)粒子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]內的隨機數(shù)；d為空間的維數(shù)。

圖1 MOPSO算法的流程

1.2 改進的全局最優(yōu)引導策略

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

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

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

1.3 初始慣性權值w的改進

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

(3)

式中：T為當前的進化代數(shù)。

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

2 彈藥維修任務調配多目標模型

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

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

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

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

在彈藥維修任務調配決策中，要充分考慮各彈藥維修機構的實際維修能力和維修經費，使各維修機構既保持一定的維修任務來加強其自身建設，又能順利完成其承擔的維修任務。因此，設置如下約束條件：

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

4) 0

3 算例與仿真分析

3.1 參數(shù)設置

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

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

3.2 算法性能比較與分析

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

表1 各算法收斂性指標GD比較

表2 各算法多樣性指標SP比較

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

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

3.3 仿真及其結果分析

結合彈藥維修任務調配多目標模型，運用MATLAB對改進MOPSO算法進行求解，可得其Pareto解集分布如圖2所示，其部分最優(yōu)解集如表3所示。

圖2 改進MOPSO算法的Pareto解集分布

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

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

4 結論

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

[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] 劉曉，劉忠，侯文姝,等.火力分配多目標規(guī)劃模型的改進MOPSO算法[J].系統(tǒng)工程與電子技術，2013,35(2):326-330.

[5] 劉勇，賈慶軒，陳鋼，等.基于多目標粒子群優(yōu)化算法的自由漂浮空間機器人負載最大化軌跡優(yōu)化[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)國，聶瑞.一種改進混沌MOPSO算法及其在飛控系統(tǒng)中的應用[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] 顏楠楠，傅正財.基于多目標粒子群優(yōu)化算法的UPFC協(xié)調控制[J].電力系統(tǒng)保護與控制，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