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

计算机科学的一些热门文献

第31卷　第2期2008年2月

计　　算　　机　　学　　报

CHINESEJOURNALOFCOMPUTERS

Vol.31No.2

Feb.2008

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

孟红云　张小华　刘三阳

1)

2)

1)2)1)

(西安电子科技大学应用数学系　西安　710071)

(西安电子科技大学智能信息处理研究所　西安　710071)

摘　要　首先给出一种改进的差分进化算法,分进化算法.该算法同时使用两个群体,中得到的部分具有某些优良特性的不可行解,.、NSGA2Ⅱ和SPEA的时间复杂度的比较表明,NSGA2Ⅱ最优,.,与NSGA2Ⅱ相比较,关键词　ADifferentialEvolutionBasedonDoublePopulationsforConstrainedMulti2ObjectiveOptimizationProblem

MENGHong2Yun1　ZHANGXiao2Hua2　LIUSan2Yang1

1)

2)

)))

(DepartmentofAppliedMathematics,XidianUniversity,Xi′an　710071)

(InstituteofIntelligentInformationProcessing,XidianUniversity,Xi′an　710071)

Abstract　Animproveddifferentialevolutionapproachisgivenfirst,andanewalgorithmbasedon

doublepopulationsforConstrainedMulti2objectiveOptimizationProblem(CMOP)ispresented.Intheproposedalgorithm,twopopulationsareadopted,oneisforthefeasiblesolutionsfounddur2ingtheevolution,andtheotherisforinfeasiblesolutionswithbetterperformancewhichareal2lowedtoparticipateintheevolutionwiththeadvantageofavoidingdifficultiessuchasconstruc2tingpenaltyfunctionanddeletinginfeasiblesolutionsdirectly.Inaddition,thetimecomplexityoftheproposedalgorithm,NSGA2ⅡandSPEAarecompared,whichshowthebestisNSGA2Ⅱ,followedbySPEAandtheproposedalgorithmsimultaneously.TheexperimentsonbenchmarksindicatethattheproposedalgorithmissuperiortoNSGA2ⅡinthemeasureofGDandSP.Keywords　differentialevolution;constrainedoptimizationproblem;multi2objectiveoptimizationproblem

1　引　言

达尔文的自然选择机理和个体的学习能力推动了进化算法的出现和发展,用进化算法求解优化问

题已成为一个研究的热点[123].但目前研究最多的却是无约束优化问题.然而,在科学研究和工程实践中,许多实际问题最终都归结为求解一个带有约束条件的函数优化问题,因此研究基于进化算法求解约束优化问题是非常有必要的.不失一般性,以最小

收稿日期:2006207207;最终修改稿收到日期:2007206224.本课题得到国家自然科学基金(60703109)资助.孟红云,女,1975年生,博士,副教授,主要研究方向为优化理论与方法、自然计算、图像处理.E2mail:mhyxdmath@http://www.77cn.com.cn.张小华,男,1974年生,博士,副教授,主要研究方向为自然计算、智能信息处理、数据挖掘和数字水印.刘三阳,男,1959年生,博士,教授,博士生导师,主要研究领域为优化理论与方法.

计算机科学的一些热门文献

2期孟红云等:用于约束多目标优化问题的双群体差分进化算法229

化问题为例,约束优化问题(ConstrainedOptimiza2tionProblem,COP)可定义如下:

minF(x)=n

x∈R

因为在现实中存在一大类约束优化问题,其最优解位于约束边界上或附近,对于这类问题,在最优解附近的不可行解的适应值很可能优于位于可行域内部的大部分可行解的适应值,因此无论从适应值本身还是从最优解的相对位置考虑,这样的不可行解对找到最优解都是很有帮助的,故如何有效利用搜索过程中的部分具有较好性质的不可行解是解决此类问题的难点之一.基于以上考虑,本文拟给出一种求[9]

化算法,NSGA2Ⅱ和[].

f1,f2,…,fk(COP)s.t.gi(x)Φ0,i=1,2,…,p

hj(x)=0,j=1,2,…,q

(1)

其中,F(x)为目标函数,gi(x),hj(x)称为约束条件,x=(x1,x2,…,xn)∈Rn称为n维决策向量.将满足所有约束条件的解空间S称为式(1)的可行域.特别的,当k=1时,式(1)为单目标优化问题;当

k>1时,式(1)为多目标优化问题.gi(x)为第i等式约束,hj(x)是第j个等式约束.,等式约束hj(x)=0)δ>0:

-δ0-hj(x)-δΦ0

(2)

2

用于约束优化的双群体差分进化算法

211　差分进化算法

　　故在以后讨论问题时,仅考虑带不等式约束的优化问题.进一步,如果x使得不等式约束gi(x)=0,则称约束gi在x处是积极的.在搜索空间S中,满足约束条件的决策变量x称为可行解,否则称为不可行解.

定义1(全局最优解).　x=(

3

3

x1

差分进化算法是一类简单而有效的进化算法,已被成功应用于求解无约束单目标和多目标优化问题[11214].该算法在整个运行过程中保持群体的规模不变,它也有类似于遗传算法的变异、交叉和选择等操作,其中变异操作定义如下:

(3)C=Pr1+FPr2-Pr3

其中,Pr1,Pr2,Pr3为从进化群体中随机选取的互不相同的3个个体,F为位于区间[015,1]中的参数.式(3)表示从种群中随机取出的两个个体Pr2,Pr3的差,经参数F放大或缩小后被加到第3个个体Pr1上,以构成新的个体C=c1,c2,…,cn.为了增加群体的多样性,交叉操作被引入差分进化算法,具体操作如下:

针对父代个体Pr=(x1,x2,…,xn)的每一分量xi,产生位于区间[0,1]中的随机数pi,根据pi与参数CR的大小关系确定是否用ci替换xi,以得到新的

ci,pi<CR

个体P′.r=(x′1,x′2,…,x′n),其中x′i=

xi,piΕCR如果新个体P′′r优于父代个体Pr,则用Pr来替换Pr;否则保持不变.在差分进化算法中,选择操作采取的是贪婪策略,即只有当产生的子代个体优于父代个体时才被保留,否则,父代个体被保留至下一代.

大量研究与实验发现差分进化算法在维护群体的多样性及搜索能力方面功能较强,但收敛速度相对较慢,因此本文拟给出一种改进的差分进化算法用于多目标优化问题,仿真实验表明,改进的差分进化算法在不破坏原有算法维护群体多样性的前提

,

3x2

,…,xn)是

3

COP的全局最优解,是指x3∈S且F(x3)不劣于可

行域内任意解y所对应的目标函数F(y),表示为

33

F(x)ΜF(y).对于单目标优化问题,F(x)ΜF(y)

等价为F(x3)ΦF(y),而对于多目标优化问题是指不存在y,使得F(y)Pareto优于F(x3).

目前,进化算法用于无约束优化问题的文献居多,与之比较,对约束优化问题的研究相对较少[426].文献[7]对当前基于进化算法的各种约束处理方法进行了较为详细的综述.对于约束优化问题的约束处理方法基本上分为两类:基于罚函数的约束处理技术和基于多目标优化技术的约束处理技术.由于罚函数法在使用中不需要约束函数和目标函数的解析性质,因此经常被应用于约束优化问题,但该类方法对罚因子有很强的依赖性,需要根据具体问题平衡罚函数与目标函数.为了避免复杂罚函数的构造,Verdegay等[8]将进化算法中的竞争选择用于约束处理,并在比较两个解的性能时提出了3个准则,但他的第3个准则“可行解优于不可行解”这一准则合理性不强.然而该文的这一准则却为进化算法求解约束优化问题提供了新思路,获得了良好效果.

计算机科学的一些热门文献

230计　　算　　机　　学　　报2008年

下,可改善差分进化算法的收敛速度.212　基于双群体的差分进化算法21211　基本概念

gbest=

g1,g2,…,gN分别为群体PoPf中每一个

以下仅讨论带不 …… 此处隐藏：14496字，全部文档内容请下载后查看。喜欢就下载吧 ……