單目標?多條件約束S?P網絡可靠性優化的微粒群算法

摘 要： 研究2?狀態單目標?多條件約束串?并聯（S?P）網絡的可靠性優化問題（RAP）。設計了具有壓縮系數的離散型微粒群算法進行求解，采用Matlab編程對問題實例進行模擬仿真，結果表明，對于合理選擇的初始解與算法參數，微粒群算法每次運行都收斂，并且能夠收斂到最優解。通過與傳統的智能算法（模擬退火算法、蟻群算法、遺傳算法）比較，微粒群算法具有初始解容易選擇、參數易于設置，收斂性好、收斂快的優勢。

關鍵詞： 多條件約束； 串?并聯網絡； 微粒群算法； 可靠性優化； 模擬仿真； 智能算法

中圖分類號： TN911.1?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2018）01?0089?04

Abstract： The reliability optimization problem of the 2?state single?objective and multi?condition constraint series?parallel （S?P） network is studied. The discrete particle swarm optimization algorithm with compression coefficient was designed to solve the above problem. The instance with the problem is simulated with Matlab programming. The simulation results show that， for the reasonably?selected initial solution and algorithm parameter， the particle swarm optimization algorithm has convergence for each operation， and can converge to the optimal solution. In comparison with the traditional intelligent algorithms such as simulated annealing algorithm， ant colony algorithm and genetic algorithm， the particle swarm optimization algorithm has the advantages of easy selection for initial solution， easy setting for parameters， good convergence and fast convergence rate.

Keywords： multi?condition constraint； series?parallel network； particle swarm optimization algorithm； reliability optimization； analog simulation； intelligent algorithm

0 引 言

在實際問題中有著廣泛應用的2?狀態系統可靠性優化問題已經取得了豐碩的研究成果[1?10]，最優冗余問題（RAP）更是得到了廣泛深入的研究[1?6]。由于RAP問題是NP?Hard的，最優化領域中有無免費午餐定理[11]的存在，針對特定RAP的實例，設計、選擇有效算法具有理論與實際意義。

RAP屬于非線性規劃問題，具有多種方法可供選擇：啟發式方法、整數規劃方法、動態規劃方法、幾何規劃方法、廣義的拉格朗日函數法、人工神經網絡、模擬退火算法、遺傳算法、蟻群算法、微粒群算法等[1?10]。

本文研究文獻[6]模型的粒子群優化算法，并對問題實例用Matlab編程，進行模擬仿真，實驗結果說明，粒子群優化算法在求解這類特定問題時，具有容易實現，收斂性好，收斂速度快的優勢。

1 模型與解的構造

系統由[n]個子系統串聯組成，每個子系統又是由選出的不同類型的元件并聯構成，在有費用和重量約束條件下，選擇合適的元件類型與數目使得整個系統的可靠度最大，具體假設和符號見文獻[6]。

模型的數學表達式為：

[maxR=i=1nR（i），s.t. i=1nC（i）≤C， i=1nW（i）≤W] （1）

式中：[R（i）=1-j=1ai（1-rij）xij，][xi1+xi2+…+xij+…+xiai≤nmax，][rij]是子系統[i]的總共為[ai]種元件的第[j]種元件的可靠性，[xij]是對應選擇元件（并聯）的個數；[nmax]是子系統冗余元件的最大個數；[R]是系統可靠度；[R（i），C（i），W（i）]分別是子系統[i]的可靠度、費用和重量；[C，W]是系統的費用和重量約束的上限。為方便用微粒群算法對模型求解，構造微粒（解）[X]如下：

[X=[x11，x12，…，x1a1，…，xi1，xi2，…，xiai，…，xn1，…，xnan]]

即各子系統的元件選擇個數為分量組合構成。

2 具有收縮系數的離散粒子群優化算法

微粒群算法有關知識請參閱文獻[11]。這里給出用于求目標函數最大的具有收縮系數的離散粒子群優化算法。為方便算法描述，引入目標函數如下：

[f（X）=R-M*min0，i=1nC（i）2-M*min0，i=1nW（i）2] （2）

式中[M]為正整數。

算法的具體描述如下：

Step1（初始化）：確定種群規模[N，]最大迭代次數[Gmax，]慣性權重[w，]速度常數[c1，c2]等參數，產生兩組粒子群[Xi]和[X′i，]分別存放粒子的位置和粒子的歷史最優位置，初始速度[Vii=1，2，…，N，]一個全局粒子[P]（群體的最優位置）；計算每個粒子對應的可靠度，判斷是否滿足費用和重量約束條件，若不滿足，則生成一個新粒子，直到滿足約束條件；根據式（2）計算目標函數值。endprint

Step2（更新個體和全局位置）：如果[Xi]的目標函數值大于[X′i]的目標函數值，則用[Xi]替換[X′i]；如果[X′i]的目標函數值大于[P]的目標函數值，則用[X′i]代替[P。]

Step3：根據式（3）～式（4）更新速度和粒子位置：

[vt+1id=w*vtid+c1*rand（ ）（pid-xtid）+c*2rand（ ）（pgt-xtid）] （3）

[xt+1id=int（xtid+vt+1id）] （4）

式中：[int（x）]為取整函數，Matlab中[floor（x），fix（x），round（x），][ceil（x）]可供選擇。

Step4：計算每個粒子對應的可靠度，判斷是否滿足費用和重量約束，否則按照式（3）～式（4）調整，直到滿足約束條件。

Step5：計算每個粒子對應的目標函數值。

Step6：判斷迭代次數[G]是否達到了最大迭代次數[Gmax，]如果是，輸出找到的最優解；否則，[G=G+1，]轉Step2。

有關算法的收斂性討論與證明請參閱文獻[11]。

3 模擬仿真

3.1 實例1

假設系統由3個子系統組成，每個子系統都有5種類型的元件供選擇，每個子系統可供選擇的元件的可靠性、費用和重量數據[6]見表1。

如果要求系統總費用[C≤30]元，總重量[W≤53]kg，[nmax≤5。]算法參數設置為：[M=100，][N=20，][Gmax=200，]慣性權重從0.9線性的減少為0.4，速度常數[c1=c2=3，]選擇初始解為[X0=][0，0，0，0，0，0，0，0，0，0，0，0，0，0，0]。

算法求得的最優解為：[X=0 ，2，0，0，00，2，1，0，00，][0，0，0，5 ，]即子系統1由5種可選擇的元件中第2類2個并聯組成，子系統2由5種可選擇的元件中第2類2個、第3類1個并聯組成，子系統3由5種可選擇的元件中第5類5個元件并聯組成。此時系統最大可靠度為0.982 2，系統費用為30元，系統重量為50 kg，本文最優解優于文獻[6]的0.981 6，算法運行時間也極大的減少。隨機運行50次算法，結果為：可靠性最大為0.982 2（3次），最小為0.969 4，平均為0.976 7，總時間為46.121 7 s。

3.2 實例2

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

如果要求系統總費用[C≤400]元，總重量[W≤414]kg，[nmax≤6。]算法參數設置為：[M=100，][N=20，][Gmax=300，]慣性權重從0.9線性地減少為0.4，速度常數[c1=c2=1.496 3，]選擇初始解為[X0=][2，2，2，2，2，2，2，2，2，2，2，2，2，2，2]。

算法求得的最優解為：[X=][3，4，6，4，3，2，4，5，4，2，3，4，5，4，5]，此時系統最大可靠度為0.945 6，系統費用為392元，系統重量為414 kg，本文算法運行時間極大地減少。隨機運行50次算法，結果為：可靠性最大為0.945 6（3次），最小為0.932 4，平均為0.941 1，總時間為104.198 4 s。

4 算法比較

為了比較算法的有效性，對實例1～2分別采用模擬退火算法、遺傳算法[13]和蟻群算法[6，13]用Matlab編程求解，求解情況見表3，表4。表3中，雖然蟻群算法[6]收斂性非常好，但算法運行時間偏長，另外，對[nmax≤5]的問題容易編程。從能夠求得最好解，并具有較好的收斂性，花費系統時間較少的角度看，微粒群算法都是較好的。

5 結 論

本文給出求解子系統具有不同類型元件并聯，子系統再串聯形成系統，并且元件和系統都具有費用和重量約束，選擇元件類型和數量使得系統可靠度最大的2?狀態單目標?多約束網絡可靠性優化問題的粒子群優化算法，經過模擬仿真與經典智能算法比較，粒子群優化算法是求解這類問題的有效工具。

參考文獻

[1] MITSUO G， YUN Y S. Soft computing approach for reliability optimization： state?of?the?art survey [J]. Reliability engineering & system safety， 2006， 91： 1008?1026.

[2] LIANG Y C， WU C C. A variable neighbourhood descent algorithm for the redundancy allocation problem [J]. IEMS， 2005， 4（1）： 94?101.

[3] LIANG Y C. An ant colony optimization algorithm for the redundancy allocation problem [J]. IEEE transactions on reliability， 2004， 53（4）： 417?423.

[4] PHAKHAPONG T， WORAWAT S， APINAN A， et al. Improved ant colony optimization for solving reliability redundancy allocation problems [J]. International journal of computer， information science and engineering， 2013， 7（2）： 130?135.endprint

[5] COIT D W， SMITH A E. Reliability optimization of series?parallel systems using a genetic algorithm [J]. IEEE transactions on reliability， 1996， 45（2）： 254?260.

[6] 程世娟，盧偉，何平.蟻群算法在冗余系統可靠性最優分配上的應用[J].計算機工程與應用，2009，45（15）：64?66.

CHENG Shijuan， LU Wei， HE Ping. Application of ant colony algorithm in the optimal allocation of redundant system reliability [J]. Computer engineering and applications， 2009， 45（15）： 64?66.

[7] GARG H， SHARMA S P. Multi?objective reliability?redundancy allocation problem using particle swarm optimization [J]. Computers & industrial engineering， 2013， 64（1）： 247?255.

[8] AGHAEI M， HAMADANI A Z， ARDAKAN M A. Redundancy allocation problem for k?out?of?n， systems with a choice of redundancy strategies [J]. Journal of industrial engineering international， 2017， 13（1）： 81?92.

[9] SHEIKHPOUR S， MAHANI A. Particle swarm optimization with intelligent mutation for nonlinear mixed?integer reliability?redundancy allocation [J]. International journal of computational intelligence & applications， 2017， 16（1）： 1?21.

[10] FEIZABADI M， JAHROMI A E. A new model for reliability optimization of series?parallel systems with non?homogeneous components [J]. Reliability engineering & system safety， 2016， 157： 101?112.

[11] 曾建潮，介婧，崔志華.微粒群算法[M].北京：科學出版社，2004.

ZENG Jianchao， JIE Jing， CUI Zhihua. Particle swarm optimization algorithm [M]. Beijing： Science Press， 2004.

[12] WONG J Y. A note on solving a system reliability problem [J]. Microelectronics reliability， 1993， 33（8）： 1045?1051.

[13] 高尚，楊靜宇，吳小俊，等.可靠性優化的蟻群算法[J].計算機應用與軟件，2004，21（12）：94?96.

GAO Shang， YANG Jingyu， WU Xiaojun， et al. Ant colony algorithm for reliability optimization [J]. Computer application and software， 2004， 21（12）： 94?96.

[14] 李東魁，董海.非相同元件并聯的S?P網絡可靠性優化研究[J].陰山學刊（自然科學版），2016，30（2）：35?41.

LI Dongkui， DONG Hai. Reliability optimization of S?P networks in parallel with non?identical components [J]. Yinshan Academic Journal （natural science edition）， 2016， 30（2）： 35?41.

[15] 烏蘭圖雅，李東魁，其木格.相異元件并聯的可靠性優化模型[J].內蒙古師范大學學報（自然科學漢文版），2015，44（6）：761?764.

WULAN Tuya， LI Dongkui， QI Muge. Reliability optimization model in parallel with non?identical components [J]. Journal of Inner Mongolia Normal University （Chinese edition of natural science）， 2015， 44（6）： 761?764.endprint