RRAP優(yōu)化問題的HSO算法研究

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

關(guān)鍵詞：可靠性-冗余分配問題（RRAP）;混合種群優(yōu)化（HSO）;編碼;算法;收斂

中圖分類號：TP391.9，TP18? ? ? 文獻(xiàn)標(biāo)識碼：A

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

1 背景

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

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

2 假設(shè)和模型

2.1 假設(shè)

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

2.2 模型

設(shè)系統(tǒng)（可靠度為Rs）由n個子系統(tǒng)（可靠度為Ri）組成，整個系統(tǒng)的結(jié)構(gòu)是S-P結(jié)構(gòu)或復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)（由子系統(tǒng)及元件計算整個系統(tǒng)可靠度可參閱文獻(xiàn)，這里不單獨討論），每個元件具有可靠度、價格和重量、體積，整個系統(tǒng)有費用、價格和體積約束，確定構(gòu)成系統(tǒng)元件的可靠度及冗余度，使得整個系統(tǒng)的可靠度最大，數(shù)學(xué)表達(dá)式為：

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

3 算法

3.1 解的編碼

在混合種群優(yōu)化（HSO）算法中，粒子（解）的構(gòu)造為：[R，X]，即由表示元件可靠度的實數(shù)組成的行向量和表示元件冗余度的正整數(shù)行向量X組成，也就是，行向量[R，X]的左邊一半元素順序是表示元件可靠度的實數(shù)變量（值介于0與1之間），右邊一半元素是表示元件冗余度的正整數(shù)變量。例如，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 新解的生成算法

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

算法1

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

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

算法2

按照均勻分布隨機數(shù)產(chǎn)生算法，隨機產(chǎn)生|X|個位于區(qū)間[r0，1]中的隨機實數(shù)。

3.3 適應(yīng)值函數(shù)

為應(yīng)用混合種群優(yōu)化（HSO）算法求解RRAP問題，需要將有約束的優(yōu)化問題（1）-（2）轉(zhuǎn)換為無約束的優(yōu)化問題，為此，引入適應(yīng)值函數(shù)如下：

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

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

3.4 兩段HSO算法

算法3（偽Matlab代碼）

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

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

Step1隨機產(chǎn)生滿足系統(tǒng)約束條件的nc個粒子存于矩陣A中;并將對應(yīng)的適應(yīng)值存于CA中;再將矩陣A存于矩陣B中（每個粒子的當(dāng)前最優(yōu)初始值）。

Step2利用矩陣A，求出當(dāng)前系統(tǒng)的全局最優(yōu)值[Xgbest，Rgbest]，即Rgbest是元件全局最優(yōu)可靠度向量，Xgbest是元件全局最優(yōu)冗余度向量。

Step3 for t=1：nt

Step3.1

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

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中的每個當(dāng)前解X，其對應(yīng)的修訂解Y，如果Y的適應(yīng)值大于X的適應(yīng)值，則將X替換為Y;否則，如果rand（1）>k（t），（delt=X的適應(yīng)值 - Y的適應(yīng)值;? k（t）= cos （3.1416 * delt^0.25*t^2/（1*10^6）） ; ）則將X替換為Y。

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

Step3.4 記錄最優(yōu)解對應(yīng)的可靠度。

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

Step5算法終止。

4 模擬仿真

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

4.1 串聯(lián)系統(tǒng)

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

[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）

其中參數(shù)如下：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;

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

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

4.2 復(fù)雜網(wǎng)絡(luò)

橋網(wǎng)絡(luò)（見圖2）系統(tǒng)的約束條件與參數(shù)同上述串聯(lián)系統(tǒng)3.1，令C0=175，W0=200，V0=110;系統(tǒng)的可靠度為：

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

公式（5）-（8）組成橋網(wǎng)絡(luò)可靠度最大優(yōu)化模型。

隨機運行算法50次，運行結(jié)果為：Rmax=0.999889;Rmin=0.999414;Ravg=0.999863，總體運行時間為450.84秒，用遺傳算法求得的最優(yōu)結(jié)果一致問題3提供的可靠性表達(dá)式有誤，結(jié)果僅做參考，與其提供的GA-PSO算法，PSO算法計算結(jié)果最好解，至小數(shù)點后6位是一致的），最優(yōu)解對應(yīng)的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 結(jié)束語

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

參考文獻(xiàn)：

[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] 徐沾杰，馬昌文，梅啟智，等.用遺傳算法求解一個系統(tǒng)可靠性優(yōu)化問題[J].清華大學(xué)學(xué)報（自然科學(xué)版），1998（7）： 54-57.

[4] 張鐵柱，滕春賢，韓志剛.遺傳算法在系統(tǒng)可靠性優(yōu)化中的應(yīng)用[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] 李東魁.三狀態(tài)設(shè)備網(wǎng)絡(luò)可靠性分解定理與網(wǎng)絡(luò)可靠度的計算[D].沈陽：東北大學(xué)，1992.

【通聯(lián)編輯：代影】