混合種群算法HSO在求解RAP問題中的應用研究

李學寶，李東魁

（包頭師范學院信息科學與技術學院，內蒙古包頭，014030）

1 緒論

可靠性冗余分配問題（RAP）是可靠性研究領域的重要課題，在最近的半個世紀，RAP問題的研究取得了豐碩的成果[1]。一般的可靠性冗余分配問題（RAP）是NP-hard的，研究可靠性冗余分配問題的智能算法，具有重要的現實意義。

Yeh Wei-Chang[2]研究GRAP問題，即允許子系統有不同類型的元件可以選擇的RAP問題時，給出了一個混合群體算法HSO，并討論了基本原理、算法的有效性和正確性。為檢驗HSO算法在解決RAP問題中的有效性，本文對兩個基本的RAP問題的模型[3-4]，設計HSO算法，進行模擬仿真，為進一步研究HSO算法在RAP問題中的應用打下基礎。

1.1 假設

（1）網絡和構成網絡的元件有且只有兩種狀態，即正常工作狀態和失效狀態。（2）網絡用一個無向圖G =（V，E）表示，其中V表示網絡結點（元件的連接）集合，E代表邊（元件）的集合。s是源結點，t是匯結點。（3）結點是完全可靠的，永不失效。（4）網絡是耦合的（Coherent）。（5）邊的失效是統計獨立的。某一邊處于某種狀態的概率是已知的。（6）每個元件（邊）的可靠度和（或）價格和重量已知；（3）系統中各元件的失效是統計獨立的；（7）失效的元件不可修復。

1.2 解的編碼

可靠性冗余分配問題（RAP），在元件的可靠度已知的前提下，未知量是元件的冗余度。在SHO算法中，粒子（解）X的編碼，代表的就是系統中各個元件的冗余度，因此，解X的編碼方法為：由代表網絡中各個元件的冗余度（整型）順序組成行向量。

2 HSO算法求解單目標（費用最小）-單約束（可靠度 >=R0）模型

2.1 模型一

假設系統G=(V，E)由n個獨立子系統組成，如圖1所示，在每個子系統中使用相同的2-狀態元件，Cn表示系統的總價格（這里僅僅考慮元件費用），R表示系統可靠性，ci表示第i種元件的單價，xi是第i個子系統第i種部件的個數，xi＞=1，R0是系統要達到預定的可靠度。pi是元件i的可靠度。

圖1 串聯-并聯網絡表示的RAP問題G=(V，E)

則單目標（費用最小）-單約束（可靠度>=R0）優化模型為：

2.2 算法

2.2.1 新解生成算法

初始解為X0，由X0出發生成一個新解的算法如下：

算法1

對X0的每個分量，如果隨機數rand>=0.5，則新解的分量為X0的對應分量加上1，否則，為X0的對應分量減去1。

2.2.2 適應值函數

為修改基本HSO算法適應公式（1）-（2）表示的費用最小化單約束模型，定義新的適應值函數如下：

2.2.3 修改的HSO算法

將Yeh Wei-Chang[2]給出的HSO算法修改如下，有關算法機理、算法正確性等請參閱文獻[2]。

算法2（偽Matlab代碼）

Step0（初始化）以行向量的形式存儲系統元件可靠度、價格等參數；設定壓縮常數c1=c2=0.5，慣性權重w=0.9。

確定元件冗余度的上下界：varmax與varmin; 確定元件冗余度（變量）收斂速度的上下界velmax與velmin;n是元件個數，nc是粒子個數,令V=zeros(n,nc);A=zeros(n,nc);B=zeros(n,nc);CA=zeros(1,nc);Z=zeros(1,nt);這里 nt是總迭代次數。

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

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算法終止。

2.3 模擬仿真

設圖1模型中，由5個子系統組成，每個子系統中元件的正常工作概率和元件價格如下：p1=0.96，p2=0.93，p3=0.85，p4=0.80，p5=0.75；c1=3元，c2=12元，c3=8元，c4=5元，c5=10元，系統要求R0=0.9。

測試都是在微型計算機上進行的；計算機配置為：CPUIntel(R)Core(TM)i5-6500@3.20Ghz 3.20Ghz,內存 8GB,硬盤600Gb；操作系統為Windows10專業版；編程軟件為MatlabR2015b。

算法參數的設置為：n=5,c1=c2=0.5;w=0.9,nc=100,nt=200,α=3。velmin=-0.5;velmax=0.5;varmin=1; varmax=4。初始解X0=[4,4,4,4,4]。

隨機運行算法50次，算法都收斂到最優解Xgbet=[2,2,2,3,2];最小費用=最大費用=平均費用=81元；總的用時為32.67秒；算法一次運行的收斂曲線，見圖2。

圖2 算法2的一次運行給出的收斂曲線

2.4 算法比較

將文獻中各種智能算法求解1.3算例的結果匯總如下表1。

表1 算法的比較結果匯總

由表1可知，HSO在求解1.3中問題時，考慮到目前微型計算機的運行速度都很快，運行算法所用時間不再是主要問題的前提下，HSO算法具有和PSO[5,15]算法、ACA[15]算法同樣好的效果。另外，HSO算法的收斂情況和種群中的粒子數及迭代次數密切相關，當保持運行次數是200，但粒子數改為50個粒子，或保持粒子數為100個，但運行次數改為100的時候，隨機運行算法50次，就會出現不可行解的情況。HSO算法出現這種情況的原因，從機理上看，可能是受到SA算法特征的影響。從上述實例的測試情況看，求解簡單的單目標-單約束可靠性優化模型的時候，HSO算法并沒有表現出它與PSO[5,15]算法的優勢來。

3 HSO算法求解單目標（可靠度最大）-多約束（費用和重量）模型

3.1 模型二

系統由n個子系統串聯組成，每個子系統又是由相同類型的元件并聯構成，在有費用和重量約束條件下，選擇合適的元件數目使得整個系統的可靠度最大[4]。

模型的數學表達式為：

為將公式（4）表示的模型轉化為沒有約束的優化問題，引入適應值函數如下：

其中α，β，γ是正整數。

3.2 算法

為討論問題方便，將Yeh Wei-Chang[2]給出的算法，用偽Mablab語言描述如下：

算法3（偽Matlab代碼）

Step0（初始化）以行向量的形式存儲系統元件可靠度、價格等參數；設定壓縮常數c1=c2=0.5，慣性權重w=0.9。

確定元件冗余度的上下界：varmax與varmin; 確定元件冗余度（變量）收斂速度的上下界velmax與velmin;n是元件個數，nc是粒子個數,令 V=zeros(n,nc);A=zeros(n,nc);B=z eros(n,nc); CA=zeros(1,nc); Z=zeros(1,nt);這里 nt是總迭代次數。

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

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

Step3 for t=1:nt

Step3.1

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

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算法終止。

3.3 模擬仿真

系統由15個子系統組成，每個子系統都由相同元件組成，每個子系統元件的可靠性、費用與重量見表2[4]。

表2 系統元件參數

如果要求系統總費用C<=400元=C0，總重量W<=414kg=W0，nmax<=6。算法參數設置為：算法參數的設置為：n=15,c1=c2=0.5;w=0.9,nc=200,nt=1000,α=1，β=3，γ=1。velmin=-0.5; velmax = 0.5; varmin=1; varmax=6。選擇初始解為X0=[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]。

算法求得的最優解為：X=[3,4,6,4,3,2,4,5,4,2,3,4,5,4,5]，此時系統最大可靠度為0.945613，系統費用392元，系統重量為414kg，本文最優解與文獻[4]相同。隨機運行50次算法，結果為：可靠性最大為0.945613，最小為0.944749，平均為0.944973，總時間為17.464秒。算法的收斂曲線見圖3。

圖3 算法3執行一次的收斂曲線

3.4 算法比較

將文獻中求解2.3問題的算法運行結果列在了表3中，除第1個算法外，每種算法都隨機的執行了50次。

表3 模型2實例算法求解結果匯總

從算法50次運行的平均結果看，HSO算法是幾個算法中最好的；從算法執行的時間上看，HSO算法總的運行時間也是最短的，HSO算法的運行速率非常高；從算法收斂到最優解的次數上看，HSO算法也是比較好的。

4 結論

本文對兩個較為簡單的可靠性冗余分配問題模型，給出了具體的HSO算法，通過模擬仿真發現，HSO算法是求解RAP問題的有效工具。更具體的說，HSO求解模型二類型的問題，比PSO等算法，具有更好的優勢，算法收斂速度快，平均解好；但求解模型一類型問題的時候，總體上看不比PSO等其它算法差多少，可是優勢并不突出。因此，HSO算法比較適合解決多約束、規模較大的RAP問題。