文／李东魁 乌兰图雅 朱艳龙
摘要：2-状态串-并联网络系统，单目标-单约束可靠性优化问题是NP-难的，有很多不同的智能优化算法求最优解，在实际应用中存在对不同类型的智能算法进行选择问题。本文通过运用常见的智能算法：模拟退火算法、蚁群算法、遗传算法、粒子群优化算法，对2-状态单目标-单约束串-并联系统可靠性模型用MATLAB编程求解，对算法参数、算法收敛性、算法执行时间等进行比较。计算机仿真结果表明，对给定的测试实例，蚁群算法、粒子群优化算法都快速的收敛到问题的最优解，而模拟退火算法、遗传算法虽然也能收敛到最优解，但较多情况下不能收敛到最优解。蚁群算法、粒子群优化算法在求解单目标-单约束串-并联网络可靠性优化问题中是更有效的工具。
教育期刊网 http://www.jyqkw.com
关键词 ：可靠性优化，串-并联网络，智能算法，算法收敛性，最优解
中文分类号：TP393 文献标识码：A
引言
系统可靠性是系统设计必须考虑的性能指标。可靠性优化是可靠性理论和工程中的重要研究领域，很多优化问题属于大规模非线性优化问题，属于NP-难的，传统的优化方法仅有少数算法被证明是有效的；20世纪80年代以来，一些新颖的优化算法，如人工神经网络、遗传算法、模拟退火、蚁群算法以及混合优化策略等，为解决复杂问题提供了新的思路与手段[1-4]。
2-状态网络系统构建过程中，人们除了关心系统的可靠度外，还要考虑元件的数量、体积、价格等因素[3]，从而可靠性优化模型可以分为：（1）构成系统的元件数量、价格、体积等不超过某一数量界限等约束条件，目标是选择合适的网络拓扑结构，使构造出来的系统具有最大可靠性（2）网络的拓扑结构具有相对固定的形状，且构成系统的可靠度满足一定的最低条件，目标是选择合适数量的元件、或适当分配具有不同可靠度的元件，使元件用量最少、或体积最小或价格最低等。可靠性优化问题也可分为[4]：（1）单目标的可靠性优化问题，进一步还可以分为冗余系统的可靠性优化问题、具有比较设计的可靠性优化问题、时间相关的可靠性分配优化问题、带有置信区间的可靠性优化问题（2）多目标的可靠性优化问题。
在实际应用中，存在着多种优化算法怎么样合理选择的问题。本文选择模拟退火算法、蚁群算法、遗传算法、粒子群优化算法，对选定可靠性优化模型的实例进行编程测试，模型属于2-状态串-并联、子系统元件都相同，不同子系统元件一般不相同的单目标-单约束、目标函数最小化可靠性优化问题。根据模拟仿真结果，对用常见智能算法求解网络可靠性优化问题算法的选择提出建议。
1、可靠性优化模型
1.1 假设
（1）研究的网络是2-状态网络。网络和构成网络的元件有且只有两种状态，即正常工作状态和失效状态。
（2）网络用一个无向图G =（V，E）表示，其中V表示网络结点集合，E代表边的集合。s是源结点，t是汇结点。
（3）结点是完全可靠的，永不失效。
（4）网络是耦合的（Coherent）。
（5）边的失效是统计独立的。某一边处于某种状态的概率是已知的。
1.2 模型
假设系统G=(V，E)由n个独立子系统组成，如图1所示，在每个子系统中使用相同的2-状态元件，Cn表示系统的总价格（这里仅仅考虑元件费用），R表示系统可靠性，ci表示第i种元件的单价，xi是第i个子系统第i种部件的个数，xi＞=1，R0是系统要达到预定的可靠度。
2、算法的实现
模拟退火算法、蚁群算法、遗传算法的原理、自然语言描述，请参阅高尚[3]等论文，粒子群优化算法请参阅王正初[5]等论文。用Matlab2008a编程，计算机上进行仿真(基本配置为CPUB960@2.2Ghz，2.2Ghz、内存4G、Windows 7操作系统)。
2.1 模拟退火算法
算法如图2所示。
3、仿真实例
设图1模型中，由5个子系统组成，每个子系统中元件的正常工作概率、开路失效概率和短路失效概率如下：p1=0.96，p2=0.93，p3=0.85，p4=0.80，p5=0.75；c1=3元，c2=12元，c3=8元， c4=5元，c5=10元，系统要求R0=0.9。
模拟退火算法测试结果： 取T = 1 0 0 0 0 0 0 ， T 0= 1 . 0 ，a=0.90，初始解为（4,4,4,4,4）（是可行解）。计算50次，计算最优解情况如下：最小费用是81元，最大费用103元；平均费用（近似最优费用）85.24元，算法平均执行时间0.1747秒，取得最优解20次，此时最优解为（2，2，2，3，2）。其中，模拟退火算法执行过程中产生的费用—迭代次数关系，如图6(a)所示。算法基本达到了高尚[3]等推荐的最好算法（蚁群算法）水平。蚁群算法的测试结果：取M=106，xm a x= 4 ， β = 0 . 9 ，[τij]4×5=[10]4×5，Q=10，初始解取（1,1,1,1,1）（不是可行解），计算50次，全部都收敛到最优解（2，2，2，3，2），最优解费用81元，算法平均执行时间0.3069秒。算法的收敛情况好于高尚[3]等推荐的最好算法（蚁群算法）水平，与王正初[5]等微粒群算法的效果相同。蚁群算法执行产生的费用—迭代次数关系，见图6(b)。
遗传算法的测试结果：取M=250，N=30，Pc= 0 . 2 ，Pm=0.5，遗传代数tt=100，t=1，初始解选为（4,4,4,4,4）。算法执行50次，计算最优解情况如下：最小费用是81元，最大费用93元；平均费用82.72元，算法平均执行时间0.8349秒，取得最优解34次，此时最优解为（2，2，2，3，2）。其中，遗传算法执行过程中产生的费用—迭代次数关系，如图6(c)所示。除了时间因素外，算法收敛情况好于高尚[3]等推荐的最好算法（蚁群算法）水平。
微粒群算法的测试结果：取加速度常数c1=c2=1.4962；种群规模N=20，进化最大代数Gmax=100，权重w满足：w=0.9-0.5*(t-1)/99 ，初始解为（4,4,4,4,4。算法执行50次，计算最优解情况如下：算法全部收敛到最优解（2，2，2，3，2），最小费用是81元，算法平均执行时间0.4272秒。其中，微粒群算法执行过程中产生的费用—迭代次数关系，如图6(d)所示。算法收敛情况好于高尚[3]等推荐的最好算法（蚁群算法）水平，与王正初[5]等算法收敛情况一致。
4、结论
本文对单目标-单约束串-并联网络可靠性优化模型，选择MATLAB为编程语言，对模拟退火算法、蚁群算法、遗传算法和微粒群算法进行了实现，模拟仿真发现：尽管网络可靠性优化模型属于NP-难问题，但合理选择不同算法的参数，研究的几个智能算法都能有效的对模型进行求解。考虑到收敛性，蚁群算法与微粒群算法都能全部收敛到最优解，而蚁群算法所用平均时间更少。单纯考虑求得最优解算法平均使用的时间，模拟退火算法的收敛速度是最快的。另外，算法的收敛性受算法在解空间中查找新解的方式影响。