RRAP優化問題的HSO算法研究

摘要：RRAP優化問題是決策變量為元件可靠度及元件冗余度的可靠性優化問題，數學模型是非線性混合整數規劃問題，屬于NP-hard問題類?；旌戏N群優化（簡寫為HSO）算法具有結構簡單、運行高效的特點，繼承了模擬退火算法SA、粒子群優化算法PSO、簡化群優化算法SSO等算法的優點。該文設計了一個兩段混合粒子群優化HSO算法，用于求解RRAP優化問題;通過模擬仿真，驗證了所給HSO算法的正確性和有效性;研究結果表明：混合粒子群優化HSO算法是解決RRAP問題的一種有效工具。

關鍵詞：可靠性-冗余分配問題（RRAP）;混合種群優化（HSO）;編碼;算法;收斂

中圖分類號：TP391.9，TP18? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）15-0020-03

1 背景

可靠性-冗余分配問題（RRAP）是可靠性冗余分配問題（RAP）中的一種重要類型，數學模型是非線性整數混合規劃問題，傳統的求解方法，比如動態規劃法、替代約束法等的應用受到限制，后啟發式算法，如，遺傳算法、粒子群優化算法等成為有效的求解手段。

廣義可靠性冗余分配問題（GRAP）和具有多種混合策略的網絡可靠性優化模型的出現，成為可靠性冗余分配問題的新發展方向，而混合后啟發式算法成為求解可靠性冗余分配問題的新手段。這里GRAP問題是指在子系統中允許不同種類的元件可以混合的RAP問題，而混合后啟發式算法是指在算法中同時采用兩種以上后啟發式算法機制的后啟發式算法?；旌戏N群算法（HSO）在求解GRAP問題中具有很好的表現，本文用改進的HSO算法求解較為復雜的RRAP問題。

2 假設和模型

2.1 假設

1）系統和元件有且僅有正常工作和失效兩個狀態;2）每個元件的可靠度、價格和重量已知;3）系統中各元件的失效是統計獨立的;4）失效的元件不可修復;5）所有備選的元件都是有效的。

2.2 模型

設系統（可靠度為Rs）由n個子系統（可靠度為Ri）組成，整個系統的結構是S-P結構或復雜網絡結構（由子系統及元件計算整個系統可靠度可參閱文獻，這里不單獨討論），每個元件具有可靠度、價格和重量、體積，整個系統有費用、價格和體積約束，確定構成系統元件的可靠度及冗余度，使得整個系統的可靠度最大，數學表達式為：

其中，i=1，2，…，m，表示有m個約束，bi是常量，一般m=3，分別是重量、費用和體積約束;rj，xj表示第j個子系統的元件可靠度向量和冗余度向量;R，X分別表示整個系統的可靠度向量和元件冗余度向量。

3 算法

3.1 解的編碼

在混合種群優化（HSO）算法中，粒子（解）的構造為：[R，X]，即由表示元件可靠度的實數組成的行向量和表示元件冗余度的正整數行向量X組成，也就是，行向量[R，X]的左邊一半元素順序是表示元件可靠度的實數變量（值介于0與1之間），右邊一半元素是表示元件冗余度的正整數變量。例如，R= [0.775，0.8737，0.9023，0.7116，0.7875]， X=[3，2，2，3，3]; 即這里的一個粒子（解）的編碼是[R，X]=[ 0.775，0.8737，0.9023，0.7116，0.7875， 3，2，2，3，3]。

3.2 新解的生成算法

設元件冗余度向量X中，分量的變化范圍為[var1，var2]，其中var1，var2為兩個正整數，且var1<=var2，則產生一個新的元件冗余度向量的算法為：

算法1

按照均勻分布隨機數產生算法，隨機產生|X|個位于區間[var1，var2]中的隨機正整數。其中|X|表示向量X的基數，即需要確定冗余度的元件個數。

設元件的可靠度向量R中，分量的變化范圍為[r0，1]， r0是個大于0，小于1的實數（一般通過實驗確定），則產生一個新的元件的可靠度向量的算法為：

算法2

按照均勻分布隨機數產生算法，隨機產生|X|個位于區間[r0，1]中的隨機實數。

3.3 適應值函數

為應用混合種群優化（HSO）算法求解RRAP問題，需要將有約束的優化問題（1）-（2）轉換為無約束的優化問題，為此，引入適應值函數如下：

這里α，β，γ是參數，C0，W0，V0分別是系統的費用、重量和體積限制，TC，TW，TV是當前解（R，X）下的系統費用、重量和體積。

基本混合種群優化HSO算法的描述，算法的原理、正確性和有效性證明，請參閱文獻，這里我們給出改進的HSO算法，用于求解RRAP問題。

3.4 兩段HSO算法

算法3（偽Matlab代碼）

Step0（初始化）以行向量的形式存儲系統元件費用、重量、體積等參數;設定壓縮常數c1=c2=0.5，慣性權重w=0.9。

確定元件冗余度的上下界：varmax1與varmin1;確定元件可靠度的上下界varmax2與varmin2; 確定元件冗余度（變量）收斂速度的上下界velmax1與velmin1;確定元件可靠度（變量）收斂速度的上下界velmax2與velmin2; n 是元件個數，nc 是粒子個數，令 V=zeros（2n，nc）; A=zeros（2n，nc）;? B=zeros（2n，nc）; CA=zeros（1， nc）; Z=zeros（1，nt）;這里nt是總迭代次數。

Step1隨機產生滿足系統約束條件的nc個粒子存于矩陣A中;并將對應的適應值存于CA中;再將矩陣A存于矩陣B中（每個粒子的當前最優初始值）。

Step2利用矩陣A，求出當前系統的全局最優值[Xgbest，Rgbest]，即Rgbest是元件全局最優可靠度向量，Xgbest是元件全局最優冗余度向量。

Step3 for t=1：nt

Step3.1

% 對種群A中的每個粒子（解），按照PSO算法迭代公式修訂后的新值存于矩陣Y中，然后按照階躍函數修訂每個解。

for j=1：nc

for i=1：n

V（i，j）=wV（i，j）+c1rand（B（i，j）-A（i，j））+c2rand（Xgbest（1，i）-A（i，j））;

V（i+n，j）=wt*V（i+n，j）+c1rand（B（i+n，j）-A（i+n，j））+c2rand（Rgbest（1，i）-A（i+n，j））;

if（V（i，j）< velmin1）

V（i，j）= velmin1;

end

if（V（i，j）> velmax1）

V（i，j）= velmax1;

end

if（V（i+n，j）< velmin2）

V（i+n，j）= velmin2;

end

if（V（i+n，j）> velmax2）

V（i+n，j）= velmax2;

end

Y（i，j）=round（A（i，j）+V（i，j））;

Y（i+n，j）=（A（i+n，j）+V（i+n，j））;

if（Y（i，j）< varmin1）

Y（i，j）= varmin1;

end

if（Y（i，j）> varmax1）

Y（i，j）= varmax1;

end

if（Y（i+n，j）< varmin2）

Y（i+n，j）= varmin2;

end

if（Y（i+n，j）> varmax2）

Y（i+n，j）= varmax2;

end

end

m=rand（1）;

if（m>=0）&&（m<0.55）

A（i，j）=Xgbest（1，i）;

A（i+n，j）=Rgbest（1，i）;

else

if（m>=0.55）&&（m<0.75）

A（i，j）=B（i，j）;

A（i+n，j）=B（i+n，j）;

else

if（m>=0.75）&&（m<0.95）

A（i，j）=Y（i，j）;

A（i+n，j）=Y（i+n，j）;

else

if（m>=0.95）&&（m<1）

A（i，j）=randi（[varmin1， varmax1]）;

A（i+n，j）= varmin2+（ varmax2 -varmin2）*rand（[1，1]）;

end

end

end

end

end

step3.2 對A中的每個當前解X，其對應的修訂解Y，如果Y的適應值大于X的適應值，則將X替換為Y;否則，如果rand（1）>k（t），（delt=X的適應值 - Y的適應值;? k（t）= cos （3.1416 * delt^0.25*t^2/（1*10^6）） ; ）則將X替換為Y。

step3.3 如果A中每個當前粒子的適應值大于這個粒子的當前最優值的適應值，則將這個粒子的當前位置最優值進行更新;如果這個粒子的當前最優值的適應值大于全局最優解的適應值，則將全局最優解進行更新。

Step3.4 記錄最優解對應的可靠度。

Step4輸出最優解及對應的費用、重量和體積約束、最優解可靠度;畫出收斂曲線。

Step5算法終止。

4 模擬仿真

為證實算法的正確性和有效性，選擇文獻中的典型算例進行模擬仿真。測試都是在微型計算機上進行的;計算機配置為：CPU為Intel（R）Core（TM）i5-6500@3.20Ghz 3.20Ghz，內存8GB，硬盤600Gb;操作系統為Windows10專業版;編程軟件為MatlabR2015b。算法參數的設置為：n=5，c1=c2=0.5;w=0.9， nc=200， nt=1000，α=β=γ=2。

4.1 串聯系統

問題出現在文獻[6]中，具體描述如下：在費用、重量和體積約束條件下，適當選擇串并聯系統元件的可靠度R和冗余度X，使得系統的可靠度最大：

[maxfR，X=i=1n（1-（1-Ri）xi）]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

s.t. [? ? ?i=1nTi-tmlnRiUi（Xi+exp （Xi4））≤C0]? ? ? ?（5）

[? ? ? ? ? ? ?i=1nwiXiexp （Xi4）≤W0]? ? ? ? ? ? ? ? ? ? ? ? （6）

[i=1npiXi2≤V0]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

其中參數如下：T=[2.33e-5，1.45e-5，5.41e-6，8.05e-5，1.95e-5];? ? U=[1.5，1.5，1.5，1.5，1.5]; tm=1000; W=[7，8，8，6，9]; P=[1，2，3，4，2]; C0=175， W0=200，V0=110;

設定算法其他參數為：varmin1=1; varmax1=3; velmax1=0.1;velmin1=-0.1; varmin2=0.7;varmax2=1;velmax2=0.1;velmin2=-0.1。

隨機運行算法50次，結果如下：Rmax=0.93168;Rmin=0.90068;Ravg=0.92844，總體運行時間為827.72秒，最優解對應的R=[0.77935，0.87126，0.90255，0.711870.78855]; X=[3，2，2，3，3]， TC=175，TW=192.48，TV=83;用遺傳算法求得的最優結果一致，算法收斂曲線見圖1.

4.2 復雜網絡

橋網絡（見圖2）系統的約束條件與參數同上述串聯系統3.1，令C0=175，W0=200，V0=110;系統的可靠度為：

[RsR，X=R1R2+R3R4+R1R4R5+R2R3R5-R1R2R3R4-R1R2R3R5-R1R2R4R5-R1R3R4R5-R2R3R4R5]+[2R1R2R3R4R5]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

公式（5）-（8）組成橋網絡可靠度最大優化模型。

隨機運行算法50次，運行結果為：Rmax=0.999889;Rmin=0.999414;Ravg=0.999863，總體運行時間為450.84秒，用遺傳算法求得的最優結果一致問題3提供的可靠性表達式有誤，結果僅做參考，與其提供的GA-PSO算法，PSO算法計算結果最好解，至小數點后6位是一致的），最優解對應的R=[0.817553， 0.868652， 0.857783， 0.710507， 0.750068];? X=[3，3，3，3，1]，TC=175，TW=195.74，TV=92.

5 結束語

本文通過模擬仿真，發現混合種群優化算法HSO在求解RRAP問題時，表現出了較好的性能，原因是它繼承了SSO、SA與PSO等算法的優點，是典型的混合型后啟發式算法。我們也發現，算法在解決特定問題的時候，與PSO等算法比，并沒有體現出更多的優越性，比如，算法的執行時間有所增加，計算最優結果的精度上也沒有顯著的提高，個別情況下，還會出現非可行解的現象，即不能保證每次運行算法都收斂到可行解。

參考文獻：

[1] Beji N，Jarboui B，Eddaly M，et al.A hybrid particle swarm optimization algorithm for the redundancy allocation problem[J].Journal of Computational Science，2010，1（3）：159-167.

[2] Coelho L D S.An efficient particle swarm approach for mixed-integer programming in reliability-redundancy optimization applications[J].Reliability Engineering & System Safety，2009，94（4）：830-837.

[3] 徐沾杰，馬昌文，梅啟智，等.用遺傳算法求解一個系統可靠性優化問題[J].清華大學學報（自然科學版），1998（7）： 54-57.

[4] 張鐵柱，滕春賢，韓志剛.遺傳算法在系統可靠性優化中的應用[J].控制與決策，2002，（3）：378-380，384.

[5] Yeh W C.A new exact solution algorithm for a novel generalized redundancy allocation problem[J].Information Sciences，2017（408）：182-197.

[6] 李東魁.三狀態設備網絡可靠性分解定理與網絡可靠度的計算[D].沈陽：東北大學，1992.

【通聯編輯：代影】