冗余及監(jiān)控混合策略的優(yōu)化配置算法研究

何　盼　譚　春　袁　月　吳開貴

1(中國科學(xué)院重慶綠色智能技術(shù)研究院　重慶　400714)

2　　　(重慶大學(xué)計算機學(xué)院　重慶　400044)

(hepan@cigit.ac.cn)

?

冗余及監(jiān)控混合策略的優(yōu)化配置算法研究

何盼1譚春1袁月1吳開貴2

1(中國科學(xué)院重慶綠色智能技術(shù)研究院重慶400714)

2(重慶大學(xué)計算機學(xué)院重慶400044)

(hepan@cigit.ac.cn)

Optimal Resources Allocation Algorithm for Optional Redundancy and Monitoring Strategies

He Pan1, Tan Chun1, Yuan Yue1, and Wu Kaigui2

1(ChongqingInstituteofGreenandIntelligentTechnology,ChineseAcademyofScience,Chongqing400714)

2(CollegeofComputerScience,ChongqingUniversity,Chongqing400044)

AbstractIn big data environment, the use of optional redundancy and monitoring strategy in one system increases the usage of resource and causes state space expansion for optimal resources allocation model. The performance of existing evolutionary search algorithms should be improved for the solution space formed by both integer and non-integer variables. To improve the algorithm efficiency, a memetic algorithm based on triple element array is proposed on the analysis of search neighborhood. First of all, the impact of change of variables such as monitoring rate on the system reliability increase is analyzed and then changing-length neighbor generation method is proposed for monitoring rate on neighbor analysis. The neighbor generation method is also proposed for strategy options considering the relations between components. After that, local search operator is refined through the iterative search among components, which increases the search range while maintaining the local advantage of individuals. This operator is used for improving the whole framework of memetic algorithm. Experiment results indicates that this algorithm can be used to get the solution of strategy option of each component and the corresponding optimized parameters for multiple optional strategies. Compared with existing multi-strategy search algorithms, the improved memetic algorithm could get better resources allocation results under the same reliability constraint. The local search operator does not have great impact on the stability of the whole algorithm.

Key wordsredundancy allocation; monitoring resources allocation; reliability optimization; memetic algorithm; sensitivity analysis

摘要大數(shù)據(jù)環(huán)境中監(jiān)控和冗余混合策略的采用引起資源優(yōu)化配置模型的狀態(tài)空間膨脹，進(jìn)化搜索算法在整型與非整型變量結(jié)合的解空間中的搜索效率有待提高，為此提出了基于搜索鄰域分析的三元組模因算法.在分析了監(jiān)控頻率等參數(shù)變化對組件及系統(tǒng)可靠性增長影響的基礎(chǔ)上，針對監(jiān)控頻率提出了基于變長鄰域的近鄰生成方法，針對策略選項提出了與組件關(guān)聯(lián)的近鄰生成方法.采用模因算法框架并改進(jìn)了局部搜索算子，通過組件間的迭代搜索在保持個體優(yōu)勢的同時增大搜索范圍.該算法能夠用于求解混合策略下的組件保障措施選項及相應(yīng)優(yōu)化配置參數(shù)；與現(xiàn)有多策略搜索算法相比，在相同可靠性約束下，該算法能夠得到消耗更低的資源配置結(jié)果；局部搜索策略對算法穩(wěn)定性未造成明顯影響.

關(guān)鍵詞冗余度分配；監(jiān)控資源分配；可靠性優(yōu)化；模因算法；敏感度分析

大數(shù)據(jù)環(huán)境中系統(tǒng)規(guī)模的增大和復(fù)雜性的提升為系統(tǒng)可靠性保障引入了新的研究焦點.大數(shù)據(jù)存儲及處理系統(tǒng)一般持續(xù)運行時間較長，并且各個組件組成復(fù)雜，通常采用分布式系統(tǒng)架構(gòu)進(jìn)行數(shù)據(jù)運算[1]，單種可靠性保障策略在其中具有一定局限性[2]，系統(tǒng)可能同時出現(xiàn)多種可靠性策略的混合應(yīng)用方式[3-4].但是任一可靠性保障策略的采用和多策略混合都會引起資源消耗增多，而大數(shù)據(jù)環(huán)境下的巨大能源消耗已成為亟待解決的問題[5]，需要從適時節(jié)約資源的角度出發(fā)對每個組件中采用的不同策略及其相應(yīng)參數(shù)進(jìn)行優(yōu)化選擇和替換.雖然已有文獻(xiàn)面向可靠性優(yōu)化建立了混合多種保障策略如不同冗余機制[6-8]、軟件重配置與周期再生[3]、冗余與非完美排錯結(jié)合[4]的資源優(yōu)化配置模型，但均未針對大數(shù)據(jù)環(huán)境下的可靠性保障策略進(jìn)行分析.在分布式計算環(huán)境中，為不中斷系統(tǒng)的正常持續(xù)執(zhí)行，自適應(yīng)策略如監(jiān)控也是常用的系統(tǒng)可靠性維護機制[9].在保留一定積極冗余[10]資源的同時，基于監(jiān)控的動態(tài)替換作為一種常用手段被用于系統(tǒng)可靠性的維護中[11].雖然現(xiàn)有研究提出了監(jiān)控策略優(yōu)化配置[12-13]及冗余與監(jiān)控結(jié)合策略的優(yōu)化模型[14]，但在策略類型及參數(shù)的求解方面仍有一定不足.由于冗余或監(jiān)控策略對系統(tǒng)可靠性影響的不同，資源優(yōu)化配置通常為NP-難非線性優(yōu)化問題，難以采用精確解法進(jìn)行求解[15].而多保障策略的采用將增加優(yōu)化模型中待求解變量的數(shù)量，使解變量的搜索空間呈指數(shù)級增長，增加進(jìn)化算法搜索的難度.所以如何對冗余監(jiān)控混合策略的變量空間進(jìn)行深入分析并提高進(jìn)化算法的搜索效率是本文主要需要解決的難題.

針對2種冗余機制混合的可靠性優(yōu)化模型，Coit[16]采用了0-1整型規(guī)劃方法求解每個組件所采取的冗余方式并得到相應(yīng)的冗余度，Tavakkoli-Moghaddam等人[17]在三元組編碼的基礎(chǔ)上，采用改進(jìn)遺傳算法進(jìn)行求解.以上文獻(xiàn)主要針對單目標(biāo)的冗余配置模型，Chambari等人[18]提出了面向多目標(biāo)的多冗余策略配置優(yōu)化模型，并采用了第2代快速非支配排序方法(NSGA Ⅱ)[19]進(jìn)行個體選擇.其后，Chambari等人[20]和Safari[21]分別采用了模擬退火算法以及基于Max-Min變異算子的遺傳算法求解該多目標(biāo)優(yōu)化問題.以上2種算法中均采用了三元組編碼方式，適用于搜索范圍較大的整型參數(shù)變量，其搜索效果優(yōu)于傳統(tǒng)的遺傳算法.以上2類研究雖然采用了不同的策略配置方式，但都局限于在冗余策略中進(jìn)行選擇，算法未對非整型變量的搜索作詳細(xì)討論.Nourelfath等人[4]考慮冗余與非完美排錯結(jié)合的可靠性優(yōu)化模型，采用劃分空間的進(jìn)化搜索算法搜索近優(yōu)解，其中遺傳算法被用于子空間的劃分，禁忌搜索被用于子空間內(nèi)部的局部搜索.在改進(jìn)了非完美排錯模型的基礎(chǔ)上，Liu等人[22]采用遺傳算法對冗余與非完美排錯結(jié)合的優(yōu)化模型進(jìn)行求解.雖然以上算法適用于整型與非整型參數(shù)混合的變量求解，但對非整型數(shù)據(jù)的特征未做進(jìn)一步分析，采用通用的搜索或選擇算子，在復(fù)雜狀態(tài)空間的搜索中仍存在一定問題.針對更為一般的軟件系統(tǒng)，Levitin[23]采用遺傳算法尋找不同軟件版本的組合以及確定它們之間的執(zhí)行順序.Ahmadizar等人[24]采用了蟻群算法解決通用的優(yōu)化配置模型，但僅用不同組件可靠性值及約束作為算法的輸入，沒有考慮具體保障策略的配置參數(shù).

考慮大數(shù)據(jù)環(huán)境下冗余與監(jiān)控策略并存的分布式系統(tǒng)，現(xiàn)有研究提供了基于三元組編碼的模因算法進(jìn)行求解[14]，該算法的交叉變異及選擇算子能夠保證算法在搜索廣度中的效果，但未對連續(xù)非整型變量的搜索進(jìn)行深入討論，在搜索深度方面還有待提高：

1) 對整型離散冗余變量和非整型連續(xù)監(jiān)控頻率變量采用相同結(jié)構(gòu)或類似的搜索算子，雖然在離散的搜索域中能夠獲得較好效果，但在連續(xù)空間搜索域中將受到限制，容易陷入局部最優(yōu)解.

2) 對不同參數(shù)變量如冗余變量和監(jiān)控頻率變量之間的內(nèi)在制約關(guān)系未做深入分析，對單個組件資源配置參數(shù)與整體系統(tǒng)資源配置參數(shù)間的關(guān)系也未作分析，將不同組件、不同策略的變量視為相互獨立的參數(shù)進(jìn)行搜索，在解的搜索深度上將受到限制.

所以，本文提出了對混合的監(jiān)控策略和冗余策略同時進(jìn)行優(yōu)化選擇配置的改進(jìn)模因算法，為保留進(jìn)化算法搜索廣度的要求，保留了已有算法中的交叉、變異以及選擇算子，同時針對連續(xù)的監(jiān)控頻率變量的特征，建立了變長鄰域的迭代局部搜索算子用于增加搜索的深度.分析了積極冗余機制與基于監(jiān)控的冗余替換機制的關(guān)系，在局部搜索過程中考慮了單個組件配置參數(shù)的變化對整體系統(tǒng)配置參數(shù)的影響，建立了改進(jìn)的模因算法提高算法搜索效率和效果.本文首先分析了已有的冗余及監(jiān)控混合策略的資源優(yōu)化模型以及現(xiàn)有搜索算法的缺點；其次基于可靠性敏感度分析建立了監(jiān)控頻率局部搜索的變長鄰域范圍.在改進(jìn)的局部搜索算子基礎(chǔ)上建立了模因算法框架，并通過實驗對比分析了改進(jìn)算法與現(xiàn)有搜索算法的優(yōu)缺點，驗證了該算法在多策略優(yōu)化配置問題上的優(yōu)越性.

1冗余及監(jiān)控混合策略的資源優(yōu)化模型

1.1假設(shè)條件

對采用了冗余及監(jiān)控混合可靠性保障策略的系統(tǒng)作4點假設(shè)：

1) 假設(shè)未采用任何保障機制時，組件i及其冗余組件的有效工作時間Xi滿足指數(shù)分布，即Xi～EXP(λi)，其中λi表示未配置保障措施的單個組件i的失效率.

2) 假設(shè)在同一時刻1個組件只能采取積極冗余或基于監(jiān)控的冗余替換其中一種機制，不同的組件可以采用不同的機制.

3) 為評估監(jiān)控頻率對組件可靠性的影響，假設(shè)基于監(jiān)控的冗余替換機制中組件的冗余度固定為2，每個組件中設(shè)置監(jiān)控的單元時間平均代價相同.

4) 假設(shè)針對的系統(tǒng)均為分布式系統(tǒng)，即系統(tǒng)可靠性與組件可靠性間的關(guān)系可通過層次方法[12]計算獲得.

1.2融合2種保障策略的資源優(yōu)化配置模型

針對可靠性保障策略進(jìn)行資源優(yōu)化的目的在于在有限的配置資源內(nèi)達(dá)到系統(tǒng)可靠性的最大化或在保障系統(tǒng)可靠性的情況下進(jìn)行資源的最小化配置.選用后者的優(yōu)化思想建立融合冗余與監(jiān)控2種保障策略的資源優(yōu)化配置模型.

(1)

在式(1)中，Ri(t)表示時刻t系統(tǒng)中組件i的可靠性，Vi表示組件i的平均訪問次數(shù)，m表示系統(tǒng)中的組件個數(shù).λmi表示組件i的監(jiān)控頻率，Ci表示組件i的冗余代價.式(1)的約束條件為系統(tǒng)可靠性Rsys(t)達(dá)到可靠性約束R0的要求，優(yōu)化目標(biāo)為達(dá)到冗余配置資源Csys與監(jiān)控配置資源Msys的最小化.xi與yi分別為組件冗余代價及監(jiān)控代價的系數(shù).

當(dāng)組件i采用單純的積極冗余機制時，該組件的可靠性Ri(t)如式(2)所示：

(2)

其中，λi表示未配置冗余的單個組件i的失效率，ni表示組件的冗余度(1≤ni≤p，p表示每個組件i的最大冗余度).此時冗余代價系數(shù)xi=ni，監(jiān)控代價系數(shù)yi=0.

利用Markov鏈理論對組件可靠性及其與監(jiān)控頻率間的相關(guān)關(guān)系進(jìn)行分析[25].當(dāng)組件i采用基于監(jiān)控的冗余替換機制時，該組件的可靠性Ri(t)如式(3)所示[12]：

(3)

其中,

組件i的監(jiān)控周期為1λmi(0≤λmi≤q，q表示每個組件i的最大監(jiān)控頻率).此時xi=2，yi=1.

1.3基于三元組編碼的傳統(tǒng)模因算法

對每個組件而言，式(1)中的待求參數(shù)包括組件策略選項、冗余度以及監(jiān)控頻率3個變量xi=[ni,λmi,αi]，其中αi表示策略選擇，故該優(yōu)化問題是復(fù)雜的多元多目標(biāo)非線性規(guī)劃問題，難以采用傳統(tǒng)線性規(guī)劃的方法進(jìn)行求解.為獲取該問題的近似最優(yōu)解，基于NSGA Ⅱ[19]的模因算法T-MOMA[14]被用于求解該問題.T-MOMA中采用了三元數(shù)組的編碼方式對每個組件的策略選擇方式、冗余度及監(jiān)控頻率進(jìn)行編碼.圖1表示了6個組件組成的系統(tǒng)三元組編碼，數(shù)組行1表示系統(tǒng)組件的冗余度，行2表示組件監(jiān)控頻率，行3代表可靠性保障策略選項(R：積極冗余，M：基于監(jiān)控的冗余替換).

T-MOMA算法中的搜索策略存在2個弊端：

Fig. 1　Example of triple element encoding mechanism.圖1 三元組編碼示例

1) 與傳統(tǒng)進(jìn)化搜索算法的解相比，三元編碼方式的解空間范圍增大，傳統(tǒng)基于三元組編碼的交叉、變異、局部搜索算子針對三元組中的某行或某列數(shù)據(jù)采取相同操作，在數(shù)據(jù)類型相同且搜索范圍相近時(如針對不同類型的冗余度搜索)，對不同參數(shù)可達(dá)到相似搜索效果.而監(jiān)控頻率參數(shù)為連續(xù)變量，監(jiān)控頻率參數(shù)的搜索空間遠(yuǎn)大于冗余參數(shù)的搜索范圍.以m個組件的系統(tǒng)為例，冗余度范圍在[1，5]內(nèi)的整型變量，遍歷搜索需要5m次，而對監(jiān)控頻率在[0，1]之內(nèi)的連續(xù)變量，建設(shè)搜索間隔為0.01，則遍歷搜索需要100m次(減小搜索間隔還將增大搜索次數(shù)).此時對兩者采用相同方法將很難對監(jiān)控策略的解空間進(jìn)行深入搜索，所以針對不同類型變量需要采用不同類型的搜索策略.

2) 現(xiàn)有算法將三元組數(shù)據(jù)中的每行數(shù)據(jù)作為孤立的變量進(jìn)行搜索.而在優(yōu)化搜索過程中保障策略選項的改變對組件以及系統(tǒng)可靠性的影響較大，在交叉、變異算子中可采用此方法，但在局部搜索中產(chǎn)生的新個體可能喪失局部優(yōu)勢，難以適應(yīng)近鄰產(chǎn)生的條件，降低了局部搜索的效果，此時需要同時對組件乃至系統(tǒng)中其他配置參數(shù)進(jìn)行相應(yīng)調(diào)整.

由于在模因算法中，局部搜索算子是增強算法搜索效率的重要因素[26]，所以在第2節(jié)中主要針對局部搜索算子對以上2個問題進(jìn)行改進(jìn).

2基于鄰域分析的局部搜索近鄰生成算法

局部搜索算子中為了對選定個體的近鄰進(jìn)行搜索選擇，首先需要確定近鄰的選擇方法以及范圍.在現(xiàn)有T-MOMA算法中，對xi=[ni,λmi,αi]中的3個變量分別在鄰域范圍內(nèi)進(jìn)行變化并產(chǎn)生相應(yīng)的近鄰.冗余度變量為離散變量，其近鄰選擇的鄰域為[-1,1].監(jiān)控頻率為連續(xù)變量，其近鄰選擇的鄰域范圍為[-q2，q2]，近鄰產(chǎn)生的改變值為[-q2，q2]中均勻分布的隨機值，其中q為λmi的取值范圍，同式(3).雖然監(jiān)控頻率的近鄰產(chǎn)生是通過隨機變量實現(xiàn)，但其鄰域取值固定，在監(jiān)控頻率取值較大時容易產(chǎn)生更優(yōu)的近鄰，但在取值較小時反而不能對較小范圍內(nèi)的λmi值進(jìn)行深入搜索.所以本節(jié)在可靠性參數(shù)敏感度分析的基礎(chǔ)上，通過建立變長的鄰域范圍，改進(jìn)局部搜索算子中的近鄰生成方法.

2.1基于敏感度分析的變長鄰域范圍確定

根據(jù)式(1)～(3)的可靠性分析模型，參數(shù)變量(包括冗余度或監(jiān)控頻率)的增加將引起組件及系統(tǒng)可靠性增長，但隨著參數(shù)變量值的增大，可靠性的增長趨勢將逐漸減弱.圖2和圖3分別表示了示例組件的可靠性隨冗余度或監(jiān)控頻率增加的變化趨勢.

Fig. 2　Component reliability changing with the increase of redundancy.圖2　組件可靠性隨冗余度增加的變化趨勢

Fig. 3　Component reliability changing with the increase of monitoring rate.圖3　組件可靠性隨監(jiān)控頻率增加的變化趨勢

為對該影響關(guān)系作進(jìn)一步分析，建立參數(shù)變量的變化對組件及系統(tǒng)可靠性增長的敏感度分析模型.

1) 參數(shù)變量對組件可靠性敏感度

冗余度及監(jiān)控頻率變化對組件的可靠性增長敏感度如式(4)～(5)所示，其中ai與bi同式(3).

(4)

(5)

2) 參數(shù)變量對系統(tǒng)可靠性敏感度

冗余度及監(jiān)控頻率變化對系統(tǒng)的可靠性增長敏感度如式(6)所示.

(6)

根據(jù)組件敏感度分析的結(jié)果，雖然冗余度增長對可靠性變化的影響呈下降趨勢，但其為固定范圍內(nèi)的離散變量，故對冗余度的局部搜索可選擇[-1,1]的鄰域范圍.與冗余度變化相比，監(jiān)控頻率的變化對可靠性增長的影響曲線較陡，同時，監(jiān)控頻率取值連續(xù)，難以對其影響進(jìn)行評估.如圖4所示，當(dāng)監(jiān)控頻率值較小(如λm1<0.005)時，其細(xì)微的變化也將引起組件可靠性較大的增長，此時應(yīng)選取范圍較小的鄰域進(jìn)行近鄰搜索；反之當(dāng)監(jiān)控頻率值較大(如λm2>0.01)時，頻率值的變化對可靠性增長的影響較小，則此時的鄰域范圍需要相應(yīng)增大.

Fig. 4　The neighbor search range of different monitoring rate.圖4　不同監(jiān)控頻率取值的鄰域范圍

采用固定長度的鄰域或隨機分布的鄰域范圍無法達(dá)到上述搜索目標(biāo).所以基于敏感度分析，建立監(jiān)控頻率的局部搜索變化范圍為[-Δλmi，Δλmi]，如式(7)所示.在選取固定ΔRsys(t)值的前提下，λmi取值越大，[-Δλmi，Δλmi]范圍越大，反之λmi取值越小，鄰域范圍越小.

(7)

2.2基于鄰域分析的近鄰生成方法

對組件xi=[ni,λmi,αi]中的3個變量分別進(jìn)行不同變化可生成不同新個體用于局部算法搜索.

1) 基于冗余度變化的近鄰生成

算法1. genNeighbour_N.

輸入：需要進(jìn)行局部搜索的個體pj、選定組件i；

① 生成新個體pj1.ni=pj.ni+1，其他值與pj相同；

2) 基于監(jiān)控頻率變化的近鄰生成

1.3.4 樹脂的靜態(tài)吸附及解吸試驗 2.0 g樹脂加入已知濃度的紅薯葉總黃酮提取溶液中室溫吸附24 h，計算樹脂靜態(tài)吸附率。將吸附后樹脂，加入到一定體積的解吸液中，于室溫下解吸24 h，按下式計算樹脂靜態(tài)解吸率：

(8)

算法2. genNeighbour_Lambda.

輸入：需要進(jìn)行局部搜索的個體pj、選定組件i；

① 根據(jù)式(7)以及pj.λmi,計算相應(yīng)Δλmi；

② 定義近鄰搜索最大循環(huán)次數(shù)z；

③ fory=1：z

④ 利用式(8)、y值以及第①行獲得的Δλmi計算εi；

⑤ 生成新個體pj2.λmi=pj.λmi+εi，其他值與pj相同；

⑦ 停止計算pj2；

⑧ end if

3) 基于策略選項混合變化的近鄰生成

Fig. 5　Neighbor generation based on the redundancy and strategy change.圖5　基于冗余度及策略選項混合變化的近鄰生成方法

Fig. 6　Neighbor generation based on the monitoring rate and strategy change.圖6　基于監(jiān)控頻率及策略選項混合變化的近鄰生成方法

算法3. genNeighbour_Strategy.

輸入：需要進(jìn)行局部搜索的個體pj、選定組件i；

① 生成新個體pj3.αi=pj.αi的反值，其他值與pj相同；

② ifpj3.αi==R

④ else

⑥ ifpj3.ni==2

⑦ 生成新個體pj6=pj3；

⑧ fork=1：m

⑨ ifpj3.αk==M

⑩ 根據(jù)式(8)、式(9)以及pj3.λmi計算相應(yīng)εk；

3基于迭代局部搜索策略的改進(jìn)模因算法

在已有的局部搜索算子中，文獻(xiàn)[21]采用了Max-Min變異方法選定個體中具有最大可靠性和最小可靠性的三元組進(jìn)行變異，將某一組件的參數(shù)變量視為整體進(jìn)行操作，在保證可靠性接近約束條件的同時可能減少資源消耗，但算法針對特定的三元組進(jìn)行變化可能減低個體的部分優(yōu)勢.文獻(xiàn)[14]針對3種變量分別進(jìn)行迭代搜索，即對不同組件的同一變量采取統(tǒng)一操作.該方法能夠提高搜索的范圍，但搜索過程脫離了組件自身的可靠性分析，容易進(jìn)入局部最優(yōu)解.本節(jié)中結(jié)合以上2種方法各自的優(yōu)點建立改進(jìn)的迭代局部搜索算子并用以改進(jìn)模因算法.

3.1迭代局部搜索算法

Fig. 7　Iterative search strategy in local search algorithm.圖7　局部搜索算法中迭代搜索策略

針對選定的個體pj的近鄰，局部搜索算法迭代的搜索該個體的近鄰，在每一次迭代中，隨機選擇個體中的任意組件i，利用第2節(jié)中的近鄰生成方法對其三元組數(shù)據(jù)xi=[ni,λmi,αi]進(jìn)行變化產(chǎn)生近鄰.該方法每次主要對個體中的1個組件進(jìn)行特定改變，能夠保持該個體的優(yōu)勢特征；同時通過多次迭代過程增大局部搜索的范圍.每次迭代產(chǎn)生近鄰個體的詳細(xì)步驟如圖7所示:

在迭代搜索每次近鄰產(chǎn)生的同時檢查其約束值以及目標(biāo)值與原個體之間的支配關(guān)系，能夠支配原始個體或不被原始個體支配的新個體將被加入子種群，繼續(xù)下一次交叉變異計算.局部搜索算法的完整框架所示如下：

算法4. 迭代局部搜索算法localsearch.

輸入：需要進(jìn)行局部搜索的個體pj、可行解集Q、算法迭代次數(shù)l、最大迭代次數(shù)lmax；

輸出：更新后的可行解集Q.

① ifl≤lmax，執(zhí)行后續(xù)搜索；

② 在個體pj中隨機選擇一個組件i；

③ ifpj.αi==R

⑤ ifpj1與pj互為非支配解，或pj1支配pj

⑥ 將pj1加入可行解Q中；

⑦ end if

⑧l(xiāng)ocalsearch(pj1,Q,l+1,lmax) ；

(pj，i)；

genNeighbour_Strategy(pj，i)；

3.2改進(jìn)模因算法框架

基于3.1節(jié)的迭代局部搜索算法4，改進(jìn)模因算法(UD-TMOMA)框架所示如下：

算法5. UD-TMOMA.

輸入：父種群P0=?、子種群Q=?、進(jìn)化代數(shù)t=0、最大進(jìn)化代數(shù)tmax；

輸出：結(jié)果子種群Q、進(jìn)化代數(shù)t.

① 種群初始化：P0=(p1,p2,…,pN)，其中p1,p2,…,pN為隨機生成的個體；

② whilet=0：tmax

③ 對Pt執(zhí)行以下操作：基于三元組編碼的交叉以及變異操作產(chǎn)生子種群Q；

④ forj=1：N×局部搜索概率

⑤ 從子種群Q中隨機選擇1個個體pj；

⑥localsearch(pj,Q,0,lmax)得到局部優(yōu)化后的子種群Q；

⑦ end for

⑧ 合并父種群Pt和子種群Q生成新種群R；

⑨ 計算種群R中各個體的約束值和目標(biāo)值；

⑩ 采用第2代快速非支配排序方法，按照非支配字體和聚集距離對R進(jìn)行倒序排序；

算法中的種群初始化、交叉變異及排序操作與T-MOMA算法類似，可參見文獻(xiàn)[14]，在本文中不作詳細(xì)闡述.

3.3算法時間復(fù)雜度分析

與T-MOMA算法或傳統(tǒng)基于Max-Min算子的遺傳算法(GA)相比，UD-TMOMA算法的其他操作與其相同，時間復(fù)雜度的主要差別體現(xiàn)在局部搜索算子中.假設(shè)每次局部搜索迭代次數(shù)為n，根據(jù)個體的情況，UD-TMOMA算法的局部搜索算子每次可能產(chǎn)生3～6個新個體，所以時間復(fù)雜度在O(3n)到O(6n)之間，傳統(tǒng)T-MOMA算法對每行向量分別采用迭代搜索，每行向量每次產(chǎn)生2個新個體，時間復(fù)雜度為O(3×2n)，而GA算法每次僅對2個特定組件進(jìn)行操作，時間復(fù)雜度為O(1).所以UD-TMOMA算法的局部搜索算子時間復(fù)雜度有一定增加，在迭代過程中迭代次數(shù)的選擇對算法時間增長有較顯著效果.

4實驗過程與結(jié)果分析

4.1實驗設(shè)置

本節(jié)我們采用文獻(xiàn)[27]中的系統(tǒng)結(jié)構(gòu)和相應(yīng)參數(shù)進(jìn)行實驗.系統(tǒng)的組織結(jié)構(gòu)如圖8所示:

Fig. 8　Example of system architecture.圖8　系統(tǒng)結(jié)構(gòu)示例

系統(tǒng)中采用的示例實驗參數(shù)如表1所示:

Table 1　The Input Parameters of Units

Fig. 9　Example of component redundancy.圖9　系統(tǒng)冗余示例

圖8所示的系統(tǒng)被抽象為2部分：組件及組件間的狀態(tài)轉(zhuǎn)移關(guān)系.采用基于體系結(jié)構(gòu)的可靠性分析方法[28]，原始狀態(tài)下的系統(tǒng)可靠性Rsys≈R1R2R33.03R4R5R60.7R70.2R80.1R9R10R11R12.系統(tǒng)中的單個組件提供了特定的功能，為了保障系統(tǒng)可靠性，在實際運行過程中，可能存在多個具有相同功能的組件，其中,1個為正在使用的組件而其他組件均作為它的冗余備份存在，如圖9所示.

每個組件中均可采用積極冗余[10]以及基于監(jiān)控的冗余替換[12]2類機制進(jìn)行冗余組件的替換.當(dāng)組件采用積極冗余替換機制時，可替換的組件均處于運行狀態(tài)中，組件可靠性主要取決于可替換的備份數(shù)量.采用監(jiān)控替換機制時，被監(jiān)測到故障的組件可以得到及時的替換，組件的可靠性主要依賴于監(jiān)控機制的頻率.考慮到2類機制共存于系統(tǒng)組件中，則需要同時對組件的冗余度以及監(jiān)控頻率進(jìn)行計算，建立該系統(tǒng)的優(yōu)化模型同式(1)，故將該系統(tǒng)模型用于本文中的UD-TMOMA算法實驗.

經(jīng)過多次實驗，UD-TMOMA算法的參數(shù)設(shè)置如下：在鄰域范圍確定中，ΔRsys(t)=0.001，種群個位為100，循環(huán)次數(shù)tmax=500，交叉概率為0.9，變異概率為0.1，局部搜索概率為0.05，為減少局部搜索引起的時間消耗，局部搜索迭代次數(shù)lmax=3，局部搜索中監(jiān)控頻率搜索的最大循環(huán)次數(shù)z=3.

4.2案例分析

為對冗余及監(jiān)控混合策略的優(yōu)化配置結(jié)果做詳細(xì)說明，在本實驗中采用UD-TMOMA對特定條件下的系統(tǒng)進(jìn)行運算，得到相應(yīng)的資源配置結(jié)果如表2所示.其中，t表示選定的系統(tǒng)時間，R0表示相應(yīng)的可靠性約束條件.由于UD-TMOMA算法的計算結(jié)果是1組平衡解集，表2中針對每組實驗數(shù)據(jù)僅選擇了其中具有代表性的2組結(jié)果.

Table 2　An Case Study of Example System

表2顯示在不同約束條件下，該算法均可用于同時計算每個組件的可靠性保障措施選項以及相應(yīng)的保障策略參數(shù)(如冗余度或監(jiān)控頻率).當(dāng)時間增加或系統(tǒng)可靠性需求增長時，需要消耗更多的資源配置，不同組件冗余度或監(jiān)控頻率之間的增長相互影響，該特性與T-MOMA算法體現(xiàn)的結(jié)果一致.

4.3算法對比分析

為了證明算法在局部搜索中的優(yōu)勢，在本節(jié)中，將UD-TMOMA算法與已有文獻(xiàn)中采用了三元組編碼的GA[21]和T-MOMA[14]算法比較.目前基于三元組的GA算法是在多選擇策略的系統(tǒng)冗余度分配領(lǐng)域的通用算法.為了增強算法的搜索效率，GA算法中采用了Max-Min變異算子，T-MOMA算法則采用了其他局部搜索策略.

1) 不同可靠性約束

在不同的可靠性約束條件下，采用3種算法分別計算近似最有資源優(yōu)化配置模型，計算獲得的2種資源消耗的解集如圖10所示.其中假設(shè)t=10 h，選用了表1所示的系統(tǒng)輸入值，設(shè)置可靠性約束從0.90變化至0.99.

圖10顯示UD-TMOMA算法獲得配置方法所消耗的資源均低于其他2種方法計算獲得的資源.為了對算法的效果進(jìn)行定量比較，采用了覆蓋率[29]作為度量標(biāo)準(zhǔn)，覆蓋率體現(xiàn)了2種解集相互支配的程度.由于以上算法均為近似算法，具有一定隨機性，所以對每種算法運行10次，所得到的每組優(yōu)化配置結(jié)果對應(yīng)的2種系統(tǒng)代價值的覆蓋率如表3所示.

Fig. 10　Results of three algorithms using different reliability constraints.圖10　3種算法對不同可靠性約束的實驗結(jié)果

ReliabilityConstraintGA∕T-MOMAT-MOMA∕GAGA∕UD-TMOMAUD-TMOMA∕GAT-MOMA∕UD-TMOMAUD-TMOMA∕T-MOMA0.900.43640.99140.00000.99920.00100.99920.910.36470.98500.00120.99960.00060.99960.920.52150.62510.00001.00000.00050.99870.930.13620.89330.00000.99910.00001.00000.940.35220.89570.00000.99910.00000.99950.950.12090.80960.00000.99840.00000.99950.960.09090.71030.00001.00000.00000.99850.970.24170.44920.00000.99940.00001.00000.980.29980.57330.00000.99560.00510.99210.990.12000.83050.00000.93180.00000.8864Average0.26840.77630.00010.99220.00070.9874

Note: AB stands for A covers B.

2) 不同系統(tǒng)參數(shù)

除了不同的約束條件外，在t=10 h時也采用不同的系統(tǒng)組件失效率對3種算法進(jìn)行實驗，實驗結(jié)果所消耗的資源如圖11所示，該實驗中設(shè)定可靠性約束為0.95，選取10組隨機的系統(tǒng)組件失效率值進(jìn)行實驗.表4顯示了不同測試用例下相應(yīng)的覆蓋率.

Fig. 11　Results of three algorithms using different system parameters.圖11　3種算法對不同系統(tǒng)參數(shù)的實驗結(jié)果

TestCaseGA∕T-MOMAT-MOMA∕GAGA∕UD-TMOMAUD-TMOMA∕GAT-MOMA∕UD-TMOMAUD-TMOMA∕T-MOMA10.06060.76610.00170.99750.00001.000020.10280.98530.00001.00000.00001.000030.36200.99540.00150.99930.00001.000040.18600.98340.00000.99920.00001.000050.52400.93490.00001.00000.00001.000060.25570.97590.00000.99950.00001.000070.26010.90690.00000.99960.00001.000080.35080.89540.00160.99650.00000.999590.32210.89600.00000.99960.00001.0000100.09910.88830.00000.99890.00001.0000Average0.25230.92280.00050.99900.00001.0000

Note: AB stands for A covers B.

從解集覆蓋率的結(jié)果可以看到GA算法與T-MOMA算法的結(jié)果基本都被新算法UD-TMOMA所支配，在可靠性約束較低即解空間較大時尤為明顯.為體現(xiàn)不同算法的解集在解空間的覆蓋程度，以上解集計算的超體積指標(biāo)(hypervolume indicator, HI)[30]值如表5所示.HI值體現(xiàn)了解集在空間的分布程度.

從HI值可以看出3種算法在解空間的分布情況基本相同，其中UD-TMOMA算法的分布結(jié)果比T-MOMA算法略差.

3) 與單策略算法比較

在本節(jié)中，基于混合多策略的資源優(yōu)化配置方法與已有文獻(xiàn)中基于單策略的可靠性優(yōu)化方法包括積極冗余配置方法[31]以及監(jiān)控替換配置方法[12]進(jìn)行了對比.t=10 h時同樣設(shè)置可靠性約束從0.90變化至0.99，在各種參數(shù)環(huán)境下分別運行基于UD-TMOMA的多策略方法以及基于MOMA[12]的監(jiān)控資源分配和基于線性規(guī)劃的冗余資源優(yōu)化方法[31].不同方法進(jìn)行可靠性優(yōu)化后的資源消耗結(jié)果集如圖12所示，為了更好地進(jìn)行對比分析，T-MOMA算法的結(jié)果也在圖12中有所體現(xiàn).然后設(shè)定可靠性約束為0.95，選取10組隨機的系統(tǒng)組件失效率值，得到的相應(yīng)資源消耗結(jié)果如圖13所示.

Table 5　Hypervolume Indicator of Different Algorithms under Different Conditions

Fig. 12　Resources comparison under different availability constraint.圖12　不同可靠性約束下的資源消耗對比

Fig.13　Resources comparison using different system parameters.圖13　不同系統(tǒng)參數(shù)下的資源消耗對比

上述實驗結(jié)果中可以看到在可靠性約束較低的情況下(如R0=0.91,0.94)，單種監(jiān)控策略在同等監(jiān)控頻率下消耗的冗余資源略少于混合策略計算得到的結(jié)果，對于T-MOMA算法尤其明顯.采用UD-TMOMA算法，該情況略有改善.

4.4實驗結(jié)果分析

從4.3節(jié)實驗中我們可以得出2個結(jié)論：

1) 雖然UD-TMOMA算法中局部搜索策略的改變對解集在解空間的分布情況稍有降低，但沒有對算法的穩(wěn)定性造成明顯影響，但在搜索性能方面有明顯增加.

2) 由于單策略的搜索算法的參數(shù)變量較少，解空間小于混合策略的搜索算法，所以當(dāng)可靠性約束較低時，單策略的搜索算法比混合策略的搜索算法獲得的解略好，隨著解空間減小，這種優(yōu)勢逐漸減弱.在與單策略搜索算法的比較中，UD-TMOMA算法的結(jié)果仍然優(yōu)于T-MOMA算法.

總的來說，與其他多策略資源搜索算法相比，在不影響算法穩(wěn)定性的前提下，UD-TMOMA能夠獲得更優(yōu)的資源配置結(jié)果.在搜索空間較大的情況下，與單策略資源搜索算法相比還略有不足.

5結(jié)束語

本文中我們主要研究了面向可靠性優(yōu)化設(shè)計的冗余和監(jiān)控混合可靠性保障策略的資源優(yōu)化配置算法.針對現(xiàn)有進(jìn)化搜索算法在多元多維解空間中搜索力度的不足，建立了基于鄰域分析的改進(jìn)模因算法.首先對冗余度及監(jiān)控頻率等參數(shù)變量變化對組件及系統(tǒng)可靠性增長影響進(jìn)行了分析.基于敏感度分析的結(jié)果建立了針對3種參數(shù)變量的近鄰生成方法，例如針對監(jiān)控頻率搜索提出了基于變長鄰域的近鄰生成方法，針對策略選項搜索提出了與組件關(guān)聯(lián)的系統(tǒng)近鄰生成方法.采用改進(jìn)近鄰生成方法建立了局部搜索算子，通過組件間的迭代搜索在保持個體優(yōu)勢的同時增大搜索范圍，并用以改進(jìn)模因算法框架.通過實驗驗證了：該算法能夠用于求解每個組件保障措施的選擇以及相應(yīng)的配置參數(shù)；與現(xiàn)有2種多策略搜索算法相比，改進(jìn)模因算法能夠獲得取得更優(yōu)的資源配置結(jié)果，在待求解空間較大時，優(yōu)化效果尤為明顯；雖然局部搜索策略使解集在解空間的分布略有降低，但對算法穩(wěn)定性未造成明顯影響.在本文中監(jiān)控策略與冗余策略作為獨立的措施被應(yīng)用于系統(tǒng)組件中，在后續(xù)的研究中將考慮兩者結(jié)合的措施，即同一組件同一時刻采取了2種或多種保障策略，在系統(tǒng)運行的過程中，考慮隨時間變化的資源分配機制及相應(yīng)的進(jìn)化搜索算法.

參考文獻(xiàn)

[1]Zhou Jiang, Wang Weiping, Meng Dan, et al. Key technology in distributed file system towards big data analysis[J]. Journal of Computer Research and Development, 2014, 51(2): 382-394 (in Chinese)(周江, 王偉平, 孟丹, 等. 面向大數(shù)據(jù)分析的分布式文件系統(tǒng)關(guān)鍵技術(shù)[J]. 計算機研究與發(fā)展, 2014, 51(2): 382-394)

[2]Amari S V, Dugan J B, Misra R B. Optimal reliability of systems subject to imperfect fault-coverage[J]. IEEE Trans on Reliability, 1999, 48(3): 275-284

[3]Du Xiaozhi, Qi Yong, Hou Di, et al. Software rejuvenation model based on reconfiguration and periodical rejuvenation[J]. Journal of Xi’an Jiaotong University, 2010, 44(1): 91-95 (in Chinese)(杜小智, 齊勇, 侯迪, 等. 重配置與周期再生相結(jié)合的軟件再生模型[J]. 西安交通大學(xué)學(xué)報, 2010, 44(1): 91-95)

[4]Nourelfath M, Chatelet E, Nahas N. Joint redundancy and imperfect preventive maintenance optimization for series-parallel multi-state degraded systems[J]. Reliability Engineering & System Safety, 2012, 103: 51-60

[5]Mi Haibo, Wang Huaimin, Yin Gang, et al. Resource on-demand reconfiguration method for virtualized data centers[J]. Journal of Software, 2011, 22(9): 2193-2205 (in Chinese)(米海波, 王懷民, 尹剛, 等. 一種面向虛擬化數(shù)字中心資源按需重配置方法[J]. 軟件學(xué)報, 2011, 22(9): 2193-2205)

[6]He Jialang, Zhang Kun, Meng Jin, et al. Hybrid software fault-tolerant model based on evolvable-modules redundancy[J]. Journal of Nanjing University of Science and Technology, 2012, 36(2): 272-277, 284 (in Chinese)(何加浪, 張琨, 孟錦, 等. 可進(jìn)化模塊冗余軟件混合容錯模型[J]. 南京理工大學(xué)學(xué)報, 2012, 36 (2): 272-277, 284)

[7]Coit D W. Cold-standby redundancy optimization for nonrepairable systems[J]. IIE Transactions, 2001, 33(6): 471-478

[8]Jia Jia, Yang Xuejun, Li Zhiling. A redundancy-multithread-based multiple GPU copies fault-Tolerance technique[J]. Journal of Computer Research and Development, 2013, 50(7): 1551-1562 (in Chinese)(賈佳, 楊學(xué)軍, 李志凌. 一種基于冗余線程的GPU多副本容錯技術(shù)[J]. 計算機研究與發(fā)展, 2013, 50(7): 1551-1562)

[9]Zhu Jun, Guo Changguo, Wu Quanyuan. A runtime monitoring web services interaction behaviors method based on CPN[J]. Journal of Computer Research and Development, 2011, 48(12): 2277-2289 (in Chinese)(朱俊, 郭長國, 吳泉源. 一種基于CPN的運行時監(jiān)控服務(wù)交互行為的方法[J]. 計算機研究與發(fā)展, 2011, 48(12): 2277-2289)

[10]Romera R, Valdes J E, Zequeira R I. Active-redundancy allocation in systems[J]. IEEE Trans on Reliability, 2004, 53(3): 313-318

[11]Ben Halima R, Fki E, Drira K, et al. A large-scale monitoring and measurement campaign for web services-based applications[J]. Concurrency Computation Practice and Experience, 2010, 22(10): 1207-1222

[12]He Pan, Yuan Yue, Wu Kaigui. Optimal multi-objective monitoring resources allocation in distributed systems[J]. Computer Science, 2014, 41(5): 64-67, 77 (in Chinese)(何盼, 袁月, 吳開貴. 分布式系統(tǒng)監(jiān)控資源多目標(biāo)優(yōu)化分配[J]. 計算機科學(xué), 2014, 41(5): 64-67, 77)

[13]He Pan, Wu Kaigui, Wen Junhao, et al. Monitoring resources allocation for service composition under different monitoring mechanisms[C]Proc of the 5th Int Conf on Complex, Intelligent and Software Intensive Systems. Los Alamitos, CA: IEEE Computer Society, 2011: 263-270

[14]He Pan. Research on resources allocation in distributed systems oriented at optimal reliability design[D]. Chongqing: Chongqing University, 2012 (in Chinese)(何盼. 面向可靠性優(yōu)化設(shè)計的分布式系統(tǒng)資源分配研究[D]. 重慶: 重慶大學(xué), 2012)

[15]Chern M S. On the computational complexity of reliability redundancy allocation in a series system[J]. Operations Research Letters, 1992, 11(5): 309-315

[16]Coit D W. Maximization of system reliability with a choice of redundancy strategies[J]. IIE Transactions, 2003, 35(6): 535-543

[17]Tavakkoli-Moghaddam R, Safari J, Sassani F. Reliability optimization of series-parallel systems with a choice of redundancy strategies using a genetic algorithm[J]. Reliability Engineering and System Safety, 2008, 93(4): 550-556

[18]Chambari A, Rahmati S H A, Najafi A A, et al. A bi-objective model to optimize reliability and cost of system with a choice of redundancy strategies[J]. Computers and Industrial Engineering, 2012, 63(1): 109-119

[19]Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182-97

[20]Chambari A, Najafi A A, Rahmati S H A, et al. An efficient simulated annealing algorithm for the redundancy allocation problem with a choice of redundancy strategies[J]. Reliability Engineering and System Safety, 2013, 119: 158-164

[21]Safari J. Multi-objective reliability optimization of series-parallel systems with a choice of redundancy strategies[J]. Reliability Engineering and System Safety, 2012, 108: 10-20

[22]Liu Y, Huang H Z, Wang Z, et al. A joint redundancy and imperfect maintenance strategy optimization for multi-state systems[J]. IEEE Trans on Reliability, 2013, 62(2): 368-378

[23]Levitin G. Optimal structure of fault-tolerant software systems[J]. Reliability Engineering and System Safety, 2005, 89(3): 286-295

[24]Ahmadizar F, Soltanpanah H. Reliability optimization of a series system with multiple-choice and budget constraints using an efficient ant colony approach[J]. Expert Systems with Applications, 2011, 38(4): 3640-3646

[25]Zhuang Lu, Cai Mian, Shen Changxiang. Trusted dynamic measurement based on interactive Markov chains[J]. Journal of Computer Research and Development, 2011, 48(8): 1464-1472 (in Chinese)(莊琭, 蔡勉, 沈昌祥. 基于交互式馬爾可夫鏈的可信動態(tài)度量研究[J]. 計算機研究與發(fā)展, 2011, 48(8): 1464-1472)

[26]Krasnogor N, Smith J. A tutorial for competent memetic algorithms: Model, taxonomy, and design issues[J]. IEEE Trans on Evolutionary Computation, 2005, 9(5): 474-488

[27]Xia Y, Wang H P, Huang Y, et al. A stochastic model for workflow QoS evaluation[J]. Scientific Programming, 2006, 14(34): 251-265

[28]Wu Caihua, Liu Juntao, Peng Shirui, et al. Deriving Markov chain usage model from UML model[J]. Journal of Computer Research and Development, 2012, 49(8): 1811-1819 (in Chinese)(吳彩華, 劉俊濤, 彭世蕤, 等. 基于UML的軟件Markov鏈?zhǔn)褂媚Ｐ偷臉?gòu)建[J]. 計算機研究與發(fā)展, 2012, 49(8): 1811-1819)

[29]Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computing, 2000, 8(2): 173-195

[30]Auger A, Bader J, Brockhoff D, et al. Theory of the hypervolume indicator: Optimalμ-distributions and the choice of the reference point[C]Proc of the 10th ACM SIGRVO Conf on Foundations of Genetic Algorithms. New York: ACM, 2009: 87-102

[31]He P, Xie Q. Reliability analysis of service composition with service pools and optimal configuration of service pool size

中圖法分類號TP302.7; TP311.5

通信作者：袁月(yuanyue@cigit.ac.cn)

基金項目：國家自然科學(xué)基金項目(61309005)；重慶市基礎(chǔ)與前沿研究計劃一般項目(cstc2014jcyjA40015)

收稿日期：2014-11-05；修回日期：2015-03-19

This work was supported by the National Natural Science Foundation of China (61309005) and the Basic and Frontier Research Program of Chongqing (cstc2014jcyjA40015)