單目標(biāo)?多條件約束S?P網(wǎng)絡(luò)可靠性優(yōu)化的微粒群算法

摘 要： 研究2?狀態(tài)單目標(biāo)?多條件約束串?并聯(lián)（S?P）網(wǎng)絡(luò)的可靠性優(yōu)化問題（RAP）。設(shè)計(jì)了具有壓縮系數(shù)的離散型微粒群算法進(jìn)行求解，采用Matlab編程對(duì)問題實(shí)例進(jìn)行模擬仿真，結(jié)果表明，對(duì)于合理選擇的初始解與算法參數(shù)，微粒群算法每次運(yùn)行都收斂，并且能夠收斂到最優(yōu)解。通過與傳統(tǒng)的智能算法（模擬退火算法、蟻群算法、遺傳算法）比較，微粒群算法具有初始解容易選擇、參數(shù)易于設(shè)置，收斂性好、收斂快的優(yōu)勢(shì)。

關(guān)鍵詞： 多條件約束； 串?并聯(lián)網(wǎng)絡(luò)； 微粒群算法； 可靠性優(yōu)化； 模擬仿真； 智能算法

中圖分類號(hào)： TN911.1?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

RAP屬于非線性規(guī)劃問題，具有多種方法可供選擇：?jiǎn)l(fā)式方法、整數(shù)規(guī)劃方法、動(dòng)態(tài)規(guī)劃方法、幾何規(guī)劃方法、廣義的拉格朗日函數(shù)法、人工神經(jīng)網(wǎng)絡(luò)、模擬退火算法、遺傳算法、蟻群算法、微粒群算法等[1?10]。

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

1 模型與解的構(gòu)造

系統(tǒng)由[n]個(gè)子系統(tǒng)串聯(lián)組成，每個(gè)子系統(tǒng)又是由選出的不同類型的元件并聯(lián)構(gòu)成，在有費(fèi)用和重量約束條件下，選擇合適的元件類型與數(shù)目使得整個(gè)系統(tǒng)的可靠度最大，具體假設(shè)和符號(hào)見文獻(xiàn)[6]。

模型的數(shù)學(xué)表達(dá)式為：

[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]是子系統(tǒng)[i]的總共為[ai]種元件的第[j]種元件的可靠性，[xij]是對(duì)應(yīng)選擇元件（并聯(lián)）的個(gè)數(shù)；[nmax]是子系統(tǒng)冗余元件的最大個(gè)數(shù)；[R]是系統(tǒng)可靠度；[R（i），C（i），W（i）]分別是子系統(tǒng)[i]的可靠度、費(fèi)用和重量；[C，W]是系統(tǒng)的費(fèi)用和重量約束的上限。為方便用微粒群算法對(duì)模型求解，構(gòu)造微粒（解）[X]如下：

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

即各子系統(tǒng)的元件選擇個(gè)數(shù)為分量組合構(gòu)成。

2 具有收縮系數(shù)的離散粒子群優(yōu)化算法

微粒群算法有關(guān)知識(shí)請(qǐng)參閱文獻(xiàn)[11]。這里給出用于求目標(biāo)函數(shù)最大的具有收縮系數(shù)的離散粒子群優(yōu)化算法。為方便算法描述，引入目標(biāo)函數(shù)如下：

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

式中[M]為正整數(shù)。

算法的具體描述如下：

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

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

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

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

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

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

Step4：計(jì)算每個(gè)粒子對(duì)應(yīng)的可靠度，判斷是否滿足費(fèi)用和重量約束，否則按照式（3）～式（4）調(diào)整，直到滿足約束條件。

Step5：計(jì)算每個(gè)粒子對(duì)應(yīng)的目標(biāo)函數(shù)值。

Step6：判斷迭代次數(shù)[G]是否達(dá)到了最大迭代次數(shù)[Gmax，]如果是，輸出找到的最優(yōu)解；否則，[G=G+1，]轉(zhuǎn)Step2。

有關(guān)算法的收斂性討論與證明請(qǐng)參閱文獻(xiàn)[11]。

3 模擬仿真

3.1 實(shí)例1

假設(shè)系統(tǒng)由3個(gè)子系統(tǒng)組成，每個(gè)子系統(tǒng)都有5種類型的元件供選擇，每個(gè)子系統(tǒng)可供選擇的元件的可靠性、費(fèi)用和重量數(shù)據(jù)[6]見表1。

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

算法求得的最優(yōu)解為：[X=0 ，2，0，0，00，2，1，0，00，][0，0，0，5 ，]即子系統(tǒng)1由5種可選擇的元件中第2類2個(gè)并聯(lián)組成，子系統(tǒng)2由5種可選擇的元件中第2類2個(gè)、第3類1個(gè)并聯(lián)組成，子系統(tǒng)3由5種可選擇的元件中第5類5個(gè)元件并聯(lián)組成。此時(shí)系統(tǒng)最大可靠度為0.982 2，系統(tǒng)費(fèi)用為30元，系統(tǒng)重量為50 kg，本文最優(yōu)解優(yōu)于文獻(xiàn)[6]的0.981 6，算法運(yùn)行時(shí)間也極大的減少。隨機(jī)運(yùn)行50次算法，結(jié)果為：可靠性最大為0.982 2（3次），最小為0.969 4，平均為0.976 7，總時(shí)間為46.121 7 s。

3.2 實(shí)例2

系統(tǒng)由15個(gè)子系統(tǒng)組成，每個(gè)子系統(tǒng)都由相同元件組成，每個(gè)子系統(tǒng)元件的可靠性、費(fèi)用與重量[12]見表2。

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

算法求得的最優(yōu)解為：[X=][3，4，6，4，3，2，4，5，4，2，3，4，5，4，5]，此時(shí)系統(tǒng)最大可靠度為0.945 6，系統(tǒng)費(fèi)用為392元，系統(tǒng)重量為414 kg，本文算法運(yùn)行時(shí)間極大地減少。隨機(jī)運(yùn)行50次算法，結(jié)果為：可靠性最大為0.945 6（3次），最小為0.932 4，平均為0.941 1，總時(shí)間為104.198 4 s。

4 算法比較

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

5 結(jié) 論

本文給出求解子系統(tǒng)具有不同類型元件并聯(lián)，子系統(tǒng)再串聯(lián)形成系統(tǒng)，并且元件和系統(tǒng)都具有費(fèi)用和重量約束，選擇元件類型和數(shù)量使得系統(tǒng)可靠度最大的2?狀態(tài)單目標(biāo)?多約束網(wǎng)絡(luò)可靠性優(yōu)化問題的粒子群優(yōu)化算法，經(jīng)過模擬仿真與經(jīng)典智能算法比較，粒子群優(yōu)化算法是求解這類問題的有效工具。

參考文獻(xiàn)

[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] 程世娟，盧偉，何平.蟻群算法在冗余系統(tǒng)可靠性最優(yōu)分配上的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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].北京：科學(xué)出版社，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] 高尚，楊靜宇，吳小俊，等.可靠性優(yōu)化的蟻群算法[J].計(jì)算機(jī)應(yīng)用與軟件，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] 李東魁，董海.非相同元件并聯(lián)的S?P網(wǎng)絡(luò)可靠性優(yōu)化研究[J].陰山學(xué)刊（自然科學(xué)版），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] 烏蘭圖雅，李東魁，其木格.相異元件并聯(lián)的可靠性優(yōu)化模型[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)（自然科學(xué)漢文版），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