單目標—多條件約束網絡RRAP問題分段迭代PSO算法研究

白迎霞，李東魁

（1.呼和浩特民族學院計算機系，內蒙古呼和浩特，010051；2.包頭師范學院學報編輯部，內蒙古包頭，014030）

0 引言

可靠性-冗余分配問題，英文表述為：Reliability Redundancy Allocation Problem，簡寫為RRAP。RRAP問題的數學模型，一般是非線性混合整數規劃問題；因為一般的可靠性優化問題是NP-Hard的，由于RRAP決策變量中既有實數部分，又有整數部分，一般的RRAP也是NP-Hard的，而且這類問題求解是可靠性優化問題中難度較大的，研究這類問題的快速算法具有重要的實際意義，也具有一定的理論價值。

COIT[1]等對可靠性冗余分配問題(RAP)的歷史發展狀況進行了總結，并預測了未來發展趨勢；本文為討論問題方便起見，對單目標可靠性冗余分配問題的文獻[2-23]，進行了重新梳理，具體情況列在表中（見表1）。

表1可見，由于問題的難度較大，可靠性-冗余分配問題的已有研究結果并不豐富，用于求解的方法主要是遺傳算法、粒子群優化算法及混合算法等，解的編碼也主要是系統元件的可靠度及冗余度，按照可靠度在左，冗余度在右構成的實數與整數共存的行向量[6,8,13,19]。已有RRAP問題的研究方法，主要是遺傳算法、遺傳算法與其它智能算法的混合算法，具有離散型特點和連續型特點的粒子群優化算法還沒有。為行文緊湊起見，有關動態規劃等傳統方法以及后啟發式算法，諸如，遺傳算法、粒子群優化算法原理等可參考文獻[24-32]。

表1 可靠性冗余分配問題（RAP）研究情況一覽表

本文研究2-狀態可靠性-冗余分配問題，設計了一個新的既具有離散型特點又具有連續型特點的混合型粒子群優化算法對RRAP問題進行求解，并通過對典型網絡的模擬仿真，對算法的正確性和有效性進行了驗證。

1 假設和模型

1.1 假設

（1）系統和元件有且僅有兩個狀態，即正常工作狀態和失效狀態；（2）系統中每個可供選擇元件的可靠度、價格、重量和體積等已知；（3）各元件的失效是相互獨立的；（4）失效的元件不可修復；（5）所有備選的元件都是有效的。

1.2 模型

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

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

2 解的結構與算法

2.1 解的結構

粒子群算法中的粒子（解）的構造為：[R，X]，即表示元件可靠度的行向量和表示元件冗余度的行向量X組成，也就是，行向量[R，X]的左邊元素順序是表示元件可靠度的實數變量（值介于0與1之間），右邊元素是表示元件冗余度的整數變量。例如(具體見3.1)，R=[0.774，0.8736，0.9022，0.7115，0.7874]，X=[3，2，2，3，3]；即這里的一個粒子是[R，X]=[0.774，0.8736，0.9022，0.7115，0.7874，3，2，2，3，3]。

2.2 新解的生成算法

初始粒子為[R0，X0]，產生新解時，分別從R0，X0出發，產生新的可靠度向量R和冗余度向量X。

從X0出發，產生新的可靠度向量X算法：

按照均勻分布隨機產生位于區間[varmin1，varmax1]的n個隨機整數；varmin1 <=varmax1，n是元件個數，事實上X與X0無關）。

從R0出發，產生新的可靠度向量R算法：

按照均勻分布隨機產生位于區間[varmin2，varmax2]的n個隨機數（實數；0< varmin2<=varmax2<1，n是元件個數，事實上R與R0無關）。

2.3 適應值函數的確定

我們將有約束可靠性-冗余分配問題改造為無約束可靠性-冗余分配問題，為此，適應值函數修改如下：

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

2.4 兩段迭代PSO算法

算法（偽Matlab代碼）

從圖1和表4可知：除經過大洋置換的壓載水中3種致病菌的垂直分布與其他壓載艙明顯不同外，其他各壓載艙中3種致病菌的垂直分布狀況基本相同，即隨著壓載水深度的增加菌落數量逐漸增加，且在各水深中3種致病菌數量均是大腸埃希菌最多，副溶血弧菌次之，霍亂弧菌最少。

Step0（初始化）設定各元件初始可靠度和冗余度R0，X0，給定初始粒子[R0，X0]；以行向量的形式存儲系統元件費用、重量、體積等參數；設定壓縮常數c1，c2。

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

Step1隨機產生滿足系統約束條件的nc個粒子存于矩陣A中；并將對應的適應值存于CA中；再隨機產生滿足系統約束條件的nc個粒子存于矩陣B中；并將對應的適應值存于CB中。

Step2 for t=1：nt

計算動態權重wt，wt=0.9?0.5*(t?1)/nt，計算當前最優解的費用TC、重量TW和體積TV及適應值e；

將B的第k列前n個分量順序賦給E，后n個分量順序賦給ER。

3 模擬仿真

3.1 串聯網絡

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

其中參數如下：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.931681；Rmin=0.929423；Ravg=0.931328，總體運行時間為408.069秒，最優解對應的R=[0.779274，0.872106，0.902881，0.711721，0.786822]；X=[3，2，2，3，3]，TC=175，TW=192.48，TV=83；結果與文獻[8]用遺傳算法求得的最優結果一致（文獻[6]提供的結果有誤），算法收斂曲線見圖1。

圖1 串聯網絡實例的算法收斂曲線

3.2 橋網絡

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

圖2 橋網絡

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

隨機運行算法50次，運行結果為：Rmax=0.999889，Rmin=0.999644，Ravg=0.999824；總體運行時間為350.83秒，結果與文獻[8]用遺傳算法求得的最優結果一致，最優解對應的R=[0.823548，0.873216，0.853279，0.7，0.746630]；X=[3，3，3，3，1]，TC=175，TW=195.74，TV=92，算法收斂曲線見圖2。

3.3 實驗結果分析

RRAP問題是比較困難的組合優化問題，文獻中除典型的串聯網絡模型、橋網絡（復雜網絡）模型外，很少見到其它用于測試的模型。本文給出的算法，經典型網絡測試后，給出的測試結果同遺傳算法、遺傳算法與其它智能算法構成的混合算法等給出的測試結果是一致的。但我們給出的算法，具有原理容易理解、快速、便于微機實現等特點。

圖3 橋網絡實例的算法收斂曲線

4 結論

本文研究屬于NP-Hard的可靠性-冗余分配（RRAP）問題的求解，設計了不同于文獻[13,19]的，一個具有常量壓縮系數，動態慣性因子的兩段，同時具有離散型特點和連續型特點的粒子群優化算法，通過典型實例的計算機模擬仿真，驗證了算法的正確性和有效性；算法具有原理容易理解，編程簡單，運行高效的特點。本文算法也可以用于具有k-out-of-n類型子系統（k>1）的系統可靠性優化問題求解。