基于MATLAB的串并联网络可靠性优化智能算法比较研究.doc

基于MATLAB的串并联网络可靠性优化智能算法比较研究 文李东魁乌兰图雅朱艳龙 摘要：2-状态串-并联网络系统，单目标-单约束可靠性优化问题是NP-难的，有很多不同的智能优化算法求最优解，在实际应用中存在对不同类型的智能算法进行选择问题。本文通过运用常见的智能算法：模拟退火算法、蚁群算法、遗传算法、粒子群优化算法，对2-状态单目标-单约束串-并联系统可靠性模型用MATLAB编程求解，对算法参数、算法收敛性、算法执行时间等进行比较。计算机仿真结果表明，对给定的测试实例，蚁群算法、粒子群优化算法都快速的收敛到问题的最优解，而模拟退火算法、遗传算法虽然也能收敛到最优解，但较多情况下不能收敛到最优解。蚁群算法、粒子群优化算法在求解单目标-单约束串-并联网络可靠性优化问题中是更有效的工具。 关键词：可靠性优化，串-并联网络，智能算法，算法收敛性，最优解 中文分类号：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等论文。用Matlabxxa编程，计算机上进行仿真(基本配置为CPUB9602.2Ghz，2.2Ghz、内存4G、Windows7操作系统)。 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=1000000，T0=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，xmax=4，=0.9，ij45=1045，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-难问题，但