基于改進MOPSO的多級系統(tǒng)備件配置優(yōu)化研究

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

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

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

?

基于改進MOPSO的多級系統(tǒng)備件配置優(yōu)化研究

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

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

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

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

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

0引言

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

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

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

1備件配置優(yōu)化建模

1.1模型假設

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

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

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

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

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

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

圖1　備件的配置關系

1.2符號說明

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

i表示第i種備件;

I表示備件種類數(shù);

J表示保障系統(tǒng)中基層級維修機構數(shù)量;

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

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

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

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

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

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

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

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

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

Soi表示中繼級配置備件i的數(shù)量;

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

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

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

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

1.3模型構建

(1) 基層級備件需求數(shù)

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

(1)

(2) 基層級備件短缺率

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

(2)

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

(3)

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

(4)

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

(5)

(3) 中繼級備件短缺率

(6)

(7)

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

(8)

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

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

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

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

(9)

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

(10)

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

(11)

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

(12)

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

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

(13)

(5) 備件i的保障度

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

(14)

整理,得

(15)

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

(16)

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

備件的配置優(yōu)化模型可以表示為

maxPS=

(17)

(18)

(19)

(20)

(21)

(22)

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

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

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

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

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

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

2備件配置優(yōu)化模型求解

2.1模型分析

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

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

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

2.2粒子表示

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

圖2　粒子表示示意圖

2.3適應度計算

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

Pi=

(23)

(24)

2.4粒子更新

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

(25)

(26)

(27)

(28)

(29)

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

2.5權重的改進

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

(30)

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

2.6算法流程

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

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

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

步驟 4更新每個粒子所找到的最優(yōu)解。

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

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

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

3算例分析

3.1問題描述

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

表1　初始數(shù)據(jù)

3.2問題求解與分析

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

表2　備件配置優(yōu)化算例中基礎數(shù)據(jù)

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

表3　備件配置優(yōu)化結果

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

圖4　備件MOPSO最優(yōu)個體適應度的變化情況

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

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

4結論

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

參考文獻：

[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.(阮旻智,李慶民,李承.改進的分層邊際算法優(yōu)化備件的初始配置方案[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.(高尚,楊靜宇,吳小俊. 可靠性優(yōu)化的蟻群算法[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.(宋貴寶, 馬廣婷, 劉學君, 等. 基于粒子群算法的導彈初始備件優(yōu)化配置[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.(羅祎, 阮旻智, 李慶民. 任意結構下可修復備件的配置方案優(yōu)化[J].系統(tǒng)工程與電子技術, 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理論的防空武器系統(tǒng)備件配置優(yōu)化[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.(董博超,宋保維,梁慶衛(wèi).馬爾可夫模型的備件配置優(yōu)化方法[J].系統(tǒng)工程,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.(阮旻智, 彭英武, 李慶民. 基于體系保障度的裝備備件三級庫存方案優(yōu)化[J].系統(tǒng)工程理論與實踐, 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.(劉華鎣. 粒子群優(yōu)化算法的改進研究及在石油工程中的應用[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

網(wǎng)絡優(yōu)先出版地址：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；網(wǎng)絡優(yōu)先出版日期：2015-01-04。