基于粒子群算法的延遲轉(zhuǎn)換備份元件優(yōu)化排序

胡傳福，史小宏

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

基于粒子群算法的延遲轉(zhuǎn)換備份元件優(yōu)化排序

胡傳福，史小宏

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

系統(tǒng)的可靠性設(shè)計中經(jīng)常使用的混合冗余備份策略可以提高系統(tǒng)的可靠性，溫備份元件的轉(zhuǎn)化通常在上一個熱備份模式的元件失效后立即轉(zhuǎn)化替換；在延遲轉(zhuǎn)換混合備用系統(tǒng)中，經(jīng)過一定的延遲時間后才會替換前一個備份元件，這些元件的初始化分布對系統(tǒng)可靠性和任務(wù)成本有較大影響。首次使用粒子群算法來處理這種可靠性系統(tǒng)的組合優(yōu)化問題，找出最優(yōu)元件排序組合和最佳延遲時間；通過這種算法處理找出的元件排序組合可以經(jīng)濟有效地應(yīng)用于系統(tǒng)可靠性設(shè)計中。

混合備份；可靠性；任務(wù)成本；粒子群算法

0 引言

可靠性設(shè)計與分析就是通過可靠性預(yù)計、分配、分析和改進等可靠性技術(shù)，把可靠性定量要求轉(zhuǎn)化為產(chǎn)品設(shè)計，形成產(chǎn)品固有可靠性，包括建立系統(tǒng)可靠性模型、進行可靠性設(shè)計、可靠性分配和各種可靠性分析[1]。在混合備份策略的設(shè)計中元件可以在預(yù)設(shè)的固定時刻從溫備份轉(zhuǎn)化到熱備份，可能會發(fā)生備份元件過早地轉(zhuǎn)換到熱備份導(dǎo)致任務(wù)成本增加和可靠性的降低，或是沒有及時轉(zhuǎn)換到熱備份導(dǎo)致從溫備份直接轉(zhuǎn)換到在線操作，使恢復(fù)延遲時間過長。在狀態(tài)獨立的轉(zhuǎn)換模式下，溫備份轉(zhuǎn)換到熱備份是由在線操作元件或當(dāng)前熱備份元件的狀態(tài)觸發(fā)的，當(dāng)其中任何一個元件失敗，溫備份元件立即轉(zhuǎn)換到熱備份，這種模式可以在一定程度減少任務(wù)成本提高可靠性，但不是最有效的。在熱備份元件失效或者替換在線元件之后，延遲轉(zhuǎn)換備份模式會將溫備份序列中的元件延遲一些時間再轉(zhuǎn)換成熱備份，延遲可以有效提高任務(wù)可靠性和減少任務(wù)成本[2]。利用粒子群算法及其改進優(yōu)化算法,結(jié)合可靠性分析方法進行結(jié)構(gòu)的可靠性優(yōu)化設(shè)計[3]，本文首次通過粒子群算法在可行解域內(nèi)優(yōu)化選擇這些元件的初始化分布和延遲時間來達(dá)到系統(tǒng)可靠性最優(yōu)化設(shè)計[4]。

1 延遲轉(zhuǎn)換混合冗余備份模型

混合冗余備份系統(tǒng)由N個獨立元件組成，元件E（1）在系統(tǒng)啟動時就進入在線操作模式，其他備份元件處于溫備份模式，溫備份模式中的元件按照序列E（2）…E（n）轉(zhuǎn)換到熱備份，當(dāng)溫備份模式中有元件存在且熱備份模式中已經(jīng)有θ時間內(nèi)元件個數(shù)為0時，溫備份元件將轉(zhuǎn)換到熱備份。即備份元件序列E（2）…E（k-1）已經(jīng)離開溫備份模式，元件E（k-1）在時刻t離開熱備份后，元件E（k）將會在時間t+θ轉(zhuǎn)換到熱備份，若當(dāng)需要進行溫備份轉(zhuǎn)換到熱備份時溫備份序列中沒有元件則任務(wù)可能會失敗，當(dāng)所有的元件在固定任務(wù)時間tM之前失效則整個任務(wù)就失敗了。元件E（k）從熱備份模式下替換失效在線元件的時間成本是THO（E（k）），從溫備份模式轉(zhuǎn)換到熱備份模式的時間成本是TWH（E（k）），TwO（E（k））是溫備份直接轉(zhuǎn)換到在線操作模式時間成本，且TWO（E（k））≥TWH（E（k））+THO（E（k））。熱備份模式下的元件單位時間消耗資源SH（E（k））大于溫備份模式下的元件單位時間消耗資源SW（E（k））但小于在線操作模式下的元件單位時間消耗資源SO（E（k）），即SO（E（k））＞SH（E（k））＞SW（E（k））。為了計算方便約定該模型滿足條件[2]：（1）在不同模式下的系統(tǒng)元件的失效時間分布是相同的。（2）對比任務(wù)時間，模式轉(zhuǎn)換時間可以忽略。（3）模式轉(zhuǎn)換機制完美可靠。

2 系統(tǒng)可靠性和費用的計算

2.1 延遲轉(zhuǎn)換冗余備份系統(tǒng)可靠性計算方法

將系統(tǒng)任務(wù)時間tM劃分成個相等時間間隔，Δ=。元件的失效時間分布的累積密度函數(shù)為Fk（t）。元件k在第i個時間間隔內(nèi)失效的概率是pk（i）=Fk（Δ（i+ 1））-Fk（Δi），它在整個任務(wù)時間段內(nèi)的自由離散失效時間可以用pk=（pk（0）pk（m））表示，其中pk（i）=Pr{Tk=Δi}（0≤i≤m）為某個時間間隔內(nèi)的元件失效概率密度[5]。沒有任何元件的操作時間會比任務(wù)時間tM更長，元件k在任務(wù)期間不會失效的概率是pk（m）=Pr{Tk≥tM=m}=因為元件在任務(wù)時間內(nèi)會處于不同的模式，累積暴露模型用近似壽命概念來表示，即元件工作在不同操作模式下的時間乘以定義的各自因子來表示近似壽命。Fk（t）是元件在操作模式下的累積失效時間分布函數(shù)，元件k的累積失效時間分布函數(shù)在溫備份模式下開始，然后轉(zhuǎn)換到熱備份模式，再轉(zhuǎn)換到在線模式是Fk（t*）。任何一個在時刻tH轉(zhuǎn)化到熱備份模式，在時刻to轉(zhuǎn)換到操作模式的元件k，失效時間tF的累積密度函數(shù)是：

2.2 延遲轉(zhuǎn)換冗余備份系統(tǒng)費用計算方法

元件E（1）在時間段0進入在線操作模式，在時間段iF離開在線操作模式的費用為：

在序列s（1），s（2），…，s（K-1）中的一個元件在時間段XK-1離開熱備份，在時段間YK-1離開在線操作模式。元件E（k）應(yīng)該在時間段Xk-1+θ轉(zhuǎn)換到熱備份，第一個元件的初始費用為0。當(dāng)?shù)贓（k）（k＞1）個元件處于溫備份，熱備份和在線模式分別取決于XK-1，YK-1和iF之間的關(guān)系，元件E（k）在操作模式下失效或在XK-1和YK-1時間段內(nèi)失效的費用可以用下式計算：

2.3 可靠性和任務(wù)預(yù)期費用評估方法

元件序列的備份系統(tǒng)的任務(wù)可靠性和預(yù)期費用算法如下所示：

3 粒子群算法組合優(yōu)化過程

3.1 粒子群算法優(yōu)化備份元件組合排序

當(dāng)系統(tǒng)元件是不同的，它們的初始化順序會較大的影響系統(tǒng)的可靠性和預(yù)期任務(wù)成本。對于所要考慮的備份系統(tǒng)的優(yōu)化問題，就是如何在眾多的元件序列中找出最優(yōu)排序的問題。PSO算法是一種迭代算法[6]。PSO算法求解優(yōu)化問題的過程為：第一步是初始化一個粒子的群體，群體中的每個粒子都有開始位置及運動速度，每個粒子的位置表示問題的一個潛在可能解，PSO算法用適應(yīng)度函數(shù)對這些粒子的優(yōu)劣狀況進行評估。如果粒子所在的位置和最優(yōu)解比較近，說明該粒子的狀況就越好。在迭代循環(huán)過程中，粒子群中的粒子根據(jù)自身的經(jīng)驗（粒子當(dāng)前所找到的最好解，稱為個體極值）和自身附近鄰居的經(jīng)驗（其近鄰當(dāng)前所找到的最好解，稱為局部極值）來更新自己的位置和運動速度。當(dāng)粒子移動到新的位置時，新的可能解就產(chǎn)生了。用這種方式，粒子群中粒子的位置不斷更新，最后收斂到問題的最優(yōu)解或近似最優(yōu)解[7]。粒子群算法的流程如下圖所示:

圖1 基本粒子群算法執(zhí)行流程

例如若有粒子群P={p1，p2，…，pM}，該粒子群由M個粒子組成，這里，M叫做粒子群規(guī)模。一個粒子通過其所在的位置和速度來表示。粒子pi的個體極值表示為pbesti，即pbesti是粒子pi當(dāng)前所發(fā)現(xiàn)的最好解。pi的局部極值表示為gi，即gi為粒子pi的近鄰當(dāng)前所發(fā)現(xiàn)的最好解。在粒子群算法中，粒子會以以下公式為依據(jù)來更新自身的速度和位置：

在這里，w是正常數(shù)，叫做慣性權(quán)重，C1，C2也同樣是兩個正常數(shù)，叫做學(xué)習(xí)因子，rand（）是在[0，1]中服從均勻分布的隨機數(shù)[8]。

3.2 粒子群算法優(yōu)化實現(xiàn)技術(shù)

（1）初始化：

粒子群的初始化也即對每個粒子pi（i=1，2，…，M）的位置xi和速度vi進行初始化，每個粒子的初始位置是在問題的解空間內(nèi)隨機產(chǎn)生的，速度的每個分量也是在指定的范圍[-Vmax，Vmax]中隨機獲得的。

（2）適應(yīng)函數(shù)：

在粒子群算法中，適應(yīng)函數(shù)被用來評估粒子的好壞，即被用來評估一個粒子所在的位置與最優(yōu)解相近的程度。適應(yīng)函數(shù)是粒子位置的函數(shù)，粒子的適應(yīng)值是由其所在的位置所決定的，通常適應(yīng)函數(shù)取為目標(biāo)函數(shù)。

（3）參數(shù)設(shè)置：

①群體規(guī)模M。群體規(guī)模M通常在10～50取值。對很多問題而言，取M=20就可以得到很好的結(jié)果。但對于較復(fù)雜的問題群體規(guī)模也試著取的大一些。如取M=100或200。

②粒子群中的最大速度Vmax決定了在每一次迭代中粒子飛行的最大距離。若Vmax比較大，那么粒子將可能飛出最好解；若Vmax比較小，則易于陷入局部最優(yōu)。如何選擇Vmax依賴于所要解決的問題。一般來說，Vmax與搜索空間每一維的變化范圍相關(guān)。如，若每一維的變化范圍為[-50，50]，則可取Vmax=c*50（0．1≤c≤1．0）。

③鄰域規(guī)模k。在使用局部鄰域結(jié)構(gòu)時，需要對鄰域規(guī)模k進行設(shè)置。當(dāng)鄰域規(guī)模為粒子群的規(guī)模M時，則局部鄰域結(jié)構(gòu)成為全局鄰域結(jié)構(gòu)[7]。

④學(xué)習(xí)因子C1，C2。通常取C1=C2=2，也可取其他不同的值，但一般使C1=C2，并在[0，4]中取值。

（4）終止條件：

①迭代次數(shù)達(dá)到預(yù)先指定的最大代數(shù)；

②適應(yīng)函數(shù)的計算次數(shù)達(dá)到預(yù)先指定的最大次數(shù)；

③所有粒子的速度趨近于0；

在上面幾種方法中，常用的方法是預(yù)先指定一個最大迭代次數(shù)和粒子的速度趨近于0[9]。

（5）約束的處理

用PSO算法求解約束優(yōu)化問題，可以參考演化計算中的關(guān)于約束條件處理的一些方法和經(jīng)驗[10]。例如，利用懲罰函數(shù)法將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題。最直接的一種方法是基于保持可行解的方法。該方法對粒子群算法作出以下修改：

①在進行初始化過程中，對所有粒子重復(fù)初始化直到所有的約束條件都滿足；

②當(dāng)計算gi時，僅考慮那些在可行區(qū)域的粒子。

對于所要考慮的備份系統(tǒng)的優(yōu)化元件序列問題也就是找出系統(tǒng)元件的序列

E（1），E（2），…，E（n）和延遲θ在達(dá)到任務(wù)可靠性水平的條件下使系統(tǒng)預(yù)期費用F最低

元件序列和延遲時間的組合表示為一個粒子，組合相近的粒子均勻分布在臨近區(qū)域，每個粒子代表的元件序列的可靠性和任務(wù)成本都可以通過上面的算法計算出來。然后將上面的限制條件重新表示為非限制問題

這里δ是一個足夠大的懲罰系數(shù)。當(dāng)δ=0，問題簡化為一個不受限的預(yù)期任務(wù)成本最小化；當(dāng)δ較大且R*=1問題簡化為可靠性最大化。通過粒子群算法在元件序列代表的初始化粒子群中找出滿足非限制問題的最優(yōu)粒子。

4 實驗及驗證過程

在現(xiàn)實系統(tǒng)中備份元件的數(shù)量不是很多，通常用窮舉法就可以找到最優(yōu)元件排序序列，但是當(dāng)備份元件較多時，排序組合就會過多。所以窮舉法找出可能最優(yōu)序列耗時較長，為了快速定位最優(yōu)排序組合，使用粒子群算法具有較明顯的優(yōu)勢。現(xiàn)在用五個服從威布爾參數(shù)特征的元件案例系統(tǒng)來驗證使用該方法是否簡單有效。元件參數(shù)如下：

表1 系統(tǒng)中元件的各種參數(shù)

當(dāng)設(shè)定從溫備份直接轉(zhuǎn)化到在線操作的轉(zhuǎn)換成本為50時，案例系統(tǒng)的預(yù)期任務(wù)費用和可靠性隨著延遲時間θ變化情況如圖2所示：

圖2 轉(zhuǎn)換延遲θ與R，E之間的函數(shù)關(guān)系

設(shè)置5個延遲時間值分別為0，8，15，30，88，100；則初始化的粒子形式如（1，2，3，4，5，0），（1，2，3，4，5，8），（1，2，3，4，5，15），（5，2，1，3，4，88），（5，2，1，3，4，100）等，要求可靠性高于97%，實驗將初始化規(guī)模設(shè)定為100，初始化相近的粒子分布在附近區(qū)域。終止條件設(shè)定為粒子的速度趨近于0，則粒子群算法在經(jīng)過六次迭代后滿足了設(shè)定條件，每次迭代找到的粒子依次為下表所示：

表2 基本粒子群算法迭代過程

則通過基本粒子群算法找到最佳延遲時間為30，最優(yōu)元件排序序列（5，2，1，3，4）。結(jié)果證明該方法能夠成功有效應(yīng)用，繪出的對應(yīng)費用和可靠性關(guān)系如下圖所示：

圖3 可靠性和預(yù)期任務(wù)成本關(guān)系

根據(jù)圖2可以幫助我們來設(shè)計系統(tǒng)的延遲冗余備份，可以根據(jù)對成本和可靠性需求的要求來分配備份元件。

5 結(jié)語

本文通過使用延遲轉(zhuǎn)換備份元件來提高系統(tǒng)設(shè)計的可靠性和經(jīng)濟性。通過對系統(tǒng)中延遲轉(zhuǎn)換冗余備份模式的分析，我們提出了使用粒子群算法來找出最優(yōu)元件序列和最佳延遲時間，并且通過實例來計算出了混合備份模式下系統(tǒng)的可靠性和預(yù)期成本進行了驗證。通過圖直觀地顯示了系統(tǒng)可靠性跟預(yù)期成本之間的關(guān)系，為系統(tǒng)元件分布和優(yōu)化提供了依據(jù)。

[1]王華偉，高軍．復(fù)雜系統(tǒng)可靠性分析與評估[M]．北京:科學(xué)出版社，2013．

[2]Levitin G，Xing L，Dai Y．Optimal Design of Hybrid Redundant Systems with Delayed Failure-Driven Standby Mode Transfer[J]．IEEE Transactions on Systems，Man and Cybermetics:Systems，2015，10（1）:2168-2216

[3]鄭嚴(yán)．基于智能算法的結(jié)構(gòu)可靠性分析及優(yōu)化設(shè)計研究[D]．西南交通大學(xué)，2012．

[4]徐玉杰．粒子群算法的改進及應(yīng)用[D]．南京師范大學(xué)，2013．

[5]Levitin G，Xing L，Dai Y．Cold vs．Hot Standby Mission Operation Cost Minimization for 1-out-of-N Systems[J]．European Journal of Operational Research，2014，234（1）:155-162．

[6]胡一波．求解約束優(yōu)化問題的幾種智能算法[D]．西安電子科技大學(xué)，2009．

[7]朱福喜，黃競偉，康利山．計算智能[M]．北京:科學(xué)出版社，2010．

[8]艾寧寧．基于混合智能算法求解隨機期望值模型和機會約束規(guī)劃[D]．長安大學(xué)，2012．

[9]趙建華，張陵，孫清．利用粒子群算法的傳感優(yōu)化布置及結(jié)構(gòu)損傷識別研究[J]．西南交通大學(xué)學(xué)報，2015，49（1）:4-5．

[10]黃慧．基于改進粒子群算法的車間作業(yè)排序的優(yōu)化及仿真研究[D]．南京航空航天大學(xué)，2012．

Redundancy Backup Components with Transfer Delay Based on Particle Swarm Algorithm Optimization

HU Chuan-fu，SHI Xiao-hong

（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

The reliability of the system is often used in the design of hybrid redundancy backup strategy,which can improve the reliability of the system．The transformation of warm backup element is usually immediately happened after a last hot backup mode component failure．In the delayed transformation hybrid backup systems,the new component will replace the previous backup components after a certain delay time．The initialize distribution of these components has a great influence on system reliability and task cost．Uses particle swarm optimization（PSO）algorithm for the first time to deal with this kind of system reliability of combinatorial optimization problem and find the optimal combination and the optimal delay time．The element combination through this algorithm processing can efficiently applied to the design of system reliability．

Hybrid Redundancy Backup;Reliability;Task Cost;Particle Swarm Algorithm

1007-1423（2017）11-0031-05

10.3969/j.issn.1007-1423.2017.11.006

胡傳福（1992-），男，安徽安慶人，碩士研究生，研究方向為移動Agent技術(shù)、復(fù)雜系統(tǒng)可靠性評估

2017-02-14

2017-03-15

史小宏（1963-），男，陜西西安人，副教授，碩士，研究方向為移動Agent技術(shù)、復(fù)雜系統(tǒng)可靠性評估