单目标?多条件约束S?P网络可靠性优化的微粒群算法
摘 要： 研究2?状态单目标?多条件约束串?并联（S?P）网络的可靠性优化问题（RAP）。设计了具有压缩系数的离散型微粒群算法进行求解，采用Matlab编程对问题实例进行模拟仿真，结果表明，对于合理选择的初始解与算法参数，微粒群算法每次运行都收敛，并且能够收敛到最优解。通过与传统的智能算法（模拟退火算法、蚁群算法、遗传算法）比较，微粒群算法具有初始解容易选择、参数易于设置，收敛性好、收敛快的优势。
关键词： 多条件约束； 串?并联网络； 微粒群算法； 可靠性优化； 模拟仿真； 智能算法
中图分类号： TN911.1?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）01?0089?04
Abstract： The reliability optimization problem of the 2?state single?objective and multi?condition constraint series?parallel （S?P） network is studied. The discrete particle swarm optimization algorithm with compression coefficient was designed to solve the above problem. The instance with the problem is simulated with Matlab programming. The simulation results show that， for the reasonably?selected initial solution and algorithm parameter， the particle swarm optimization algorithm has convergence for each operation， and can converge to the optimal solution. In comparison with the traditional intelligent algorithms such as simulated annealing algorithm， ant colony algorithm and genetic algorithm， the particle swarm optimization algorithm has the advantages of easy selection for initial solution， easy setting for parameters， good convergence and fast convergence rate.
Keywords： multi?condition constraint； series?parallel network； particle swarm optimization algorithm； reliability optimization； analog simulation； intelligent algorithm
0 引 言
在实际问题中有着广泛应用的2?状态系统可靠性优化问题已经取得了丰硕的研究成果[1?10]，最优冗余问题（RAP）更是得到了广泛深入的研究[1?6]。由于RAP问题是NP?Hard的，最优化领域中有无免费午餐定理[11]的存在，针对特定RAP的实例，设计、选择有效算法具有理论与实际意义。
RAP属于非线性规划问题，具有多种方法可供选择：启发式方法、整数规划方法、动态规划方法、几何规划方法、广义的拉格朗日函数法、人工神经网络、模拟退火算法、遗传算法、蚁群算法、微粒群算法等[1?10]。
本文研究文献[6]模型的粒子群优化算法，并对问题实例用Matlab编程，进行模拟仿真，实验结果说明，粒子群优化算法在求解这类特定问题时，具有容易实现，收敛性好，收敛速度快的优势。
1 模型与解的构造
系统由[n]个子系统串联组成，每个子系统又是由选出的不同类型的元件并联构成，在有费用和重量约束条件下，选择合适的元件类型与数目使得整个系统的可靠度最大，具体假设和符号见文献[6]。
模型的数学表达式为：
[maxR=i=1nR（i），s.t. i=1nC（i）≤C， i=1nW（i）≤W] （1）
式中：[R（i）=1-j=1ai（1-rij）xij，][xi1+xi2+…+xij+…+xiai≤nmax，][rij]是子系统[i]的总共为[ai]种元件的第[j]种元件的可靠性，[xij]是对应选择元件（并联）的个数；[nmax]是子系统冗余元件的最大个数；[R]是系统可靠度；[R（i），C（i），W（i）]分别是子系统[i]的可靠度、费用和重量；[C，W]是系统的费用和重量约束的上限。为方便用微粒群算法对模型求解，构造微粒（解）[X]如下：
[X=[x11，x12，…，x1a1，…，xi1，xi2，…，xiai，…，xn1，…，xnan]]
即各子系统的元件选择个数为分量组合构成。
2 具有收缩系数的离散粒子群优化算法
微粒群算法有关知识请参阅文献[11]。这里给出用于求目标函数最大的具有收缩系数的离散粒子群优化算法。为方便算法描述，引入目标函数如下：
[f（X）=R-M*min0，i=1nC（i）2-M*min0，i=1nW（i）2] （2）
式中[M]为正整数。
算法的具体描述如下：
Step1（初始化）：确定种群规模[N，]最大迭代次数[Gmax，]惯性权重[w，]速度常数[c1，c2]等参数，产生两组粒子群[Xi]和[X′i，]分别存放粒子的位置和粒子的历史最优位置，初始速度[Vii=1，2，…，N，]一个全局粒子[P]（群体的最优位置）；计算每个粒子对应的可靠度，判断是否满足费用和重量约束条件，若不满足，则生成一个新粒子，直到满足约束条件；根据式（2）计算目标函数值。
Step2（更新个体和全局位置）：如果[Xi]的目标函数值大于[X′i]的目标函数值，则用[Xi]替换[X′i]；如果[X′i]的目标函数值大于[P]的目标函数值，则用[X′i]代替[P。]
Step3：根据式（3）～式（4）更新速度和粒子位置：
[vt+1id=w*vtid+c1*rand（ ）（pid-xtid）+c*2rand（ ）（pgt-xtid）] （3）
[xt+1id=int（xtid+vt+1id）] （4）
式中：[int（x）]为取整函数，Matlab中[floor（x），fix（x），round（x），][ceil（x）]可供选择。
Step4：计算每个粒子对应的可靠度，判断是否满足费用和重量约束，否则按照式（3）～式（4）调整，直到满足约束条件。
Step5：计算每个粒子对应的目标函数值。
Step6：判断迭代次数[G]是否达到了最大迭代次数[Gmax，]如果是，输出找到的最优解；否则，[G=G+1，]转Step2。
有关算法的收敛性討论与证明请参阅文献[11]。
3 模拟仿真
3.1 实例1
假设系统由3个子系统组成，每个子系统都有5种类型的元件供选择，每个子系统可供选择的元件的可靠性、费用和重量数据[6]见表1。
如果要求系统总费用[C≤30]元，总重量[W≤53]kg，[nmax≤5。]算法参数设置为：[M=100，][N=20，][Gmax=200，]惯性权重从0.9线性的减少为0.4，速度常数[c1=c2=3，]选择初始解为[X0=][0，0，0，0，0，0，0，0，0，0，0，0，0，0，0]。
算法求得的最优解为：[X=0 ，2，0，0，00，2，1，0，00，][0，0，0，5 ，]即子系统1由5种可选择的元件中第2类2个并联组成，子系统2由5种可选择的元件中第2类2个、第3类1个并联组成，子系统3由5种可选择的元件中第5类5个元件并联组成。此时系统最大可靠度为0.982 2，系统费用为30元，系统重量为50 kg，本文最优解优于文献[6]的0.981 6，算法运行时间也极大的减少。随机运行50次算法，结果为：可靠性最大为0.982 2（3次），最小为0.969 4，平均为0.976 7，总时间为46.121 7 s。
3.2 实例2
系统由15个子系统组成，每个子系统都由相同元件组成，每个子系统元件的可靠性、费用与重量[12]见表2。
如果要求系统总费用[C≤400]元，总重量[W≤414]kg，[nmax≤6。]算法参数设置为：[M=100，][N=20，][Gmax=300，]惯性权重从0.9线性地减少为0.4，速度常数[c1=c2=1.496 3，]选择初始解为[X0=][2，2，2，2，2，2，2，2，2，2，2，2，2，2，2]。
算法求得的最优解为：[X=][3，4，6，4，3，2，4，5，4，2，3，4，5，4，5]，此时系统最大可靠度为0.945 6，系统费用为392元，系统重量为414 kg，本文算法运行时间极大地减少。随机运行50次算法，结果为：可靠性最大为0.945 6（3次），最小为0.932 4，平均为0.941 1，总时间为104.198 4 s。
4 算法比较
为了比较算法的有效性，对实例1～2分别采用模拟退火算法、遗传算法[13]和蚁群算法[6，13]用Matlab编程求解，求解情况见表3，表4。表3中，虽然蚁群算法[6]收敛性非常好，但算法运行时间偏长，另外，对[nmax≤5]的问题容易编程。从能够求得最好解，并具有较好的收敛性，花费系统时间较少的角度看，微粒群算法都是较好的。
5 结 论
本文给出求解子系统具有不同类型元件并联，子系统再串联形成系统，并且元件和系统都具有费用和重量约束，选择元件类型和数量使得系统可靠度最大的2?状态单目标?多约束网络可靠性优化问题的粒子群优化算法，经过模拟仿真与经典智能算法比较，粒子群优化算法是求解这类问题的有效工具。
参考文献
[1] MITSUO G， YUN Y S. Soft computing approach for reliability optimization： state?of?the?art survey [J]. Reliability engineering & system safety， 2006， 91： 1008?1026.
[2] LIANG Y C， WU C C. A variable neighbourhood descent algorithm for the redundancy allocation problem [J]. IEMS， 2005， 4（1）： 94?101.
[3] LIANG Y C. An ant colony optimization algorithm for the redundancy allocation problem [J]. IEEE transactions on reliability， 2004， 53（4）： 417?423.
[4] PHAKHAPONG T， WORAWAT S， APINAN A， et al. Improved ant colony optimization for solving reliability redundancy allocation problems [J]. International journal of computer， information science and engineering， 2013， 7（2）： 130?135.
[5] COIT D W， SMITH A E. Reliability optimization of series?parallel systems using a genetic algorithm [J]. IEEE transactions on reliability， 1996， 45（2）： 254?260.
[6] 程世娟，卢伟，何平.蚁群算法在冗余系统可靠性最优分配上的应用[J].计算机工程与应用，2009，45（15）：64?66.
CHENG Shijuan， LU Wei， HE Ping. Application of ant colony algorithm in the optimal allocation of redundant system reliability [J]. Computer engineering and applications， 2009， 45（15）： 64?66.
[7] GARG H， SHARMA S P. Multi?objective reliability?redundancy allocation problem using particle swarm optimization [J]. Computers & industrial engineering， 2013， 64（1）： 247?255.
[8] AGHAEI M， HAMADANI A Z， ARDAKAN M A. Redundancy allocation problem for k?out?of?n， systems with a choice of redundancy strategies [J]. Journal of industrial engineering international， 2017， 13（1）： 81?92.
[9] SHEIKHPOUR S， MAHANI A. Particle swarm optimization with intelligent mutation for nonlinear mixed?integer reliability?redundancy allocation [J]. International journal of computational intelligence & applications， 2017， 16（1）： 1?21.
[10] FEIZABADI M， JAHROMI A E. A new model for reliability optimization of series?parallel systems with non?homogeneous components [J]. Reliability engineering & system safety， 2016， 157： 101?112.
[11] 曾建潮，介婧，崔志华.微粒群算法[M].北京：科學出版社，2004.
ZENG Jianchao， JIE Jing， CUI Zhihua. Particle swarm optimization algorithm [M]. Beijing： Science Press， 2004.
[12] WONG J Y. A note on solving a system reliability problem [J]. Microelectronics reliability， 1993， 33（8）： 1045?1051.
[13] 高尚，杨静宇，吴小俊，等.可靠性优化的蚁群算法[J].计算机应用与软件，2004，21（12）：94?96.
GAO Shang， YANG Jingyu， WU Xiaojun， et al. Ant colony algorithm for reliability optimization [J]. Computer application and software， 2004， 21（12）： 94?96.
[14] 李东魁，董海.非相同元件并联的S?P网络可靠性优化研究[J].阴山学刊（自然科学版），2016，30（2）：35?41.
LI Dongkui， DONG Hai. Reliability optimization of S?P networks in parallel with non?identical components [J]. Yinshan Academic Journal （natural science edition）， 2016， 30（2）： 35?41.
[15] 乌兰图雅，李东魁，其木格.相异元件并联的可靠性优化模型[J].内蒙古师范大学学报（自然科学汉文版），2015，44（6）：761?764.
WULAN Tuya， LI Dongkui， QI Muge. Reliability optimization model in parallel with non?identical components [J]. Journal of Inner Mongolia Normal University （Chinese edition of natural science）， 2015， 44（6）： 761?764.
关键词： 多条件约束； 串?并联网络； 微粒群算法； 可靠性优化； 模拟仿真； 智能算法
中图分类号： TN911.1?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）01?0089?04
Abstract： The reliability optimization problem of the 2?state single?objective and multi?condition constraint series?parallel （S?P） network is studied. The discrete particle swarm optimization algorithm with compression coefficient was designed to solve the above problem. The instance with the problem is simulated with Matlab programming. The simulation results show that， for the reasonably?selected initial solution and algorithm parameter， the particle swarm optimization algorithm has convergence for each operation， and can converge to the optimal solution. In comparison with the traditional intelligent algorithms such as simulated annealing algorithm， ant colony algorithm and genetic algorithm， the particle swarm optimization algorithm has the advantages of easy selection for initial solution， easy setting for parameters， good convergence and fast convergence rate.
Keywords： multi?condition constraint； series?parallel network； particle swarm optimization algorithm； reliability optimization； analog simulation； intelligent algorithm
0 引 言
在实际问题中有着广泛应用的2?状态系统可靠性优化问题已经取得了丰硕的研究成果[1?10]，最优冗余问题（RAP）更是得到了广泛深入的研究[1?6]。由于RAP问题是NP?Hard的，最优化领域中有无免费午餐定理[11]的存在，针对特定RAP的实例，设计、选择有效算法具有理论与实际意义。
RAP属于非线性规划问题，具有多种方法可供选择：启发式方法、整数规划方法、动态规划方法、几何规划方法、广义的拉格朗日函数法、人工神经网络、模拟退火算法、遗传算法、蚁群算法、微粒群算法等[1?10]。
本文研究文献[6]模型的粒子群优化算法，并对问题实例用Matlab编程，进行模拟仿真，实验结果说明，粒子群优化算法在求解这类特定问题时，具有容易实现，收敛性好，收敛速度快的优势。
1 模型与解的构造
系统由[n]个子系统串联组成，每个子系统又是由选出的不同类型的元件并联构成，在有费用和重量约束条件下，选择合适的元件类型与数目使得整个系统的可靠度最大，具体假设和符号见文献[6]。
模型的数学表达式为：
[maxR=i=1nR（i），s.t. i=1nC（i）≤C， i=1nW（i）≤W] （1）
式中：[R（i）=1-j=1ai（1-rij）xij，][xi1+xi2+…+xij+…+xiai≤nmax，][rij]是子系统[i]的总共为[ai]种元件的第[j]种元件的可靠性，[xij]是对应选择元件（并联）的个数；[nmax]是子系统冗余元件的最大个数；[R]是系统可靠度；[R（i），C（i），W（i）]分别是子系统[i]的可靠度、费用和重量；[C，W]是系统的费用和重量约束的上限。为方便用微粒群算法对模型求解，构造微粒（解）[X]如下：
[X=[x11，x12，…，x1a1，…，xi1，xi2，…，xiai，…，xn1，…，xnan]]
即各子系统的元件选择个数为分量组合构成。
2 具有收缩系数的离散粒子群优化算法
微粒群算法有关知识请参阅文献[11]。这里给出用于求目标函数最大的具有收缩系数的离散粒子群优化算法。为方便算法描述，引入目标函数如下：
[f（X）=R-M*min0，i=1nC（i）2-M*min0，i=1nW（i）2] （2）
式中[M]为正整数。
算法的具体描述如下：
Step1（初始化）：确定种群规模[N，]最大迭代次数[Gmax，]惯性权重[w，]速度常数[c1，c2]等参数，产生两组粒子群[Xi]和[X′i，]分别存放粒子的位置和粒子的历史最优位置，初始速度[Vii=1，2，…，N，]一个全局粒子[P]（群体的最优位置）；计算每个粒子对应的可靠度，判断是否满足费用和重量约束条件，若不满足，则生成一个新粒子，直到满足约束条件；根据式（2）计算目标函数值。
Step2（更新个体和全局位置）：如果[Xi]的目标函数值大于[X′i]的目标函数值，则用[Xi]替换[X′i]；如果[X′i]的目标函数值大于[P]的目标函数值，则用[X′i]代替[P。]
Step3：根据式（3）～式（4）更新速度和粒子位置：
[vt+1id=w*vtid+c1*rand（ ）（pid-xtid）+c*2rand（ ）（pgt-xtid）] （3）
[xt+1id=int（xtid+vt+1id）] （4）
式中：[int（x）]为取整函数，Matlab中[floor（x），fix（x），round（x），][ceil（x）]可供选择。
Step4：计算每个粒子对应的可靠度，判断是否满足费用和重量约束，否则按照式（3）～式（4）调整，直到满足约束条件。
Step5：计算每个粒子对应的目标函数值。
Step6：判断迭代次数[G]是否达到了最大迭代次数[Gmax，]如果是，输出找到的最优解；否则，[G=G+1，]转Step2。
有关算法的收敛性討论与证明请参阅文献[11]。
3 模拟仿真
3.1 实例1
假设系统由3个子系统组成，每个子系统都有5种类型的元件供选择，每个子系统可供选择的元件的可靠性、费用和重量数据[6]见表1。
如果要求系统总费用[C≤30]元，总重量[W≤53]kg，[nmax≤5。]算法参数设置为：[M=100，][N=20，][Gmax=200，]惯性权重从0.9线性的减少为0.4，速度常数[c1=c2=3，]选择初始解为[X0=][0，0，0，0，0，0，0，0，0，0，0，0，0，0，0]。
算法求得的最优解为：[X=0 ，2，0，0，00，2，1，0，00，][0，0，0，5 ，]即子系统1由5种可选择的元件中第2类2个并联组成，子系统2由5种可选择的元件中第2类2个、第3类1个并联组成，子系统3由5种可选择的元件中第5类5个元件并联组成。此时系统最大可靠度为0.982 2，系统费用为30元，系统重量为50 kg，本文最优解优于文献[6]的0.981 6，算法运行时间也极大的减少。随机运行50次算法，结果为：可靠性最大为0.982 2（3次），最小为0.969 4，平均为0.976 7，总时间为46.121 7 s。
3.2 实例2
系统由15个子系统组成，每个子系统都由相同元件组成，每个子系统元件的可靠性、费用与重量[12]见表2。
如果要求系统总费用[C≤400]元，总重量[W≤414]kg，[nmax≤6。]算法参数设置为：[M=100，][N=20，][Gmax=300，]惯性权重从0.9线性地减少为0.4，速度常数[c1=c2=1.496 3，]选择初始解为[X0=][2，2，2，2，2，2，2，2，2，2，2，2，2，2，2]。
算法求得的最优解为：[X=][3，4，6，4，3，2，4，5，4，2，3，4，5，4，5]，此时系统最大可靠度为0.945 6，系统费用为392元，系统重量为414 kg，本文算法运行时间极大地减少。随机运行50次算法，结果为：可靠性最大为0.945 6（3次），最小为0.932 4，平均为0.941 1，总时间为104.198 4 s。
4 算法比较
为了比较算法的有效性，对实例1～2分别采用模拟退火算法、遗传算法[13]和蚁群算法[6，13]用Matlab编程求解，求解情况见表3，表4。表3中，虽然蚁群算法[6]收敛性非常好，但算法运行时间偏长，另外，对[nmax≤5]的问题容易编程。从能够求得最好解，并具有较好的收敛性，花费系统时间较少的角度看，微粒群算法都是较好的。
5 结 论
本文给出求解子系统具有不同类型元件并联，子系统再串联形成系统，并且元件和系统都具有费用和重量约束，选择元件类型和数量使得系统可靠度最大的2?状态单目标?多约束网络可靠性优化问题的粒子群优化算法，经过模拟仿真与经典智能算法比较，粒子群优化算法是求解这类问题的有效工具。
参考文献
[1] MITSUO G， YUN Y S. Soft computing approach for reliability optimization： state?of?the?art survey [J]. Reliability engineering & system safety， 2006， 91： 1008?1026.
[2] LIANG Y C， WU C C. A variable neighbourhood descent algorithm for the redundancy allocation problem [J]. IEMS， 2005， 4（1）： 94?101.
[3] LIANG Y C. An ant colony optimization algorithm for the redundancy allocation problem [J]. IEEE transactions on reliability， 2004， 53（4）： 417?423.
[4] PHAKHAPONG T， WORAWAT S， APINAN A， et al. Improved ant colony optimization for solving reliability redundancy allocation problems [J]. International journal of computer， information science and engineering， 2013， 7（2）： 130?135.
[5] COIT D W， SMITH A E. Reliability optimization of series?parallel systems using a genetic algorithm [J]. IEEE transactions on reliability， 1996， 45（2）： 254?260.
[6] 程世娟，卢伟，何平.蚁群算法在冗余系统可靠性最优分配上的应用[J].计算机工程与应用，2009，45（15）：64?66.
CHENG Shijuan， LU Wei， HE Ping. Application of ant colony algorithm in the optimal allocation of redundant system reliability [J]. Computer engineering and applications， 2009， 45（15）： 64?66.
[7] GARG H， SHARMA S P. Multi?objective reliability?redundancy allocation problem using particle swarm optimization [J]. Computers & industrial engineering， 2013， 64（1）： 247?255.
[8] AGHAEI M， HAMADANI A Z， ARDAKAN M A. Redundancy allocation problem for k?out?of?n， systems with a choice of redundancy strategies [J]. Journal of industrial engineering international， 2017， 13（1）： 81?92.
[9] SHEIKHPOUR S， MAHANI A. Particle swarm optimization with intelligent mutation for nonlinear mixed?integer reliability?redundancy allocation [J]. International journal of computational intelligence & applications， 2017， 16（1）： 1?21.
[10] FEIZABADI M， JAHROMI A E. A new model for reliability optimization of series?parallel systems with non?homogeneous components [J]. Reliability engineering & system safety， 2016， 157： 101?112.
[11] 曾建潮，介婧，崔志华.微粒群算法[M].北京：科學出版社，2004.
ZENG Jianchao， JIE Jing， CUI Zhihua. Particle swarm optimization algorithm [M]. Beijing： Science Press， 2004.
[12] WONG J Y. A note on solving a system reliability problem [J]. Microelectronics reliability， 1993， 33（8）： 1045?1051.
[13] 高尚，杨静宇，吴小俊，等.可靠性优化的蚁群算法[J].计算机应用与软件，2004，21（12）：94?96.
GAO Shang， YANG Jingyu， WU Xiaojun， et al. Ant colony algorithm for reliability optimization [J]. Computer application and software， 2004， 21（12）： 94?96.
[14] 李东魁，董海.非相同元件并联的S?P网络可靠性优化研究[J].阴山学刊（自然科学版），2016，30（2）：35?41.
LI Dongkui， DONG Hai. Reliability optimization of S?P networks in parallel with non?identical components [J]. Yinshan Academic Journal （natural science edition）， 2016， 30（2）： 35?41.
[15] 乌兰图雅，李东魁，其木格.相异元件并联的可靠性优化模型[J].内蒙古师范大学学报（自然科学汉文版），2015，44（6）：761?764.
WULAN Tuya， LI Dongkui， QI Muge. Reliability optimization model in parallel with non?identical components [J]. Journal of Inner Mongolia Normal University （Chinese edition of natural science）， 2015， 44（6）： 761?764.
