宋洪宇,史小宏

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

基于蟻群遺傳算法的冗余備用元件優(yōu)化研究

宋洪宇,史小宏

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

為了解決復(fù)雜系統(tǒng)的可靠性和任務(wù)成本評(píng)估問(wèn)題，提出混合冗余備用系統(tǒng)設(shè)計(jì)模式。通過(guò)概率統(tǒng)計(jì)分布方法來(lái)計(jì)算復(fù)雜系統(tǒng)元件的可靠性和任務(wù)成本，利用蟻群和遺傳相結(jié)合的混合算法來(lái)解決備用元件的最優(yōu)分布問(wèn)題。最后通過(guò)仿真實(shí)驗(yàn)計(jì)算出系統(tǒng)的可靠性和任務(wù)成本，以及備用元件的優(yōu)化分布序列，在滿足一定的系統(tǒng)可靠性的基礎(chǔ)上使得備用元件的操作成本最小化。

冗余備用；可靠性；任務(wù)成本；蟻群遺傳算法；最優(yōu)分布

0 引言

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

考慮到冷熱備用各自的優(yōu)缺點(diǎn)，提出混合冗余備用系統(tǒng)模式，即讓較少的元件處于熱備用模式下，可以隨時(shí)快速地替換出現(xiàn)故障的工作元件，讓大部分元件處于冷備用模式下，當(dāng)熱備用模式下的元件用完后，處于冷備用模式下的元件會(huì)轉(zhuǎn)移到熱備用模式下[3]。這種冗余備用模式不僅保留了熱備用模式快速替換的特點(diǎn)，還大大提高了系統(tǒng)的可靠性，與此同時(shí)，處于冷備用模式下的元件運(yùn)行成本低，又大大降低了系統(tǒng)的成本開(kāi)銷(xiāo)。

最后，當(dāng)冗余元件滿足系統(tǒng)可靠性時(shí)，使用離散數(shù)學(xué)的概率分布方法來(lái)計(jì)算系統(tǒng)可靠性和預(yù)期任務(wù)成本。冗余備用模式下的元件分布和啟動(dòng)順序?qū)ο到y(tǒng)的可靠性和成本會(huì)產(chǎn)生嚴(yán)重的影響[4]，利用蟻群遺傳混合算法來(lái)優(yōu)化冗余備用模式下的元件，分析備用元件在冗余模型中的不同分配對(duì)系統(tǒng)可靠性和預(yù)期任務(wù)成本的影響，并找出最優(yōu)元件分布和初始化順序[5]。

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

假設(shè)系統(tǒng)中有N個(gè)獨(dú)立的備用元件s(1),s(2),…，s(N)，讓H個(gè)備用元件處于熱備用模式下，當(dāng)系統(tǒng)開(kāi)始運(yùn)行的時(shí)候，對(duì)s(1),s(2),…，s(H)進(jìn)行了初始化，剩下的N-H個(gè)備用元件s(H+1),…,s(N)處于冷備用模式下。

當(dāng)系統(tǒng)中運(yùn)行的工作元件失效時(shí)，處于熱備用模式下的元件會(huì)立刻替換失效元件；當(dāng)熱備用模式下的元件用完后，處于冷備用模式下的元件進(jìn)行初始化。

為了方便求得系統(tǒng)可靠性，提出一些附加假設(shè)：

(1)系統(tǒng)中的元件數(shù)量和類(lèi)型是固定的；

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

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

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

1.1 故障元件概率計(jì)算

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

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

(1)

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

(2)

根據(jù)韋伯分布提供的規(guī)模參數(shù)ηk以及狀態(tài)參數(shù)βk，得到的分布函數(shù)和概率密度函數(shù)公式如下：

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

(3)

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

(4)

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

由于系統(tǒng)元件的運(yùn)行時(shí)間不會(huì)超過(guò)任務(wù)時(shí)間t，在整個(gè)任務(wù)結(jié)束之前元件k不會(huì)失效的概率為：pk(m)=Pr{Tk≥t=Δm}就可以表示為：

(5)

1.2 系統(tǒng)元件的失效時(shí)間分布

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

(6)

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

(7)

(8)

1.3 系統(tǒng)可靠性和預(yù)期成本計(jì)算

根據(jù)上面的研究工作，備用元件的系統(tǒng)可靠性和預(yù)期成本評(píng)估算法如下：

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 蟻群遺傳算法元件優(yōu)化

2.1 蟻群遺傳算法的思想

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

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

圖1 混合算法流程圖

2.2 蟻群遺傳算法的優(yōu)化過(guò)程

(1)定義目標(biāo)函數(shù)和適應(yīng)度函數(shù)，計(jì)算每個(gè)個(gè)體的適應(yīng)度f(wàn)i，對(duì)種群規(guī)模中的個(gè)體進(jìn)行如下遺傳操作，從而產(chǎn)生下一代個(gè)體。

①選擇算子，使用遺傳算法中的輪盤(pán)賭方法，種群中個(gè)體適應(yīng)度函數(shù)值越大，被選擇的機(jī)率就越高。

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

(9)

其中e∈(0,1)

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

(2)反復(fù)執(zhí)行選擇、交叉、變異操作，直至達(dá)到遺傳算法結(jié)束前提。假定最少循環(huán)次數(shù)為Nmin，最多循環(huán)次數(shù)為Nmax，在遺傳算法的迭代過(guò)程中計(jì)算進(jìn)化率，公式如下:

(10)

如果持續(xù)三次進(jìn)化速率不大于最小進(jìn)化速率，則結(jié)束遺傳算法的循環(huán)，開(kāi)始執(zhí)行蟻群算法。

(3)當(dāng)遺傳算法運(yùn)行完畢后，將產(chǎn)生的適應(yīng)度強(qiáng)的后代加入到新組合中。

(4)依據(jù)優(yōu)化解得出吸引強(qiáng)度初始分布，使用蟻群算法信息素的初始值設(shè)定方法，求出其信息素初始值τ，有τ=τc+τg，其中τc表示給出的信息素常量，τg表示遺傳算法求得結(jié)果轉(zhuǎn)換的信息素值。

(5)m只螞蟻被放置在它們各自的初始節(jié)點(diǎn)上，計(jì)算每只螞蟻從i節(jié)點(diǎn)移動(dòng)到j(luò)節(jié)點(diǎn)的移動(dòng)概率pm(i,j)，依據(jù)移動(dòng)概率轉(zhuǎn)移每只螞蟻到下一節(jié)點(diǎn)，并且執(zhí)行信息素局部更新。

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

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

整個(gè)過(guò)程的流程圖如圖1所示。

由于備用元件的初始化順序強(qiáng)烈地影響著系統(tǒng)的可靠性和預(yù)期任務(wù)成本，接下來(lái)要解決的問(wèn)題就是找出混合冗余備用元件的最優(yōu)分布序列，當(dāng)達(dá)到相應(yīng)可靠性級(jí)別R*時(shí)，使得系統(tǒng)的花銷(xiāo)最小化。

minCs.t R≥R*

(11)

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

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

3 仿真結(jié)果與分析

3.1 模擬計(jì)算結(jié)果與分析

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

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

接下來(lái)研究時(shí)間單元m對(duì)系統(tǒng)可靠性和預(yù)期成本的影響，將三個(gè)備用元件放置在熱備用模式下，其余三個(gè)備用元件放置在冷備用模式下，根據(jù)圖2能夠得出不同時(shí)間單元對(duì)可靠性和預(yù)期成本的影響。

圖2 可靠性和任務(wù)成本隨時(shí)間間隔m的變化

3.2 元件最優(yōu)分布與初始化順序

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

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

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

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

最后得出不同的可靠性與預(yù)期任務(wù)成本的一個(gè)平衡趨勢(shì)曲線，如圖4所示。這種平衡趨勢(shì)曲線能夠協(xié)助復(fù)雜系統(tǒng)的混合冗余備用模型的設(shè)計(jì)，并且可依據(jù)對(duì)成本和可靠性的需要來(lái)分配備用元件。

圖4 可靠性和任務(wù)成本平衡曲線

4 結(jié)論

本文針對(duì)系統(tǒng)中工作的元件遇到故障不可修復(fù)的情況，設(shè)計(jì)了一種混合冗余備用模型，根據(jù)概率分布的計(jì)算方法，通過(guò)仿真實(shí)驗(yàn)來(lái)計(jì)算得出混合備用模式下系統(tǒng)的可靠性和預(yù)期運(yùn)行成本，提出了基于蟻群遺傳混合算法對(duì)系統(tǒng)中冗余備用元件的分布進(jìn)行處理和優(yōu)化的方案，找到了在滿足一定可靠性和預(yù)期任務(wù)成本的條件下，系統(tǒng)中備用元件的一組初始化序列，為系統(tǒng)元件分布和優(yōu)化提供了依據(jù)。

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

[2] 黎邵平,李錫文.雙機(jī)熱冗余控制系統(tǒng)的可靠性分析[J].自動(dòng)化技術(shù)與應(yīng)用，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] 楊博文,趙海,劉飛,等.基于可靠度的導(dǎo)彈維修備件需求評(píng)估方法研究[J].微型機(jī)與應(yīng)用,2011,30(4):94-96.

[5] 仲?gòu)┸?冷備狀態(tài)下具有兩個(gè)狀態(tài)的由兩個(gè)相同部件并聯(lián)的可修系統(tǒng)研究[D].烏魯木齊：新疆大學(xué),2006.

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

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

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

[9] 姜封國(guó).基于混合遺傳算法的隨機(jī)結(jié)構(gòu)可靠性優(yōu)化設(shè)計(jì)[J].華南理工大學(xué)學(xué)報(bào),2008，36(1):152-156.

[10] 徐德明.改進(jìn)的遺傳混合蟻群算法在TSP問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)時(shí)代，2012(11)：1-64.

[11] 楊劍峰.基于遺傳算法和螞蟻算法求解函數(shù)優(yōu)化問(wèn)題[J].浙江大學(xué)學(xué)報(bào)，2007,41(3):427-430.

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

[13] 張青鳳.遺傳算法在最優(yōu)化問(wèn)題中的應(yīng)用研究[J].山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，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

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

2016-11-30)

宋洪宇，(1991-)，男，碩士，主要研究方向：移動(dòng)Agent技術(shù)、復(fù)雜系統(tǒng)可靠性評(píng)估。

史小宏，(1963-)，男,副教授，主要研究方向：移動(dòng)Agent技術(shù)、復(fù)雜系統(tǒng)可靠性評(píng)估。