李 震 崔驍松 孫晨旭 苗 虹 王東升 王召斌 魏海峰

（1.江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212003）（2.江蘇科技大學(xué)經(jīng)濟(jì)管理學(xué)院 鎮(zhèn)江 212003）（3.江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

從系統(tǒng)的角度來看，彈性已被視為系統(tǒng)的一個屬性，即系統(tǒng)受到攻擊（或受到干擾）導(dǎo)致系統(tǒng)物理損壞并且超出其控制范圍之后能夠恢復(fù)其基本（或通用）功能的能力［1］。而相應(yīng)的維修策略的制定以及能夠恢復(fù)到什么程度對系統(tǒng)的彈性來說就顯得尤為重要。

文獻(xiàn)［2］提出了一種基于迭代計(jì)算的啟發(fā)式算法優(yōu)化網(wǎng)絡(luò)拓?fù)洌瑢o定圖添加鏈路改善網(wǎng)絡(luò)的平均效率函數(shù)以提高網(wǎng)絡(luò)彈性。文獻(xiàn)［3］提出了一種采用啟發(fā)式優(yōu)化算法的多級恢復(fù)問題，通過重構(gòu)和DG（分布式電源）孤島來恢復(fù)系統(tǒng)。具體來說，文獻(xiàn)［4］和文獻(xiàn)［5］提出了啟發(fā)式和窮舉搜索算法來找到最優(yōu)島，以此來恢復(fù)分布式系統(tǒng)彈性。而智能優(yōu)化算法也是系統(tǒng)彈性恢復(fù)的一種策略，文獻(xiàn)［6］提出了一種有針對性的提升供應(yīng)鏈彈性的深度學(xué)習(xí)機(jī)制，此算法比傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)更加能夠提高供應(yīng)鏈績效，并且結(jié)合案例進(jìn)行了相應(yīng)驗(yàn)證。

但是，現(xiàn)有系統(tǒng)恢復(fù)策略中算法適應(yīng)值函數(shù)的設(shè)置很少涉及到任務(wù)重要度信息這一缺陷，在時間約束方面也相對較少。這樣是不符合有限時間內(nèi)的搶修和戰(zhàn)時搶修的實(shí)際情況，所以也難以得到相對應(yīng)的搶修和戰(zhàn)時系統(tǒng)彈性恢復(fù)策略。在比如搶修或者戰(zhàn)時等實(shí)際情況下，系統(tǒng)在遭到破壞后，希望在最短時間內(nèi)恢復(fù)關(guān)鍵的重要功能，而現(xiàn)有的系統(tǒng)彈性恢復(fù)的智能優(yōu)化算法中的適應(yīng)值函數(shù)很少涉及到任務(wù)重要度等信息，這樣就很難度量出系統(tǒng)中關(guān)鍵的重要任務(wù)的恢復(fù)程度，并且缺少對有限維修時間約束和分組并行維修模式的考慮，而這些都是有待改進(jìn)的方面。

針對以上情況，文章將遺傳算法用于求解系統(tǒng)在有限時間內(nèi)，考慮分組并行維修和優(yōu)先恢復(fù)關(guān)鍵重要功能的彈性恢復(fù)策略，將任務(wù)重要度、時間以及分組并行維修因素納入系統(tǒng)彈性的研究范圍內(nèi)，進(jìn)行深入的系統(tǒng)彈性分析研究。

2 系統(tǒng)彈性概述

2.1 彈性的定義

最早在20世紀(jì)70年代時，Holling［7］將彈性定義為系統(tǒng)的特征，使其能夠吸收內(nèi)部或外部沖擊強(qiáng)迫的變化，而不會導(dǎo)致生態(tài)系統(tǒng)中的規(guī)則更改。David D.Woods［8］提出彈性指的是系統(tǒng)如何從破壞或創(chuàng)傷事件中恢復(fù)并返回到以前或正常的活動的能力。Grotberg［9］提出彈性是一種普遍的能力，指允許個人，團(tuán)體或社區(qū)預(yù)防來減少災(zāi)害事件所帶來的影響。Hollnagel［10］認(rèn)為彈性是系統(tǒng)在重大事故或持續(xù)壓力干擾發(fā)生之前，期間或之后調(diào)整其功能以便它可以維持所需的操作的內(nèi)在能力。Wil?davsky［11］指出彈性是一個術(shù)語，是組織或系統(tǒng)在遇到意外危險時響應(yīng)或反彈的能力。

彈性是一種使系統(tǒng)從令人未能預(yù)料到的或破壞性的事件中轉(zhuǎn)向一種適應(yīng)性的方法，以確保系統(tǒng)在一個期間的操作保持其連續(xù)性［12］。彈性反映了系統(tǒng)吸收沖擊和恢復(fù)的能力，同時是一種改變其結(jié)構(gòu)和面對長期壓力，變化和不確定性的運(yùn)作手段［13］。

2.2 彈性的度量

通常來說，彈性的評估過程可以被分為兩類：定性評估和定量評估。

定性評估的方法一般傾向于評估沒有數(shù)值描述的系統(tǒng)彈性，其一般包含兩個子類別：1）彈性概念框架；2）半定性方法。彈性概念框架是一種將彈性分類成幾種關(guān)鍵屬性進(jìn)行討論的定性評估方法，而半定性方法則是通過一些相關(guān)問題來進(jìn)行設(shè)計(jì)，將系統(tǒng)的特性作為基礎(chǔ)來對彈性進(jìn)行評估。定性的彈性度量方法在文獻(xiàn)［14～15］中有詳細(xì)的介紹。

定量方法則將系統(tǒng)的彈性量化為一個指標(biāo)，使人對其有一個相對直觀的了解，定量方法一般包括兩個子類別：1）通用的彈性方法，提供不論領(lǐng)域的方法來量化彈性；2）基于模型結(jié)構(gòu)的方法。該方法是用來對特性領(lǐng)域的組件彈性進(jìn)行建模分析的。

通用的彈性度量方法包括兩種，分別為積分彈性模型和商彈性模型。兩種彈性模型的圖示如下圖所示。

2.2.1 積分彈性模型

在系統(tǒng)中，系統(tǒng)的彈性可以根據(jù)系統(tǒng)性能隨時間的變化來量化［16～17］。圖1經(jīng)常被稱為理解系統(tǒng)對中斷的典型響應(yīng)的指南圖示。如式（1）所示，這是一種積分彈性模型，也稱為時間關(guān)聯(lián)性彈性模型。

圖1 積分彈性模型

其中R是彈性，Q(t)是系統(tǒng)功能或性能函數(shù)，t是時間，td是發(fā)生中斷的時間，th是總檢查時間。因此，彈性可以簡單地表示為整合關(guān)于時間的已知性能函數(shù)。邊界條件是發(fā)生中斷的時間和給定的檢查時間。不用實(shí)現(xiàn)系統(tǒng)完全恢復(fù)或可接受恢復(fù)的時間作上限，以確保為系統(tǒng)分配更高的彈性值，以更快的速度恢復(fù)到目標(biāo)正常運(yùn)行狀態(tài)。

2.2.2 商彈性模型

文章使用如圖2所示的商彈性模型來度量系統(tǒng)彈性。商彈性模型也稱為非時間關(guān)聯(lián)性彈性模型。根據(jù)公式（2）所示，系統(tǒng)彈性定義為性能的恢復(fù)值與損失值的比值。

圖2 商彈性模型

式中：R(t)為t時刻系統(tǒng)彈性，Recovery(t)為t時刻恢復(fù)的系統(tǒng)性能，Loss(td)為系統(tǒng)性能的損失值。

式（2）展示了系統(tǒng)從干擾事件中恢復(fù)的能力。如果Recovery(t)=Loss(td)，那么系統(tǒng)具有完全彈性；如果沒有恢復(fù)，即Recovery(t)=0，那么系統(tǒng)便沒有表現(xiàn)出彈性。此模型只考慮性能恢復(fù)程度，而與恢復(fù)的時長沒有關(guān)系，因此也稱為非時間關(guān)聯(lián)性彈性模型。

3 遺傳算法設(shè)計(jì)

遺傳算法是模擬生物界的遺傳和進(jìn)化過程而建立起來的一種搜索算法，體現(xiàn)著“生存競爭、優(yōu)勝劣汰、適者生存”的競爭機(jī)制。遺傳算法具有良好的全局搜索能力，可以快速地將解空間中的全體解搜索出，而不會陷入局部最優(yōu)解的快速下降陷阱，并且利用它的內(nèi)在并行性，可以方便地進(jìn)行分布式計(jì)算，加快求解速度。

3.1 編碼方式

染色體采用二級制編碼，編碼順序?yàn)楣?jié)點(diǎn)的維修恢復(fù)順序，并且將節(jié)點(diǎn)的任務(wù)重要度以及維修時間等信息加入到節(jié)點(diǎn)信息中，本算法中祖先種群是隨機(jī)編碼產(chǎn)生的。

3.2 分組模式

由于單一維修恢復(fù)方式的速度較慢，而且在實(shí)際的搶修或戰(zhàn)時情況下，一般會存在多個維修小組對系統(tǒng)進(jìn)行恢復(fù)。所以在算法中加入分組維修的策略，分組數(shù)nSalesmen=5，即分為5個維修小組同時維修，每組至少維修節(jié)點(diǎn)數(shù)minTour=3。

3.3 約束條件

每個維修小組的維修時間表達(dá)式ti(i=1，2，3，4，5)如式（3）所示：

其中，k表示節(jié)點(diǎn)的索引，m表示對應(yīng)維修小組維修的開始節(jié)點(diǎn)的索引，n表示對應(yīng)維修小組維修的終止節(jié)點(diǎn)的索引，h(pRoute(k))表示維修人員維修第k個節(jié)點(diǎn)所需要的時間，dmat(pRoute(k)，pRoute(k+1))表示維修路線中第k個節(jié)點(diǎn)到第k+1個節(jié)點(diǎn)的距離，v表示維修人員的行走速度。

總時間約束為t<1800，因?yàn)榫S修小組是同時維修，所以時間約束為ti(i=1，2，3，4，5)<1800。

3.4 適應(yīng)度函數(shù)

構(gòu)造出基于任務(wù)重要度的適應(yīng)值函數(shù)，根據(jù)重要度適應(yīng)值函數(shù)，評價種群中每個個體當(dāng)前的適應(yīng)值?；谌蝿?wù)重要度的適應(yīng)值函數(shù)表達(dá)式total?Metr如式（4）（5）所示：

其中，k表示節(jié)點(diǎn)的索引，m表示對應(yīng)維修小組維修的開始節(jié)點(diǎn)的索引，n表示對應(yīng)維修小組在約束時間內(nèi)所能維修完成的最后一個節(jié)點(diǎn)的索引，metri表示第i組維修小組的總?cè)蝿?wù)重要度。

3.5 GA算子操作

3.5.1 選種

選種是模擬生物進(jìn)化的自然選擇原理，適度值高的個體有更多的機(jī)會繁殖后代。選種是遺傳算法的關(guān)鍵，有多種方法，如輪盤選種，隨機(jī)遍歷抽樣選種等，選種過程是隨機(jī)的，每一個個體被選中的機(jī)會與其適度值成正比，本文中采用的是輪盤選種策略。

3.5.2 交叉

對于選中的用于繁殖的每一對個體（基因碼鏈），隨機(jī)地選取一個截?cái)帱c(diǎn)，將雙親（原來的兩個個體）的基因碼鏈截?cái)?，互換從該截?cái)帱c(diǎn)起的末尾部分或其它部分而成后代，雜交是基因遺傳算法的一個重要算子，有單點(diǎn)雜交和多點(diǎn)雜交，本文采用多點(diǎn)交叉。

3.5.3 突變

對于從群體中隨機(jī)選中的個體，隨機(jī)選取某一位（或多位）進(jìn)行數(shù)碼翻轉(zhuǎn)（如對二進(jìn)制由1變?yōu)?，由0變?yōu)?，對十進(jìn)制采用加5或減5）。即對群體中的每一個個體，以某一概率改變某一個或某一些基因座上的基因值為其他的等位基因。突變也有單點(diǎn)、二點(diǎn)和多點(diǎn)3種，同生物界一樣，突變發(fā)生的概率很低，遠(yuǎn)小于雜交概率。文中采用單點(diǎn)突變。突變?yōu)樾聜€體的產(chǎn)生提供了機(jī)會。

3.6 終止條件判斷

因?yàn)檫z傳算法是隨機(jī)搜索算法，找到一個正式的、明確的收斂性判別標(biāo)準(zhǔn)是困難的。常用遺傳算法終止采用達(dá)到預(yù)先設(shè)定的代數(shù)和根據(jù)問題定義測試種群中最優(yōu)個體的性能。如果沒有可接受的解答，遺傳算法重新啟動或用新的搜索初始條件。本算法終止條件為最大迭代次數(shù)numIter=1000。

4 算例分析

4.1 基礎(chǔ)數(shù)據(jù)

如圖3所示為40個節(jié)點(diǎn)的具體位置示意圖，40個節(jié)點(diǎn)位置都是隨機(jī)生成的。橫坐標(biāo)與縱坐標(biāo)為（0，100）之間的隨機(jī)數(shù)。節(jié)點(diǎn)重要度為（1，5）之間的隨機(jī)數(shù)，節(jié)點(diǎn)維修時間為（1，500）之間的隨機(jī)數(shù)，初始化總時間t=0，種群大小popSize=80。

圖3 節(jié)點(diǎn)位置

如圖4所示為節(jié)點(diǎn)的距離矩陣，使用了imagesc函數(shù)將距離矩陣中的元素?cái)?shù)值按大小轉(zhuǎn)化為不同顏色，并在坐標(biāo)軸對應(yīng)位置處以這種顏色染色，顏色越深代表數(shù)值越小。

圖4 節(jié)點(diǎn)距離矩陣

4.2 求解結(jié)果

如圖5所示的為種群每代最優(yōu)重要度的迭代進(jìn)化曲線，圖中可以看出曲線收斂速度很快，之后趨于平緩，最優(yōu)重要度為94.4，最優(yōu)代數(shù)為671代。

圖5 最優(yōu)重要度進(jìn)化曲線

如圖6所示的是在時間約束下任務(wù)重要度最高的恢復(fù)策略，圖7則是在時間約束下隨機(jī)維修的維修策略，代表5個維修小組的維修路徑。具體的數(shù)據(jù)對比如表1所示。

圖6 基于時間約束和任務(wù)重要度的恢復(fù)策略

圖7 基于時間約束和隨機(jī)的恢復(fù)策略

表1 兩種恢復(fù)策略對比

如表1所示，40個節(jié)點(diǎn)的總?cè)蝿?wù)重要度為95.9，時間約束設(shè)定為30min，基于任務(wù)重要度最高的遺傳算法恢復(fù)策略中，可以維修完成的節(jié)點(diǎn)總數(shù)為30，總?cè)蝿?wù)重要度為94.4，最優(yōu)代數(shù)為671代。而在隨機(jī)維修的恢復(fù)策略中，可以維修完成的節(jié)點(diǎn)總數(shù)為29，總?cè)蝿?wù)重要度僅僅為76.3。

4.3 系統(tǒng)彈性對比

兩種系統(tǒng)彈性的對比如表2所示。系統(tǒng)性能指標(biāo)是通過任務(wù)重要度來衡量的，根據(jù)式（2）中的商彈性模型可以得出對應(yīng)系統(tǒng)的彈性值。

表2 兩種系統(tǒng)彈性對比

圖5 左圖所示的在時間約束下任務(wù)重要度最高的遺傳算法維修策略中，系統(tǒng)彈性值：

圖5 右圖所示的在時間約束下隨機(jī)維修的維修策略中，系統(tǒng)彈性值：

對比可知使用本文中遺傳算法的系統(tǒng)擁有更良好的彈性性能。

5 結(jié)語

文章針對現(xiàn)有的系統(tǒng)恢復(fù)策略中算法適應(yīng)值函數(shù)的設(shè)置很少涉及到任務(wù)重要度等信息這一缺陷，基于時間約束以及任務(wù)重要度，建立了相對應(yīng)的適應(yīng)度函數(shù)，并且在恢復(fù)策略中加入并行分組維修模式。此種考慮時間和任務(wù)重要度的系統(tǒng)彈性恢復(fù)方法簡潔、高效，可以迅速獲取在有限時間里使得任務(wù)重要度最高的維修策略以及最優(yōu)維修結(jié)果，可以使受損后的系統(tǒng)關(guān)鍵功能得到迅速恢復(fù)，并且通過對比驗(yàn)證了此系統(tǒng)更加良好的系統(tǒng)彈性恢復(fù)能力。