一种基于改进遗传算法的系统弹性恢复方法及恢复系统

摘要

本发明公开了一种基于改进遗传算法的系统弹性恢复方法及恢复系统，该恢复方法包括以下步骤：初始化算法参数，种群个体编码为节点的维修路径；生成初始种群，部分初始种群的个体为随机产生，剩余部分则根据贪婪策略产生；根据适应度函数，评价每一代种群个体的适应值，记录当前种群最优个体及其适应值；对父代种群保留精英个体，通过组间反转、交叉和滑动生成子代种群；将父代个体和子代个体匹配特殊基因实现组内首首变异，最终生成子代种群，并提供一种基于改进遗传算法的系统弹性恢复系统。本发明的恢复方法和恢复系统贴近现实环境需求，收敛速度快且不易早熟，能在一定时间内有效恢复系统弹性。

权利要求

1.一种基于改进遗传算法的系统弹性恢复方法，其特征在于，包括以下步骤：(1)初始化算法参数，种群个体编码为节点的维修路径；

(2)生成初始种群，部分初始种群的个体为随机产生，剩余部分则根据贪婪策略产生；

(3)考虑有限时间、有限备件及分组维修下，构造基于任务重要度的适应度函数；

(4)根据适应度函数，评价每一代种群个体的适应值，记录当前种群最优个体及其适应值；

(5)代数迭代，判断当前代最优个体的适应值是否高于历史最优个体对应的适应值，如果是则更新历史最优适应值和历史最优个体，再继续以下步骤；如果否，则直接继续以下步骤；

(6)对父代种群保留精英个体，通过组间反转、交叉和滑动生成子代种群；

(7)将父代个体和子代个体匹配特殊基因实现组内首首变异，最终生成子代种群；

所述匹配特殊基因实现组内变异的具体方法如下：将父代精英个体中各维修序列首节点与步骤(6)生成的子代个体相应首节点进行匹配，若能匹配成功，则将父代个体维修序列首节点的下一个维修节点作为变异点，与子代个体相应的下一个维修节点进行交换，生成最终的子代个体；

(8)判断是否满足算法结束条件，如果是，则继续以下步骤，如果否，则种群迭代数+1，跳转实施步骤(4)；

(9)输出最优适应值及对应的最优代数，并画出最优个体即最优维修路径；

(10)度量恢复后的系统弹性值。

2.根据权利要求1所述的基于改进遗传算法的系统弹性恢复方法，其特征在于：所述初始化算法参数主要包括：节点位置矩阵xy、节点数n、节点任务重要度z、节点维修时间h、节点所需备件数c、维修小组数s、维修人员平均走速v、最小维修节点数minTour、种群大小popSize和迭代次数numIter。

3.根据权利要求1所述的基于改进遗传算法的系统弹性恢复方法，其特征在于，所述步骤(2)中根据贪婪策略生成部分初始种群的具体方法如下：(a)在N个受损节点中，随机产生每个维修小组维修的首个节点；

(b)设置贪婪度模型，公式如下：

其中，F(X,Y)表示节点X对节点Y的贪婪度，degree(X)表示节点X的任务重要度，distance(X,Y)表示节点X与节点Y之间的距离，h(X)表示节点X维修所需时间，70为通过模拟实验得到的系数，用于生成合理的贪婪度，v表示维修人员平均走速；

(c)根据贪婪策略进行每组下一个维修节点的选择，由此类推，得到每个小组的维修序列，进而得到单个个体的序列，循环M次，产生M个初始个体加入初始种群中，其中，M<种群大小。

4.根据权利要求1所述的基于改进遗传算法的系统弹性恢复方法，其特征在于，所述步骤(7)中生成最终子代种群的具体方法如下：对步骤(6)生成的子代种群，匹配特殊基因实现组内首首变异，最终生成子代种群。

5.根据权利要求4所述的基于改进遗传算法的系统弹性恢复方法，其特征在于，所述父代精英个体得到的具体方法如下：对父代种群分组，算法选取每组适应度值最高的个体作为每组的精英个体，对父代精英个体进行变异生成子代个体，进而生成子代种群。

6.一种基于改进遗传算法的系统弹性恢复系统，其特征在于：包括节点初始化模块、种群初始化模块、变异迭代模块和弹性度量模块，节点初始化模块用于初始化节点位置、节点所需备件、节点任务重要度、节点维修时间和最小维修节点数信息，种群初始化模块用于生成初始种群，结合随机生成和贪婪策略的方法生成初始种群，变异迭代模块用于继承父代精英个体并生成子代种群，包括三种变异和组内首首变异，到达最大迭代次数时，算法结束，弹性度量模块用于度量系统恢复后的弹性值；

所述组内首首变异通过将父代精英个体中各维修序列首节点与子代个体相应首节点进行匹配，若能匹配成功，则将父代个体维修序列首节点的下一个维修节点作为变异点，与子代个体相应的下一个维修节点进行交换，生成最终的子代个体。

说明书

一种基于改进遗传算法的系统弹性恢复方法及恢复系统

技术领域

[0001] 本发明涉及一种系统弹性恢复方法及恢复系统，尤其涉及一种基于改进遗传算法的系统弹性恢复方法及恢复系统。

背景技术

[0002] 弹性和安全性一样，都被视为系统的一个属性，即系统受到攻击(或受到干扰)导致系统物理损坏并且超出其控制范围之后能够恢复其基本(或通用)功能的能力。一个弹性
系统可以更好的适应快速变化、不确定、激烈的对抗环境。目前，系统的弹性是大多建立于
系统受损后相应的恢复方法之上的，如人为修复。那么，在大部分组件需要维修的情况下，
合理的维修目标设定、维修资源调度以及最优维修路径规划就成为了维修策略的核心问
题。而短期内系统弹性的强弱与恢复方法的优劣是有直接关系，所以恢复方法的制定对于
系统弹性性能恢复有着至关重要的作用。

[0003] 目前，解决路径规划问题或者恢复问题时大多采用群体智能优化算法，以遗传算法(GA)为主。遗传算法具有能够求出优化问题全局最优解的特点，但是传统的遗传算法初
始种群随机，且收敛速度慢、容易早熟。同时，现有的运用遗传算法解决系统弹性恢复问题
案例中，适应度函数和约束条件的设置很少同时考虑任务重要度、备件约束和时间约束。

发明内容

[0004] 发明目的：本发明的第一目的为提供一种贴近现实环境需求、收敛速度快且不易早熟、能在一定时间内有效恢复系统弹性的基于改进遗传算法的系统弹性恢复方法，本发
明的第二目的为提供一种基于改进遗传算法的系统弹性恢复系统。

[0005] 技术方案：本发明的基于改进遗传算法的系统弹性恢复方法，包括以下步骤：

[0006] (1)初始化算法参数，种群个体编码为节点的维修路径；

[0007] (2)生成初始种群，部分初始种群的个体为随机产生，剩余部分则根据贪婪度模型，使用贪婪策略产生；

[0008] (3)考虑有限时间、有限备件及分组维修下，构造基于任务重要度的适应度函数；

[0009] (4)根据适应度函数，评价每一代种群个体的适应值，记录当前种群最优个体及其适应值；

[0010] (5)代数迭代，判断当前代最优个体的适应值是否高于历史最优个体对应的适应值，如果是则更新历史最优适应值和历史最优个体，再继续以下步骤；如果否，则直接继续
以下步骤；

[0011] (6)对父代种群保留精英个体，通过组间反转、交叉和滑动生成子代种群；

[0012] (7)将父代个体和子代个体匹配特殊基因实现组内首首变异，最终生成子代种群；

[0013] (8)判断是否满足算法结束条件，如果是，则继续以下步骤，如果否，则种群迭代数+1，跳转实施步骤(4)；

[0014] (9)输出最优适应值及对应的最优代数，并画出最优个体即最优维修路径；

[0015] (10)度量恢复后的系统弹性值。

[0016] 此种考虑时间、备件和任务重要度的系统弹性分组并行恢复方法，能有效调动人力和物力，迅速恢复系统关键任务的运作，在有限时间内使得受损系统的弹性得到最大化
的恢复，收敛性好且不易早熟。

[0017] 进一步地，步骤(1)中的初始化算法参数主要包括：节点位置矩阵xy、节点数n、节点任务重要度z、节点维修时间h、节点所需备件数c、维修小组数s、维修人员平均走速v、最
小维修节点数minTour、种群大小popSize和迭代次数numIter。

[0018] 步骤(2)提出的利用贪婪策略有选择性的生成部分初始种群，具体流程如下：

[0019] (a)在N个受损节点中，随机产生每个维修小组维修的首个节点。

[0020] (b)设置贪婪度模型：

[0021]

[0022] 其中：F(X,Y)表示节点X对节点Y的贪婪度，degree(X)表示节点X的任务重要度，distance(X,Y)表示节点X与节点Y之间的距离，h(X)表示节点X维修所需时间，70为通过模
拟实验得到的系数，用于生成合理的贪婪度；

[0023] (c)根据贪婪策略进行每组下一个维修节点地选择，即下一个节点为当前优先度最高的节点。由此类推，可以得到每个小组的维修序列，进而得到单个个体的序列。循环M
次，产生M个初始个体加入初始种群中，其中，M<种群大小。

[0024] 步骤(3)中考虑有限时间和有限备件的具体方法为在每个节点中加入重要度、维修所需时间及维修所需备件信息，以分组并行维修的形式再加入时间约束和备件约束。其
中，重要度、维修所需时间及维修所需备件信息见步骤(1)，时间约束为t<1800(单位：s)，考
虑维修小组是同时维修，具体为：

[0025] ti＜1800(i＝1，2，3，4，5)

[0026] 其中，每个维修小组维修时间ti为：

[0027]

[0028] 备件约束为：

[0029]

[0030]

[0031]

[0032] 式中，componentiA表示第i个维修小组在实际维修中维修完成的节点总共使用的零件A的数量，componentiB表示第i个维修小组在实际维修中维修完成的节点总共使用的零
件B的数量，componentiC表示第i个维修小组在实际维修中维修完成的节点总共使用的零件
C的数量，m表示对应维修小组维修的开始节点的索引，n表示对应维修小组维修的终止节点
的索引，DjA表示对应维修小组维修第j个节点使用的零件A的个数，DjB表示对应维修小组维
修第j个节点使用的零件B的个数，DjC表示对应维修小组维修第j个节点使用的零件C的个
数。

[0033] 任务重要度适应度函数公式为：

[0034]

[0035] 式中，totaldegree表示所有维修小组完成的总任务重要度，s表示维修小组数，k表示节点索引，zi[pRoute(k)]表示第i个维修小组维修序列中的第k个节点的任务重要度。

[0036] 进一步的，当ti≥1800(i＝1，2，3，4，5)或者componentiA＞12或者componentiB＞12或者componentiC＞12时，则跳出循环体，计算所有维修小组维修完成的总任务重要度、维修
剩余零件数、各组维修所用时间，并记录各组维修序列，各组维修开始时ti均重置为0。

[0037] 步骤(6)中匹配特殊基因实现组内变异的具体方法是将父代精英个体中各维修序列首节点与组间反转、交叉、滑动生成的子代个体相应首节点进行匹配，若能匹配成功，则
将父代个体维修序列首节点的下一个维修节点作为变异点，与子代个体相应的下一个维修
节点进行交换，生成子代个体。也称为首首变异。

[0038] 步骤(9)为结合任务重要度和商弹性模型度量系统弹性。

[0039] 本发明的基于改进遗传算法的系统弹性恢复系统，包括节点初始化模块、种群初始化模块、变异迭代模块和弹性度量模块，节点初始化模块用于初始化节点位置、节点所需
备件、节点任务重要度、节点维修时间和最小维修节点数等信息，种群初始化模块用于生成
初始种群，结合随机生成和贪婪策略的方法生成初始种群，变异迭代模块用于继承父代精
英个体并生成子代种群，包括三种变异和组内首首变异，到达最大迭代次数时，算法结束，
弹性度量模块用于度量系统恢复后的弹性值。

[0040] 有益效果：与现有技术相比，本发明具有如下显著优点：

[0041] (1)用改进的遗传算法来优化维修路径提高了弹性恢复问题的最优解且收敛速度快；

[0042] (2)用改进的遗传算法来优化维修路径比起传统遗传算法能使维修结果相对稳定，比传统遗传算法的稳定性更高；

[0043] (3)在改变每个算法迭代次数的时，改进的遗传算法的运行结果依然比传统遗传算法的结果更优、稳定性更高；

[0044] (4)基于改进遗传算法的系统弹性恢复系统结合了贪婪度模型，生成了一部分优化的初始种群，提高了算法的收敛速度；

[0045] (5)基于改进遗传算法的系统弹性恢复系统通过组内首首变异，实现了较优的个体变异，这种有关联的变异避免了变异的纯随机性，增强了变异的关联性和目的性，使得算
法具有更好的迭代和求解结果。

附图说明

[0046] 图1是本发明的流程图；

[0047] 图2是本发明的节点位置图；

[0048] 图3是本发明的最优重要度的进化曲线图；

[0049] 图4是本发明在时间、备件约束下任务重要度最高的维修策略；

[0050] 图5是本发明中改进的遗传算法和传统遗传算法最优重要度进化曲线对比图；

[0051] 图6是首首变异算子的示意图。

具体实施方式

[0052] 下面结合实施例对本发明的技术方案作进一步说明。

[0053] 为加深对本发明的理解，下面将结合附图和实施例对本发明做进一步详细描述，该实例仅用于解释本发明，并不对本发明的保护范围构成限定。

[0054] 如图1所示，是基于改进遗传算法的系统弹性恢复方法的流程示意图。包括以下步骤：

[0055] (1)初始化算法参数，种群个体编码为节点的维修路径。本发明实例中，选用的实验数据来源于某舰航空母舰，将某舰系统所需维修的设备节点数N设为50，50个节点位置都
是根据某舰上设备的实际位置确定的，其具体位置如图2所示，横坐标范围(0,295)，纵坐标
范围(0,75)。节点任务重要度z为(1,6)之间的整数，节点所需备件数c为(1,3)之间的整数，
设备节点维修时间h在(150,450)之间，维修小组数s＝5，维修人员平均走速v＝3/2，每组最
小维修节点数minTour＝3，种群大小popSize＝80，迭代次数numIter＝600；

[0056] (2)采用半随机半贪婪思想生成大小为80的初始种群。其中，40个个体通过randperm()和rand_breaks()函数随机生成，后40个个体利用贪婪策略有选择性的生成，
具体流程如下：

[0057] 1)在N个受损节点中，随机产生每个维修小组维修的首节点。

[0058] 2)设置贪婪度模型为：

[0059]

[0060] 其中：F(X,Y)表示节点X对节点Y的优先度，degree(X)表示节点X的任务重要度，distance(X,Y)表示节点X与节点Y之间的距离，h(X)表示节点X维修所需时间,70为通过模
拟实验得到的优选系数，用于生成合理的贪婪度。

[0061] 3)根据贪婪策略进行每组下一个维修节点地选择，即下一个节点为当前优先度最高的节点。由此类推，可以得到每个小组的维修序列，进而得到单个个体的序列。循环40次，
产生40个初始个体加入初始种群中。

[0062] (3)考虑有限时间、有限备件及分组维修下，构造基于任务重要度的适应度函数，具体方法为以分组并行维修的形式加入时间约束和备件约束，时间约束为t<1800(单位：
s)，考虑维修小组是同时维修，具体为:

[0063] ti＜1800(i＝1，2，3，4，5)  (2)

[0064] 其中，每个维修小组维修时间ti为：

[0065]

[0066] 备件约束为：

[0067]

[0068]

[0069]

[0070] 式中，componentiA表示第i个维修小组在实际维修中维修完成的节点总共使用的零件A的数量，componentiB表示第i个维修小组在实际维修中维修完成的节点总共使用的零
件B的数量，componentiC表示第i个维修小组在实际维修中维修完成的节点总共使用的零件
C的数量，m表示对应维修小组维修的开始节点的索引，n表示对应维修小组维修的终止节点
的索引，DjA表示对应维修小组维修第j个节点使用的零件A的个数，DjB表示对应维修小组维
修第j个节点使用的零件B的个数，DjC表示对应维修小组维修第j个节点使用的零件C的个
数。

[0071] 任务重要度适应度函数公式为：

[0072]

[0073] 式中，totaldegree表示所有维修小组完成的总任务重要度，s表示维修小组数，k表示节点索引，zi[pRoute(k)]表示第i个维修小组维修序列中的第k个节点的任务重要度。

[0074] 进一步的，当ti≥1800(i＝1，2，3，4，5)或者componentiA＞12或者componentiB＞12或者componentiC＞12时，则跳出循环体，计算所有维修小组维修完成的总任务重要度、维修
剩余零件数、各组维修所用时间，并记录各组维修序列，各组维修开始时ti均重置为0。

[0075] (4)根据适应度函数，评价每一代种群个体的适应值，记录当前种群最优个体及其适应值；

[0076] (5)代数迭代，判断当前代最优个体的适应值是否高于历史最优个体对应的适应值，如果是则更新历史最优适应值和历史最优个体，再继续以下步骤；如果否，则直接继续
以下步骤；

[0077] (6)对父代种群保留精英个体，通过组间反转、交叉、滑动生成子代种群，近一步地，匹配特殊基因实现组内首首变异，最终生成子代种群，其中，匹配特殊基因实现组内首
首变异的具体方法是将父代精英个体中各维修序列首节点与组间反转、交叉、滑动生成的
子代个体相应首节点进行匹配，若能匹配成功，则将父代个体维修序列首节点的下一个维
修节点作为变异点，与子代个体相应的下一个维修节点进行交换，生成子代个体，如图6所
示。

[0078] (7)判断是否满足算法结束条件，如果是，则继续以下步骤，如果否，则种群迭代数+1，跳转实施步骤(4)；

[0079] (8)输出最优适应值及对应的最优代数，并画出最优个体维修序列；

[0080] (9)度量恢复后的系统弹性值。系统弹性定义为系统性能的恢复值与损失值的比值，可用商弹性模型来度量：

[0081] R(t)＝Recovery(t)/Loss(td)  (8)

[0082] 通过以上步骤，得到基于改进遗传算法的系统弹性恢复方法、最优任务重要度及系统弹性。

[0083] 图2所示为50个节点的具体位置示意图，50个节点位置都是根据某舰上设备的实际位置确定的。

[0084] 图3所示为改进的遗传算法种群每代最优重要度的进化曲线图，图中可以看出曲线的收敛速度很快，最优任务重要度为127，最优代数为575。

[0085] 图4所示为改进的遗传算法在时间、备件约束下任务重要度最高的维修策略，图中5种不同粗细的线条代表5个维修小组的维修路径，50个设备节点的初始系统总任务重要度
为170，设备节点全部失效后，限定维修时间不超过30min，每组A、B、C三种类型的零件数分
别为12个，基于改进的遗传算法的维修策略维修了共29个节点，第一组维修序列为49，46，
40，18，15，41，第二组维修序列为38，48，13，10，16，14，25，第三组维修序列为43，44，28，4，
45，12，第四组维修序列为50，7，39，26，23，第五组维修序列为24，17，42，47，29，维修后系统
总任务重要度为127，最优代数为第575代，维修时间为1782.1s。

[0086] 图5所示为改进的遗传算法和已有遗传算法最优任务重要度进化曲线对比图，此处已有遗传算法特征为初始种群随机且只包含组间反转、交叉、滑动这三种变异，图中深色
曲线为改进的遗传算法的最优任务重要度进化曲线，浅色曲线为已有遗传算法最优任务重
要度进化曲线，显而易见，深色曲线比浅色曲线收敛速度更快，改进的遗传算法在第575代
达到最优解，最优任务重要度为127，而已有遗传算法在第542代达到最优解，最优任务重要
度为124。

[0087] 本发明中，系统性能与任务重要度有关，可得图5中改进的遗传算法维修下的系统弹性值为0.75，而已有遗传算法维修下系统弹性值为0.729，由此可见，改进的遗传算法维
修下系统弹性更高。

[0088] 计算两种算法的最优解和最差解，每个算法运行20次，计算20次的平均值和均方差，结果如下表所示：

[0089] 表1两种算法的任务重要度稳定性对比表

[0090]

[0091] 表2两种算法的迭代次数稳定性对比表

[0092]

[0093]

[0094] 从表1可以看出，第二种改进的遗传算法的平均任务重要性最高，均方差较小，说明该算法具有较好的稳定性；同时较传统遗传算法，第二种改进的遗传算法的最高任务重
要度高，算法的最优解优于传统遗传算法。从表2可以看出，第二章改进的遗传算法的代数
平均值远小于传统遗传算法，可见第二种改进的遗传算法收敛性更好。

[0095] 表3不同迭代次数的重要度均值

[0096]

[0097] 表4不同迭代次数的重要度方差

[0098]

[0099] 表5不同迭代次数的代数均值

[0100]

[0101] 由表3～表5可以发现，在不同的迭代次数中，改进的遗传算法在优化系统维修路径时任务重要度平均值、任务重要度方差和代数平均值一直保持较优，这说明改进的遗传
算法不仅能得到最优解，而且收敛速度快，且在不同迭代次数下具有很好的稳定性。

[0102] 综上，本发明提出一种基于改进遗传算法的系统弹性恢复方法，基于时间、备件约束和任务重要度构造的适应度函数来生成系统弹性恢复方法，采用分组的形式并行维修设
备失效节点，以总任务重要度作为系统性能衡量指标。改进的遗传算法的系统弹性恢复方
法，关键在于初始种群并非全部随机生成，而是以贪婪度模型为导向的贪婪策略有目的性
的生成，并且种群在反转、交叉、滑动后，再根据父代种群的优良特性与子代种群特殊基因
匹配，实现子代种群的组内基因的首首变异，这样可以加速算法的收敛性、提高算法的最优
解。本发明的解较已有遗传算法更优，且更具稳定性，特别是在不同的迭代次数下情况更是
如此。