王健;赵娜;刘超;孙志礼
【摘 要】In this paper,a new algorithm of par-ticle swarm optimization and local search is pro-posed to solve the redundancy allocation problem for series parallel system.The structure of series parallel system is introduced in the paper.The new algorithm is used to design the system struc-ture with a minimum cost to provide a desired level of availability.The availability of the system is abtained through the universal generating function (UGF)method.Then the new algorithm is applied to get the optimal solution.The proposed algo-rithm are demonstrated via an illustrative case.%将粒子群算法和局部搜索算法相结合，用于解决串并联系统的冗余分配问题。介绍串并联系统结构，确定该冗余分配问题以系统最小费用为优化目标，以系统可用度不能低于某一确定值为约束条件。应用概率生成函数(UGF)方法计算系统可用度，将粒子群算法和局部搜索算法相结合进行优化求解，并给出迭代过程。通过实例对优化迭代过程进行具体说明。 【期刊名称】《机械与电子》 【年(卷),期】2014(000)001 【总页数】4页(P18-21)
【关键词】粒子群算法;局部搜索算法;串并联系统;冗余分配;概率生成函数 【作 者】王健;赵娜;刘超;孙志礼
【作者单位】东北大学机械工程与自动化学院，辽宁 沈阳 110819;东北大学机械工程与自动化学院，辽宁 沈阳 110819;东北大学机械工程与自动化学院，辽宁 沈阳 110819;东北大学机械工程与自动化学院，辽宁 沈阳 110819 【正文语种】中 文 【中图分类】TB114.3 0 引言
保持工作系统具有较高的可靠性及可用度对设备使用者和设计人员都非常重要。在系统可靠性工程中主要有2种方法提高系统可靠性指标，一种是提高系统中各个部件的可靠性水平；另一种是在系统中并联与现有部件具有相同功能的部件。当选择第2种方法时，若系统中并联部件太多，不但会造成系统庞大结构复杂，而且造价过高，若系统中并联部件不足，则会造成可靠性指标不能满足设计要求，因此，设计者必须在系统花费和系统可靠性水平间加以平衡。
早期学者们试图寻找上述冗余分配问题［1］的精确最优解，但计算量随着问题解维数的增加呈指数增长，所有维数较高冗余分配问题要想得到精确最优解是相当困难的。后来，遗传算法［2］、粒子群算法［3］和蚁群算法［4］等启发式算法应用到冗余分配问题中，希望能得到近似解，但实际应用中发现单纯使用一种算法容易得到局部最优解而不是整个问题的最优解。因此，将粒子群算法同局部搜索算法相结合，能有效避免在算法迭代过程中局部收敛现象。 1 系统结构模型
串并联系统［5-6］结构模型如图1所示。整个系统由Ns个子系统串联而成，各子系统内部部件间为并联关系。第i个子系统中共有V i个不同可用类型部件，每种类型部件均能实现相同的功能，只有能力、可用度和费用不同。第j（j｛1，
2，…，V i｝）类部件共有H ij个不同的工作状态，每个状态的工作能力不同，显然H ij≥2，即每个类型部件至少应有2个工作状态。 图1 串并联系统结构
子系统i中第j个类型部件的单价用C ij表示，该类型部件处在状态h（h｛1，2，…，H ij｝）的概率为Aijh，对应的工作能力为 Wijh，这里的 H ij，Aijh和Wijh是部件的固有性质，其中，Aijh是根据部件的状态转移概率矩阵及维修更换策略经过较复杂计算得到。参考文献［7］中对该过程进行了详细说明，而这里认为系统处在稳定工作状态时各子系统中各类型部件的Aijh是已知的。子系统i中j类型部件的数量由X ij表示，这样子系统i的结构可由向量X i表示，即
V i为子系统i中部件类型个数，显然Xij≥0。整个系统结构由各子系统结构完全确定，用向量X表示整个系统结构： X＝［X 1，X 2，…，X Ns］ Ns为子系统个数。
这样整个系统的花费CS为：
系统可用度用AS表示，在运行过程中系统可用度的下限设为A 0，则结构优化问题为：
结束条件为AS≥A 0。求解式（2）所得系统结构X即为系统的最优结构。 2 系统可用度计算
在此，计算系统可用度使用概率生成函数方法，并假设系统中各个部件间的工作状态是相互独立的，这一假设非常重要，是应用UGF计算系统可用度的前提条件。 由上文可知，子系统i中j类部件的UGF为：
根据UGF在处理独立随机变量中的性质及子系统中各个部件间为并联关系，子系统i的UGF为：
式（4）可以展开为：
A pi为子系统工作能力为W pi的概率。由于各个子系统间为串联关系，根据式（5）可以得到系统的UGF为：
式（6）可以展开为：
Q为系统的状态个数；W q为各个状态对应的工作能力。
若将系统工作时间分成M 段，第m（m｛1，2，…，M｝）段长度为T m，且第m段要求系统工作能力不低于W 0m，则系统在第m个工作时间段内的可用度为：
则系统在整个工作过程中的可用度为：
3 粒子群算法和局部搜索算法 3．1 粒子群算法
粒子群算法（PSO）是一种群智能算法，在求解高维非线性不可微问题中表现出较好的效率，PSO算法在处理这类问题时要比遗传算法收敛速度快很多。它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，它们只能根据自己和相邻鸟的经验，选择下一步向哪个方向移动去寻找食物。）
标准PSO算法首先要随机产生一定数量N P的“粒子”，同时产生与每个初始粒子对应的前进速度，用X表示粒子的位置，Y表示X 的速度。实际问题中X各分量的取值不可能是任意的，式（2）所要优化问题的X分量的上限用X B表示。每个粒子都沿着自己的速度方向移动，更新位置并寻找问题的最优解，粒子的速度及位置更新过程为：
X（t＋1），X（t）为粒子在第t＋1次和第t次迭代后所处位置；Y（t＋1）为粒子在第t＋1次迭代时的速度；X PB为粒子自身所得到的最优解，称之为局部最优解；X GB为所有粒子得到的最优解，每次迭代后都要对X PB和X GB进行更新；l 1和l 2为X PB和X GB的影响因子；u 1和u 2为取自［0，1］区间均匀分布随机数；w为粒子初始速度影响因子。
粒子群算法中用适应度函数决定一个粒子或解的好坏程度。所提优化问题的适应度函数由2部分组成，一部分为粒子X所决定系统的费用CS，另一部分为，若X所决定系统的可用度不能满足A 0要求，则应该在CS基础上增加C P作为惩罚，以利于在以后迭代中将可用度小于A 0的解淘汰掉，实现约束条件AS≥A 0。所以式（2）对应的适应度函数可表示为：
γ为惩罚系数，参考文献［8］中给出选取γ的系统说明。 3．2 局部搜索策略
为弥补PSO算法在迭代过程中可能出现局部收敛的缺陷，加快整个求解过程的收敛速度和求解精度，给出5种局部搜索策略作为对原始PSO的补充。
a．“＋1”。对每个子系统中在现有解基础上增加1个部件，增加的部件可以属于系统中任何类型。
b．“-1”。对每个子系统中在现有解基础上减少1个部件，减少的部件可以属于
系统中任何类型，若系统中某一类型部件数为0，则不对其进行任何操作。 c．“-1，＋1”。每个子系统中在现有解基础上减少1个部件，减少的部件可以属于系统中任何类型，若系统中某一类型部件数为0，则不对其进行任何操作，同时增加1个子系统中其他类型部件。
d．“-1，＋β”。与c类似，不同的是，在删除1个部件后要增加β个其他型号部件，β的计算为：
e．“-all，＋β”：该策略与d类似，不同在于要删除所有j1类型部件，用β个j 2类型部件代替，β由下式决定：
经过以上某种局部搜索策略处理后得到的粒子X′要与X 进行比较，取其中最好的粒子继续进行PSO迭代。
需要说明的是，为了控制算法的计算量，并不是在每次PSO迭代前对所有粒子进行局部搜索，而是规定每进行一定次数PSO迭代后，对所得粒子随机挑选一定比例进行局部搜索处理，这样既可以使算法计算量不会太大，又能在一定程度上加快收敛速度和避免局部收敛。 4 实例
假设共有4个子系统，所有可选部件都只有工作和故障2个状态。部件故障状态时工作能力为0。各子系统中部件的类型数量、费用可用度和工作能力等指标如表1所示。系统整个工作过程分为3个阶段，各个阶段需要的系统工作能力及工作时间如表2所示，系统的可用度不能低于A 0＝0．9。
本例中取N P＝1 000，即随机产生1 000个粒子作为解，并随机产生N P个粒子的速度，这时各局部最优解就是各粒子。根据式（11）和式（12）及A 0，确定N P个粒子的最优解就是全局最优解，再依照式（10）进行迭代（式（10）的参
数如表3所示），每次迭代后根据式（11）和式（12）更新局部最优解和全局最优解。迭代过程采用3．2节中局部搜索策略（e），且每进行n＝5次PSO迭代就进行1次局部搜索，局部搜索比例为5%，即每进行5次PSO迭代后，随机选取1 000×5%＝50个粒子进行局部搜索。
根据上文叙述方法进行迭代求解，当A 0取不同值时，得到最优解的取值情况如表4所示。
表1 各类型部件参数子系统 部件类型 Cij Aijh Wij h 1 1 0．520 0．970 0．50 2 0．620 0．964 0．80 3 0．720 0．980 0．80 4 0．890 0．969 1．00 5 1．020 0．960 1．50 2 1 0．516 0．967 0．20 2 0．916 0．914 0．50 3 0．967 0．960 0．50 4 1．367 0．953 0．75 3 1 0．214 0．959 0．60 2 0．384 0．970 0．90 3 0．534 0．959 1．80 4 0．614 0．960 2．00 5 0．783 0．970 2．00 6 0．813 0．960 2．40 4 1 0．683 0．989 0．25 2 0．645 0．979 0．25 3 0．697 0．980 0．30 4 1．190 0．960 0．70 5 1．260 0．980 0．70
表2 不同时间段工作能力要求W 0m 1．0 0．8 0．4 Tm（h）20 30 50
表3 粒子群算法的参数w l1 l2 N P N TγXB 0．6 1．7 1．7 1 000 100 2 000 8
表4 最优解表A 0 AS CS 最优解0．90 0．901 5．423 ［0，0，0，1，0；0，0，2，0；3，0，0，0，0，0；0，0，1，0，1］0．96 0．963 7．009 ［3，0，0，0，0；0，1，2，0；3，0，0，0，0，0；0，0，1，0，1］0．99 0．992 8．180 ［3，0，0，0，0；0，0，3，0；3，0，0，0，
0，0；0，0，1，2，0］ 5 结束语
利用UGF方法计算系统可用度，提出用粒子群算法和局部搜索算法相结合的方法，解决串并联系统结构优化问题，能够有效避免单独使用粒子群算法时出现局部收敛和收敛速度较慢现象，增大了得到问题真正最优解的概率。在求解迭代过程中，向适应度函数加入罚函数，用以实现对系统可用度的约束。 参考文献：
［1］ 侯雪梅，刘 伟，高 飞，等．基于群智能的模糊多目标软件可靠性冗余分配［J］．计算机应用，2013，33（4）：1142-1145．
［2］ 葛继科，邱玉辉，吴春明，等．遗传算法研究综述［J］．计算机应用研究，2008，25（10）：2911-2916．
［3］ 侯云鹤，鲁丽娟，熊信艮，等．改进粒子群算法及其在电力系统经济负荷分配中的应用［J］．中国电机工程学报，2004，24（7）：95-100．
［4］ 韩 攀，陈 谋，陈哨东，等．基于改进蚁群算法的无人机航迹规划［J］．吉林大学学报（信息科学版），2013，31（1）：66-72．
［5］ Wang G J，Zhang Y L．An optimal replacement policy for a two-component series system assuming geometric process repair
［J］．Computers ＆ M athematics with Applications，2007，54（2）：192–202．
［6］ Nourelfath M，Ait-Kadi D．Optimization of series-parallel multi-state systems under maintenance policies［J］．Reliability Engineering ＆ S ystem Safety，2007，92（12）：1620-1626．
［7］ Zhou Yifan，Zhang Zhisheng，Lin Tianran，et al．Maintenance optimization of a multi-state series-parallel system considering economic
dependence and state-dependent inspection intervals［J］．Reliability Engineering＆ S ystem Safety，2013，111：248-259．
［8］ 吴化尧，聂长海．覆盖表生成的粒子群算法：参数优化和自适应算法［J］．小型微型计算机系统，2012，33（10）：2259-2257．
因篇幅问题不能全部显示，请点此查看更多更全内容