宋洪宇,史小宏

　　(上海海事大學(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ǔ)上使得備用元件的操作成本最小化。

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

　　中圖分類號(hào)：TP302.8文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.10.012

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

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)行下去。常用的冗余類型有熱備份和冷備份［2］，當(dāng)元件處于熱備用模式下的時(shí)候，一旦工作中的元件出現(xiàn)故障，熱備用元件可以提供快速恢復(fù)。為了確保系統(tǒng)能夠隨時(shí)替換出現(xiàn)故障的工作元件，就需要時(shí)刻補(bǔ)充熱備用模式下的元件。由于熱備用中的元件一直處于工作中，這就增加了系統(tǒng)的成本開銷和能源消耗，與此相比，處于冷備用模式下的元件是低成本的，但是當(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)的成本開銷。

　　最后，當(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)開始運(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è)：

　?。?）系統(tǒng)中的元件數(shù)量和類型是固定的；

　?。?）元件之間相互獨(dú)立；

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

　?。?）工作中的元件和備用元件的失效是不可修復(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<m），pk(i)表示備用元件k在第i個(gè)時(shí)間間隔失效的概率。

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

　　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í)間開始到間隔Xk發(fā)生失效時(shí)，向量為Qk=(Qk(0),…,Qk(m))，可知，Qk(i)=Pr{Xk=Δi}。若備用元件s(1)在運(yùn)行時(shí)間開始時(shí)進(jìn)行初始化，便有X1=Ts(1)和Q1(i)=ps(1)(0≤i≤m)。熱備用模式下的冗余元件在運(yùn)行時(shí)間開始時(shí)便進(jìn)行初始化，可知Xk=max(Xk－1,Th(k))，那么熱備用模式下的冗余元件可靠性公式為：

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

　　Qk(i)=∑ij=0Pr{Xk－1=Δj}Pr{Th(k)=Δ(i－j)}

　　=∑ij=0Qk－1(z)ph(k)(i－j)（7）

　　Qk(m)=∑m－1j=0Pr{Xk－1=Δj}∑mn=m－jPr{Th(k)=Δn}

　　=∑m－1j=0Qk－1(j)∑mn=m－jph(k)(n)（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)

　　for k=1,…,H

　　set Qk(j)=0(1<=j<=m)

　　C=C+Vh(k)

　　for i=0,…,m;C=C+△*i*w h(k)*p h(k)(i)

　　for z=0,…,m-1

　　for i=0,…,m

　　j = max(z,i)

　　Qk(j)=Qk(j)+Q k-1(z)*p h(k)(i)

　　R=R+Qk(m)

　　for k=H+1,…,N

　　set Qk(j)=0(0<=j<=m)

　　C = C+V h(k)(1-Q k-1(m))+△*m*

　　W h(k)*Q k-1(m)

　　for i 0=0,…,m-1

　　C = C+△*i0*W h(k)*Q k-1(i0)

　　fori=0,…,m

　　j =i +i0

　　if (j>m) j=m

　　C=C+△*(j-i0)*w h(k)*Q k-1(i0)*

　　p h(k)(i)

　　Q k(j)=Q k(j)+Q k-1(i0)*p h(k)(i)

　　R = R + Q k(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)，把遺傳算法引入到蟻群算法迭代中，把遺傳算法每一次父類計(jì)算生成的解當(dāng)成蟻群算法的初始群體，根據(jù)蟻群算法的多次循環(huán)，加快收斂速度，提高求解效率并找到最優(yōu)解［10］。本文采用遺傳算法進(jìn)行遺傳算子操作，生成合適的解作為蟻群算法的初始信息素，利用蟻群算法進(jìn)行螞蟻路徑轉(zhuǎn)移和信息素的更新［11］，獲得最優(yōu)解。

　　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è)體。

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

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

　　X′=eX+(1－e)Y

　　Y′=(1－e)X+eY′（9）

　　其中e∈(0,1)

　?、圩儺愃阕樱捎秒x散突變算子［12］，用特定概率對(duì)父代中每個(gè)個(gè)體進(jìn)行變異，返回突變后的個(gè)體并放入新種群中。

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

　　f-=(fn－fn－1)/∑ni=1fi（10）

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

　?。?）當(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)的花銷最小化。

　　min C s.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ù)成本開銷，當(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)開銷，設(shè)定系統(tǒng)的總運(yùn)行時(shí)間t=300，當(dāng)m=500時(shí)，前面三個(gè)備用元件放置在熱備用模式中，后面三個(gè)備用元件放置在冷備用模式中，那么根據(jù)前面的估算方法就能夠得出系統(tǒng)的任務(wù)成本開銷C=21 476和可靠性R=0.956 2。

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

　　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所示。

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

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

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ù)。

參考文獻(xiàn)

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

　?。?］ 黎邵平,李錫文.雙機(jī)熱冗余控制系統(tǒng)的可靠性分析［J］.自動(dòng)化技術(shù)與應(yīng)用，2006,25(12):18-20.

　?。?］ 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.

　?。?］ 楊博文,趙海,劉飛,等.基于可靠度的導(dǎo)彈維修備件需求評(píng)估方法研究［J］.微型機(jī)與應(yīng)用,2011,30(4):94-96.

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

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

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

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

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

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

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