粒子群及局部搜索算法在串并聯系統結構優化中的應用

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

（東北大學機械工程與自動化學院，遼寧 沈陽110819）

0 引言

保持工作系統具有較高的可靠性及可用度對設備使用者和設計人員都非常重要。在系統可靠性工程中主要有2種方法提高系統可靠性指標，一種是提高系統中各個部件的可靠性水平；另一種是在系統中并聯與現有部件具有相同功能的部件。當選擇第2種方法時，若系統中并聯部件太多，不但會造成系統龐大結構復雜，而且造價過高，若系統中并聯部件不足，則會造成可靠性指標不能滿足設計要求，因此，設計者必須在系統花費和系統可靠性水平間加以平衡。

早期學者們試圖尋找上述冗余分配問題［1］的精確最優解，但計算量隨著問題解維數的增加呈指數增長，所有維數較高冗余分配問題要想得到精確最優解是相當困難的。后來，遺傳算法［2］、粒子群算法［3］和蟻群算法［4］等啟發式算法應用到冗余分配問題中，希望能得到近似解，但實際應用中發現單純使用一種算法容易得到局部最優解而不是整個問題的最優解。因此，將粒子群算法同局部搜索算法相結合，能有效避免在算法迭代過程中局部收斂現象。

1 系統結構模型

串并聯系統［5-6］結構模型如圖1所示。整個系統由Ns個子系統串聯而成，各子系統內部部件間為并聯關系。第i個子系統中共有Vi個不同可用類型部件，每種類型部件均能實現相同的功能，只有能力、可用度和費用不同。第j（j｛1，2，…，Vi｝）類部件共有Hij個不同的工作狀態，每個狀態的工作能力不同，顯然Hij≥2，即每個類型部件至少應有2個工作狀態。

圖1 串并聯系統結構

子系統i中第j個類型部件的單價用Cij表示，該類型部件處在狀態h（h｛1，2，…，Hij｝）的概率為Aijh，對應的工作能力為 Wijh，這里的 Hij，Aijh和Wijh是部件的固有性質，其中，Aijh是根據部件的狀態轉移概率矩陣及維修更換策略經過較復雜計算得到。參考文獻［7］中對該過程進行了詳細說明，而這里認為系統處在穩定工作狀態時各子系統中各類型部件的Aijh是已知的。子系統i中j類型部件的數量由Xij表示，這樣子系統i的結構可由向量Xi表示，即

Vi為子系統i中部件類型個數，顯然Xij≥0。整個系統結構由各子系統結構完全確定，用向量X表示整個系統結構：

X＝［X1，X2，…，XNs］

Ns為子系統個數。

這樣整個系統的花費CS為：

系統可用度用AS表示，在運行過程中系統可用度的下限設為A0，則結構優化問題為：

結束條件為AS≥A0。求解式（2）所得系統結構X即為系統的最優結構。

2 系統可用度計算

在此，計算系統可用度使用概率生成函數方法，并假設系統中各個部件間的工作狀態是相互獨立的，這一假設非常重要，是應用UGF計算系統可用度的前提條件。

由上文可知，子系統i中j類部件的UGF為：

根據UGF在處理獨立隨機變量中的性質及子系統中各個部件間為并聯關系，子系統i的UGF為：

式（4）可以展開為：

Api為子系統工作能力為Wpi的概率。由于各個子系統間為串聯關系，根據式（5）可以得到系統的UGF為：

式（6）可以展開為：

Q為系統的狀態個數；Wq為各個狀態對應的工作能力。

若將系統工作時間分成M 段，第m（m｛1，2，…，M｝）段長度為Tm，且第m段要求系統工作能力不低于W0m，則系統在第m個工作時間段內的可用度為：

則系統在整個工作過程中的可用度為：

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

3．1 粒子群算法

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

標準PSO算法首先要隨機產生一定數量NP的“粒子”，同時產生與每個初始粒子對應的前進速度，用X表示粒子的位置，Y表示X 的速度。實際問題中X各分量的取值不可能是任意的，式（2）所要優化問題的X分量的上限用XB表示。每個粒子都沿著自己的速度方向移動，更新位置并尋找問題的最優解，粒子的速度及位置更新過程為：

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

粒子群算法中用適應度函數決定一個粒子或解的好壞程度。所提優化問題的適應度函數由2部分組成，一部分為粒子X所決定系統的費用CS，另一部分為，若X所決定系統的可用度不能滿足A0要求，則應該在CS基礎上增加CP作為懲罰，以利于在以后迭代中將可用度小于A0的解淘汰掉，實現約束條件AS≥A0。所以式（2）對應的適應度函數可表示為：

γ為懲罰系數，參考文獻［8］中給出選取γ的系統說明。

3．2 局部搜索策略

為彌補PSO算法在迭代過程中可能出現局部收斂的缺陷，加快整個求解過程的收斂速度和求解精度，給出5種局部搜索策略作為對原始PSO的補充。

a．“＋1”。對每個子系統中在現有解基礎上增加1個部件，增加的部件可以屬于系統中任何類型。

b．“-1”。對每個子系統中在現有解基礎上減少1個部件，減少的部件可以屬于系統中任何類型，若系統中某一類型部件數為0，則不對其進行任何操作。

c．“-1，＋1”。每個子系統中在現有解基礎上減少1個部件，減少的部件可以屬于系統中任何類型，若系統中某一類型部件數為0，則不對其進行任何操作，同時增加1個子系統中其他類型部件。

d．“-1，＋β”。與c類似，不同的是，在刪除1個部件后要增加β個其他型號部件，β的計算為：

e．“-all，＋β”：該策略與d類似，不同在于要刪除所有j1類型部件，用β個j2類型部件代替，β由下式決定：

經過以上某種局部搜索策略處理后得到的粒子X′要與X 進行比較，取其中最好的粒子繼續進行PSO迭代。

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

4 實例

假設共有4個子系統，所有可選部件都只有工作和故障2個狀態。部件故障狀態時工作能力為0。各子系統中部件的類型數量、費用可用度和工作能力等指標如表1所示。系統整個工作過程分為3個階段，各個階段需要的系統工作能力及工作時間如表2所示，系統的可用度不能低于A0＝0．9。

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

根據上文敘述方法進行迭代求解，當A0取不同值時，得到最優解的取值情況如表4所示。

表1 各類型部件參數

表2 不同時間段工作能力要求

表3 粒子群算法的參數

表4 最優解表

5 結束語

利用UGF方法計算系統可用度，提出用粒子群算法和局部搜索算法相結合的方法，解決串并聯系統結構優化問題，能夠有效避免單獨使用粒子群算法時出現局部收斂和收斂速度較慢現象，增大了得到問題真正最優解的概率。在求解迭代過程中，向適應度函數加入罰函數，用以實現對系統可用度的約束。

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

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

［3］ 侯云鶴，魯麗娟，熊信艮，等．改進粒子群算法及其在電力系統經濟負荷分配中的應用［J］．中國電機工程學報，2004，24（7）：95-100．

［4］ 韓 攀，陳 謀，陳哨東，等．基于改進蟻群算法的無人機航跡規劃［J］．吉林大學學報（信息科學版），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］ 吳化堯，聶長海．覆蓋表生成的粒子群算法：參數優化和自適應算法［J］．小型微型計算機系統，2012，33（10）：2259-2257．