粒子群及局部搜索算法在串并联系统结构优化中的应用

王 健，赵 娜，刘 超，孙志礼

（东北大学机械工程与自动化学院，辽宁 沈阳110819）

0 引言

保持工作系统具有较高的可靠性及可用度对设备使用者和设计人员都非常重要。在系统可靠性工程中主要有2种方法提高系统可靠性指标，一种是提高系统中各个部件的可靠性水平；另一种是在系统中并联与现有部件具有相同功能的部件。当选择第2种方法时，若系统中并联部件太多，不但会造成系统庞大结构复杂，而且造价过高，若系统中并联部件不足，则会造成可靠性指标不能满足设计要求，因此，设计者必须在系统花费和系统可靠性水平间加以平衡。

早期学者们试图寻找上述冗余分配问题［1］的精确最优解，但计算量随着问题解维数的增加呈指数增长，所有维数较高冗余分配问题要想得到精确最优解是相当困难的。后来，遗传算法［2］、粒子群算法［3］和蚁群算法［4］等启发式算法应用到冗余分配问题中，希望能得到近似解，但实际应用中发现单纯使用一种算法容易得到局部最优解而不是整个问题的最优解。因此，将粒子群算法同局部搜索算法相结合，能有效避免在算法迭代过程中局部收敛现象。

1 系统结构模型

串并联系统［5-6］结构模型如图1所示。整个系统由Ns个子系统串联而成，各子系统内部部件间为并联关系。第i个子系统中共有Vi个不同可用类型部件，每种类型部件均能实现相同的功能，只有能力、可用度和费用不同。第j（j｛1，2，…，Vi｝）类部件共有Hij个不同的工作状态，每个状态的工作能力不同，显然Hij≥2，即每个类型部件至少应有2个工作状态。

图1 串并联系统结构

子系统i中第j个类型部件的单价用Cij表示，该类型部件处在状态h（h｛1，2，…，Hij｝）的概率为Aijh，对应的工作能力为 Wijh，这里的 Hij，Aijh和Wijh是部件的固有性质，其中，Aijh是根据部件的状态转移概率矩阵及维修更换策略经过较复杂计算得到。参考文献［7］中对该过程进行了详细说明，而这里认为系统处在稳定工作状态时各子系统中各类型部件的Aijh是已知的。子系统i中j类型部件的数量由Xij表示，这样子系统i的结构可由向量Xi表示，即

Vi为子系统i中部件类型个数，显然Xij≥0。整个系统结构由各子系统结构完全确定，用向量X表示整个系统结构：

X＝［X1，X2，…，XNs］

Ns为子系统个数。

这样整个系统的花费CS为：

系统可用度用AS表示，在运行过程中系统可用度的下限设为A0，则结构优化问题为：

结束条件为AS≥A0。求解式（2）所得系统结构X即为系统的最优结构。

2 系统可用度计算

在此，计算系统可用度使用概率生成函数方法，并假设系统中各个部件间的工作状态是相互独立的，这一假设非常重要，是应用UGF计算系统可用度的前提条件。

由上文可知，子系统i中j类部件的UGF为：

根据UGF在处理独立随机变量中的性质及子系统中各个部件间为并联关系，子系统i的UGF为：

式（4）可以展开为：

Api为子系统工作能力为Wpi的概率。由于各个子系统间为串联关系，根据式（5）可以得到系统的UGF为：

式（6）可以展开为：

Q为系统的状态个数；Wq为各个状态对应的工作能力。

若将系统工作时间分成M 段，第m（m｛1，2，…，M｝）段长度为Tm，且第m段要求系统工作能力不低于W0m，则系统在第m个工作时间段内的可用度为：

则系统在整个工作过程中的可用度为：

3 粒子群算法和局部搜索算法

3．1 粒子群算法

粒子群算法（PSO）是一种群智能算法，在求解高维非线性不可微问题中表现出较好的效率，PSO算法在处理这类问题时要比遗传算法收敛速度快很多。它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，它们只能根据自己和相邻鸟的经验，选择下一步向哪个方向移动去寻找食物。）

标准PSO算法首先要随机产生一定数量NP的“粒子”，同时产生与每个初始粒子对应的前进速度，用X表示粒子的位置，Y表示X 的速度。实际问题中X各分量的取值不可能是任意的，式（2）所要优化问题的X分量的上限用XB表示。每个粒子都沿着自己的速度方向移动，更新位置并寻找问题的最优解，粒子的速度及位置更新过程为：

X（t＋1），X（t）为粒子在第t＋1次和第t次迭代后所处位置；Y（t＋1）为粒子在第t＋1次迭代时的速度；XPB为粒子自身所得到的最优解，称之为局部最优解；XGB为所有粒子得到的最优解，每次迭代后都要对XPB和XGB进行更新；l1和l2为XPB和XGB的影响因子；u1和u2为取自［0，1］区间均匀分布随机数；w为粒子初始速度影响因子。

粒子群算法中用适应度函数决定一个粒子或解的好坏程度。所提优化问题的适应度函数由2部分组成，一部分为粒子X所决定系统的费用CS，另一部分为，若X所决定系统的可用度不能满足A0要求，则应该在CS基础上增加CP作为惩罚，以利于在以后迭代中将可用度小于A0的解淘汰掉，实现约束条件AS≥A0。所以式（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类型部件，用β个j2类型部件代替，β由下式决定：

经过以上某种局部搜索策略处理后得到的粒子X′要与X 进行比较，取其中最好的粒子继续进行PSO迭代。

需要说明的是，为了控制算法的计算量，并不是在每次PSO迭代前对所有粒子进行局部搜索，而是规定每进行一定次数PSO迭代后，对所得粒子随机挑选一定比例进行局部搜索处理，这样既可以使算法计算量不会太大，又能在一定程度上加快收敛速度和避免局部收敛。

4 实例

假设共有4个子系统，所有可选部件都只有工作和故障2个状态。部件故障状态时工作能力为0。各子系统中部件的类型数量、费用可用度和工作能力等指标如表1所示。系统整个工作过程分为3个阶段，各个阶段需要的系统工作能力及工作时间如表2所示，系统的可用度不能低于A0＝0．9。

本例中取NP＝1 000，即随机产生1 000个粒子作为解，并随机产生NP个粒子的速度，这时各局部最优解就是各粒子。根据式（11）和式（12）及A0，确定NP个粒子的最优解就是全局最优解，再依照式（10）进行迭代（式（10）的参数如表3所示），每次迭代后根据式（11）和式（12）更新局部最优解和全局最优解。迭代过程采用3．2节中局部搜索策略（e），且每进行n＝5次PSO迭代就进行1次局部搜索，局部搜索比例为5%，即每进行5次PSO迭代后，随机选取1 000×5%＝50个粒子进行局部搜索。

根据上文叙述方法进行迭代求解，当A0取不同值时，得到最优解的取值情况如表4所示。

表1 各类型部件参数

表2 不同时间段工作能力要求

表3 粒子群算法的参数

表4 最优解表

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．