白迎霞，李東魁

（1.呼和浩特民族學(xué)院計算機(jī)系，內(nèi)蒙古呼和浩特，010051；2.包頭師范學(xué)院學(xué)報編輯部，內(nèi)蒙古包頭，014030）

0 引言

可靠性-冗余分配問題，英文表述為：Reliability Redundancy Allocation Problem，簡寫為RRAP。RRAP問題的數(shù)學(xué)模型，一般是非線性混合整數(shù)規(guī)劃問題；因?yàn)橐话愕目煽啃詢?yōu)化問題是NP-Hard的，由于RRAP決策變量中既有實(shí)數(shù)部分，又有整數(shù)部分，一般的RRAP也是NP-Hard的，而且這類問題求解是可靠性優(yōu)化問題中難度較大的，研究這類問題的快速算法具有重要的實(shí)際意義，也具有一定的理論價值。

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

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

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

本文研究2-狀態(tài)可靠性-冗余分配問題，設(shè)計了一個新的既具有離散型特點(diǎn)又具有連續(xù)型特點(diǎn)的混合型粒子群優(yōu)化算法對RRAP問題進(jìn)行求解，并通過對典型網(wǎng)絡(luò)的模擬仿真，對算法的正確性和有效性進(jìn)行了驗(yàn)證。

1 假設(shè)和模型

1.1 假設(shè)

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

1.2 模型

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

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

2 解的結(jié)構(gòu)與算法

2.1 解的結(jié)構(gòu)

粒子群算法中的粒子（解）的構(gòu)造為：[R，X]，即表示元件可靠度的行向量和表示元件冗余度的行向量X組成，也就是，行向量[R，X]的左邊元素順序是表示元件可靠度的實(shí)數(shù)變量（值介于0與1之間），右邊元素是表示元件冗余度的整數(shù)變量。例如(具體見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]，產(chǎn)生新解時，分別從R0，X0出發(fā)，產(chǎn)生新的可靠度向量R和冗余度向量X。

從X0出發(fā)，產(chǎn)生新的可靠度向量X算法：

按照均勻分布隨機(jī)產(chǎn)生位于區(qū)間[varmin1，varmax1]的n個隨機(jī)整數(shù)；varmin1 <=varmax1，n是元件個數(shù)，事實(shí)上X與X0無關(guān)）。

從R0出發(fā)，產(chǎn)生新的可靠度向量R算法：

按照均勻分布隨機(jī)產(chǎn)生位于區(qū)間[varmin2，varmax2]的n個隨機(jī)數(shù)（實(shí)數(shù)；0< varmin2<=varmax2<1，n是元件個數(shù)，事實(shí)上R與R0無關(guān)）。

2.3 適應(yīng)值函數(shù)的確定

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

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

2.4 兩段迭代PSO算法

算法（偽Matlab代碼）

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

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

確定元件冗余度的上下界：varmin1與varmax1；確定元件可靠度的上下界varmin2與varmax2；確定元件冗余度（變量）收斂速度的上下界velmax1與velmin1；確定元件可靠度（變量）收斂速度的上下界velmax2與velmin2；n是元件個數(shù)，nc是粒子個數(shù)，令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是總迭代次數(shù)。

Step1隨機(jī)產(chǎn)生滿足系統(tǒng)約束條件的nc個粒子存于矩陣A中；并將對應(yīng)的適應(yīng)值存于CA中；再隨機(jī)產(chǎn)生滿足系統(tǒng)約束條件的nc個粒子存于矩陣B中；并將對應(yīng)的適應(yīng)值存于CB中。

Step2 for t=1：nt

計算動態(tài)權(quán)重wt，wt=0.9?0.5*(t?1)/nt，計算當(dāng)前最優(yōu)解的費(fèi)用TC、重量TW和體積TV及適應(yīng)值e；

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

3 模擬仿真

3.1 串聯(lián)網(wǎng)絡(luò)

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

其中參數(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。

隨機(jī)運(yùn)行算法50次，結(jié)果如下：Rmax=0.931681；Rmin=0.929423；Ravg=0.931328，總體運(yùn)行時間為408.069秒，最優(yōu)解對應(yīng)的R=[0.779274，0.872106，0.902881，0.711721，0.786822]；X=[3，2，2，3，3]，TC=175，TW=192.48，TV=83；結(jié)果與文獻(xiàn)[8]用遺傳算法求得的最優(yōu)結(jié)果一致（文獻(xiàn)[6]提供的結(jié)果有誤），算法收斂曲線見圖1。

圖1 串聯(lián)網(wǎng)絡(luò)實(shí)例的算法收斂曲線

3.2 橋網(wǎng)絡(luò)

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

圖2 橋網(wǎng)絡(luò)

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

隨機(jī)運(yùn)行算法50次，運(yùn)行結(jié)果為：Rmax=0.999889，Rmin=0.999644，Ravg=0.999824；總體運(yùn)行時間為350.83秒，結(jié)果與文獻(xiàn)[8]用遺傳算法求得的最優(yōu)結(jié)果一致，最優(yōu)解對應(yīng)的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 實(shí)驗(yàn)結(jié)果分析

RRAP問題是比較困難的組合優(yōu)化問題，文獻(xiàn)中除典型的串聯(lián)網(wǎng)絡(luò)模型、橋網(wǎng)絡(luò)（復(fù)雜網(wǎng)絡(luò)）模型外，很少見到其它用于測試的模型。本文給出的算法，經(jīng)典型網(wǎng)絡(luò)測試后，給出的測試結(jié)果同遺傳算法、遺傳算法與其它智能算法構(gòu)成的混合算法等給出的測試結(jié)果是一致的。但我們給出的算法，具有原理容易理解、快速、便于微機(jī)實(shí)現(xiàn)等特點(diǎn)。

圖3 橋網(wǎng)絡(luò)實(shí)例的算法收斂曲線

4 結(jié)論

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