基于蟻群遺傳算法的冗余備用元件優化研究

宋洪宇,史小宏

(上海海事大學 信息工程學院，上海 201306)

基于蟻群遺傳算法的冗余備用元件優化研究

宋洪宇,史小宏

(上海海事大學 信息工程學院，上海 201306)

為了解決復雜系統的可靠性和任務成本評估問題，提出混合冗余備用系統設計模式。通過概率統計分布方法來計算復雜系統元件的可靠性和任務成本，利用蟻群和遺傳相結合的混合算法來解決備用元件的最優分布問題。最后通過仿真實驗計算出系統的可靠性和任務成本，以及備用元件的優化分布序列，在滿足一定的系統可靠性的基礎上使得備用元件的操作成本最小化。

冗余備用；可靠性；任務成本；蟻群遺傳算法；最優分布

0 引言

復雜系統在工作中時常會出現故障，為了保障其可靠性，其中一個廣泛使用的技術就是冗余備用[1]：一個或多個元件處于工作狀態下，當有一個正在工作的元件出現故障的時候，就會有一個備用元件被激活來替換這個出現故障的元件，保證系統能夠繼續運行下去。常用的冗余類型有熱備份和冷備份[2]，當元件處于熱備用模式下的時候，一旦工作中的元件出現故障，熱備用元件可以提供快速恢復。為了確保系統能夠隨時替換出現故障的工作元件，就需要時刻補充熱備用模式下的元件。由于熱備用中的元件一直處于工作中，這就增加了系統的成本開銷和能源消耗，與此相比，處于冷備用模式下的元件是低成本的，但是當它去替換工作中失效的元件時，需要長時間的恢復延遲。

考慮到冷熱備用各自的優缺點，提出混合冗余備用系統模式，即讓較少的元件處于熱備用模式下，可以隨時快速地替換出現故障的工作元件，讓大部分元件處于冷備用模式下，當熱備用模式下的元件用完后，處于冷備用模式下的元件會轉移到熱備用模式下[3]。這種冗余備用模式不僅保留了熱備用模式快速替換的特點，還大大提高了系統的可靠性，與此同時，處于冷備用模式下的元件運行成本低，又大大降低了系統的成本開銷。

最后，當冗余元件滿足系統可靠性時，使用離散數學的概率分布方法來計算系統可靠性和預期任務成本。冗余備用模式下的元件分布和啟動順序對系統的可靠性和成本會產生嚴重的影響[4]，利用蟻群遺傳混合算法來優化冗余備用模式下的元件，分析備用元件在冗余模型中的不同分配對系統可靠性和預期任務成本的影響，并找出最優元件分布和初始化順序[5]。

1 元件的混合冗余備用模型

假設系統中有N個獨立的備用元件s(1),s(2),…，s(N)，讓H個備用元件處于熱備用模式下，當系統開始運行的時候，對s(1),s(2),…，s(H)進行了初始化，剩下的N-H個備用元件s(H+1),…,s(N)處于冷備用模式下。

當系統中運行的工作元件失效時，處于熱備用模式下的元件會立刻替換失效元件；當熱備用模式下的元件用完后，處于冷備用模式下的元件進行初始化。

為了方便求得系統可靠性，提出一些附加假設：

(1)系統中的元件數量和類型是固定的；

(2)元件之間相互獨立；

(3)和任務時間相比，替換失效元件的時間可以忽略不計；

(4)工作中的元件和備用元件的失效是不可修復的。

1.1 故障元件概率計算

將整個運行時間t分成m個相同的時間單元，即Δ=t/m，備用元件k在第i個時間單元失效的概率為pk(i)，每個備用元件有相同的累計失效分布函數Fk(t)。假設指數分布的時間失效率為λk，那么

Fk(t)=1-exp(-λkt)

(1)

pk(i)=[1-exp(-λkΔ)]exp(-λkΔi)

(2)

根據韋伯分布提供的規模參數ηk以及狀態參數βk，得到的分布函數和概率密度函數公式如下：

Fk(t)=1-exp(-(t/ηk)βk)

(3)

pk(i)=exp{-[Δi/ηk]βk}-exp{-[Δ(i+1)/ηk]βk}

(4)

考慮到備用元件的失效分布時間Tk是離散的而不是連續的，假設Tk的概率質量函數用向量表示為pk={pk(0),…,pk(m)}，pk(i)=Pr{Δi≤Tk<Δ(i+1)}(0≤i

由于系統元件的運行時間不會超過任務時間t，在整個任務結束之前元件k不會失效的概率為：pk(m)=Pr{Tk≥t=Δm}就可以表示為：

(5)

1.2 系統元件的失效時間分布

根據前面給出模型的描述可知，當k=H+1時，說明熱備用模式下的元件已經用完，系統中冷備用模式下的元件在第k-1個元件出現失效時便進行初始化。當系統中第k個備用元件從運行時間開始到間隔Xk發生失效時，向量為Qk=(Qk(0),…,Qk(m))，可知，Qk(i)=Pr{Xk=Δi}。若備用元件s(1)在運行時間開始時進行初始化，便有X1=Ts(1)和Q1(i)=ps(1)(0≤i≤m)。熱備用模式下的冗余元件在運行時間開始時便進行初始化，可知Xk=max(Xk-1,Th(k))，那么熱備用模式下的冗余元件可靠性公式為：

(6)

當熱備用模式下的元件全部使用完或發生失效時，處于冷備用模式下的元件便會進行初始化，可知Xk=Xk-1+Th(1)，冷備用模式下的元件可靠性公式有：

(7)

(8)

1.3 系統可靠性和預期成本計算

根據上面的研究工作，備用元件的系統可靠性和預期成本評估算法如下：

C=R=0,Q0(1)=1,Q0(i)=0(2<=i<=m)

fork=1,…,H

setQk(j)=0(1<=j<=m)

C=C+Vh(k)

fori=0,…,m;C=C+△*i*wh(k)*ph(k)(i)

forz=0,…,m-1

fori=0,…,m

j= max(z,i)

Qk(j)=Qk(j)+Qk-1(z)*ph(k)(i)

R=R+Qk(m)

fork=H+1,…,N

setQk(j)=0(0<=j<=m)

C=C+Vh(k)(1-Qk-1(m))+△*m*

Wh(k)*Qk-1(m)

fori0=0,…,m-1

C=C+△*i0*Wh(k)*Qk-1(i0)

fori=0,…,m

j=i+i0

if (j>m)j=m

C=C+△*(j-i0)*wh(k)*Qk-1(i0)*

ph(k)(i)

Qk(j)=Qk(j)+Qk-1(i0)*ph(k)(i)

R=R+Qk(m)

2 蟻群遺傳算法元件優化

2.1 蟻群遺傳算法的思想

遺傳算法[6]具備全局搜索能力，能夠迅速地搜索出解空間中的全部解，通過其內在并行性進行分布式計算，求解速度明顯加快。缺點是沒有很好地使用系統反饋回來的信息，使搜索產生盲目性，降低了最優解的收斂速度，致使計算最優解效率較低。蟻群算法[7]是一種基于種群的優化算法，它由多只螞蟻共同構建解路徑，該算法根據在解路徑上遺留且互換信息素來實現優化過程，提高了解路徑的效率。擁有正反饋機制，利用信息素的持續變化以及收斂得到優化解。然而，由于缺少初始信息素，因此信息的積累過程比較耗時。

蟻群遺傳算法[8-9]就是把蟻群算法和遺傳算法組合起來，把遺傳算法引入到蟻群算法迭代中，把遺傳算法每一次父類計算生成的解當成蟻群算法的初始群體，根據蟻群算法的多次循環，加快收斂速度，提高求解效率并找到最優解[10]。本文采用遺傳算法進行遺傳算子操作，生成合適的解作為蟻群算法的初始信息素，利用蟻群算法進行螞蟻路徑轉移和信息素的更新[11]，獲得最優解。

圖1 混合算法流程圖

2.2 蟻群遺傳算法的優化過程

(1)定義目標函數和適應度函數，計算每個個體的適應度fi，對種群規模中的個體進行如下遺傳操作，從而產生下一代個體。

①選擇算子，使用遺傳算法中的輪盤賭方法，種群中個體適應度函數值越大，被選擇的機率就越高。

②交叉算子，利用實數編碼，交叉操作使用算術交叉算子，首先隨機確定參與交叉的父代，接著進行兩兩配對，父代中的個體X和Y按照式(9)產生兩個新的個體:

(9)

其中e∈(0,1)

③變異算子，采用離散突變算子[12]，用特定概率對父代中每個個體進行變異，返回突變后的個體并放入新種群中。

(2)反復執行選擇、交叉、變異操作，直至達到遺傳算法結束前提。假定最少循環次數為Nmin，最多循環次數為Nmax，在遺傳算法的迭代過程中計算進化率，公式如下:

(10)

如果持續三次進化速率不大于最小進化速率，則結束遺傳算法的循環，開始執行蟻群算法。

(3)當遺傳算法運行完畢后，將產生的適應度強的后代加入到新組合中。

(4)依據優化解得出吸引強度初始分布，使用蟻群算法信息素的初始值設定方法，求出其信息素初始值τ，有τ=τc+τg，其中τc表示給出的信息素常量，τg表示遺傳算法求得結果轉換的信息素值。

(5)m只螞蟻被放置在它們各自的初始節點上，計算每只螞蟻從i節點移動到j節點的移動概率pm(i,j)，依據移動概率轉移每只螞蟻到下一節點，并且執行信息素局部更新。

(6)判斷所有螞蟻是否已生成整個路徑[13]，若還沒有生成整體路徑則執行步驟(5)，否則，執行步驟(7)。

(7)比較所有的可行解,輸出最優解。

整個過程的流程圖如圖1所示。

由于備用元件的初始化順序強烈地影響著系統的可靠性和預期任務成本，接下來要解決的問題就是找出混合冗余備用元件的最優分布序列，當達到相應可靠性級別R*時，使得系統的花銷最小化。

minCs.t R≥R*

(11)

將備用元件的初始化序列用染色體來表示，尋找存在于熱備用模式和冷備用模式下的冗余元件，根據前面求可靠性和任務成本的計算方法，能夠得出系統中備用元件按照相應順序時的可靠性R和預期任務成本C，接下來再根據公式(11),先設定Ω=M-C-σmin{0,R*-R}，其中M是一個非常大的整數，通過此式來解決系統冗余元件的優化分布問題,當σ=0時，能夠計算出系統最小任務成本開銷，當σ變大且R*=1時，就變成了計算系統元件的最大可靠性問題。

當蟻群遺傳算法進行時，從0～N的隨機數字中選擇一組數據組合作為解決方案，任意生成的集合表示系統中冗余備用元件的初始化序列，例如{3,1,4,6,2,5}這組數字組合，3,1,4表示熱備用冗余元件的初始化序列，利用遺傳算法交叉和變異的手段得到新的解決方案，進而求出適應度函數值，接著把求得的初始化序列放入到上一節的可靠性和任務成本計算方法里，得出這種狀況下的可靠性和預期任務成本，并帶入公式(11)中去判斷得出的適應度函數值是否滿足需求，然后根據蟻群算法信息素的初始值設定方法，求出其信息素初始值并進行信息素局部更新，獲得新的個體保留最優解，直到蟻群遺傳算法計算出一組元件初始化列表，當求出的系統可靠性滿足公式(11)時，蟻群遺傳算法終止，保留最優解情形下的備用元件的初始化列表。

3 仿真結果與分析

3.1 模擬計算結果與分析

本節通過仿真實驗來實現模型，假定一個復雜多態系統中含有6個備用冗余元件，系統中元件的失效狀態能夠使用韋伯失效分布模型來表述，表1提供了韋伯規模參數ηk和狀態參數βk。此外，表1還提供了冷備用和熱備用模式下的冗余元件的啟動開銷，設定系統的總運行時間t=300，當m=500時，前面三個備用元件放置在熱備用模式中，后面三個備用元件放置在冷備用模式中，那么根據前面的估算方法就能夠得出系統的任務成本開銷C=21 476和可靠性R=0.956 2。

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

接下來研究時間單元m對系統可靠性和預期成本的影響，將三個備用元件放置在熱備用模式下，其余三個備用元件放置在冷備用模式下，根據圖2能夠得出不同時間單元對可靠性和預期成本的影響。

圖2 可靠性和任務成本隨時間間隔m的變化

3.2 元件最優分布與初始化順序

設定有8個備用元件存在于系統中，根據表1提供的各種參數以及模型中的可靠性與成本估算方法，采用蟻群遺傳混合算法進行優化處理，能夠獲得系統中備用元件的最優序列分布，并且隨著遺傳迭代的改變，最優解越來越趨于穩定，如圖3所示。

圖3 元件成本遺傳迭代分布

同時能夠求出在達到不同的可靠性級別R*的時候，設置蟻群算法初始值信息素τc為20，遺傳算法進入到蟻群算法的信息素強度值τg為2，螞蟻數量為6，采用蟻群遺傳算法得出復雜系統的可靠性和預期任務成本以及備用元件的初始化序列，如表2所示。

表2 根據不同可靠度R*求出的元件順序

最后得出不同的可靠性與預期任務成本的一個平衡趨勢曲線，如圖4所示。這種平衡趨勢曲線能夠協助復雜系統的混合冗余備用模型的設計，并且可依據對成本和可靠性的需要來分配備用元件。

圖4 可靠性和任務成本平衡曲線

4 結論

本文針對系統中工作的元件遇到故障不可修復的情況，設計了一種混合冗余備用模型，根據概率分布的計算方法，通過仿真實驗來計算得出混合備用模式下系統的可靠性和預期運行成本，提出了基于蟻群遺傳混合算法對系統中冗余備用元件的分布進行處理和優化的方案，找到了在滿足一定可靠性和預期任務成本的條件下，系統中備用元件的一組初始化序列，為系統元件分布和優化提供了依據。

[1] 劉士喜,許志才,方賢文.基于隨機Petri網的冗余備份系統可信賴性研究[J].安徽理工大學學報(自然科學版)，2009,29(3):48-53.

[2] 黎邵平,李錫文.雙機熱冗余控制系統的可靠性分析[J].自動化技術與應用，2006,25(12):18-20.

[3] LEVITIN G,Liu Dongxing,Dai Yuanshun.Reliability and mission cost of 1-out-of N:G systems with state-dependent standby mode transfers[J].IEEE Transactions on Reliability,2015,64(1):454-462.

[4] 楊博文,趙海,劉飛,等.基于可靠度的導彈維修備件需求評估方法研究[J].微型機與應用,2011,30(4):94-96.

[5] 仲彥軍.冷備狀態下具有兩個狀態的由兩個相同部件并聯的可修系統研究[D].烏魯木齊：新疆大學,2006.

[6] 馬書南，帥訓波，曹鳳雪.一種基于逆序算子優化組合遺傳算法[J].電子技術應用,2006，32(6)：19-21.

[7] 程世娟,盧偉,何平.蟻群算法在冗余系統可靠性最優分配上的應用[J].計算機工程與應用，2009，45(15)：64-66.

[8] 申利民.基于遺傳蟻群融合算法的測試用例最小化研究[J].計算機工程，2012，38(16):57-64.

[9] 姜封國.基于混合遺傳算法的隨機結構可靠性優化設計[J].華南理工大學學報,2008，36(1):152-156.

[10] 徐德明.改進的遺傳混合蟻群算法在TSP問題中的應用[J].計算機時代，2012(11)：1-64.

[11] 楊劍峰.基于遺傳算法和螞蟻算法求解函數優化問題[J].浙江大學學報，2007,41(3):427-430.

[12] 劉立東,蔡淮.融入遺傳算法的混合蟻群算法[J].計算機工程與設計，2008,29(5)：1248-1250.

[13] 張青鳳.遺傳算法在最優化問題中的應用研究[J].山西師范大學學報(自然科學版)，2014,28(1)：38-42.

Research on redundant spare element optimization based on ant colony and genetic algorithm

Song Hongyu，Shi Xiaohong

(Information Engineering College,Shanghai Maritime University,Shanghai 201306,China )

In order to solve the problem of complex system reliability and mission cost evaluation,a hybrid redundant backup system model is proposed.The components’s reliability and mission cost of complex system are calculated by the probability distribution method of discrete mathematics,and the optimal distribution of spare components is solved by the hybrid algorithm with ant colony and genetic algorithm.Finally,the reliability and mission cost of the system and the optimal distribution of the spare components are calculated by the simulation experiment.The reliability of the system is improved on the basis of minimizing the operation cost.

redundant backup;reliability;mission cost;ant colony and genetic algorithm;optimal distribution

TP302.8

A

10.19358/j.issn.1674- 7720.2017.10.012

宋洪宇,史小宏.基于蟻群遺傳算法的冗余備用元件優化研究[J].微型機與應用，2017,36(10)：40-43，47.

2016-11-30)

宋洪宇，(1991-)，男，碩士，主要研究方向：移動Agent技術、復雜系統可靠性評估。

史小宏，(1963-)，男,副教授，主要研究方向：移動Agent技術、復雜系統可靠性評估。