单目标—多条件约束网络RRAP问题分段迭代PSO算法研究

白迎霞，李东魁

（1.呼和浩特民族学院计算机系，内蒙古呼和浩特，010051；2.包头师范学院学报编辑部，内蒙古包头，014030）

0 引言

可靠性-冗余分配问题，英文表述为：Reliability Redundancy Allocation Problem，简写为RRAP。RRAP问题的数学模型，一般是非线性混合整数规划问题；因为一般的可靠性优化问题是NP-Hard的，由于RRAP决策变量中既有实数部分，又有整数部分，一般的RRAP也是NP-Hard的，而且这类问题求解是可靠性优化问题中难度较大的，研究这类问题的快速算法具有重要的实际意义，也具有一定的理论价值。

COIT[1]等对可靠性冗余分配问题(RAP)的历史发展状况进行了总结，并预测了未来发展趋势；本文为讨论问题方便起见，对单目标可靠性冗余分配问题的文献[2-23]，进行了重新梳理，具体情况列在表中（见表1）。

表1可见，由于问题的难度较大，可靠性-冗余分配问题的已有研究结果并不丰富，用于求解的方法主要是遗传算法、粒子群优化算法及混合算法等，解的编码也主要是系统元件的可靠度及冗余度，按照可靠度在左，冗余度在右构成的实数与整数共存的行向量[6,8,13,19]。已有RRAP问题的研究方法，主要是遗传算法、遗传算法与其它智能算法的混合算法，具有离散型特点和连续型特点的粒子群优化算法还没有。为行文紧凑起见，有关动态规划等传统方法以及后启发式算法，诸如，遗传算法、粒子群优化算法原理等可参考文献[24-32]。

表1 可靠性冗余分配问题（RAP）研究情况一览表

本文研究2-状态可靠性-冗余分配问题，设计了一个新的既具有离散型特点又具有连续型特点的混合型粒子群优化算法对RRAP问题进行求解，并通过对典型网络的模拟仿真，对算法的正确性和有效性进行了验证。

1 假设和模型

1.1 假设

（1）系统和元件有且仅有两个状态，即正常工作状态和失效状态；（2）系统中每个可供选择元件的可靠度、价格、重量和体积等已知；（3）各元件的失效是相互独立的；（4）失效的元件不可修复；（5）所有备选的元件都是有效的。

1.2 模型

设系统（可靠度为Rs）由n个子系统(可靠度为Ri)组成，整个系统的结构是复杂网络结构（由子系统及元件计算整个系统可靠度可参阅文献[33-39],这里不单独讨论），每个元件具有可靠度、价格和重量、体积，整个系统有费用、价格和体积等约束，确定构成系统元件的可靠度及冗余度，使得整个系统的可靠度最大，数学表示为：

其中，i=1，2，…，m，表示有m个约束，bi是常量，一般m=3，分别是重量、费用和体积约束；rj，xj表示第j个子系统的元件可靠度向量和冗余度向量；R，X分别表示整个系统的可靠度向量和元件冗余度向量。

2 解的结构与算法

2.1 解的结构

粒子群算法中的粒子（解）的构造为：[R，X]，即表示元件可靠度的行向量和表示元件冗余度的行向量X组成，也就是，行向量[R，X]的左边元素顺序是表示元件可靠度的实数变量（值介于0与1之间），右边元素是表示元件冗余度的整数变量。例如(具体见3.1)，R=[0.774，0.8736，0.9022，0.7115，0.7874]，X=[3，2，2，3，3]；即这里的一个粒子是[R，X]=[0.774，0.8736，0.9022，0.7115，0.7874，3，2，2，3，3]。

2.2 新解的生成算法

初始粒子为[R0，X0]，产生新解时，分别从R0，X0出发，产生新的可靠度向量R和冗余度向量X。

从X0出发，产生新的可靠度向量X算法：

按照均匀分布随机产生位于区间[varmin1，varmax1]的n个随机整数；varmin1 <=varmax1，n是元件个数，事实上X与X0无关）。

从R0出发，产生新的可靠度向量R算法：

按照均匀分布随机产生位于区间[varmin2，varmax2]的n个随机数（实数；0< varmin2<=varmax2<1，n是元件个数，事实上R与R0无关）。

2.3 适应值函数的确定

我们将有约束可靠性-冗余分配问题改造为无约束可靠性-冗余分配问题，为此，适应值函数修改如下：

这里α，β，γ是参数，C0，W0，V0分别是系统的费用、重量和体积限制，TC，TW，TV是当前解（R，X）下的系统费用、重量和体积。

2.4 两段迭代PSO算法

算法（伪Matlab代码）

从图1和表4可知：除经过大洋置换的压载水中3种致病菌的垂直分布与其他压载舱明显不同外，其他各压载舱中3种致病菌的垂直分布状况基本相同，即随着压载水深度的增加菌落数量逐渐增加，且在各水深中3种致病菌数量均是大肠埃希菌最多，副溶血弧菌次之，霍乱弧菌最少。

Step0（初始化）设定各元件初始可靠度和冗余度R0，X0，给定初始粒子[R0，X0]；以行向量的形式存储系统元件费用、重量、体积等参数；设定压缩常数c1，c2。

确定元件冗余度的上下界：varmin1与varmax1；确定元件可靠度的上下界varmin2与varmax2；确定元件冗余度（变量）收敛速度的上下界velmax1与velmin1；确定元件可靠度（变量）收敛速度的上下界velmax2与velmin2；n是元件个数，nc是粒子个数，令V=zeros(2n，nc)；E=X0；ER=R0；A=zeros(2n，nc)；B=zeros(2n，nc)；CA=zeros(1，nc)；CB=zeros(1，nc)；Z=zeros(1，nt)；这里nt是总迭代次数。

Step1随机产生满足系统约束条件的nc个粒子存于矩阵A中；并将对应的适应值存于CA中；再随机产生满足系统约束条件的nc个粒子存于矩阵B中；并将对应的适应值存于CB中。

Step2 for t=1：nt

计算动态权重wt，wt=0.9−0.5*(t−1)/nt，计算当前最优解的费用TC、重量TW和体积TV及适应值e；

将B的第k列前n个分量顺序赋给E，后n个分量顺序赋给ER。

3 模拟仿真

3.1 串联网络

问题描述如下[6]，在费用、重量和体积约束条件下，适当选择串并联系统元件的可靠度R和冗余度X，使得系统的可靠度最大：

其中参数如下：T=[2.33e-5，1.45e-5，5.41e-6，8.05e-5，1.95e-5]；U=[1.5，1.5，1.5，1.5，1.5]；tm=1000；W=[7，8，8，6，9]；P=[1，2，3，4，2]；C0=175，W0=200，V0=110。

设定算法其它参数为：varmin1=1，varmax1=3；velmax1=0.1，velmin1=-0.1；varmin2=0.7，varmax2=1；velmax2=0.1，velmin2=-0.1。

随机运行算法50次，结果如下：Rmax=0.931681；Rmin=0.929423；Ravg=0.931328，总体运行时间为408.069秒，最优解对应的R=[0.779274，0.872106，0.902881，0.711721，0.786822]；X=[3，2，2，3，3]，TC=175，TW=192.48，TV=83；结果与文献[8]用遗传算法求得的最优结果一致（文献[6]提供的结果有误），算法收敛曲线见图1。

图1 串联网络实例的算法收敛曲线

3.2 桥网络

桥网络（见图2）系统的约束条件与参数同3.1，令C0=175，W0=200，V0=110；系统的可靠度为:

图2 桥网络

公式（5）-（8）组成桥网络可靠度最大优化模型。

随机运行算法50次，运行结果为：Rmax=0.999889，Rmin=0.999644，Ravg=0.999824；总体运行时间为350.83秒，结果与文献[8]用遗传算法求得的最优结果一致，最优解对应的R=[0.823548，0.873216，0.853279，0.7，0.746630]；X=[3，3，3，3，1]，TC=175，TW=195.74，TV=92，算法收敛曲线见图2。

3.3 实验结果分析

RRAP问题是比较困难的组合优化问题，文献中除典型的串联网络模型、桥网络（复杂网络）模型外，很少见到其它用于测试的模型。本文给出的算法，经典型网络测试后，给出的测试结果同遗传算法、遗传算法与其它智能算法构成的混合算法等给出的测试结果是一致的。但我们给出的算法，具有原理容易理解、快速、便于微机实现等特点。

图3 桥网络实例的算法收敛曲线

4 结论

本文研究属于NP-Hard的可靠性-冗余分配（RRAP）问题的求解，设计了不同于文献[13,19]的，一个具有常量压缩系数，动态惯性因子的两段，同时具有离散型特点和连续型特点的粒子群优化算法，通过典型实例的计算机模拟仿真，验证了算法的正确性和有效性；算法具有原理容易理解，编程简单，运行高效的特点。本文算法也可以用于具有k-out-of-n类型子系统（k>1）的系统可靠性优化问题求解。