标题 | RRAP优化问题的HSO算法研究 |
范文 | 摘要:RRAP优化问题是决策变量为元件可靠度及元件冗余度的可靠性优化问题,数学模型是非线性混合整数规划问题,属于NP-hard问题类。混合种群优化(简写为HSO)算法具有结构简单、运行高效的特点,继承了模拟退火算法SA、粒子群优化算法PSO、简化群优化算法SSO等算法的优点。该文设计了一个两段混合粒子群优化HSO算法,用于求解RRAP优化问题;通过模拟仿真,验证了所给HSO算法的正确性和有效性;研究结果表明:混合粒子群优化HSO算法是解决RRAP问题的一种有效工具。 关键词:可靠性-冗余分配问题(RRAP);混合种群优化(HSO);编码;算法;收敛 中图分类号:TP391.9,TP18? ? ? 文献标识码:A 文章编号:1009-3044(2021)15-0020-03 1 背景 可靠性-冗余分配问题(RRAP)是可靠性冗余分配问题(RAP)中的一种重要类型,数学模型是非线性整数混合规划问题,传统的求解方法,比如动态规划法、替代约束法等的应用受到限制,后启发式算法,如,遗传算法、粒子群优化算法等成为有效的求解手段。 广义可靠性冗余分配问题(GRAP)和具有多种混合策略的网络可靠性优化模型的出现,成为可靠性冗余分配问题的新发展方向,而混合后启发式算法成为求解可靠性冗余分配问题的新手段。这里GRAP问题是指在子系统中允许不同种类的元件可以混合的RAP问题,而混合后启发式算法是指在算法中同时采用两种以上后启发式算法机制的后启发式算法。混合种群算法(HSO)在求解GRAP问题中具有很好的表现,本文用改进的HSO算法求解较为复杂的RRAP问题。 2 假设和模型 2.1 假设 1)系统和元件有且仅有正常工作和失效两个状态;2)每个元件的可靠度、价格和重量已知;3)系统中各元件的失效是统计独立的;4)失效的元件不可修复;5)所有备选的元件都是有效的。 2.2 模型 设系统(可靠度为Rs)由n个子系统(可靠度为Ri)组成,整个系统的结构是S-P结构或复杂网络结构(由子系统及元件计算整个系统可靠度可参阅文献,这里不单独讨论),每个元件具有可靠度、价格和重量、体积,整个系统有费用、价格和体积约束,确定构成系统元件的可靠度及冗余度,使得整个系統的可靠度最大,数学表达式为: 其中,i=1,2,…,m,表示有m个约束,bi是常量,一般m=3,分别是重量、费用和体积约束;rj,xj表示第j个子系统的元件可靠度向量和冗余度向量;R,X分别表示整个系统的可靠度向量和元件冗余度向量。 3 算法 3.1 解的编码 在混合种群优化(HSO)算法中,粒子(解)的构造为:[R,X],即由表示元件可靠度的实数组成的行向量和表示元件冗余度的正整数行向量X组成,也就是,行向量[R,X]的左边一半元素顺序是表示元件可靠度的实数变量(值介于0与1之间),右边一半元素是表示元件冗余度的正整数变量。例如,R= [0.775,0.8737,0.9023,0.7116,0.7875], X=[3,2,2,3,3]; 即这里的一个粒子(解)的编码是[R,X]=[ 0.775,0.8737,0.9023,0.7116,0.7875, 3,2,2,3,3]。 3.2 新解的生成算法 设元件冗余度向量X中,分量的变化范围为[var1,var2],其中var1,var2为两个正整数,且var1<=var2,则产生一个新的元件冗余度向量的算法为: 算法1 按照均匀分布随机数产生算法,随机产生|X|个位于区间[var1,var2]中的随机正整数。其中|X|表示向量X的基数,即需要确定冗余度的元件个数。 设元件的可靠度向量R中,分量的变化范围为[r0,1], r0是个大于0,小于1的实数(一般通过实验确定),则产生一个新的元件的可靠度向量的算法为: 算法2 按照均匀分布随机数产生算法,随机产生|X|个位于区间[r0,1]中的随机实数。 3.3 适应值函数 为应用混合种群优化(HSO)算法求解RRAP问题,需要将有约束的优化问题(1)-(2)转换为无约束的优化问题,为此,引入适应值函数如下: 这里α,β,γ是参数,C0,W0,V0分别是系统的费用、重量和体积限制,TC,TW,TV是当前解(R,X)下的系统费用、重量和体积。 基本混合种群优化HSO算法的描述,算法的原理、正确性和有效性证明,请参阅文献,这里我们给出改进的HSO算法,用于求解RRAP问题。 3.4 两段HSO算法 算法3(伪Matlab代码) Step0(初始化)以行向量的形式存储系统元件费用、重量、体积等参数;设定压缩常数c1=c2=0.5,惯性权重w=0.9。 确定元件冗余度的上下界:varmax1与varmin1;确定元件可靠度的上下界varmax2与varmin2; 确定元件冗余度(变量)收敛速度的上下界velmax1与velmin1;确定元件可靠度(变量)收敛速度的上下界velmax2与velmin2; n 是元件个数,nc 是粒子个数,令 V=zeros(2n,nc); A=zeros(2n,nc);? B=zeros(2n,nc); CA=zeros(1, nc); Z=zeros(1,nt);这里nt是总迭代次数。 Step1随机产生满足系统约束条件的nc个粒子存于矩阵A中;并将对应的适应值存于CA中;再将矩阵A存于矩阵B中(每个粒子的当前最优初始值)。 Step2利用矩阵A,求出当前系统的全局最优值[Xgbest,Rgbest],即Rgbest是元件全局最优可靠度向量,Xgbest是元件全局最优冗余度向量。 Step3 for t=1:nt Step3.1 % 对种群A中的每个粒子(解),按照PSO算法迭代公式修订后的新值存于矩阵Y中,然后按照阶跃函数修订每个解。 for j=1:nc for i=1:n V(i,j)=wV(i,j)+c1rand(B(i,j)-A(i,j))+c2rand(Xgbest(1,i)-A(i,j)); V(i+n,j)=wt*V(i+n,j)+c1rand(B(i+n,j)-A(i+n,j))+c2rand(Rgbest(1,i)-A(i+n,j)); if(V(i,j)< velmin1) V(i,j)= velmin1; end if(V(i,j)> velmax1) V(i,j)= velmax1; end if(V(i+n,j)< velmin2) V(i+n,j)= velmin2; end if(V(i+n,j)> velmax2) V(i+n,j)= velmax2; end Y(i,j)=round(A(i,j)+V(i,j)); Y(i+n,j)=(A(i+n,j)+V(i+n,j)); if(Y(i,j)< varmin1) Y(i,j)= varmin1; end if(Y(i,j)> varmax1) Y(i,j)= varmax1; end if(Y(i+n,j)< varmin2) Y(i+n,j)= varmin2; end if(Y(i+n,j)> varmax2) Y(i+n,j)= varmax2; end end m=rand(1); if(m>=0)&&(m<0.55) A(i,j)=Xgbest(1,i); A(i+n,j)=Rgbest(1,i); else if(m>=0.55)&&(m<0.75) A(i,j)=B(i,j); A(i+n,j)=B(i+n,j); else if(m>=0.75)&&(m<0.95) A(i,j)=Y(i,j); A(i+n,j)=Y(i+n,j); else if(m>=0.95)&&(m<1) A(i,j)=randi([varmin1, varmax1]); A(i+n,j)= varmin2+( varmax2 -varmin2)*rand([1,1]); end end end end end step3.2 對A中的每个当前解X,其对应的修订解Y,如果Y的适应值大于X的适应值,则将X替换为Y;否则,如果rand(1)>k(t),(delt=X的适应值 - Y的适应值;? k(t)= cos (3.1416 * delt^0.25*t^2/(1*10^6)) ; )则将X替换为Y。 step3.3 如果A中每个当前粒子的适应值大于这个粒子的当前最优值的适应值,则将这个粒子的当前位置最优值进行更新;如果这个粒子的当前最优值的适应值大于全局最优解的适应值,则将全局最优解进行更新。 Step3.4 记录最优解对应的可靠度。 Step4输出最优解及对应的费用、重量和体积约束、最优解可靠度;画出收敛曲线。 Step5算法终止。 4 模拟仿真 为证实算法的正确性和有效性,选择文献中的典型算例进行模拟仿真。测试都是在微型计算机上进行的;计算机配置为:CPU为Intel(R)Core(TM)i5-6500@3.20Ghz 3.20Ghz,内存8GB,硬盘600Gb;操作系统为Windows10专业版;编程软件为MatlabR2015b。算法参数的设置为:n=5,c1=c2=0.5;w=0.9, nc=200, nt=1000,α=β=γ=2。 4.1 串联系统 问题出现在文献[6]中,具体描述如下:在费用、重量和体积约束条件下,适当选择串并联系统元件的可靠度R和冗余度X,使得系统的可靠度最大: [maxfR,X=i=1n(1-(1-Ri)xi)]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (4) s.t. [? ? ?i=1nTi-tmlnRiUi(Xi+exp (Xi4))≤C0]? ? ? ?(5) [? ? ? ? ? ? ?i=1nwiXiexp (Xi4)≤W0]? ? ? ? ? ? ? ? ? ? ? ? (6) [i=1npiXi2≤V0]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (7) 其中参数如下: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.93168;Rmin=0.90068;Ravg=0.92844,总体运行时间为827.72秒,最优解对应的R=[0.77935,0.87126,0.90255,0.711870.78855]; X=[3,2,2,3,3], TC=175,TW=192.48,TV=83;用遗传算法求得的最优结果一致,算法收敛曲线见图1. 4.2 复杂网络 桥网络(见图2)系统的约束条件与参数同上述串联系统3.1,令C0=175,W0=200,V0=110;系统的可靠度为: [RsR,X=R1R2+R3R4+R1R4R5+R2R3R5-R1R2R3R4-R1R2R3R5-R1R2R4R5-R1R3R4R5-R2R3R4R5]+[2R1R2R3R4R5]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (8) 公式(5)-(8)组成桥网络可靠度最大优化模型。 随机运行算法50次,运行结果为:Rmax=0.999889;Rmin=0.999414;Ravg=0.999863,总体运行时间为450.84秒,用遗传算法求得的最优结果一致问题3提供的可靠性表达式有误,结果仅做参考,与其提供的GA-PSO算法,PSO算法计算结果最好解,至小数点后6位是一致的),最优解对应的R=[0.817553, 0.868652, 0.857783, 0.710507, 0.750068];? X=[3,3,3,3,1],TC=175,TW=195.74,TV=92. 5 结束语 本文通过模拟仿真,发现混合种群优化算法HSO在求解RRAP问题时,表现出了较好的性能,原因是它继承了SSO、SA与PSO等算法的优点,是典型的混合型后启发式算法。我们也发现,算法在解决特定问题的时候,与PSO等算法比,并没有体现出更多的优越性,比如,算法的执行时间有所增加,计算最优结果的精度上也没有显著的提高,个别情况下,还会出现非可行解的现象,即不能保证每次运行算法都收敛到可行解。 参考文献: [1] Beji N,Jarboui B,Eddaly M,et al.A hybrid particle swarm optimization algorithm for the redundancy allocation problem[J].Journal of Computational Science,2010,1(3):159-167. [2] Coelho L D S.An efficient particle swarm approach for mixed-integer programming in reliability-redundancy optimization applications[J].Reliability Engineering & System Safety,2009,94(4):830-837. [3] 徐沾杰,馬昌文,梅启智,等.用遗传算法求解一个系统可靠性优化问题[J].清华大学学报(自然科学版),1998(7): 54-57. [4] 张铁柱,滕春贤,韩志刚.遗传算法在系统可靠性优化中的应用[J].控制与决策,2002,(3):378-380,384. [5] Yeh W C.A new exact solution algorithm for a novel generalized redundancy allocation problem[J].Information Sciences,2017(408):182-197. [6] 李东魁.三状态设备网络可靠性分解定理与网络可靠度的计算[D].沈阳:东北大学,1992. 【通联编辑:代影】 |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。