基于粒子群算法的延迟转换备份元件优化排序

胡传福，史小宏

（上海海事大学信息工程学院，上海 201306）

基于粒子群算法的延迟转换备份元件优化排序

胡传福，史小宏

（上海海事大学信息工程学院，上海 201306）

系统的可靠性设计中经常使用的混合冗余备份策略可以提高系统的可靠性，温备份元件的转化通常在上一个热备份模式的元件失效后立即转化替换；在延迟转换混合备用系统中，经过一定的延迟时间后才会替换前一个备份元件，这些元件的初始化分布对系统可靠性和任务成本有较大影响。首次使用粒子群算法来处理这种可靠性系统的组合优化问题，找出最优元件排序组合和最佳延迟时间；通过这种算法处理找出的元件排序组合可以经济有效地应用于系统可靠性设计中。

混合备份；可靠性；任务成本；粒子群算法

0 引言

可靠性设计与分析就是通过可靠性预计、分配、分析和改进等可靠性技术，把可靠性定量要求转化为产品设计，形成产品固有可靠性，包括建立系统可靠性模型、进行可靠性设计、可靠性分配和各种可靠性分析[1]。在混合备份策略的设计中元件可以在预设的固定时刻从温备份转化到热备份，可能会发生备份元件过早地转换到热备份导致任务成本增加和可靠性的降低，或是没有及时转换到热备份导致从温备份直接转换到在线操作，使恢复延迟时间过长。在状态独立的转换模式下，温备份转换到热备份是由在线操作元件或当前热备份元件的状态触发的，当其中任何一个元件失败，温备份元件立即转换到热备份，这种模式可以在一定程度减少任务成本提高可靠性，但不是最有效的。在热备份元件失效或者替换在线元件之后，延迟转换备份模式会将温备份序列中的元件延迟一些时间再转换成热备份，延迟可以有效提高任务可靠性和减少任务成本[2]。利用粒子群算法及其改进优化算法,结合可靠性分析方法进行结构的可靠性优化设计[3]，本文首次通过粒子群算法在可行解域内优化选择这些元件的初始化分布和延迟时间来达到系统可靠性最优化设计[4]。

1 延迟转换混合冗余备份模型

混合冗余备份系统由N个独立元件组成，元件E（1）在系统启动时就进入在线操作模式，其他备份元件处于温备份模式，温备份模式中的元件按照序列E（2）…E（n）转换到热备份，当温备份模式中有元件存在且热备份模式中已经有θ时间内元件个数为0时，温备份元件将转换到热备份。即备份元件序列E（2）…E（k-1）已经离开温备份模式，元件E（k-1）在时刻t离开热备份后，元件E（k）将会在时间t+θ转换到热备份，若当需要进行温备份转换到热备份时温备份序列中没有元件则任务可能会失败，当所有的元件在固定任务时间tM之前失效则整个任务就失败了。元件E（k）从热备份模式下替换失效在线元件的时间成本是THO（E（k）），从温备份模式转换到热备份模式的时间成本是TWH（E（k）），TwO（E（k））是温备份直接转换到在线操作模式时间成本，且TWO（E（k））≥TWH（E（k））+THO（E（k））。热备份模式下的元件单位时间消耗资源SH（E（k））大于温备份模式下的元件单位时间消耗资源SW（E（k））但小于在线操作模式下的元件单位时间消耗资源SO（E（k）），即SO（E（k））＞SH（E（k））＞SW（E（k））。为了计算方便约定该模型满足条件[2]：（1）在不同模式下的系统元件的失效时间分布是相同的。（2）对比任务时间，模式转换时间可以忽略。（3）模式转换机制完美可靠。

2 系统可靠性和费用的计算

2.1 延迟转换冗余备份系统可靠性计算方法

将系统任务时间tM划分成个相等时间间隔，Δ=。元件的失效时间分布的累积密度函数为Fk（t）。元件k在第i个时间间隔内失效的概率是pk（i）=Fk（Δ（i+ 1））-Fk（Δi），它在整个任务时间段内的自由离散失效时间可以用pk=（pk（0）pk（m））表示，其中pk（i）=Pr{Tk=Δi}（0≤i≤m）为某个时间间隔内的元件失效概率密度[5]。没有任何元件的操作时间会比任务时间tM更长，元件k在任务期间不会失效的概率是pk（m）=Pr{Tk≥tM=m}=因为元件在任务时间内会处于不同的模式，累积暴露模型用近似寿命概念来表示，即元件工作在不同操作模式下的时间乘以定义的各自因子来表示近似寿命。Fk（t）是元件在操作模式下的累积失效时间分布函数，元件k的累积失效时间分布函数在温备份模式下开始，然后转换到热备份模式，再转换到在线模式是Fk（t*）。任何一个在时刻tH转化到热备份模式，在时刻to转换到操作模式的元件k，失效时间tF的累积密度函数是：

2.2 延迟转换冗余备份系统费用计算方法

元件E（1）在时间段0进入在线操作模式，在时间段iF离开在线操作模式的费用为：

在序列s（1），s（2），…，s（K-1）中的一个元件在时间段XK-1离开热备份，在时段间YK-1离开在线操作模式。元件E（k）应该在时间段Xk-1+θ转换到热备份，第一个元件的初始费用为0。当第E（k）（k＞1）个元件处于温备份，热备份和在线模式分别取决于XK-1，YK-1和iF之间的关系，元件E（k）在操作模式下失效或在XK-1和YK-1时间段内失效的费用可以用下式计算：

2.3 可靠性和任务预期费用评估方法

元件序列的备份系统的任务可靠性和预期费用算法如下所示：

3 粒子群算法组合优化过程

3.1 粒子群算法优化备份元件组合排序

当系统元件是不同的，它们的初始化顺序会较大的影响系统的可靠性和预期任务成本。对于所要考虑的备份系统的优化问题，就是如何在众多的元件序列中找出最优排序的问题。PSO算法是一种迭代算法[6]。PSO算法求解优化问题的过程为：第一步是初始化一个粒子的群体，群体中的每个粒子都有开始位置及运动速度，每个粒子的位置表示问题的一个潜在可能解，PSO算法用适应度函数对这些粒子的优劣状况进行评估。如果粒子所在的位置和最优解比较近，说明该粒子的状况就越好。在迭代循环过程中，粒子群中的粒子根据自身的经验（粒子当前所找到的最好解，称为个体极值）和自身附近邻居的经验（其近邻当前所找到的最好解，称为局部极值）来更新自己的位置和运动速度。当粒子移动到新的位置时，新的可能解就产生了。用这种方式，粒子群中粒子的位置不断更新，最后收敛到问题的最优解或近似最优解[7]。粒子群算法的流程如下图所示:

图1 基本粒子群算法执行流程

例如若有粒子群P={p1，p2，…，pM}，该粒子群由M个粒子组成，这里，M叫做粒子群规模。一个粒子通过其所在的位置和速度来表示。粒子pi的个体极值表示为pbesti，即pbesti是粒子pi当前所发现的最好解。pi的局部极值表示为gi，即gi为粒子pi的近邻当前所发现的最好解。在粒子群算法中，粒子会以以下公式为依据来更新自身的速度和位置：

在这里，w是正常数，叫做惯性权重，C1，C2也同样是两个正常数，叫做学习因子，rand（）是在[0，1]中服从均匀分布的随机数[8]。

3.2 粒子群算法优化实现技术

（1）初始化：

粒子群的初始化也即对每个粒子pi（i=1，2，…，M）的位置xi和速度vi进行初始化，每个粒子的初始位置是在问题的解空间内随机产生的，速度的每个分量也是在指定的范围[-Vmax，Vmax]中随机获得的。

（2）适应函数：

在粒子群算法中，适应函数被用来评估粒子的好坏，即被用来评估一个粒子所在的位置与最优解相近的程度。适应函数是粒子位置的函数，粒子的适应值是由其所在的位置所决定的，通常适应函数取为目标函数。

（3）参数设置：

①群体规模M。群体规模M通常在10～50取值。对很多问题而言，取M=20就可以得到很好的结果。但对于较复杂的问题群体规模也试着取的大一些。如取M=100或200。

②粒子群中的最大速度Vmax决定了在每一次迭代中粒子飞行的最大距离。若Vmax比较大，那么粒子将可能飞出最好解；若Vmax比较小，则易于陷入局部最优。如何选择Vmax依赖于所要解决的问题。一般来说，Vmax与搜索空间每一维的变化范围相关。如，若每一维的变化范围为[-50，50]，则可取Vmax=c*50（0．1≤c≤1．0）。

③邻域规模k。在使用局部邻域结构时，需要对邻域规模k进行设置。当邻域规模为粒子群的规模M时，则局部邻域结构成为全局邻域结构[7]。

④学习因子C1，C2。通常取C1=C2=2，也可取其他不同的值，但一般使C1=C2，并在[0，4]中取值。

（4）终止条件：

①迭代次数达到预先指定的最大代数；

②适应函数的计算次数达到预先指定的最大次数；

③所有粒子的速度趋近于0；

在上面几种方法中，常用的方法是预先指定一个最大迭代次数和粒子的速度趋近于0[9]。

（5）约束的处理

用PSO算法求解约束优化问题，可以参考演化计算中的关于约束条件处理的一些方法和经验[10]。例如，利用惩罚函数法将约束优化问题转化为无约束优化问题。最直接的一种方法是基于保持可行解的方法。该方法对粒子群算法作出以下修改：

①在进行初始化过程中，对所有粒子重复初始化直到所有的约束条件都满足；

②当计算gi时，仅考虑那些在可行区域的粒子。

对于所要考虑的备份系统的优化元件序列问题也就是找出系统元件的序列

E（1），E（2），…，E（n）和延迟θ在达到任务可靠性水平的条件下使系统预期费用F最低

元件序列和延迟时间的组合表示为一个粒子，组合相近的粒子均匀分布在临近区域，每个粒子代表的元件序列的可靠性和任务成本都可以通过上面的算法计算出来。然后将上面的限制条件重新表示为非限制问题

这里δ是一个足够大的惩罚系数。当δ=0，问题简化为一个不受限的预期任务成本最小化；当δ较大且R*=1问题简化为可靠性最大化。通过粒子群算法在元件序列代表的初始化粒子群中找出满足非限制问题的最优粒子。

4 实验及验证过程

在现实系统中备份元件的数量不是很多，通常用穷举法就可以找到最优元件排序序列，但是当备份元件较多时，排序组合就会过多。所以穷举法找出可能最优序列耗时较长，为了快速定位最优排序组合，使用粒子群算法具有较明显的优势。现在用五个服从威布尔参数特征的元件案例系统来验证使用该方法是否简单有效。元件参数如下：

表1 系统中元件的各种参数

当设定从温备份直接转化到在线操作的转换成本为50时，案例系统的预期任务费用和可靠性随着延迟时间θ变化情况如图2所示：

图2 转换延迟θ与R，E之间的函数关系

设置5个延迟时间值分别为0，8，15，30，88，100；则初始化的粒子形式如（1，2，3，4，5，0），（1，2，3，4，5，8），（1，2，3，4，5，15），（5，2，1，3，4，88），（5，2，1，3，4，100）等，要求可靠性高于97%，实验将初始化规模设定为100，初始化相近的粒子分布在附近区域。终止条件设定为粒子的速度趋近于0，则粒子群算法在经过六次迭代后满足了设定条件，每次迭代找到的粒子依次为下表所示：

表2 基本粒子群算法迭代过程

则通过基本粒子群算法找到最佳延迟时间为30，最优元件排序序列（5，2，1，3，4）。结果证明该方法能够成功有效应用，绘出的对应费用和可靠性关系如下图所示：

图3 可靠性和预期任务成本关系

根据图2可以帮助我们来设计系统的延迟冗余备份，可以根据对成本和可靠性需求的要求来分配备份元件。

5 结语

本文通过使用延迟转换备份元件来提高系统设计的可靠性和经济性。通过对系统中延迟转换冗余备份模式的分析，我们提出了使用粒子群算法来找出最优元件序列和最佳延迟时间，并且通过实例来计算出了混合备份模式下系统的可靠性和预期成本进行了验证。通过图直观地显示了系统可靠性跟预期成本之间的关系，为系统元件分布和优化提供了依据。

[1]王华伟，高军．复杂系统可靠性分析与评估[M]．北京:科学出版社，2013．

[2]Levitin G，Xing L，Dai Y．Optimal Design of Hybrid Redundant Systems with Delayed Failure-Driven Standby Mode Transfer[J]．IEEE Transactions on Systems，Man and Cybermetics:Systems，2015，10（1）:2168-2216

[3]郑严．基于智能算法的结构可靠性分析及优化设计研究[D]．西南交通大学，2012．

[4]徐玉杰．粒子群算法的改进及应用[D]．南京师范大学，2013．

[5]Levitin G，Xing L，Dai Y．Cold vs．Hot Standby Mission Operation Cost Minimization for 1-out-of-N Systems[J]．European Journal of Operational Research，2014，234（1）:155-162．

[6]胡一波．求解约束优化问题的几种智能算法[D]．西安电子科技大学，2009．

[7]朱福喜，黄竞伟，康利山．计算智能[M]．北京:科学出版社，2010．

[8]艾宁宁．基于混合智能算法求解随机期望值模型和机会约束规划[D]．长安大学，2012．

[9]赵建华，张陵，孙清．利用粒子群算法的传感优化布置及结构损伤识别研究[J]．西南交通大学学报，2015，49（1）:4-5．

[10]黄慧．基于改进粒子群算法的车间作业排序的优化及仿真研究[D]．南京航空航天大学，2012．

Redundancy Backup Components with Transfer Delay Based on Particle Swarm Algorithm Optimization

HU Chuan-fu，SHI Xiao-hong

（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

The reliability of the system is often used in the design of hybrid redundancy backup strategy,which can improve the reliability of the system．The transformation of warm backup element is usually immediately happened after a last hot backup mode component failure．In the delayed transformation hybrid backup systems,the new component will replace the previous backup components after a certain delay time．The initialize distribution of these components has a great influence on system reliability and task cost．Uses particle swarm optimization（PSO）algorithm for the first time to deal with this kind of system reliability of combinatorial optimization problem and find the optimal combination and the optimal delay time．The element combination through this algorithm processing can efficiently applied to the design of system reliability．

Hybrid Redundancy Backup;Reliability;Task Cost;Particle Swarm Algorithm

1007-1423（2017）11-0031-05

10.3969/j.issn.1007-1423.2017.11.006

胡传福（1992-），男，安徽安庆人，硕士研究生，研究方向为移动Agent技术、复杂系统可靠性评估

2017-02-14

2017-03-15

史小宏（1963-），男，陕西西安人，副教授，硕士，研究方向为移动Agent技术、复杂系统可靠性评估