用于约束多目标优化问题的双群体差分进化算法

1用于约束多目标优化问题的双群体差分进化算法孟红云1张小华2刘三阳1(1.西安电子科技大学应用数学系，西安，710071；2.西安电子科技大学智能信息处理研究所，西安，710071)摘要：首先给出一种改进的差分进化算法，然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法．该算法同时使用两个群体，其中一个用于保存搜索过程中找到的可行解，另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解，避免了构造罚函数和直接删除不可行解．此外，将本文算法、NSGA-Ⅱ和SPEA的时间复杂度进行比较表明，NSGA-Ⅱ最优，本文算法与SPEA相当.对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势.关键字：差分进化算法；约束优化问题；多目标优化问题；中图分类号：TP181引言达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展，用进化算法求解优化问题已成为一个研究的热点[1-3]．但目前研究最多的却是无约束优化问题．然而，在科学研究和工程实践中，许多实际问题最终都归结为求解一个带有约束条件的函数优化问题，因此研究基于进化算法求解约束优化问题是非常有必要的．不失一般性，以最小化问题为例，约束优化问题（ConstrainedOptimizationProblem，COP）可定义如下：)(COPqjxhpixgtsxfxfxfxFjikRxn,,1,0)(,,1,0)(..,,,)(min21（1）其中)(xF为目标函数，)(),(xhxgji称为约束条件，nnRxxxx),,,(21称为n维决策向量．将满足所有约束条件的解空间S称为(1)的可行域．特别的，当1k时，(1)为单目标优化问题；当1k时，（1）为多目标优化问题．)(xgi为第i个不等式约束，)(xhj是第j个等式约束．另一方面，对于等式约束0)(xhj可通过容许误差（也称容忍度）0将它转化为两个不等式约束：0)(0)(xhxhjj（2）故在以后讨论问题时，仅考虑带不等式约束的优化问题．进一步，如果x使得不等式约束0)(xgi，则称约束xgi在x处是积极的．在搜索空间S中，满足约束条件的决策变量x称为可行解，否则称为不可行解．定义1（全局最优解）**2*1*,,,nxxxx是COP的全局最优解，是指Sx*且)(*xF不劣于可行域内任意解y所对应的目标函数)(yF，表示为)()(*yFxF．对于单目标优化问题，)()(*yFxF等价为)()(*yFxF，而对于多目标优化问题是指不存在y，使得)(yFPareto优于)(*xF．目前，进化算法用于无约束优化问题的文献居多，与之比较，对约束优化问题的研究相对较少[4-6]。文[7]对当前基于进化算法的各种约束处理方法进行了较为详细的综述.对于约束优化问题的约束处理方法基本上分为两类：基于罚函数的约束处理技术和基于多目标优化技2术的约束处理技术．由于罚函数法在使用中不需要约束函数和目标函数的解析性质，因此经常被应用于约束优化问题，但该类方法对罚因子有很强的依赖性，需要根据具体问题平衡罚函数与目标函数．为了避免复杂罚函数的构造，Verdegay等[8]将进化算法中的竞争选择用于约束处理，并在比较两个解的性能时提出了三个准则,但他的第三个准则—可行解优于不可行解—这一准则合理性不强.然而该文的这一准则却为进化算法求解约束优化问题提供了新思路，获得了良好效果.因为在现实中存在一大类约束优化问题，其最优解位于约束边界上或附近，对于这类问题，在最优解附近的不可行解的适应值很可能优于位于可行域内部的大部分可行解的适应值，因此无论从适应值本身还是从最优解的相对位置考虑，这样的不可行解对找到最优解都是很有帮助的，故如何有效利用搜索过程中的部分具有较好性质的不可行解是解决此类问题的难点之一．基于以上考虑，本文拟给出一种求解约束多目标优化问题的基于双群体机制的差分进化算法，并对文中算法的时间复杂度与NSGA-Ⅱ[9]和SPEA[10]进行比较，最后用实验仿真说明文中算法的可行性及有效性．2用于约束优化的双群体差分进化算法2.1差分进化算法差分进化算法是一类简单而有效的进化算法，已被成功应用于求解无约束单目标和多目标优化问题[11-14]．该算法在整个运行过程中保持群体的规模不变，它也有类似于遗传算法的变异、交叉和选择等操作，其中变异操作定义如下：321rrrPPFPC(3)其中1rP,32,rrPP为从进化群体中随机选取的互不相同的三个个体，F为位于区间]1,5.0[中的参数．(3)式表示从种群中随机取出的两个个体32,rrPP的差，经参数F放大或缩小后被加到第三个个体1rP上，以构成新的个体nccC,,1．为了增加群体的多样性，交叉操作被引入差分进化算法，具体操作如下：针对父代个体),,(1nrxxP的每一分量ix，产生位于区间]1,0[中的随机数ip，根据ip与参数CR的大小关系确定是否用ic替换ix，以得到新的个体),,(1nrxxP，其中,,iiixcxififCRpCRpii．如果新个体rP优于父代个体rP，则用rP来替换rP，否则保持不变．在差分进化算法中，选择操作采取的是贪婪策略，即只有当产生的子代个体优于父代个体时才被保留，否则，父代个体被保留至下一代．大量研究与实验发现差分进化算法在维护群体的多样性及搜索能力方面功能较强，但收敛速度相对较慢，因此本文拟给出一种改进的差分进化算法用于多目标优化问题，仿真实验表明，改进的差分进化算法在不破坏原有算法维护群体多样性的前提下，可改善差分进化算法的收敛速度．2.2基于双群体的差分进化算法2.2.1基本概念以下仅讨论带不等式约束的多目标优化问题3njuxlxxxpixgtsxfxfxFjjjnik,,1,,,,,,1,0)(..,,min)(min11（4）定义2.1x称为（4）的不可行解，是指至少存在一个pi1，满足0xgi．定义2.2x违反约束的强度，即约束违反度函数定义为piixgxP1,0max)(，本文取2．定义2.3x违反约束的数目piixgNumxN1)(，其中0,10,0xxxNum．定义2.4不可行解x优于不可行解y，是指x的约束向量xNxP,Pareto优于y的约束向量yNyP,．2.2.2基本思想由上一节分析可知，在搜索过程中遇到的不可行解不能简单丢掉．因此，在设计算法时不但要考虑算法的收敛速度，而且还必须保证群体中可行解的优势地位；另一方面，对于多目标优化问题，维持搜索群体的多样性与考虑群体的收敛速度是同等重要的．基于此考虑，本节采用基于双群体的差分进化算法求解约束多目标优化问题，其中群体fPoP用来保存搜索过程中遇到的可行解，cPoP用来保存搜索过程中遇到的占优不可行解，同时fPoP具有较强的记忆功能，可记忆fPoP中每一个体搜索到的最优可行解和整个群体fPoP到目前为止搜索到的最优可行解，分别记为lbest和gbest，其中lbest表示个体对自身的思考和认知，gbest表示个体间的信息交流，这一点和PSO算法类似．与此同时，我们还通过一种改进的差分进化算法产生新的群体，在产生新群体的过程中，群体cPoP中的部分个体参与了个体再生，并通过新生成的个体更新fPoP、cPoP、lbest和gbest．为了避免性能较优的不可行解被删除，本文拟采用双群体搜索机制，其中群体1,,,21NfxxxPoP用于记录可行解，群体cPoP2,,,21Nyyy记录不可行解，21,NN分别为群体fPoP与cPoP的规模，满足21NN，1,,,21Nzzzlbest和3,,,21Nggggbest分别为群体fPoP中每一个个体ix搜索到最优可行解iz和群体fPoP迄今为止搜索到最优可行解．2.2.3改进的差分进化算法为了维护群体fPoP的多样性和收敛性，同时有效的利用已搜索到的不可行解的某些优良特性，下面给出一种改进的差分进化算法，并通过以下两种方式产生新的个体．方法1：3422211rrrrrxgFxzFxC4其中frrrPoPxxx321,,，lbestzr2，gbestgr4．方法2：5423211rrrrrygFyzFxC其中frPoPx1，crrPoPyy53,，lbestzr2，gbestgr4．方法1的目的在于通过向最优个体学习，改善算法的收敛速度．方法2的主要目的在于和不可行个体进行信息交流，共享不可行解的一些优良特性，增加群体的多样性．在具体操作过程中，首先用改进的差分进化算法产生新的个体nccC,,1，然后针对父代个体),,(1nrxxP的每一个分量ix，产生位于区间]1,0[中的随机数ip，根据ip与参数CR的大小关系确定是否用ic来替换ix，得到新的个体),,(1nrxxP．如果rP是可行解，而且fPoP的规模小于给定规模1N，则可直接将rP插入fPoP；如果插入后的群体的规模大于给定规模1N，首先两两比较fPoP中的个体，如果存在两个个体fjiPoPxx,，满足)(ixFPareto优于)(jxF，则将个体jx删除，如果不存在，也就是说集合fPoP中任意两个个体所对应的目标向量都不可比较，则计算fPoP中任意两个个体间的距离，随机删除距离最小的两个个体中的一个．如果rP是不可行解，而且cPoP的规模小于给定规模2N，则可直接将rP插入群体cPoP中；如果cPoP等于给定规模阈值2N，计算插入rP后的群体cPoP中任意两个个体的约束向量，如果存在两个个体fjiPoPyy,，满足约束向量iiyNyP,Pareto优于约束向量jjyNyP,，则删除jy；如果不存在，则删除满足)(iyP)(maxyPcPoPy的个体iy．经过以上操作，群体fPoP和cPoP的规模不会大于给定规模阈值．最后利用新生成的群体fPoP更新最优个体集合lbest和gbest，群体gbest的更新方法和SPEA算法中外部群体的更新方法相同，而lbest的更新方法如下：如果新生成的可行解rPPareto优于对应的局部最优解iz，则用rP替换iz，否则不予替换．2.3算法的基本流程综上所述，基于双群体的差分进化算法的约束处理技术的流程可表示如下：step1.随机生成N21NNN个个体，判断每一个体的可行性，然后根据个体可行性将其插入到对应的群体fPoP或cPoP中；并初始化lbest和gbest及参数CR和dP．step2.判断搜索是否结束，如果结束，转向step5，否则转向step3.5step3.生成随机数p，如果dPp，根据方法1，生成新的个体rP；否则，根据方法2生成新的个体rP，如果rP是可行解，将rP插入到fPoP中；否则rP插入到cPoP中，反复执行直到生成1N个可行解．step4.根据新生成的群体fPoP更新最优个体集lbest和gbest，转向step2．step5.输出最优解集gbest．3算法分析3.1算法的性能衡量约束优化问题的算法性能的衡量可分为两部分，一部分为最终获得的最优解的性能的衡量，如通过GD[15]来度量最优群体的逼近性，SP[16]来衡量最优解的分布均匀性，或通过计算目标函数的次数衡量算法的复杂度和算法的收敛速度．另一部分是针对约束优化问题来衡量群体的多样性，Koziel&Michalewicz[17]给出一种多样性度量准则，其定义如下：||||SF（5）其中F表示每一次搜索过程中生成的可行解的数目，S为所生成的所有个体的数目．相应地，为了衡量群体中的不可行解违反约束的强度，可采用约束违反度函数的均值来度量：cPoPycavgPoPyPP/)(