基于時間和任務重要度的系統彈性恢復研究*

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

（1.江蘇科技大學電子信息學院 鎮江 212003）（2.江蘇科技大學經濟管理學院 鎮江 212003）（3.江蘇科技大學計算機學院 鎮江 212003）

1 引言

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

文獻［2］提出了一種基于迭代計算的啟發式算法優化網絡拓撲，對給定圖添加鏈路改善網絡的平均效率函數以提高網絡彈性。文獻［3］提出了一種采用啟發式優化算法的多級恢復問題，通過重構和DG（分布式電源）孤島來恢復系統。具體來說，文獻［4］和文獻［5］提出了啟發式和窮舉搜索算法來找到最優島，以此來恢復分布式系統彈性。而智能優化算法也是系統彈性恢復的一種策略，文獻［6］提出了一種有針對性的提升供應鏈彈性的深度學習機制，此算法比傳統的BP神經網絡更加能夠提高供應鏈績效，并且結合案例進行了相應驗證。

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

針對以上情況，文章將遺傳算法用于求解系統在有限時間內，考慮分組并行維修和優先恢復關鍵重要功能的彈性恢復策略，將任務重要度、時間以及分組并行維修因素納入系統彈性的研究范圍內，進行深入的系統彈性分析研究。

2 系統彈性概述

2.1 彈性的定義

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

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

2.2 彈性的度量

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

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

定量方法則將系統的彈性量化為一個指標，使人對其有一個相對直觀的了解，定量方法一般包括兩個子類別：1）通用的彈性方法，提供不論領域的方法來量化彈性；2）基于模型結構的方法。該方法是用來對特性領域的組件彈性進行建模分析的。

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

2.2.1 積分彈性模型

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

圖1 積分彈性模型

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

2.2.2 商彈性模型

文章使用如圖2所示的商彈性模型來度量系統彈性。商彈性模型也稱為非時間關聯性彈性模型。根據公式（2）所示，系統彈性定義為性能的恢復值與損失值的比值。

圖2 商彈性模型

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

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

3 遺傳算法設計

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

3.1 編碼方式

染色體采用二級制編碼，編碼順序為節點的維修恢復順序，并且將節點的任務重要度以及維修時間等信息加入到節點信息中，本算法中祖先種群是隨機編碼產生的。

3.2 分組模式

由于單一維修恢復方式的速度較慢，而且在實際的搶修或戰時情況下，一般會存在多個維修小組對系統進行恢復。所以在算法中加入分組維修的策略，分組數nSalesmen=5，即分為5個維修小組同時維修，每組至少維修節點數minTour=3。

3.3 約束條件

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

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

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

3.4 適應度函數

構造出基于任務重要度的適應值函數，根據重要度適應值函數，評價種群中每個個體當前的適應值。基于任務重要度的適應值函數表達式total?Metr如式（4）（5）所示：

其中，k表示節點的索引，m表示對應維修小組維修的開始節點的索引，n表示對應維修小組在約束時間內所能維修完成的最后一個節點的索引，metri表示第i組維修小組的總任務重要度。

3.5 GA算子操作

3.5.1 選種

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

3.5.2 交叉

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

3.5.3 突變

對于從群體中隨機選中的個體，隨機選取某一位（或多位）進行數碼翻轉（如對二進制由1變為0，由0變為1，對十進制采用加5或減5）。即對群體中的每一個個體，以某一概率改變某一個或某一些基因座上的基因值為其他的等位基因。突變也有單點、二點和多點3種，同生物界一樣，突變發生的概率很低，遠小于雜交概率。文中采用單點突變。突變為新個體的產生提供了機會。

3.6 終止條件判斷

因為遺傳算法是隨機搜索算法，找到一個正式的、明確的收斂性判別標準是困難的。常用遺傳算法終止采用達到預先設定的代數和根據問題定義測試種群中最優個體的性能。如果沒有可接受的解答，遺傳算法重新啟動或用新的搜索初始條件。本算法終止條件為最大迭代次數numIter=1000。

4 算例分析

4.1 基礎數據

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

圖3 節點位置

如圖4所示為節點的距離矩陣，使用了imagesc函數將距離矩陣中的元素數值按大小轉化為不同顏色，并在坐標軸對應位置處以這種顏色染色，顏色越深代表數值越小。

圖4 節點距離矩陣

4.2 求解結果

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

圖5 最優重要度進化曲線

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

圖6 基于時間約束和任務重要度的恢復策略

圖7 基于時間約束和隨機的恢復策略

表1 兩種恢復策略對比

如表1所示，40個節點的總任務重要度為95.9，時間約束設定為30min，基于任務重要度最高的遺傳算法恢復策略中，可以維修完成的節點總數為30，總任務重要度為94.4，最優代數為671代。而在隨機維修的恢復策略中，可以維修完成的節點總數為29，總任務重要度僅僅為76.3。

4.3 系統彈性對比

兩種系統彈性的對比如表2所示。系統性能指標是通過任務重要度來衡量的，根據式（2）中的商彈性模型可以得出對應系統的彈性值。

表2 兩種系統彈性對比

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

圖5 右圖所示的在時間約束下隨機維修的維修策略中，系統彈性值：

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

5 結語

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