基于改進MOPSO的多級系統備件配置優化研究

王亞彬, 趙建民, 程中華, 王建增

(1.軍械工程學院裝備指揮與管理系, 河北 石家莊 050003;

2.中國人民解放軍66046部隊, 河北 石家莊 050000)

?

基于改進MOPSO的多級系統備件配置優化研究

王亞彬1, 趙建民1, 程中華1, 王建增2

(1.軍械工程學院裝備指揮與管理系, 河北 石家莊 050003;

2.中國人民解放軍66046部隊, 河北 石家莊 050000)

摘要：備件是裝備保障的重要物質基礎,合理規劃備件的配置方案是提高裝備保障效能的關鍵。針對多級保障系統備件配置優化的高維、非線性問題,構建了以備件保障度最大、保障費用最小為目標函數,以其他準則為約束條件的優化配置模型。面向優化模型求解的難題,在傳統粒子群算法的基礎上,提出了一種改進的粒子群求解算法,給出了該算法的設計思路和優化流程,采用基于準則的方法以及改進慣性權重等措施,以兩個目標作為引導,在備件配置方案生成時可以避免長時間的無效搜索,提高了粒子群優化算法的求解效率,最后通過算例證明該方法的可行性和有效性。

關鍵詞：多目標粒子群優化方法; 備件; 配置; 優化; 保障度

0引言

備件是裝備保障的重要物質基礎,是影響裝備戰備完好性和保障能力的重要因素。備件配置優化是通過備件的合理匹配,使其達到最佳的綜合技術經濟效益,其本質上是一個資源配置優化的決策過程,因而越來越多的研究人員,采用了系統決策、運籌學、工程經濟學等理論進行備件配置優化研究[1]。文獻[2]等利用蒙特卡羅仿真、分層邊際算法研究了維修過程中備件的配置優化問題;文獻[3]分別給出了模擬退火算法、遺傳算法及蟻群算法對該類問題的求解;文獻[4-5]研究了基于粒子群算法的兩級體制下備件配置優化問題;文獻[6-7]利用遺傳算法對備件儲備數量進行了相關研究,構建了優化模型;文獻[8]基于METRIC理論對防空武器系統的備件配置進行了優化研究;文獻[9]利用馬爾可夫模型研究了備件配置優化的方法;文獻[10]從體系保障度優化的角度對備件庫存方案進行了研究。雖然以上研究都取得了一定的成果,然而它們大多是以單種裝備為對象,從單目標角度考慮備件的配置優化問題,實際上,備件配置決策時往往要著眼保障系統整體,針對多種裝備,同時考慮備件保障度、保障費用等多個目標。由于各個目標之間關系較為復雜,有的目標之間相互矛盾,有的相互補充,這就使得備件多目標配置優化問題比單目標配置優化問題要復雜的多。

粒子群優化(particle swarm optimization,PSO)算法是一種新興的基于群體智能理論的演化計算技術,1995年由美國的Eberhart和Kennedy博士提出。多目標粒子群優化方法(multiple objective PSO,MOPSO)與求解單目標PSO方法相比,不同點在于MOPSO需要在各個不同目標之間進行權衡,最終找到一組解。其關鍵問題是如何確定一個適當的適應度函數,來度量一個解決方案在多目標層面上的質量。根據適應度函數的確定方法,可將求解多目標問題的粒子群算法分為以下3類:一是目標聚合法[11],將多目標函數進行加權聚合,轉化為單目標函數進行計算;二是基于帕累托支配的方法[12],將非劣解集中最孤立的非劣解賦給全局極值,從而引導MOPSO方法盡可能的找出分布均勻的非劣解集;三是基于準則的方法[13],該方法不同時考慮所有目標,而是根據優化過程中的不同情況,將適應度函數在不同目標間轉化。

本文構建了以備件保障度最大、保障費用最小為目標函數、以其他準則為約束條件的備件多目標優化配置模型;在此基礎上,面向多目標約束模型求解的難題,設計了基于準則的粒子群求解算法,并進行了算例分析。

1備件配置優化建模

1.1模型假設

(1) 裝備維修分為中繼級和基層級兩級,在中繼級有一個師倉庫,在基層級有多團倉庫;

(2) 各類型裝備對備件的需求相互獨立,故障分布為指數分布,備件需求服從泊松分布;

(3) 所有部件故障均會影響系統任務的完成;

(4) 由于預防性維修容易提前預測和安排,而事后維修的隨機性較大,所以僅考慮事后維修情況;

(5) 所有故障件都進行換件維修。

備件的配置關系如圖1所示,其中裝備(k,Nj)中的k表示第k類型裝備,Nj表示該型裝備的數量。

圖1　備件的配置關系

1.2符號說明

為了便于對問題描述,該模型中的常用符號說明如下:

i表示第i種備件;

I表示備件種類數;

J表示保障系統中基層級維修機構數量;

Nj表示第j個基層級單位有某型號裝備數量;

K表示所有基層級單位共有某型號裝備數量;

Eji表示第j個基層級在規定的裝備工作時間內,對備件i的平均需求數量;

Ei表示所有基層級在規定的裝備工作時間內,對備件i的平均需求數量;

E[B(Si)]表示所有基層級向中繼級請領備件i的平均數量(短缺數量);

E[D(Si,Soi)]表示中繼級備件i的平均請領數量(短缺數量);

to表示平均基層級向中繼級請領備件的時間;

tm表示平均中繼級籌措備件的延遲時間;

Sji表示第j個基層級配備備件i的數量;

Soi表示中繼級配置備件i的數量;

P(xji)表示第j個基層級需要備件i的數量為xji的概率;

Eoi表示中繼級第i類備件的平均需求數量;

Ci表示第i類備件的單價;

Tbfi表示部件i的平均故障間隔時間。

1.3模型構建

(1) 基層級備件需求數

由于P(xji)表示在規定的裝備工作時間內,對第j個基層級需要備件i的數量為xji的概率。因此,第j個基層級在規定的裝備工作時間內對備件i的平均需求數量為

(1)

(2) 基層級備件短缺率

所有基層級在規定的裝備工作時間內,對備件i的平均需求數量Ei可表示為

(2)

所有基層級向中繼級請領備件i的平均數量E[B(Si)]可表示為

(3)

式中,第j個基層級的平均短缺數E[B(Sji)]是備件需求數量超過儲備數量Sji的平均值,即

(4)

所以,由基層級平均需求數量Ei和平均請領數量E[B(Si)],可以得到備件i在基層級的短缺率為

(5)

(3) 中繼級備件短缺率

(6)

(7)

根據假設條件,第j個庫存第i種備件需求數為k的概率P(Xji=k)為

(8)

式中,λji為第j個工作單元第i種備件的需求率；t為裝備工作時間。

為計算系統不缺備件的概率,運用泊松分布的性質和隨機過程原理,當N=2時,可得

也就是說,對于N=2的情況,備件需求仍然服從泊松分布。假設N=n,該結論成立,對于N=n+1時,與上式相同的分析可得

根據數學歸納原理,可以得出N=n+1時,總的備件需求仍然服從泊松分布。因此,有

(9)

在求得了中繼級備件i需求概率的基礎上,利用相同的方法,可得中繼級備件i的平均需求數量

(10)

中繼級的平均請領數量(短缺數量)為

(11)

則中繼級備件i的短缺率為

(12)

(4) 基層級備件保障平均延遲時間

基層級備件保障延遲的原因,一是基層級短缺而中繼級不短缺;二是基層級和中繼級都短缺。因此,基層級備件的平均保障延遲時間為

(13)

(5) 備件i的保障度

假設已知部件i的壽命分布,可以得到該部件的平均故障間隔時間Tbfi,即該部件的平均工作時間,則備件i的穩態保障度為

(14)

整理,得

(15)

以上求得了備件i的保障度,其他備件的保障度可由類似的方法得到。根據文獻[14]可知,同型裝備上所有備件的保障度可用各備件保障度的乘積表示,即所有備件的保障度可表示為

(16)

(6) 多目標配置優化模型

備件的配置優化模型可以表示為

maxPS=

(17)

(18)

(19)

(20)

(21)

(22)

式(17)表示該類型所有備件的保障度最大。

式(18)表示該類型所有備件保障費用最小。

約束(19)表示備件i在基層級的短缺率大于等于0,小于等于1。

約束(20)表示備件i在中繼級的短缺率大于等于0,小于等于1。

約束(21)表示備件i在基層級的配置數量不超過最高庫存限額,且為整數。

約束(22)表示備件i在中繼級的配置數量不超過最高庫存限額,且為整數。

2備件配置優化模型求解

2.1模型分析

由式(17)~式(22)可知,備件配置優化模型為高維、非線性優化模型,采用一般的優化算法難以奏效。為了進一步求解該類優化模型,本文對其做了以下分析與處理:

(1) 在本文構建的備件配置優化模型中,共有兩個不同的目標函數,并且在不同時間階段、不同任務需求中,決策者對這兩個目標的偏好是不同的,因此,采用基于準則的方法求解MOPSO更為合理。

(2) 在粒子群算法中,ω是最重要的可控參數。針對粒子群算法容易早熟以及算法后期在全局最優解附近產生振蕩的現象,需要對ω進行改進,以提高解的質量和求解的效率。

2.2粒子表示

本文采用基于向量的粒子表示方法,如圖2所示。每個粒子對應一個備件配置方案,xn=[xn,1,…，xn,j,…,xn,m,xn,m+1],n∈{1,2,…,N},(N為粒子個數),粒子維數為m+1;xn,i表示備件在基層級的配置數量,j∈{1,2,…,m},m為基層級機構數量;xn,m+1表示備件在中繼級的配置數量。

圖2　粒子表示示意圖

2.3適應度計算

適應度函數用來評價群體中個體的優劣,其數值引導著粒子群的移動方向與速度。針對備件i的保障度最大和保障費用最小兩個目標,本文采用基于準則的方法來確定適應度函數,分別計算每個粒子的適應度,具體算法如下:

Pi=

(23)

(24)

2.4粒子更新

由于粒子群算法的快速收斂速度而極易導致種群多樣性的損失,為了防止其陷入局部最優解,本文針對兩個目標提出了選用兩個粒子群的動態種群策略,設搜索空間為D維,總粒子數為n。每個粒子群優化一個單獨的目標,第一個粒子群的全局最優粒子被用于第二個粒子群的速度方程中,而第二個粒子群的全局最優粒子又被用于第一個粒子群的速度更新中n,則

(25)

(26)

(27)

(28)

(29)

式中,c1和c2為常數,稱為加速因子;r1,r2為[0,1]之間的隨機數;ω稱慣性因子;vi d(t) 表示在t時刻第i個粒子的速度;Sj,Vid(t) 表示在t時刻第j個粒子群第i個粒子的位置;Sj·pid(t)表示t時刻第j個粒子群“飛行”歷史中的最優位置;Si·pgd(t) 表示t時刻第j個粒子群的全局最優粒子的位置。

2.5權重的改進

在粒子群算法中,慣性因子是最重要的可控參數,用來控制當前粒子速度更新后對粒子速度的影響程度。該參數越大,越有利于進行大范圍全局搜索;該參數越小,越有利于在當前范圍內進行局部搜索。通過大量試驗表明[15],該參數在0.4~1.4間動態取值,效果較好。在本文中,慣性因子按以下公式選擇:

(30)

式中,ωmax表示最大慣性權重；ωmin表示最小慣性權重；g表示迭代步數；Gmax表示最大迭代步數。

2.6算法流程

步驟 1初始化。隨機初始化非劣解集(none-inferior solution set, NISS)和粒子群POP1、POP2,計算粒子群中每個粒子的目標以及約束,初始化粒子群中每個粒子的速度以及每個粒子所遍歷到的最好點。

步驟 2更新粒子種群。按式(25)和式(26)更新粒子的速度,按式(27)~式(29)更新粒子的位置。

步驟 3更新非劣解集(NISS)。

步驟 4更新每個粒子所找到的最優解。

步驟 5終止條件判斷,若滿足則終止程序,否則轉至步驟2。

MOPSO算法的基本流程如圖3所示。

圖3　基于準則的多目標粒子群算法流程

3算例分析

3.1問題描述

已知某師X、Y團均配備某型裝備18臺,A、B為該裝備的兩種關鍵備件,假設該裝備只在團基層級修理機構修理,師中繼級僅提供備件保障,t0為480 h,tm為720 h。單位時間內備件的需求概率Pji,平均故障間隔時間Tbf,以及故障率等參數見表1所示,為完成一年的訓練任務(按1 600 h計算),如何配置該類備件,可使該系統備件的保障度最大,同時保障費用最小？

表1　初始數據

3.2問題求解與分析

計算可得備件在不同機構的需求數量Eji、Eoi等基礎數據,詳見表2所示。

表2　備件配置優化算例中基礎數據

本文利用Matlab編寫粒子群算法程序,在計算機配置為Intel(R) Core(TM)i5 CPU 2.27GHz 內存2G 時,兩個種群規模均為40個粒子,迭代次數為100代,ωmax為1.2,ωmin為0.5,c1為0.5,c2為0.5時的平均計算時間為6 s。表3是備件在不同配置情況下的優化結果,圖4為最優個體適應度的變化情況,圖5是非劣解在目標空間的分布情況。從表3中可以看出,當保障費用為6 900元時,最優配置方案是備件A在中繼級配置2件,備件B在中繼級配置9件,此時備件的保障度為0.792;隨著保障費用的增加,保障度也在不斷增加。決策者可以根據需要和實際條件,從不同優化方案中選擇合適的備件配置方案,以滿足備件保障度和費用的要求。圖4反映了最優個體適應度與進化代數關系,不難看出,當迭代到50代時最優個體的適應度基本趨于穩定值。

表3　備件配置優化結果

由圖5可以看出,非劣解在目標空間的分布情況,即:在一定范圍內隨著保障費用的增加,備件保障度也在不斷提高;當備件保障度達到0.95后,即使再增加保障費用,備件保障度的變化也是很小。另外,非劣解在目標空間的分布分別對應表3中的12個不同配置方案,決策者可以從保障費用和備件保障度兩個目標進行綜合權衡,從非劣解中選擇確定一個合適的方案,進行備件的配置。

圖4　備件MOPSO最優個體適應度的變化情況

圖5　備件非劣解在目標空間的分布

例如,若要求備件的保障度不低于0.95,費用最小,則可以選擇目標空間中的第10個非劣解(P=0.950,C=13 500元),此時的配置方案是備件A在兩個基層級配置數量均為1件,在中繼級配置數量為3件;備件B在兩個基層級配置數量均為2件,在中繼級配置數量為11件。

4結論

著眼多級維修保障系統的整體,同時考慮備件保障度、保障費用等目標,構建了備件的配置優化模型,引入了粒子群算法,兩個目標作為引導,在備件配置方案生成時可以避免長時間的無效搜索,并通過算例驗證了模型和算法的可行性與有效性,解決配置優化模型的高維、非線性求解難題,為備件的配置優化的科學決策提供了重要支撐。

參考文獻：

[1] Wang W B. A joint spare part and maintenance inspection optimization model using the delay-time concept[J].ReliabilityEngineeringandSystemSafety, 2011, 96(4): 1535-1541.

[2] Ruan M Z, Li Q M, Li C. Improved layered marginal algorithm to optimize initial spare part configuration project[J].ActaArmamentarii,2012,33(10):1251-1257.(阮旻智,李慶民,李承.改進的分層邊際算法優化備件的初始配置方案[J].兵工學報,2012,33(10):1251-1257.)

[3] Gao S, Yang J Y, Wu X J. Ant coling algorithm for optimization of system reliability[J].ComputerApplicationandSoftware, 2004, 21(12): 94-96.(高尚,楊靜宇,吳小俊. 可靠性優化的蟻群算法[J].計算機應用與軟件, 2004, 21(12): 94-96).

[4] Song G B, Ma G T, Liu X J, et al. Optimal allocation of initial spares of missile based on particle swarm optimization algorithm[J].ShipElectronicEngineering, 2012, 32(9): 118-120.(宋貴寶, 馬廣婷, 劉學君, 等. 基于粒子群算法的導彈初始備件優化配置[J].艦船電子工程, 2012, 32(9): 118-120.)

[5] Luo Y, Ruan M Z, Li Q M. Configuration project optimization for repairable spare parts under discretional structures[J].SystemsEngineeringandElectronics, 2012, 34(9): 1865-1871.(羅祎, 阮旻智, 李慶民. 任意結構下可修復備件的配置方案優化[J].系統工程與電子技術, 2012, 34(9):1865-1871.)

[6] Derek T D. Heuristic Algorithm for U.S. naval mission resource allocation[R]. ADA488672, 2008.

[7] Ilgin M A, Tunali S. Joint optimization of spare parts inventory and maintenance policies using genetic algorithms[J].InternationalJournalofAdvancedManufacturingTechnology, 2007, 30(5): 594-604.

[8] Guo Q, Zhang Z Y, Huang L P, et al. Research on optimization of disposition of spare parts for air defense weapon system based on METRIC theory[J].FireControl&CommandControl, 2011,36(8):100-103.(郭強,張振友,黃立坡,等.基于METRIC理論的防空武器系統備件配置優化[J].火力與指揮控制,2011,36(8):100-103.)

[9] Dong B C, Song B W, Liang Q W. The method of spares configuration optimization based on markov model[J].SystemsEngineering,2011,29(9):124-126.(董博超,宋保維,梁慶衛.馬爾可夫模型的備件配置優化方法[J].系統工程,2011,29(9):124-126.)

[10] Ruan M Z, Peng Y W, Li Q M. Optimization of three-echelon inventory project for equipment spare parts based on system support degree[J].SystemsEngineering—Theory&Practice, 2012, 32(7): 1623-1630.(阮旻智, 彭英武, 李慶民. 基于體系保障度的裝備備件三級庫存方案優化[J].系統工程理論與實踐, 2012, 32(7): 1623-1630.)

[11] Maripi J K. An effective parallel particle swarm optimization algorithm and its performance evaluation[D]. Carbondale: Southern Illinois University, 2010.

[12] Baltar A M, Fontane D G. Use of multi-objective particle swarm optimization in water resources management[J].JournalofWaterResourcesPlanningandManagement, 2008, 35(8): 257-265.

[13] Gong D W, Zhang Y, Zhang J H. Multi-objective particle swarm optimization based on minimal particle angle[J].LectureNotesinComputerScience, 2005, 3644(1): 571-576.

[14] Liang H B, Gao Q, Zhao J M, et al.Ordnancematerialmanagement[M].Beijing:Science Press,1998:122-129.(梁海濱,高崎,趙建民,等.軍械維修器材管理學[M].北京:科學出版社,1998:122-129.)

[15] Liu H Y. Improvement of particle swarm optimization and its application in petroleum engineering[D]. Daqing: Northeast Petroleum University, 2012.(劉華鎣. 粒子群優化算法的改進研究及在石油工程中的應用[D]. 大慶: 東北石油大學, 2012.)

王亞彬(1975-),男,講師,博士,主要研究方向為裝備保障理論與應用。

E-mail:wangyabin123@163.com

趙建民(1961-),男,教授,博士,主要研究方向為裝備保障理論與應用。

E-mail:jm_zhao@hotmail.com

程中華(1972-),男,副教授,博士,主要研究方向為裝備保障理論與應用。

E-mail:cheng_zhonghua@163.com

王建增(1976-),男,工程師,主要研究方向為維修器材保障理論與應用。

E-mail:wang_jianzeng@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150104.1331.007.html

Optimization for spare parts allocation in multi-echelon

support system based on improved MOPSO

WANG Ya-bin1, ZHAO Jian-min1, CHENG Zhong-hua1, WANG Jian-zeng2

(1.DepartmentofEquipmentCommandandManagement,OrdnanceEngineeringCollege,

Shijiazhuang050003,China; 2.Unit66046ofthePLA,Shijiazhuang050000,China)

Abstract:Spare parts is a key component of equipment support, and a reasonable allocation plan of spare parts is the key factor for improving the efficacy of equipment support. Spare parts allocation and optimization in a multi-echelon support system presents difficult problems, which involves non-linear objective function and integer variables to be optimized. A multi-objective optimization model is developed, which maximizes support probability and minimizes support costs. In order to obtain the solution of the model, an improved multi-objective particle swarm optimization (MOPSO) method is employed, based on the traditional particle swarm method. The design idea and optimization procedure of this algorithm are put forward, rule based and inertia weigh improving method are introduced. In this method, dimensions reduction and rules-based multi-objective optimization are employed, which can improve the solving efficiency for the MOPSO method. At last, a numerical example is given, which examines the feasibility and validity of this method.

Keywords:multiple objective particle swarm optimization (MOPSO); spare parts; allocation; optimization; support probability

作者簡介：

中圖分類號：N 945.24

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2015.07.18

基金項目：“十二五”武器裝備預研項目(51327020101)資助課題

收稿日期：2014-07-30；修回日期：2014-11-08；網絡優先出版日期：2015-01-04。