付 林, 史小宏

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

復(fù)雜多態(tài)系統(tǒng)的冗余備份元件優(yōu)化①

付 林, 史小宏

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

在復(fù)雜的多態(tài)系統(tǒng)中, 系統(tǒng)可靠性非常重要, 最常見(jiàn)的是冷熱備份模式來(lái)實(shí)現(xiàn)系統(tǒng)的可靠性. 本文中我們提出了混合冗余備份模式, 計(jì)算復(fù)雜系統(tǒng)的可靠性和任務(wù)成本, 解決復(fù)雜系統(tǒng)中的備份元件優(yōu)化分布和初始化問(wèn)題. 本文主要是通過(guò)離散數(shù)學(xué)的概率分布計(jì)算復(fù)雜系統(tǒng)中元件的可靠性和任務(wù)成本, 利用量子遺傳算法來(lái)解決冗余備份元件的優(yōu)化分布問(wèn)題. 最后同時(shí)通過(guò)仿真實(shí)驗(yàn)來(lái)計(jì)算出系統(tǒng)的可靠性和預(yù)期的任務(wù)成本,以及冗余備分元件的優(yōu)化分布, 得出了復(fù)雜系統(tǒng)可靠性與成本的平衡關(guān)系.

冗余備份; 冷熱備份; 量子遺傳算法; 可靠性; 任務(wù)成本

1 引言

傳統(tǒng)類(lèi)型的冗余備份主要是利用元件備份來(lái)做系統(tǒng)可靠性保障的[1], 這類(lèi)備份只是單純的靠元件的替換來(lái)滿(mǎn)足可靠性要求, 而你沒(méi)有考慮成本損耗問(wèn)題,另外就是冷備份和熱備份[2]. 這類(lèi)備份模式雖然也是利用多余的元件來(lái)做備份, 不過(guò)考慮到了成本損耗問(wèn)題, 沒(méi)有進(jìn)一步的去探討元件的優(yōu)化分對(duì)于系統(tǒng)可靠性和成本的影響. 元件處于熱冗余備份模式下的時(shí)候,當(dāng)有運(yùn)行操作的元件故障的時(shí)候, 可以快速的替換掉故障元件, 從而提供快速恢復(fù), 為了保證能夠隨時(shí)替換出故障的運(yùn)行操作元件, 就需要時(shí)刻補(bǔ)充處于熱備份模式的備用元件, 這就增加了整個(gè)系統(tǒng)的成本開(kāi)支,相比之下, 冷備份模式下的元件, 就不會(huì)有這樣的消耗, 但是冷備份元件替換故障元件的時(shí)候, 需要很長(zhǎng)的恢復(fù)延遲時(shí). 系統(tǒng)中熱備份冗余相關(guān)的成本消耗和系統(tǒng)可靠性高于冷備份冗余元件. 因此需要在可靠性和成本之間做一個(gè)平衡[3]. 一個(gè)好的辦法是可以通過(guò)在同一個(gè)系統(tǒng)中設(shè)計(jì)兩種類(lèi)型的冗余, 即讓一部分備用元件處于熱備份模式下, 讓大多數(shù)備份元件處于冷備份模式下可以減少維護(hù)成本, 同時(shí)熱冗余備份元件又可以保證一定的系統(tǒng)可靠性, 最后對(duì)系統(tǒng)的可靠性和成本的需求不同, 冷熱備份模式中系統(tǒng)元素的分布和備用元素啟動(dòng)的順序會(huì)嚴(yán)重影響系統(tǒng)的可靠性以及任務(wù)的成本[4]. 冷和熱備份中元件的分布以及初始化序列的選擇可以使得系統(tǒng)滿(mǎn)足一定的可靠性同時(shí)成本最小化, 在本文中我們將使用可靠性和預(yù)期成本算法計(jì)算復(fù)雜系統(tǒng)的可靠性和預(yù)期任務(wù)成本, 利用冗余元件來(lái)滿(mǎn)足系統(tǒng)可靠性的同時(shí), 計(jì)算系統(tǒng)的任務(wù)成本,同時(shí)在文中我們使用量子遺傳算法去優(yōu)化系統(tǒng)中備份元件的初始化順序, 研究冗余元件在系統(tǒng)中的分布不同對(duì)系統(tǒng)的可靠性和成本的影響, 從而在滿(mǎn)足一定的可靠性基礎(chǔ)上計(jì)算系統(tǒng)的可靠行和成本, 并找出對(duì)應(yīng)的備份元素的初始化順序.

2 元件的混合冗余備份模型

假設(shè)系統(tǒng)中有N個(gè)元件h( 1),h(2),...,h(N), 假定最開(kāi)始的H個(gè)元件是處于熱備份模式下, 因此在任務(wù)開(kāi)始的時(shí)候元件h(1),h(2),...,h(H)就開(kāi)始初始化了, 剩下的N-H個(gè)元件h(H+1),...,h(N)處于冷備份模式下,所有處于熱備份模式下的元件在任務(wù)開(kāi)始的時(shí)候就被初始化了, 當(dāng)處于操作狀態(tài)的元件故障后熱備份模式下的一個(gè)元件就會(huì)替換掉故障的元件, 當(dāng)所有熱備份模式下的備用元件都替換完之后, 緊接著就將冷備份模式中的元件初始化, 如果所有元件在任務(wù)結(jié)束時(shí)間之前都故障了, 那么整個(gè)系統(tǒng)任務(wù)就失敗了.

為了計(jì)算系統(tǒng)的可靠性我們做出如下假設(shè)[5]:

1) 系統(tǒng)中的各個(gè)元件是相互獨(dú)立的

2) 在替故障元件到系統(tǒng)恢復(fù)這段時(shí)延跟整個(gè)任務(wù)時(shí)間相比可以忽略不計(jì)

3) 由于熱備份模式下的元件壓力跟操作狀態(tài)下一樣, 所以維護(hù)成本用操作成本來(lái)計(jì)算

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

5) 系統(tǒng)和元件故障是不可修復(fù)的

2.1 操作時(shí)間段內(nèi)的故障元件的概率計(jì)算

我們假設(shè)系統(tǒng)的任務(wù)時(shí)間是t, 將任務(wù)時(shí)間t劃分成m個(gè)相等的時(shí)間間隔, 每個(gè)時(shí)間間隔是Δ=t /m, 元件j在第i時(shí)間間隔故障的概率分布函數(shù)pj(i)可以通過(guò)累計(jì)故障分布函數(shù)Fj(t)來(lái)獲得, 其中第i時(shí)間間隔為Δi=Δ(i+1)-Δ(i), 對(duì)應(yīng)的累計(jì)分布函數(shù)為Fj(Δ(i+1))-Fj(Δi)

對(duì)于元件故障時(shí)間分布滿(mǎn)足故障指數(shù)為λj的指數(shù)分布的時(shí)候, 則元件j的故障累積時(shí)間分布函數(shù)就可以用下面公式表示:

對(duì)應(yīng)的元件j在第i時(shí)間間隔故障的概率分布函數(shù)pj(i)就可以通過(guò)對(duì)分布函數(shù)求導(dǎo)得到, 如下式:

對(duì)應(yīng)的比例參數(shù)αj和形狀參數(shù)βj的威布爾分布函數(shù)和概率密度函數(shù)為:

在我們的系統(tǒng)模型中元件的故障時(shí)間分布式離散的而不是連續(xù)的, 那么整個(gè)任務(wù)時(shí)間段內(nèi)元件j的離散時(shí)間可以Tj就可以用向量Pj=(pj(0),...,pj(m))來(lái)表示, 其中pj(i) =Pr{Tj=Δi} 是時(shí)間間隔為Δi(0≤i≤m)的故障概率. 因?yàn)闆](méi)有元件的操作時(shí)間比總的任務(wù)時(shí)間t要長(zhǎng), 因此元件j在時(shí)間內(nèi)不出現(xiàn)故障的概率pj(m)=Pr{Tj≥t=Δm}, 就可以表示為

2.2 系統(tǒng)元件的故障時(shí)間分布計(jì)算

對(duì)于任意一組給定的元件序列h( 1),h(2),...,h(N),我假定最開(kāi)始的H個(gè)元件是處于熱備份模式下, 因此在任務(wù)開(kāi)始的時(shí)候元件h(1),h(2),...,h(H)就開(kāi)始初始化了, 剩下的N-H個(gè)元件處于冷備份模式下. 對(duì)于任意一個(gè)j＞H處于冷備份的元件在系統(tǒng)中j-1個(gè)元件出故障的時(shí)候開(kāi)始初始化,h(j)該元件在系統(tǒng)中初始化的索引序列. 那么系統(tǒng)中第j個(gè)在任務(wù)開(kāi)始到時(shí)間Xj出現(xiàn)故障就可以表示為向量Qj=(Qj(0),...,Qj(m)), 其中Qj(i)=Pr{Xj=Δi} . 那么元件h(1)在時(shí)間任務(wù)開(kāi)始的時(shí)候初始化, 就有X1=Th(1)和Q1(i)=ph(1)(0≤i≤m). 所有的熱備份下的元件都是在任務(wù)開(kāi)始的時(shí)候初始化的, 因此熱備份模式下的元件有Xj=max(Xj-1,Th(j)), 進(jìn)而獲得可靠性如下:

對(duì)于冷備份下的元件, 要等到熱備份下的元件都出現(xiàn)故障后才會(huì)去初始化, 因此有Xj=Xj-1+Th(1),進(jìn)而獲得冷備份下元件的可靠性如下:

2.3 可靠性與預(yù)期任務(wù)成本計(jì)算算法

3 量子遺傳算法優(yōu)化元件分布與初始化序列

3.1 量子遺傳算法的思想

系統(tǒng)的元件的分布與初始化序列優(yōu)化問(wèn)題是一個(gè)復(fù)雜的組合優(yōu)化問(wèn)題[6], 有N*N!個(gè)可能的解決方法, 要去詳盡的檢測(cè)每一種可能來(lái)確定一個(gè)相對(duì)最優(yōu)的方法是不可能, 傳統(tǒng)的啟發(fā)式算法計(jì)算量比較復(fù)雜并且得到的解的誤差比較大[7], 利用遺傳算法來(lái)搜尋的時(shí)候不用去考慮下一步的搜尋方向來(lái)找到一個(gè)最優(yōu)的解.

遺傳算法來(lái)自于生物進(jìn)化論, 通過(guò)模擬自然界的生物進(jìn)化, 用編碼串也就是生物進(jìn)化里面的“染色體”對(duì)問(wèn)題進(jìn)行優(yōu)化. 將問(wèn)題的所有的解的集合在一起,形成一個(gè)種群, 利用選擇, 交叉, 變異對(duì)種群的解進(jìn)行優(yōu)化, 每個(gè)染色體都對(duì)應(yīng)有一個(gè)解值. 采用用遺傳算法解決問(wèn)題時(shí), 需要確定以下幾個(gè)要素[8,9]:

1) 通過(guò)對(duì)染色體上的基因進(jìn)行編碼將問(wèn)題的解體現(xiàn)出來(lái)確定染色體的編碼.

2) 將適應(yīng)度高的個(gè)體遺傳到下一代群體當(dāng)中去建立個(gè)體的適應(yīng)度函數(shù).

3) 初始化種群.

4) 對(duì)基因進(jìn)行復(fù)制, 交叉, 變異等遺傳操作產(chǎn)生下一代群體, 確定遺傳算子.

5) 確定群體規(guī)模, 終止進(jìn)化代數(shù), 交叉率pc, 變異概率pm.

量子遺傳算法是將量子計(jì)算和遺傳算法結(jié)合起來(lái).對(duì)比傳統(tǒng)的遺傳算法和量子遺傳算法, 研究人員發(fā)現(xiàn)量子遺傳算法能夠種群規(guī)模很小的情況下, 用很小的代價(jià)找出相關(guān)問(wèn)題的最優(yōu)解[10]. 量子遺傳算法采用的編碼方式與傳統(tǒng)的遺傳算法編碼方法有很大的不同,量子遺傳算法利用量子位染色體編碼, 而且利用量子門(mén)來(lái)完成種群的更新, 從而產(chǎn)生新的最優(yōu)種群[11], 這里就是找到最優(yōu)的解集.

3.2 量子遺傳算法的優(yōu)化過(guò)程

第一步: 用量子比特表示最小的信息單元. 一個(gè)量子比特的狀態(tài)可表示為在量子遺傳算法中第t代染色體種群可以表示為Q(t)=[q1(t),q2(t),...,qn(t)], 其中,

第二步: 量子算子的定義, 選擇算子: 采用跟遺傳算法類(lèi)似的輪盤(pán)賭來(lái)確定遺傳算子. 變異算子: 在量子遺傳算法中通過(guò)量子旋轉(zhuǎn)門(mén)的旋轉(zhuǎn)角來(lái)表示量子染色體中的變異操作, 下面的式子是本文用到的量子變異算子[12].

交叉算子: 在量子遺傳算法中采用量子的相干性的特性進(jìn)行全干擾交叉操作[13], 使得種群中的個(gè)體都能夠參與到進(jìn)化中而不是局部的進(jìn)化. 以種群規(guī)模為5計(jì)算, 染色體的長(zhǎng)度為5計(jì)算, 用A, B, C, D, E表示交叉后獲得的新的染色體如表1所示.

表1 全干擾交叉

所謂的元素分布與優(yōu)化問(wèn)題就是找出一組元素初始化列, 使得在滿(mǎn)足一定的可靠性級(jí)別R*的時(shí)候系統(tǒng)的成本最小[14].

對(duì)于任何染色體代表的元件的初始化順序, 我們可以找出處于熱備份模式和冷備份模式下的元件, 利用利用上面的求可靠性和任務(wù)成本的算法, 我們可以求出系統(tǒng)中元件處于該順序的時(shí)候的可靠性R和預(yù)期的任務(wù)成本C, 這樣的話我們?cè)倮霉?8), 我們可以定義一個(gè)值,式中M是一個(gè)足夠大的整數(shù), 我們可以利用這個(gè)公式解決系統(tǒng)的優(yōu)化問(wèn)題, 當(dāng)σ=0的時(shí)候, 就可以求出最小任務(wù)成本, 當(dāng)σ比較大而R*=1的時(shí)候, 問(wèn)題就轉(zhuǎn)化為了求系統(tǒng)的最大可靠性問(wèn)題. 在量子遺傳算法的開(kāi)始的時(shí)候用一組0到N的任意數(shù)字代表一組解決方法, 隨機(jī)產(chǎn)生的數(shù)字代表了系統(tǒng)中冗余備份元件的初始化順序, 比如2,3,5,6,1,4這組數(shù)字, 2,3,5就代表了熱備份元件的初始順序, 通過(guò)交叉和變異過(guò)程獲得新的的解決方方法, 根據(jù)求解的方法來(lái)求適應(yīng)度函數(shù)的值, 將得到的初始化順序代入到2.3節(jié)的可靠性和預(yù)期任務(wù)成本算法中去, 計(jì)算這種情況下的可靠性和任務(wù)成本,帶入到公式(8)中去比較求得適應(yīng)度值是否滿(mǎn)足要求,然后操作量子旋轉(zhuǎn)門(mén), 調(diào)整種群的個(gè)體, 獲得新的個(gè)體保留最優(yōu)解, 之道量子遺傳算法跌代到求出一組初始化序列, 并且求得此時(shí)的可靠性滿(mǎn)足公式(8), 量子遺傳算法結(jié)束, 記錄下得到最優(yōu)解情況下的備份元件的初始化序列.

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

4.1 模型計(jì)算結(jié)果與分析

我們可以通過(guò)一個(gè)例子來(lái)驗(yàn)證一下模型, 假設(shè)一個(gè)復(fù)雜系統(tǒng)中含有10個(gè)元件, 我們利用威布爾失效時(shí)間分布模型來(lái)描述系統(tǒng)中元件的故障狀態(tài), 并且在表2中給出了威布爾規(guī)模參數(shù)αj和狀態(tài)參數(shù)βj. 同時(shí)在表2中給出了冷備份和熱備份模式下的元件啟動(dòng)成本, 假設(shè)系統(tǒng)的任務(wù)時(shí)間是t=400, m=500的時(shí)候前五個(gè)元件處于熱備份模式下, 后五個(gè)元件處于冷備份模式下, 這樣我們利用上面的算法就可以計(jì)算出系統(tǒng)的任務(wù)成本C=22656和可靠性R=0.8109.

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

2 100 1.0 2050 5 40 15 3 150 1.1 2150 9 70 13 4 80 1.0 2000 4 50 9 5 110 1.3 2200 6 80 12 6 75 1.0 2050 5 90 10 7 120 1.0 2150 6 70 12 8 130 1.1 2080 9 70 13 9 110 1.0 2150 3 90 9 10 140 1.1 2080 4 60 8

同時(shí)為了研究不同任務(wù)時(shí)間段m對(duì)系統(tǒng)可靠性和成本的影響, 假設(shè)五個(gè)元件處于熱備份模式下, 另外五個(gè)元件處于冷備份模式下, 我們可以通過(guò)圖1看出不同任務(wù)時(shí)間段對(duì)可靠性和成本的影響.

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

4.2 元件分布優(yōu)化與初始化序列結(jié)果與分析

我們假設(shè)系統(tǒng)中有10個(gè)元件, 利用表2中給的參數(shù)和模型中提出的可靠性與成本計(jì)算算法, 利用量子遺傳算法來(lái)優(yōu)化處理, 我們可以得出系統(tǒng)中元件最優(yōu)元素分布隨著遺傳代數(shù)而變化, 最優(yōu)解達(dá)到一個(gè)穩(wěn)定的趨勢(shì)如圖2所示.

圖2 系統(tǒng)中元件的分布隨著遺傳代數(shù)的變化

同時(shí)我們可以求出在滿(mǎn)足不同的可靠性R*的時(shí)候,利用量子遺傳算法計(jì)算出系統(tǒng)的可靠性和預(yù)期任務(wù)成本以及系統(tǒng)中元件的初始化序列如表3所示.

表3 對(duì)于滿(mǎn)足不同的可靠性R*得到的元件序列

最后我們可以得到不同的可靠性與預(yù)期任務(wù)成本的一個(gè)平衡曲線如圖3, 根據(jù)這個(gè)圖可以幫助我們來(lái)設(shè)計(jì)系統(tǒng)的混合冗余備份, 可以根據(jù)對(duì)成本和可靠性需求的要求來(lái)分配備份元件.

圖3 可靠性和預(yù)期任務(wù)成本的平衡

5 結(jié)語(yǔ)

在本文中我們主要解決的是系統(tǒng)元件不可修復(fù)的情況, 通過(guò)對(duì)系統(tǒng)中冗余備份模式的分析, 提出了我們的算法, 并且通過(guò)實(shí)例來(lái)計(jì)算出了混合備份模式下系統(tǒng)的可靠性和預(yù)期成本, 在論文的后半部分利用量子遺傳算法對(duì)系統(tǒng)中元件分布進(jìn)行處理, 找出了在滿(mǎn)足一定可靠性和預(yù)期成本的時(shí)候系統(tǒng)中元件的一組初始化序列, 通過(guò)圖三直觀的顯示了系統(tǒng)可靠性跟預(yù)期成本之間的關(guān)系, 為系統(tǒng)元件分布和優(yōu)化提供了依據(jù).

1 祝春標(biāo).基于多部件的冗余備份計(jì)算機(jī)通信系統(tǒng)分析.信息與電腦:理論版,2010(5).

2 葛晶晶.基于Markov過(guò)程的網(wǎng)絡(luò)控制系統(tǒng)冗余技術(shù)研究[碩士學(xué)位論文].大連:大連理工大學(xué),2014.

3 Levitin G, Xing L, Dai Y. Cold vs. hot standby mission operation cost minimization for 1-out-of-N systems. European Journal of Operational Research, 2014, 234(1): 155–162.

4 黎湘,郁文賢,莊釗文,等.決策層信息融合的神經(jīng)網(wǎng)絡(luò)模型與算法研究.電子學(xué)報(bào),1997,(9):117–120.

5 吳頔.不可修復(fù)如新的多狀態(tài)串聯(lián)系統(tǒng)可靠性分析[碩士學(xué)位論文].武漢:武漢科技大學(xué),2013.

6 許傳玉,朱若男,梁穎紅,等.遺傳算法在復(fù)雜系統(tǒng)可靠性?xún)?yōu)化中的應(yīng)用.哈爾濱理工大學(xué)學(xué)報(bào),2000,5(3):90–93.

7 汪松泉.遺傳算法在組合優(yōu)化中的應(yīng)用研究[碩士學(xué)位論文].合肥:安徽大學(xué),2010.

8 邵軍,程華,徐軍.遺傳算法在結(jié)構(gòu)可靠性?xún)?yōu)化中的應(yīng)用.四川建筑科學(xué)研究,2001,27(2):4-5.

9鄭世玨,陳曉燕,高麗.基于量子遺傳算法的傳感器節(jié)點(diǎn)優(yōu)化部署方法.計(jì)算機(jī)工程與設(shè)計(jì),2008,29(7):1681–1683.

10 周殊,潘煒,羅斌,等.一種基于粒子群優(yōu)化方法的改進(jìn)量子遺傳算法及應(yīng)用.電子學(xué)報(bào),2006,34(5):897–901.

11 周傳華,錢(qián)鋒.基于改進(jìn)量子遺傳算法的小波神經(jīng)網(wǎng)絡(luò)優(yōu)化及其軟測(cè)量應(yīng)用.華東理工大學(xué)學(xué)報(bào):自然科學(xué)版,2008, 34(6):850–853.

12 陳曉燕.基于量子遺傳算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究[碩士學(xué)位論文].武漢:華中師范大學(xué),2009.

13 楊玉,戴紅偉,李存華.量子干擾交叉遺傳算法及其應(yīng)用研究.2011年江蘇省人工智能學(xué)術(shù)會(huì)議,2011.

14 張鐵柱,滕春賢,韓志剛.遺傳算法在系統(tǒng)可靠性?xún)?yōu)化中的應(yīng)用.控制與決策,2002,17(3):378–380.

Optimization of Redundant Backup Components in Complex Polymorphic System

FU Lin, SHI Xiao-Hong
(College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

In the complex polymorphic system, system reliability is very important, and the most common mode to realize the system reliability is the cold and hot backup mode. In this paper we propose a hybrid redundant backup mode, to calculate the reliability of complex systems and task cost, and to solve the problems of optimization distribution and initialization of backup components in complex system. With the probability distribution of discrete mathematics, this paper mainly calculates the reliability and task cost of components in complex system. Then, use quantum genetic algorithm to solve the problem of redundancy backup element optimization distribution. Finally, simulation is implemented to calculate the reliability of the system, the expected task cost, and optimization distribution of redundant backup devices. It concludes the balance relationship between reliability and task cost of complex system.

redundancy backup; cold and hot backup; quantum genetic algorithm; reliability; task cost

2016-03-26;收到修改稿時(shí)間:2016-05-05

10.15888/j.cnki.csa.005497