粒子群及局部搜索算法在串并聯(lián)系統(tǒng)結(jié)構(gòu)優(yōu)化中的應(yīng)用

王 健，趙 娜，劉 超，孫志禮

（東北大學(xué)機(jī)械工程與自動(dòng)化學(xué)院，遼寧 沈陽(yáng)110819）

0 引言

保持工作系統(tǒng)具有較高的可靠性及可用度對(duì)設(shè)備使用者和設(shè)計(jì)人員都非常重要。在系統(tǒng)可靠性工程中主要有2種方法提高系統(tǒng)可靠性指標(biāo)，一種是提高系統(tǒng)中各個(gè)部件的可靠性水平；另一種是在系統(tǒng)中并聯(lián)與現(xiàn)有部件具有相同功能的部件。當(dāng)選擇第2種方法時(shí)，若系統(tǒng)中并聯(lián)部件太多，不但會(huì)造成系統(tǒng)龐大結(jié)構(gòu)復(fù)雜，而且造價(jià)過(guò)高，若系統(tǒng)中并聯(lián)部件不足，則會(huì)造成可靠性指標(biāo)不能滿(mǎn)足設(shè)計(jì)要求，因此，設(shè)計(jì)者必須在系統(tǒng)花費(fèi)和系統(tǒng)可靠性水平間加以平衡。

早期學(xué)者們?cè)噲D尋找上述冗余分配問(wèn)題［1］的精確最優(yōu)解，但計(jì)算量隨著問(wèn)題解維數(shù)的增加呈指數(shù)增長(zhǎng)，所有維數(shù)較高冗余分配問(wèn)題要想得到精確最優(yōu)解是相當(dāng)困難的。后來(lái)，遺傳算法［2］、粒子群算法［3］和蟻群算法［4］等啟發(fā)式算法應(yīng)用到冗余分配問(wèn)題中，希望能得到近似解，但實(shí)際應(yīng)用中發(fā)現(xiàn)單純使用一種算法容易得到局部最優(yōu)解而不是整個(gè)問(wèn)題的最優(yōu)解。因此，將粒子群算法同局部搜索算法相結(jié)合，能有效避免在算法迭代過(guò)程中局部收斂現(xiàn)象。

1 系統(tǒng)結(jié)構(gòu)模型

串并聯(lián)系統(tǒng)［5-6］結(jié)構(gòu)模型如圖1所示。整個(gè)系統(tǒng)由Ns個(gè)子系統(tǒng)串聯(lián)而成，各子系統(tǒng)內(nèi)部部件間為并聯(lián)關(guān)系。第i個(gè)子系統(tǒng)中共有Vi個(gè)不同可用類(lèi)型部件，每種類(lèi)型部件均能實(shí)現(xiàn)相同的功能，只有能力、可用度和費(fèi)用不同。第j（j｛1，2，…，Vi｝）類(lèi)部件共有Hij個(gè)不同的工作狀態(tài)，每個(gè)狀態(tài)的工作能力不同，顯然Hij≥2，即每個(gè)類(lèi)型部件至少應(yīng)有2個(gè)工作狀態(tài)。

圖1 串并聯(lián)系統(tǒng)結(jié)構(gòu)

子系統(tǒng)i中第j個(gè)類(lèi)型部件的單價(jià)用Cij表示，該類(lèi)型部件處在狀態(tài)h（h｛1，2，…，Hij｝）的概率為Aijh，對(duì)應(yīng)的工作能力為 Wijh，這里的 Hij，Aijh和Wijh是部件的固有性質(zhì)，其中，Aijh是根據(jù)部件的狀態(tài)轉(zhuǎn)移概率矩陣及維修更換策略經(jīng)過(guò)較復(fù)雜計(jì)算得到。參考文獻(xiàn)［7］中對(duì)該過(guò)程進(jìn)行了詳細(xì)說(shuō)明，而這里認(rèn)為系統(tǒng)處在穩(wěn)定工作狀態(tài)時(shí)各子系統(tǒng)中各類(lèi)型部件的Aijh是已知的。子系統(tǒng)i中j類(lèi)型部件的數(shù)量由Xij表示，這樣子系統(tǒng)i的結(jié)構(gòu)可由向量Xi表示，即

Vi為子系統(tǒng)i中部件類(lèi)型個(gè)數(shù)，顯然Xij≥0。整個(gè)系統(tǒng)結(jié)構(gòu)由各子系統(tǒng)結(jié)構(gòu)完全確定，用向量X表示整個(gè)系統(tǒng)結(jié)構(gòu)：

X＝［X1，X2，…，XNs］

Ns為子系統(tǒng)個(gè)數(shù)。

這樣整個(gè)系統(tǒng)的花費(fèi)CS為：

系統(tǒng)可用度用AS表示，在運(yùn)行過(guò)程中系統(tǒng)可用度的下限設(shè)為A0，則結(jié)構(gòu)優(yōu)化問(wèn)題為：

結(jié)束條件為AS≥A0。求解式（2）所得系統(tǒng)結(jié)構(gòu)X即為系統(tǒng)的最優(yōu)結(jié)構(gòu)。

2 系統(tǒng)可用度計(jì)算

在此，計(jì)算系統(tǒng)可用度使用概率生成函數(shù)方法，并假設(shè)系統(tǒng)中各個(gè)部件間的工作狀態(tài)是相互獨(dú)立的，這一假設(shè)非常重要，是應(yīng)用UGF計(jì)算系統(tǒng)可用度的前提條件。

由上文可知，子系統(tǒng)i中j類(lèi)部件的UGF為：

根據(jù)UGF在處理獨(dú)立隨機(jī)變量中的性質(zhì)及子系統(tǒng)中各個(gè)部件間為并聯(lián)關(guān)系，子系統(tǒng)i的UGF為：

式（4）可以展開(kāi)為：

Api為子系統(tǒng)工作能力為Wpi的概率。由于各個(gè)子系統(tǒng)間為串聯(lián)關(guān)系，根據(jù)式（5）可以得到系統(tǒng)的UGF為：

式（6）可以展開(kāi)為：

Q為系統(tǒng)的狀態(tài)個(gè)數(shù)；Wq為各個(gè)狀態(tài)對(duì)應(yīng)的工作能力。

若將系統(tǒng)工作時(shí)間分成M 段，第m（m｛1，2，…，M｝）段長(zhǎng)度為T(mén)m，且第m段要求系統(tǒng)工作能力不低于W0m，則系統(tǒng)在第m個(gè)工作時(shí)間段內(nèi)的可用度為：

則系統(tǒng)在整個(gè)工作過(guò)程中的可用度為：

3 粒子群算法和局部搜索算法

3．1 粒子群算法

粒子群算法（PSO）是一種群智能算法，在求解高維非線(xiàn)性不可微問(wèn)題中表現(xiàn)出較好的效率，PSO算法在處理這類(lèi)問(wèn)題時(shí)要比遺傳算法收斂速度快很多。它的基本概念源于對(duì)鳥(niǎo)群覓食行為的研究。設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)搜尋食物，在這個(gè)區(qū)域里只有一塊食物，所有的鳥(niǎo)都不知道食物在哪里，它們只能根據(jù)自己和相鄰鳥(niǎo)的經(jīng)驗(yàn)，選擇下一步向哪個(gè)方向移動(dòng)去尋找食物。）

標(biāo)準(zhǔn)PSO算法首先要隨機(jī)產(chǎn)生一定數(shù)量NP的“粒子”，同時(shí)產(chǎn)生與每個(gè)初始粒子對(duì)應(yīng)的前進(jìn)速度，用X表示粒子的位置，Y表示X 的速度。實(shí)際問(wèn)題中X各分量的取值不可能是任意的，式（2）所要優(yōu)化問(wèn)題的X分量的上限用XB表示。每個(gè)粒子都沿著自己的速度方向移動(dòng)，更新位置并尋找問(wèn)題的最優(yōu)解，粒子的速度及位置更新過(guò)程為：

X（t＋1），X（t）為粒子在第t＋1次和第t次迭代后所處位置；Y（t＋1）為粒子在第t＋1次迭代時(shí)的速度；XPB為粒子自身所得到的最優(yōu)解，稱(chēng)之為局部最優(yōu)解；XGB為所有粒子得到的最優(yōu)解，每次迭代后都要對(duì)XPB和XGB進(jìn)行更新；l1和l2為XPB和XGB的影響因子；u1和u2為取自［0，1］區(qū)間均勻分布隨機(jī)數(shù)；w為粒子初始速度影響因子。

粒子群算法中用適應(yīng)度函數(shù)決定一個(gè)粒子或解的好壞程度。所提優(yōu)化問(wèn)題的適應(yīng)度函數(shù)由2部分組成，一部分為粒子X(jué)所決定系統(tǒng)的費(fèi)用CS，另一部分為，若X所決定系統(tǒng)的可用度不能滿(mǎn)足A0要求，則應(yīng)該在CS基礎(chǔ)上增加CP作為懲罰，以利于在以后迭代中將可用度小于A0的解淘汰掉，實(shí)現(xiàn)約束條件AS≥A0。所以式（2）對(duì)應(yīng)的適應(yīng)度函數(shù)可表示為：

γ為懲罰系數(shù)，參考文獻(xiàn)［8］中給出選取γ的系統(tǒng)說(shuō)明。

3．2 局部搜索策略

為彌補(bǔ)PSO算法在迭代過(guò)程中可能出現(xiàn)局部收斂的缺陷，加快整個(gè)求解過(guò)程的收斂速度和求解精度，給出5種局部搜索策略作為對(duì)原始PSO的補(bǔ)充。

a．“＋1”。對(duì)每個(gè)子系統(tǒng)中在現(xiàn)有解基礎(chǔ)上增加1個(gè)部件，增加的部件可以屬于系統(tǒng)中任何類(lèi)型。

b．“-1”。對(duì)每個(gè)子系統(tǒng)中在現(xiàn)有解基礎(chǔ)上減少1個(gè)部件，減少的部件可以屬于系統(tǒng)中任何類(lèi)型，若系統(tǒng)中某一類(lèi)型部件數(shù)為0，則不對(duì)其進(jìn)行任何操作。

c．“-1，＋1”。每個(gè)子系統(tǒng)中在現(xiàn)有解基礎(chǔ)上減少1個(gè)部件，減少的部件可以屬于系統(tǒng)中任何類(lèi)型，若系統(tǒng)中某一類(lèi)型部件數(shù)為0，則不對(duì)其進(jìn)行任何操作，同時(shí)增加1個(gè)子系統(tǒng)中其他類(lèi)型部件。

d．“-1，＋β”。與c類(lèi)似，不同的是，在刪除1個(gè)部件后要增加β個(gè)其他型號(hào)部件，β的計(jì)算為：

e．“-all，＋β”：該策略與d類(lèi)似，不同在于要?jiǎng)h除所有j1類(lèi)型部件，用β個(gè)j2類(lèi)型部件代替，β由下式?jīng)Q定：

經(jīng)過(guò)以上某種局部搜索策略處理后得到的粒子X(jué)′要與X 進(jìn)行比較，取其中最好的粒子繼續(xù)進(jìn)行PSO迭代。

需要說(shuō)明的是，為了控制算法的計(jì)算量，并不是在每次PSO迭代前對(duì)所有粒子進(jìn)行局部搜索，而是規(guī)定每進(jìn)行一定次數(shù)PSO迭代后，對(duì)所得粒子隨機(jī)挑選一定比例進(jìn)行局部搜索處理，這樣既可以使算法計(jì)算量不會(huì)太大，又能在一定程度上加快收斂速度和避免局部收斂。

4 實(shí)例

假設(shè)共有4個(gè)子系統(tǒng)，所有可選部件都只有工作和故障2個(gè)狀態(tài)。部件故障狀態(tài)時(shí)工作能力為0。各子系統(tǒng)中部件的類(lèi)型數(shù)量、費(fèi)用可用度和工作能力等指標(biāo)如表1所示。系統(tǒng)整個(gè)工作過(guò)程分為3個(gè)階段，各個(gè)階段需要的系統(tǒng)工作能力及工作時(shí)間如表2所示，系統(tǒng)的可用度不能低于A0＝0．9。

本例中取NP＝1 000，即隨機(jī)產(chǎn)生1 000個(gè)粒子作為解，并隨機(jī)產(chǎn)生NP個(gè)粒子的速度，這時(shí)各局部最優(yōu)解就是各粒子。根據(jù)式（11）和式（12）及A0，確定NP個(gè)粒子的最優(yōu)解就是全局最優(yōu)解，再依照式（10）進(jìn)行迭代（式（10）的參數(shù)如表3所示），每次迭代后根據(jù)式（11）和式（12）更新局部最優(yōu)解和全局最優(yōu)解。迭代過(guò)程采用3．2節(jié)中局部搜索策略（e），且每進(jìn)行n＝5次PSO迭代就進(jìn)行1次局部搜索，局部搜索比例為5%，即每進(jìn)行5次PSO迭代后，隨機(jī)選取1 000×5%＝50個(gè)粒子進(jìn)行局部搜索。

根據(jù)上文敘述方法進(jìn)行迭代求解，當(dāng)A0取不同值時(shí)，得到最優(yōu)解的取值情況如表4所示。

表1 各類(lèi)型部件參數(shù)

表2 不同時(shí)間段工作能力要求

表3 粒子群算法的參數(shù)

表4 最優(yōu)解表

5 結(jié)束語(yǔ)

利用UGF方法計(jì)算系統(tǒng)可用度，提出用粒子群算法和局部搜索算法相結(jié)合的方法，解決串并聯(lián)系統(tǒng)結(jié)構(gòu)優(yōu)化問(wèn)題，能夠有效避免單獨(dú)使用粒子群算法時(shí)出現(xiàn)局部收斂和收斂速度較慢現(xiàn)象，增大了得到問(wèn)題真正最優(yōu)解的概率。在求解迭代過(guò)程中，向適應(yīng)度函數(shù)加入罰函數(shù)，用以實(shí)現(xiàn)對(duì)系統(tǒng)可用度的約束。

［1］ 侯雪梅，劉 偉，高 飛，等．基于群智能的模糊多目標(biāo)軟件可靠性冗余分配［J］．計(jì)算機(jī)應(yīng)用，2013，33（4）：1142-1145．

［2］ 葛繼科，邱玉輝，吳春明，等．遺傳算法研究綜述［J］．計(jì)算機(jī)應(yīng)用研究，2008，25（10）：2911-2916．

［3］ 侯云鶴，魯麗娟，熊信艮，等．改進(jìn)粒子群算法及其在電力系統(tǒng)經(jīng)濟(jì)負(fù)荷分配中的應(yīng)用［J］．中國(guó)電機(jī)工程學(xué)報(bào)，2004，24（7）：95-100．

［4］ 韓 攀，陳 謀，陳哨東，等．基于改進(jìn)蟻群算法的無(wú)人機(jī)航跡規(guī)劃［J］．吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2013，31（1）：66-72．

［5］ Wang G J，Zhang Y L．An optimal replacement policy for a two-component series system assuming geometric process repair［J］．Computers ＆ M athematics with Applications，2007，54（2）：192–202．

［6］ Nourelfath M，Ait-Kadi D．Optimization of series-parallel multi-state systems under maintenance policies［J］．Reliability Engineering ＆ S ystem Safety，2007，92（12）：1620-1626．

［7］ Zhou Yifan，Zhang Zhisheng，Lin Tianran，et al．Maintenance optimization of a multi-state series-parallel system considering economic dependence and state-dependent inspection intervals［J］．Reliability Engineering＆ S ystem Safety，2013，111：248-259．

［8］ 吳化堯，聶長(zhǎng)海．覆蓋表生成的粒子群算法：參數(shù)優(yōu)化和自適應(yīng)算法［J］．小型微型計(jì)算機(jī)系統(tǒng)，2012，33（10）：2259-2257．