基于粒子群算法的延遲轉換備份元件優化排序

胡傳福，史小宏

（上海海事大學信息工程學院，上海 201306）

基于粒子群算法的延遲轉換備份元件優化排序

胡傳福，史小宏

（上海海事大學信息工程學院，上海 201306）

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

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

0 引言

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

1 延遲轉換混合冗余備份模型

混合冗余備份系統由N個獨立元件組成，元件E（1）在系統啟動時就進入在線操作模式，其他備份元件處于溫備份模式，溫備份模式中的元件按照序列E（2）…E（n）轉換到熱備份，當溫備份模式中有元件存在且熱備份模式中已經有θ時間內元件個數為0時，溫備份元件將轉換到熱備份。即備份元件序列E（2）…E（k-1）已經離開溫備份模式，元件E（k-1）在時刻t離開熱備份后，元件E（k）將會在時間t+θ轉換到熱備份，若當需要進行溫備份轉換到熱備份時溫備份序列中沒有元件則任務可能會失敗，當所有的元件在固定任務時間tM之前失效則整個任務就失敗了。元件E（k）從熱備份模式下替換失效在線元件的時間成本是THO（E（k）），從溫備份模式轉換到熱備份模式的時間成本是TWH（E（k）），TwO（E（k））是溫備份直接轉換到在線操作模式時間成本，且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）在不同模式下的系統元件的失效時間分布是相同的。（2）對比任務時間，模式轉換時間可以忽略。（3）模式轉換機制完美可靠。

2 系統可靠性和費用的計算

2.1 延遲轉換冗余備份系統可靠性計算方法

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

2.2 延遲轉換冗余備份系統費用計算方法

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

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

2.3 可靠性和任務預期費用評估方法

元件序列的備份系統的任務可靠性和預期費用算法如下所示：

3 粒子群算法組合優化過程

3.1 粒子群算法優化備份元件組合排序

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

圖1 基本粒子群算法執行流程

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

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

3.2 粒子群算法優化實現技術

（1）初始化：

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

（2）適應函數：

在粒子群算法中，適應函數被用來評估粒子的好壞，即被用來評估一個粒子所在的位置與最優解相近的程度。適應函數是粒子位置的函數，粒子的適應值是由其所在的位置所決定的，通常適應函數取為目標函數。

（3）參數設置：

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

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

③鄰域規模k。在使用局部鄰域結構時，需要對鄰域規模k進行設置。當鄰域規模為粒子群的規模M時，則局部鄰域結構成為全局鄰域結構[7]。

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

（4）終止條件：

①迭代次數達到預先指定的最大代數；

②適應函數的計算次數達到預先指定的最大次數；

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

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

（5）約束的處理

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

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

②當計算gi時，僅考慮那些在可行區域的粒子。

對于所要考慮的備份系統的優化元件序列問題也就是找出系統元件的序列

E（1），E（2），…，E（n）和延遲θ在達到任務可靠性水平的條件下使系統預期費用F最低

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

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

4 實驗及驗證過程

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

表1 系統中元件的各種參數

當設定從溫備份直接轉化到在線操作的轉換成本為50時，案例系統的預期任務費用和可靠性隨著延遲時間θ變化情況如圖2所示：

圖2 轉換延遲θ與R，E之間的函數關系

設置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%，實驗將初始化規模設定為100，初始化相近的粒子分布在附近區域。終止條件設定為粒子的速度趨近于0，則粒子群算法在經過六次迭代后滿足了設定條件，每次迭代找到的粒子依次為下表所示：

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

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

圖3 可靠性和預期任務成本關系

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

5 結語

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

[1]王華偉，高軍．復雜系統可靠性分析與評估[M]．北京:科學出版社，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]鄭嚴．基于智能算法的結構可靠性分析及優化設計研究[D]．西南交通大學，2012．

[4]徐玉杰．粒子群算法的改進及應用[D]．南京師范大學，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]胡一波．求解約束優化問題的幾種智能算法[D]．西安電子科技大學，2009．

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

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

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

[10]黃慧．基于改進粒子群算法的車間作業排序的優化及仿真研究[D]．南京航空航天大學，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技術、復雜系統可靠性評估

2017-02-14

2017-03-15

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