基于时间和任务重要度的系统弹性恢复研究*

李 震 崔骁松 孙晨旭 苗 虹 王东升 王召斌 魏海峰

（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 结语

文章针对现有的系统恢复策略中算法适应值函数的设置很少涉及到任务重要度等信息这一缺陷，基于时间约束以及任务重要度，建立了相对应的适应度函数，并且在恢复策略中加入并行分组维修模式。此种考虑时间和任务重要度的系统弹性恢复方法简洁、高效，可以迅速获取在有限时间里使得任务重要度最高的维修策略以及最优维修结果，可以使受损后的系统关键功能得到迅速恢复，并且通过对比验证了此系统更加良好的系统弹性恢复能力。