文档库 最新最全的文档下载
当前位置:文档库 › 用于约束多目标优化问题的双群体差分进化算法

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

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

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

孟红云1张小华2刘三阳1

(1.西安电子科技大学应用数学系,西安,710071;

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

摘要:首先给出一种改进的差分进化算法,然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法.该算法同时使用两个群体,其中一个用于保存搜索过程中找到的可行解,另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解,避免了构造罚函数和直接删除不可行解.此外,将本文算法、NSGA-Ⅱ和SPEA 的时间复杂度进行比较表明,NSGA-Ⅱ最优,本文算法与SPEA 相当.对经典测试函数的仿真结果表明,与NSGA-Ⅱ相比较,本文算法在均匀性及逼近性方面均具有一定的优势.关键字:差分进化算法;约束优化问题;多目标优化问题;

中图分类号:TP18

1引言

达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展,用进化算法求解优化问题已成为一个研究的热点[1-3].但目前研究最多的却是无约束优化问题.然而,在科学研究和工程实践中,许多实际问题最终都归结为求解一个带有约束条件的函数优化问题,因此研究基于进化算法求解约束优化问题是非常有必要的.不失一般性,以最小化问题为例,约束优化问题(Constrained Optimization Problem ,COP )可定义如下:

)(COP ()()()()q j x h p

i x g t s x f x f x f x F j i k R

x n ,,1,0)( ,,1,0)( ..,,,(min 21L L L ===≤=∈(1)其中)(x F 为目标函数,(),(x h x g j i 称为约束条件,n n R x x x x ∈=),,,(21L 称为n 维决策向量.将满足所有约束条件的解空间S 称为(1)的可行域.特别的,当1=k 时,(1)为单目标优化问题;当1>k 时,(1)为多目标优化问题.)(x g i 为第i 个不等式约束,)(x h j 是第j 个等式约束.另一方面,对于等式约束0)(=x h j 可通过容许误差(也称容忍度)0>δ将它转化为两个不等式约束:

?????≤??≤?0)(0(δδx h x h j j (2)

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

定义1(全局最优解)()

**2*1*,,,n x x x x L =是COP 的全局最优解,是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标函数)(y F ,表示为)( )(*y F x F p .对于单目标优化问题,)( )(*y F x F p 等价为)()(*y F x F ≤,而对于多目标优化问题是指不存在y ,使得)(y F Pareto 优于)(*x F .

目前,进化算法用于无约束优化问题的文献居多,与之比较,对约束优化问题的研究相对较少[4-6]。文[7]对当前基于进化算法的各种约束处理方法进行了较为详细的综述.对于约束优化问题的约束处理方法基本上分为两类:基于罚函数的约束处理技术和基于多目标优化技

术的约束处理技术.由于罚函数法在使用中不需要约束函数和目标函数的解析性质,因此经常被应用于约束优化问题,但该类方法对罚因子有很强的依赖性,需要根据具体问题平衡罚函数与目标函数.为了避免复杂罚函数的构造,Verdegay 等[8]将进化算法中的竞争选择用于约束处理,并在比较两个解的性能时提出了三个准则,但他的第三个准则—可行解优于不可行解—这一准则合理性不强.然而该文的这一准则却为进化算法求解约束优化问题提供了新思路,获得了良好效果.

因为在现实中存在一大类约束优化问题,其最优解位于约束边界上或附近,对于这类问题,在最优解附近的不可行解的适应值很可能优于位于可行域内部的大部分可行解的适应值,因此无论从适应值本身还是从最优解的相对位置考虑,这样的不可行解对找到最优解都是很有帮助的,故如何有效利用搜索过程中的部分具有较好性质的不可行解是解决此类问题的难点之一.基于以上考虑,本文拟给出一种求解约束多目标优化问题的基于双群体机制的差分进化算法,并对文中算法的时间复杂度与NSGA-Ⅱ[9]和SPEA [10]进行比较,最后用实验仿真说明文中算法的可行性及有效性.

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

2.1差分进化算法

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

()321r r r P P F P C ??+=(3)

其中1r P ,32,r r P P 为从进化群体中随机选取的互不相同的三个个体,F 为位于区间]1,5.0[中的参数.(3)式表示从种群中随机取出的两个个体32,r r P P 的差,经参数F 放大或缩小后被加到第三个个体1r P 上,以构成新的个体()n c c C ,,1L =.为了增加群体的多样性,交叉操作被引入差分进化算法,具体操作如下:针对父代个体),,(1n r x x P L =的每一分量i x ,产生位于区间]1,0[中的随机数i p ,根据i p 与

参数CR 的大小关系确定是否用i c 替换i x ,以得到新的个体),,(1n r x x P ′′=′L ,

其中

, , ???=′i i i x c x if if CR

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

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

2.2基于双群体的差分进化算法

2.2.1基本概念

以下仅讨论带不等式约束的多目标优化问题

(()()

()n j u x l x x x p

i x g t s x f x f x F j j j n i k ,,1,,,, ,,1,0)( ..,,min )(min 11L L L L =≤≤==<=(4)

定义2.1x 称为(4)的不可行解,是指至少存在一个p i ≤≤1,满足()0≥x g i .定义2.2x 违反约束的强度,即约束违反度函数定义为()()∑==

p

i i x g x P 1,0max (σ,本文取2=σ.定义2.3x 违反约束的数目()()∑==p

i i x g Num x N 1)(,其中()???≥<=0 , 10 , 0x x x Num .定义2.4不可行解x 优于不可行解y ,是指x 的约束向量()()()x N x P ,Pareto 优于y 的约束向量()()()y N y P ,.

2.2.2基本思想

由上一节分析可知,在搜索过程中遇到的不可行解不能简单丢掉.因此,在设计算法时不但要考虑算法的收敛速度,而且还必须保证群体中可行解的优势地位;另一方面,对于多目标优化问题,维持搜索群体的多样性与考虑群体的收敛速度是同等重要的.基于此考虑,本节采用基于双群体的差分进化算法求解约束多目标优化问题,其中群体f PoP 用来保存搜索过程中遇到的可行解,c PoP 用来保存搜索过程中遇到的占优不可行解,同时f PoP 具有较强的记忆功能,可记忆f PoP 中每一个体搜索到的最优可行解和整个群体f PoP 到目前为止搜索到的最优可行解,分别记为lbest 和gbest ,其中lbest 表示个体对自身的思考和认知,gbest 表示个体间的信息交流,这一点和PSO 算法类似.与此同时,我们还通过一种改进的差分进化算法产生新的群体,在产生新群体的过程中,群体c PoP 中的部分个体参与了个体再生,并通过新生成的个体更新f PoP 、c PoP 、lbest 和gbest .为了避免性能较优的不可行解被删除,本文拟采用双群体搜索机制,其中群体{}1,,,21N f x x x PoP L =用于记录可行解,群体c PoP {}2,,,21N y y y L =记录不可行解,

21,N N 分别为群体f PoP 与c PoP 的规模,满足21N N >,{}1,,,21N z z z lbest L =和{}3,,,21N g g g gbest L =分别为群体f PoP 中每一个个体i x 搜索到最优可行解i z 和群体f PoP 迄今为止搜索到最优可行解.

2.2.3改进的差分进化算法

为了维护群体f PoP 的多样性和收敛性,同时有效的利用已搜索到的不可行解的某些优良特性,下面给出一种改进的差分进化算法,并通过以下两种方式产生新的个体.

方法1:()()

3422211r r r r r x g F x z F x C ?+?+=

其中f r r r PoP x x x ∈321,,,lbest z r ∈2,gbest g r ∈4.

方法2:()()

5423211r r r r r y g F y z F x C ?+?+=其中f r PoP x ∈1,c r r PoP y y ∈53,,lbest z r ∈2,gbest g r ∈4.

方法1的目的在于通过向最优个体学习,改善算法的收敛速度.方法2的主要目的在于和不可行个体进行信息交流,共享不可行解的一些优良特性,增加群体的多样性.在具体操作过程中,首先用改进的差分进化算法产生新的个体()n c c C ,,1L =,然后针对父代个体),,(1n r x x P L =的每一个分量i x ,产生位于区间]1,0[中的随机数i p ,根据i p 与参数CR 的

大小关系确定是否用i c 来替换i x ,得到新的个体),,(1n r x x P ′′=′L .

如果r P ′是可行解,而且f PoP 的规模小于给定规模1N ,则可直接将r P ′插入f PoP ;如果插入后的群体的规模大于给定规模1N ,首先两两比较f PoP 中的个体,如果存在两个个体f j i PoP x x ∈,,满足)(i x F Pareto 优于)(j x F ,则将个体j x 删除,如果不存在,也就是说集合f PoP 中任意两个个体所对应的目标向量都不可比较,则计算f PoP 中任意两个个体间的距离,随机删除距离最小的两个个体中的一个.

如果r P ′是不可行解,而且c PoP 的规模小于给定规模2N ,则可直接将r P ′插入群体c PoP 中;如果c PoP 等于给定规模阈值2N ,计算插入r P ′后的群体c PoP 中任意两个个体的约束向量,如果存在两个个体f j i PoP y y ∈,,满足约束向量()()()i i y N y P ,Pareto 优于约束向量()()()j j y N y P ,,则删除j y ;如果不存在,则删除满足=)(i y P )(max y P c

PoP y ∈的个体i y .经过以上操作,群体f PoP 和c PoP 的规模不会大于给定规模阈值.最后利用新生成的群体f PoP 更新最优个体集合lbest 和gbest ,群体gbest 的更新方法和SPEA 算法中外部群体的更新方法相同,而lbest 的更新方法如下:如果新生成的可行解r P ′Pareto 优于对应的局部最优解i z ,则用r P ′替换i z ,否则不予替换.

2.3算法的基本流程

综上所述,基于双群体的差分进化算法的约束处理技术的流程可表示如下:

step1.随机生成N ()21N N N +≥个个体,判断每一个体的可行性,然后根据个体可行性将其插入到对应的群体f PoP 或c PoP 中;并初始化lbest 和gbest 及参数CR 和d P .

step2.判断搜索是否结束,如果结束,转向step step5

5,否则转向step3.

step3.生成随机数p ,如果d P p ≥,根据方法1,生成新的个体r P ′;否则,根据方法2生成新的个体r P ′,如果r P ′是可行解,将r P ′插入到f PoP 中;否则r P ′插入到c PoP 中,反复执行直到生成1N 个可行解.

step4.根据新生成的群体f PoP 更新最优个体集lbest 和gbest ,转向step2.

step5.输出最优解集gbest .

3算法分析

3.1算法的性能衡量

约束优化问题的算法性能的衡量可分为两部分,一部分为最终获得的最优解的性能的衡量,如通过GD [15]来度量最优群体的逼近性,SP [16]来衡量最优解的分布均匀性,或通过计算目标函数的次数衡量算法的复杂度和算法的收敛速度.另一部分是针对约束优化问题来衡量群体的多样性,Koziel &Michalewicz [17]给出一种多样性度量准则ρ,其定义如下:

|||

|S F =ρ(5)其中F 表示每一次搜索过程中生成的可行解的数目,S 为所生成的所有个体的数目.相应地,为了衡量群体中的不可行解违反约束的强度,可采用约束违反度函数的均值来度量:

∑∈=

c PoP y c avg PoP y P P /)((6)其中c PoP 表示集合c PoP 所包含元素的数目.然而在实际问题中,决策者往往只对某一范围的最优解感兴趣,故下边只评价本文算法对标准测试函数最终获得的最优解集的逼近性与均匀性,并与NSGA-Ⅱ进行比较.

3.2算法的时间复杂性分析

我们仅考虑种群规模对算法时间复杂度的影响,设可行群体f PoP 的规模为1N ,不可行群体c PoP 的规模为2N ,群体lbest 的规模为1N ,群体gbest 的最大规模为3N ,则文中算法迭代一次的时间复杂度可计算如下:算法中重组和变异操作的时间复杂度为)(1N O ;判断进化群体中个体可行性所需时间复杂度为)(1N O ;更新群体f PoP 、c PoP 和lbest 的时间复杂度分别为)(1N O 、)(2N O 和)(1N O ;计算群体f PoP 和gbest 的适应度所需时间复杂度为)(31N N O +;用于更新最优群体gbest 的时间复杂度最差为))((231N N O +;保持最优群体gbest 和进化群体f PoP 多样性的时间复杂度最差为))log()())((3131331N N N N N N O ++++;

则算法迭代一次所需的时间复杂度最差为

)(1N O +)(1N O +)(1N O +)(2N O +)(1N O +)(31N N O ++))((231N N O +))

log()(())((3131331N N N N O N N O ++++(7)

上述复杂度可简化为))

log()(())(())((3131231331N N N N O N N O N N O ++++++(8)设N 为所有种群的规模,令321N N N N ++=,则本文算法的时间复杂度))log()(())(())((3131231331N N N N O N N O N N O ++++++<)

(3N O (9)

NSGA-Ⅱ[9]和SPEA [10]是多目标进化算中两个最具有代表性的优秀算法,这两个算法的时间复杂度最差分别为)(2N O 和))((3

N N O +,其中N N ,分别为进化种群规模和外部种群集的规模.因而,SPEA 和本文算法的时间复杂度最差为)(3N O ,这比NSGA-Ⅱ的时间复杂度稍高一些,但接下来的实验结果告诉我们,本文算法的均匀性及逼近性却明显优于NSGA-Ⅱ.事实上,SPEA 和本文算法的时间复杂度主要用于环境选择(Environmental selection)上,如果文中对gbest 采取NSGA-Ⅱ中的多样性保持策略,则本文算法的复杂度将降至)(2N O .4实验结果与分析

(1)测试函数与参数设置

为了验证本文给出算法的可行性,我们采用Deb [18]建议的用来测试约束多目标优化算法性能的四个常见的测试函数来检验本文算法的性能.可行解集合的规模1001=N ,不可行解集合的规模102=N .初始化时,随机生成个体的数目200=N ,参数25.0=CR ,5.0=d p .21,F F 为位于区间]0.1,5,0[中的一致随机数.Deb 给出的测试函数可用统一的解析表示,即

()()()()()()[]()()()[]()???????+?≥??=?????????????????=??????=d c x f e x f b a x f e x f x g x c x f x c x x f x f x F |})](cos )([sin sin{|sin )(cos (1min min )(min 12121121θθπθθ其中()()[]∑=?+=5222cos 1041i i i x x x c π,.5,4,3,2,55,101=≤≤?≤≤i x x i 测试函数选取不同的参数e d c b a ,,,,,θ时,所构造的测试函数性质不同,可行解和不可行解的分布也不同,最终导致全局Pareto 最优解集的不同.其中通过控制参数b 的大小,可以控制Pareto 前端不连续的段数,b 越大段数越多;而较小参数d 可以使得每一不连续Pareto 前端仅包含一个Pareto 点;参数a 调节连续可行域到Pareto 前端的点的距离,a 越大距离越远,其作用在于调节问题求解的难度;参数c 的作用在于改变分段Pareto 前端之间的分布特性,当c =1时,Pareto 前端为均匀分布;当1>c 时,Pareto 前端向1f 较大的方向移动;当1

图4.1测试函数CTP1在目标空间示意图图4.2测试函数CTP2在目标空间示意图

图4.3测试函数CTP3在目标空间示意图图4.4测试函数CTP4在目标空间示意图

测试函数CTP1:

πθ1.0=,40=a ,5.0=b ,1=c ,2=d ,2?=e .可行解、不可行解、全局Pareto 前端分布如图4.1所示.

测试函数CTP2:

πθ05.0?=,40=a ,5=b ,1=c ,6=d ,0=e .可行解、不可行解、全局Pareto 前端分布如图4.2所示.

测试函数CTP3:

πθ2.0?=,2.0=a ,10=b ,1=c ,6=d ,1=e .可行解、不可行解、全局Pareto 前端分布如图4.3所示.

测试函数CTP4:

πθ2.0?=,1.0=a ,10=b ,1=c ,5.0=d ,1=e .可行解、不可行解、全局Pareto 前端分布如图4.4所示.

(2)实验结果与分析

在相同的测试函数和目标函数计算次数下,将本文算法和经典的NSGA-II 算法进行比

较,并将各自算法独立运行30次,然后统计两种算法所得Pareto 最优解集的均匀性(Spacing,SP )与逼近性(Generational distance,GD )的最好、最差、均值、方差和中间值,以此作为衡量算法性能的标准.由于真实Pareto 最优集是未知的,故我们将两种算法所得的60个近似Pareto 最优解集之并集的Pareto 滤集作为真实Pareto 最优解集的逼近,其中测试函数CTP1,CTP2,CTP3的函数值计算次数为10200,而CTP4的函数值计算次数为610014.这里,集合I 的Pareto 滤集)(I Pareto 定义为{})()(, ,|)(x F y F I y I x x I Pareto p ∈?/∈=.图4.5、4.6、4.7、4.8为从30次运行中随机选择的一次运行结果,从实验曲线可以看到本文算法求出的Pareto Front 在逼近性方面要优于NSGA-II .

图4.5测试函数CTP1的Pareto Front 图 4.6测试函数CTP2的Pareto Front

图4.7测试函数CTP3的Pareto Front 图4.8测试函数CTP4的Pareto Front

为了进一步定量的评价两种算法的逼近性与均匀性,表4.1,4.2,4.3,4.4给出了两种算法对上述四个测试函数的SP ,GD 的统计结果,从表中数据容易看出,在解集的逼近性和均匀性方面本文算法对四个测试函数的标准方差都明显小于经典的NSGA-II 算法,这说

表4.1测试函数CTP1评价准则的统计结果

best worst avg median Std.Dev.

SP NSGA-II0.42850.71790.57490.56940.1842 Proposed0.51870.61380.57050.56840.1043

GD

NSGA-II0.00050.00210.00170.00150.0013 Proposed9.821e-05 5.367e-04 2.0625e-004 2.636e-040.0003

表4.2测试函数CTP2评价准则的统计结果

best worst avg median Std.Dev.

SP

NSGA-II0.32750.41210.39240.37320.2157 Proposed0.26890.33510.29650.29740.0813

GD

NSGA-II0.00080.00170.0010.00130.0011 Proposed 1.547e-05 1.784e-04 2.306e-78.033e-050.0001

表4.3测试函数CTP3评价准则的统计结果

best worst avg median Std.Dev.

SP NSGA-II0.52190.74510.36990.37910.2312 Proposed0.51870.61380.29650.28340.1813

GD

NSGA-II0.00050.00210.00120.00130.0013 Proposed9.821e-05 5.367e-048.0325e-005 2.636e-040.0002表4.4测试函数CTP4评价准则的统计结果

best worst avg median Std.Dev.

SP NSGA-II0.27530.56340.34900.35760.1278 Proposed0.22450.52860.34260.33810.1138

GD NSGA-II0.00110.00360.00230.00230.0030 Proposed 1.3232e-8 3.371e-7 4.6452e-8 5.173e-80.0001

明本文的算法性能更稳定.另一方面,上述定量的度量结果也表明在搜索过程中适当的运用性能较优的不可行解的信息不仅有助于保持群体的多样性,而且增强了算法的搜索功能,并在一定程度上起到了维持解集的均匀性的作用.

5结论

本文借助粒子群算法的基本思想给出了一种改进的差分进化算法,在适当的利用部分优良不可行个体的基础上,提出了用于约束多目标优化问题的双群体差分进化算法.该算法中的两个群体分别用于记录进化过程中的可行解及部分性能较优的不可行解,其优点在于可以充分利用每次迭代产生的子代个体的信息.此外,还对文中算法的时间复杂度与NSGA-Ⅱ和SPEA进行比较.经典测试函数的数值仿真结果表明,本文算法无论在解集的逼近性及均匀性方面都优于NSGA-II算法,这表明文中提出的基于双群体的差分进化算法可用于求解带约束的多目标优化问题方面有一定的优势.

正如“没有免费的午餐定理”[19]所指出的,任何一种算法不可能在所有的性能方面占尽

优势,虽然本文算法在求解约束多目标优化问题方面具有一定的优势,但计算量要稍高于NSGA-II。接下来我们的研究将致力于如何降低算法的时间复杂度及本文算法的实际应用。

参考文献

[1].Mitsuo Gen and Runwei Cheng,Genetic algorithms&Engineering Design.John Wiley&Sons,Inc,New

York,1997.’

[2].Fred Glover,Heuristics for Integer programming using surrogate constraints.Decision Sciences,1977,

8(1):156-166;

[3].David E.Goldberg,Genetic in search,optimization and machine learning.Addison-Wesley Publishing

Co.,Reading,Massachusetts,1989.

[4].Wang Yuexuan,Liu Lianchen,etc,.Constrained Multiobjective Optimization Evolutionary Algorithm.

Journal of Tsinghua Univ(Sci&Tech),2005,45(1),103-106.

(王跃宣,刘连臣等.处理带约束的多目标优化进化算法.清华大学学报(自然科学版),2005,45(1),103-106).

[5].Zhang Yongde,Huang Shabai.On Ant Colony Algorithm for Solving Multiobjective Optimization Problems.

Control and Decision.2004,20(2),170-174.

(张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策,2005,20(2),170-174.)[6].Gao Yugen,Cheng Feng,etc,.A New Improved Genetic Algorithms Based on Converting Infeasible

Individuals into Feasible Ones and Its Property Analysis.Acta Electronica Sinica,2006,34(4),638-641.

(高玉根,程峰,王灿,王国彪.基于违约解转化法的遗传算法及其性能分析.电子学报,2006,34(4),638-641).

[7].Carlos A.Coello Coello.Theoretical and Numerical Constraint-Handling Techniques used with Evolutionary

Algorithms:A Survey of the State of the Art,Computer Methods in Applied Mechanics and Engineering, Vol.191,No.11--12,pp.1245--1287,January2002.

[8].Fernando Jiménez and JoséL.Verdegay.Evolutionary techniques for constrained optimization problems.In

Hans-Jürgen Zimmermann,editor,7th European Congress on Intelligent Techniques and Soft Computing (EUFIT'99),Aachen,Germany,1999.Verlag Mainz.ISBN3-89653-808-X.

[9].Kalyanmoy Deb,Amrit Pratap,Sameer Agarwal,and T.Meyarivan.A Fast and Elitist Multiobjective

Genetic Algorithm:NSGA--II,IEEE Transactions on Evolutionary Computation,2002,6(2),182--197. [10].Eckart Zitzler and Lothar Thiele.Multiobjective evolutionary algorithms:A comparative case study and the

strength pareto approach.IEEE Trans.On Evolutionary Computation,1999,3(4),257-271.

[11].Storn,R.and K.Price(1995).Differential evolution:a simple and efficient adaptive scheme for global

optimization over continuous spaces.Technical Report TR-95-012,International Computer Science Institute, Berkeley.

[12].Yung-Chien Lin,Kao-Shing Hwang,and Feng-Sheng Wang.Hybrid Differential Evolution with Multiplier

Updating Method for Nonlinear Constrained Optimization Problems.CEC'2002,volume1,pages872-877, Piscataway,New Jersey,May2002.

[13].Abbass,H.,Sarker,R.and Newton, C.PDE:A Pareto-frontier Differential Evolution Approach for

Multi-objective Optimization Problems.Proceedings of the Congress on EC2001(CEC’2001),vol.2,IEEE Service Center,Piscataway,New Jersey,971-978.

[14].Li Bing-yu,Xiao Yun-shi,Wu Qi-di.Hybrid algorithm based on particle swarm optimization for solving

constrained optimization problems.Control and Decision,2004,19(7),804-807.

(李炳宇,萧蕴诗,吴启迪.一种基于粒子群算法求解约束优化问题的混合算法,控制与决策,2004,19(7),

804-807).

[15].D.A.Van Veldhuizen and https://www.wendangku.net/doc/747433610.html,mont.Multiobjective Evolutionary Algorithm Research:A history and

https://www.wendangku.net/doc/747433610.html,put.Eng.,Graduate School of Eng.,Air Force Inst.Technol.,Wright-Patterson AFB, OH.Tech.Rep.TR-98-03,1998.

[16].J.Schott.Fault tolerant design using single and multicriteria genetic algorithm optimization.Master’s thesis,

Department of Aeronautics and Astronautics,Massachusetts Institute of Technology,1995.

[17].S.Koziel and Michalewicz.Evolutionary algorithms,homomorphous Mapping,and constrained parameter

optimization.Evolutionary Computation,1996,7(1):19-44.

[18].Kalyanmoy Deb,Amrit Pratap,and T.Meyarivan.Constrained Test Problems for Multi-objective

Evolutionary Optimization.In:Proceedings of the1st International Conference on Evolutionary Multi-Criterion Optimization,Zurich,Switzerland,2001,Springer-Verlag,284-298

[19].Wolpert D.H.,Macready W.G..No free lunch theorems for search.Santa Fe,NM:Santa Fe Institute.

Technical Report:SFI-TR-05-010,1995.

A Differential Evolution Based on double Populations for Constrained

Multi-objective Optimization Problem

MENG Hong-yun1,ZHANG Xiao-hua2,LIU San-yang1

(1.Dept.of Applied Math.,Xidian University,Xi’an710071,China;

2.Institute of Intelligent Information Processing,Xidian University,Xi’an,710071) Abstract:An improved differential evolution approach is given first,and a new algorithm based on double Populations for Constrained Multi-objective Optimization Problem(CMOP)is presented.In the proposed algorithm,two populations are adopted,one is for the feasible solutions found during the evolution,and the other is for infeasible solutions with better performance which are allowed to participate in the evolution with the advantage of avoiding difficulties such as constructing penalty function and deleting infeasible solutions directly. In addition,the time complexity of the proposed algorithm,NSGA-Ⅱand SPEA are compared,which show the best is NSGA-Ⅱ,followed by SPEA and our algorithm simultaneously.The experiments on benchmarks indicate that our algorithm is superior to NSGA-Ⅱin the measure of GD and SP.

Keywords:Differential Evolution;Constrained Optimization Problem;multi-objective optimization problem; Background

Constrained optimization,both for nonlinear programming and multi-objective optimization,is a very important problem and has a variety of applications in engineering,management,mathematics and other fields.A common way to constrained optimization problem is to deal with constraints by penalty function,with the disadvantage and difficulty in choosing the penalty factors.In this paper,the authors propose a differential evolution based on double populations for constrained multi-objective optimization problem.By using the definitions and the mechanism in the paper,an effective evolutionary algorithm for constrained multi-objective optimization problem is given and the time complexity is discussed and compared with the state of the art—NSGA-Ⅱand SPEA,which shows the time complexity of

the proposed algorithm is as the same magnitude as SPEA and is higher than that of NSGA-Ⅱ,while simulations illustrate that the proposed algorithm is superior to NSGA-Ⅱin the measure of GD and SP.However,it is worthy to note that the time complexity of our algorithm will decrease greatly if a strategy like NSGA-Ⅱis taken for updating optimal population gbest.

孟红云,女,1975年生,博士,副教授,主要研究领域为优化理论与方法、自然计算、图像处理.E-mail: mhyxdmath@https://www.wendangku.net/doc/747433610.html,.

张小华,男,1974年生,博士,副教授,主要研究领域为自然计算、智能信息处理、数据挖掘和数字水印.刘三阳,男,1959年生,博士,教授,博士生导师,主要研究领域为优化理论与方法.

MENG Hong-yun,born in1975,Ph.D.,associate professor.Her research interests include Optimization theory and algorithm,natural computation,image processing.

ZHANG Xiao-hua,born in1974,Ph.D.,associate professor.His research interests include natural computation, intelligent information processing,data mining,and digital watermark.

LIU San-yang,born in1959,Ph.D.,professor,Ph.D.supervisor.His research interests include Optimization theory and methods.

第一作者照片

作者孟红云的联系方式:

Email:mhyxdmath@https://www.wendangku.net/doc/747433610.html,

手机:013636804033

差分进化算法及应用研究

湖南大学 硕士学位论文 差分进化算法及应用研究 姓名:吴亮红 申请学位级别:硕士 专业:控制理论与控制工程指导教师:王耀南 20070310

硕士学位论文 摘要 论文首先介绍了智能优化算法的产生对现代优化技术的重要影响,阐述了智能优化算法的研究和发展对现代优化技术和工程实践应用的必要性,归纳总结了智能优化算法的主要特点,简要介绍了智能优化算法的主要研究内容及应用领域。 对差分进化算法的原理进行了详细的介绍,给出了差分进化算法的伪代码。针对混合整数非线性规划问题的特点,在差分进化算法的变异操作中加入取整运算,提出了一种适合于求解各种混合整数非线性规划问题的改进差分进化算法。同时,采用时变交叉概率因子的方法以提高算法的全局搜索能力和收敛速率。用四个典型测试函数进行了实验研究,实验结果表明,改进的差分进化算法用于求解混合整数非线性规划问题时收敛速度快,精度高,鲁棒性强。 采用非固定多段映射罚函数法处理问题的约束条件,提出了一种用改进差分进化算法求解非线性约束优化问题的新方法。结合差分进化算法两种不同变异方式的特点,引入模拟退火策略,使算法在搜索的初始阶段有较强的全局搜索能力,而在后阶段有较强的局部搜索能力,以提高算法的全局收敛性和收敛速率。用几个典型Benchmarks函数进行了测试,实验结果表明,该方法全局搜索能力强,鲁棒性好,精度高,收敛速度快,是一种求解非线性约束优化问题的有效方法。 为保持所求得的多目标优化问题Pareto最优解的多样性,提出了一种精英保留和根据目标函数值进行排序的多目标优化差分进化算法。对排序策略中目标函数的选择方式进行了分析和比较,并提出了一种确定进化过程中求得的精英解是否进入Pareto最优解集的阈值确定方法。用多个经典测试函数进行了实验分析,并与NSGA-Ⅱ算法进行了比较。实验结果表明,本文方法收敛到问题的Pareto前沿效果良好,获得解的散布范围广,能有效保持所求得的Pareto最优解的多样性。 提出了一种新的基于群体适应度方差自适应二次变异的差分进化算法。该算法在运行过程中根据群体适应度方差的大小,增加一种新的变异算子对最优个体和部分其它个体同时进行变异操作,以提高种群多样性,增强差分进化算法跳出局部最优解的能力。对几种典型Benchmarks函数进行了测试,实验结果表明,该方法能有效避免早熟收敛,显著提高算法的全局搜索能力。提出了将该改进算法用来整定不完全微分PID控制器最优或近似最优参数的新方法。为克服频域中常用的积分性能指标如IAE,ISE和ITSE的不足,提出了一种新的时域性能指标对控制器性能进行测试和评价。用三个典型的控制系统对提出的ASMDE-PID控制器进行了测试。实验结果表明,该方法实现容易,收敛性能稳定,计算效率高。与ZN,GA和ASA方法相比,DE在提高系统单位阶跃响应性能方面效率更高,鲁棒性更强。 为了提高差分进化算法的全局搜索能力和收敛速率,提出了一种双群体伪并行差分

1多目标优化

多目标优化算法 ——11级计算一班 20113745 陆慧玲 近年来,多目标优化问题求解已成为演化计算的一个重要研究方向,而基于Pareto 最优概念的多目标演化算法则是当前演化计算的研究热点。多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。 最优化问题是工程实践和科学研究中主要的问题形式之一,其中,仅有一个目标函数的最优化问题称为单目标优化问题,目标函数超过一个并且需要同时处理的最优化问题称为多目标优化问题(multiobjectiveoptimizationprob- lems,简称MOPs)。对于多目标优化问题,一个解对于某个目标来说可能是较好的,而对于其他目标来讲可能是较差的,因此,存在一个折衷解的集合,称为Pareto 最优解集(Pareto optimal set)或非支配解集(nondominated set)。起初,多目标优化问题往往通过加权等方式转化为单目标问题,然后用数学规划的方法来求解,每次只能得到一种权值情况下的最优解。同时,由于多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的,传统的数学规划方法往往效率较低,且它们对于权重值或目标给定的次序较敏感。进化算法通过在代与代之间维持由潜在解组成的种群来实现全局搜索,这种从种群到种群的方法对于搜索多目标优化问题的Pareto 最优解集是很有用的。 第一代进化多目标优化算法以Goldberg 的建议为萌芽。1989 年,Goldberg 建议用非支配排序和小生境技术来解决多目标优化问题。非支配排序的过程为:对当前种群中的非支配个体分配等级1,并将其从竞争中移去;然后从当前种群中选出非支配个体,并对其分配等级2,该过程持续到种群中所有个体都分配到次序后结束。小生境技术用来保持种群多样性,防止早熟。Goldberg 虽然没有把他的思想具体实施到进化多目标优化中,但是其思想对以后的学者来说,具有启发意义。随后,一些学者基于这种思想提出了MOGA,NSGA 和NPGA。 从20 世纪末期开始,进化多目标优化领域的研究趋势发生了巨大的变化,l999 年,Zitzler 等人提出了SPEA。该方法使精英保留机制在进化多目标优化领域流行起来。第二代进化多目标优化算法的诞生就是以精英保留策略的引入为标志。在进化多目标优化领域,精英保留策略指的是采用一个外部种群(相对于原来个体种群而言)来保留非支配个体。(1)SPEA 和SPEA2 SPEA 是Zitzler 和Thiele 在1999 年提出来的算法。在该算法中,个体的适应度又称为Pareto 强度,非支配集中个体的适应度定义为其所支配的个体总数在群体中所占的比

多目标进化算法总结

MOGA i x 是第t 代种群中个体,其rank 值定义为: () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值(fitness value )分配算法: 1、 将所有个体依照rank 值大小排序分类; 2、 利用插值函数给所有个体分配适应值(从rank1到 rank * n N ≤),一般采用线性函数 3、 适应值共享:rank 值相同的个体拥有相同的适应值, 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme ): 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector :() 1,,q g g g =??? 分为以下三种情况: 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???>

当a y 支配b y 时,选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时,选择b y 优点:算法思想容易,效率优良 缺点:算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法

NPGA 基本思想: 1、初始化种群Pop 2、锦标赛选择机制:随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配,而2x 没有被CS 中任一个体支配,则选择2x 。 3、其他情况一律称为死结(Tie ),采用适应度共享机制选择。 个体适应度:i f 小生境计数(Niche Count ):(),i j Pop m Sh d i j ∈= ????∑ 共享函数:1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度(the shared fitness ): i i f m 选择共享适应度较大的个体进入下一代 优点:能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点:需要设置共享参数

多目标进化算法总结

MOGA i x 是第t 代种群中个体,其rank 值定义为: () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值(fitness value )分配算法: 1、 将所有个体依照rank 值大小排序分类; 2、 利用插值函数给所有个体分配适应值(从rank1到 rank * n N ≤),一般采用线性函数 3、 适应值共享:rank 值相同的个体拥有相同的适应值, 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme ): 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector :() 1,,q g g g =??? 分为以下三种情况:

1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时,选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时,选择b y 优点:算法思想容易,效率优良 缺点:算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法

NPGA 基本思想: 1、初始化种群Pop 2、锦标赛选择机制:随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配,而2x 没有被CS 中任一个体支配,则选择2x 。 3、其他情况一律称为死结(Tie ),采用适应度共享机制选择。 个体适应度:i f 小生境计数(Niche Count ):(),i j Pop m Sh d i j ∈= ????∑ 共享函数:1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度(the shared fitness ): i i f m 选择共享适应度较大的个体进入下一代 优点:能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点:需要设置共享参数

进化计算综述

进化计算综述 1.什么是进化计算 在计算机科学领域,进化计算(Evolutionary Computation)是人工智能(Artificial Intelligence),进一步说是智能计算(Computational Intelligence)中涉及到组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响,通过程序迭代模拟这一过程,把要解决的问题看作环境,在一些可能的解组成的种群中,通过自然演化寻求最优解。 2.进化计算的起源 运用达尔文理论解决问题的思想起源于20世纪50年代。 20世纪60年代,这一想法在三个地方分别被发展起来。美国的Lawrence J. Fogel提出了进化编程(Evolutionary programming),而来自美国Michigan 大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想,并将其进行提取、简化与抽象提出了遗传算法(Genetic algorithms)。在德国,Ingo Rechenberg 和Hans-Paul Schwefel提出了进化策略(Evolution strategies)。 这些理论大约独自发展了15年。在80年代之前,并没有引起人们太大的关注,因为它本身还不够成熟,而且受到了当时计算机容量小、运算速度慢的限制,并没有发展出实际的应用成果。

到了20世纪90年代初,遗传编程(Genetic programming)这一分支也被提出,进化计算作为一个学科开始正式出现。四个分支交流频繁,取长补短,并融合出了新的进化算法,促进了进化计算的巨大发展。 Nils Aall Barricelli在20世纪六十年代开始进行用进化算法和人工生命模拟进化的工作。Alex Fraser发表的一系列关于模拟人工选择的论文大大发展了这一工作。 [1]Ingo Rechenberg在上世纪60 年代和70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。[2]特别是John Holland的作品让遗传算法变得流行起来。[3]随着学术研究兴趣的增长,计算机能力的急剧增加使包括自动演化的计算机程序等实际的应用程序成为现实。[4]比起人类设计的软件,进化算法可以更有效地解决多维的问题,优化系统的设计。[5] 3.进化计算的分支 进化计算的主要分支有:遗传算法GA ,遗传编程GP、进化策略ES、进化编程EP。下面将对这4个分支依次做简要的介绍。 1遗传算法(Genetic Algorithms): 遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法,由美国John HenryHoland教授于1975年在他的专著《Adaptation in Natural and Artificial Systems》中首次提出。[6]它是利用某种编码技术作用于称为染色体的二进制数串,其基本思想是模拟由这些串组成的种群的进化过程,通过有组织地然而是随机地信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染

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

用于约束多目标优化问题的双群体差分进化算法 孟红云1 张小华2 刘三阳1 (1.西安电子科技大学 应用数学系,西安,710071; 2.西安电子科技大学 智能信息处理研究所,西安,710071) 摘 要:首先给出一种改进的差分进化算法,然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法.该算法同时使用两个群体,其中一个用于保存搜索过程中找到的可行解,另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解,避免了构造罚函数和直接删除不可行解.此外,将本文算法、N SGA-Ⅱ和SPEA 的时间复杂度进行比较表明,NS GA-Ⅱ最优,本文算法与SPE A相当.对经典测试函数的仿真结果表明,与NSGA-Ⅱ相比较,本文算法在均匀性及逼近性方面均具有一定的优势. 关键字: 差分进化算法;约束优化问题;多目标优化问题; 中图分类号:TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展,用进化算法求解优化问题已成为一个研究的热点[1-3].但目前研究最多的却是无约束优化问题.然而,在科学研究和工程实践中,许多实际问题最终都归结为求解一个带有约束条件的函数优化问题,因此研究基于进化算法求解约束优化问题是非常有必要的.不失一般性,以最小化问题为例,约束优化问题(Constrai ned Opti mizatio n Prob lem ,COP )可定义如下: )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ (1) 其中)(x F 为目标函数,)(),(x h x g j i 称为约束条件,n n R x x x x ∈=),,,(21 称为n 维决策 向量.将满足所有约束条件的解空间S 称为(1)的可行域.特别的,当1=k 时,(1)为单目标优化问题;当1>k 时,(1)为多目标优化问题.)(x g i 为第i 个不等式约束,)(x h j 是第j 个等式约束.另一方面,对于等式约束0)(=x h j 可通过容许误差(也称容忍度)0>δ将它转化为两个不等式约束: ?????≤--≤-0 )(0)(δδx h x h j j (2) 故在以后讨论问题时,仅考虑带不等式约束的优化问题.进一步,如果x 使得不等式约束0)(=x g i ,则称约束()x g i 在x 处是积极的.在搜索空间S 中,满足约束条件的决策变量x 称为可行解,否则称为不可行解. 定义1(全局最优解)() **2*1*,,,n x x x x =是COP 的全局最优解,是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标函数)(y F ,表示为)( )(* y F x F . 对于单目标优化问题,)( )(*y F x F 等价为)()(*y F x F ≤,而对于多目标优化问题是指不存在y ,使得)(y F Pa re to 优于)(*x F . 目前,进化算法用于无约束优化问题的文献居多,与之比较,对约束优化问题的研究相对

基本差分进化算法

基本差分进化算法 基本模拟退火算法概述 DE 算法是一种基于群体进化的算法,其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。由于DE 算法操作简单,寻优能力强,自提出以来引起了国内外学者的高度关注,目前已在电力系统优化调度、配网重构等领域得到了应用。 1、算法原理 DE 算法首先在N 维可行解空间随机生成初始种群P 0001[,,]N =X x x L ,其中000T 1[,,]i i iN x x =x L ,p N 为DE 种群规模。DE 算法的核心思想在于采取变异和交叉操 作生成试验种群,然后对试验种群进行适应度评估,再通过贪婪思想的选择机制,将原种群和试验种群进行一对一比较,择优进入下一代。 基本DE 算法主要包括变异、交叉和选择三个操作。首先,在种群中随机选取三个个体,进行变异操作: 1123()t t t t i r r r F +=+-v x x x 其中1t i +v 表示变异后得到的种群,t 表示种群代数,F 为缩放因子,一般取(0,2],它的大小可以决定种群分布情况,使种群在全局范围内进行搜索;1t r x 、2t r x 、3t r x 为从种群中随机抽取的三个不同的个体。 然后,将变异种群和原种群进行交叉操作: 1,R 1 ,,R () or () () and ()t i j t i j t i j v rand j C j randn i u x rand j C j randn i ++?≤=?=?>≠?? 其中t 1,i j u +表示交叉后得到的种群,()rand j 为[0,1]之间的随机数,j 表示个体的第j 个分量,R C 为交叉概率,()randn i 为[1,,]N L 之间的随机量,用于保证新个体至少有一维分量由变异个体贡献。 最后,DE 算法通过贪婪选择模式,从原种群和试验种群中选择适应度更高的个体进入下一代: 11t 11 ()() ()()t t t i i i i t t t i i i f f f f ++++?<=?≥?u u x x x u x 1()t i f +u 、()t i f x 分别为1t i +u 和t i x 的适应度。当试验个体1t i +u 的适应度优于t i x 时,

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

用于约束多目标优化问题的双群体差分进化算 法精编 Document number:WTT-LKK-GBB-08921-EIGG-22986

用于约束多目标优化问题的双群体差分进化算法 孟红云 1 张小华2刘三阳1 (1.西安电子科技大学应用数学系,西安,710071; 2.西安电子科技大学智能信息处理研究所,西安,710071)摘要:首先给出一种改进的差分进化算法,然后提出一 种基于双群体搜索机制的求解约束多目标优化问题的差分 进化算法.该算法同时使用两个群体,其中一个用于保存 搜索过程中找到的可行解,另一个用于记录在搜索过程中 得到的部分具有某些优良特性的不可行解,避免了构造罚 函数和直接删除不可行解.此外,将本文算法、NSGA-Ⅱ和SPEA的时间复杂度进行比较表明,NSGA-Ⅱ最优,本文算法与SPEA相当.对经典测试函数的仿真结果表明,与NSGA-Ⅱ相比较,本文算法在均匀性及逼近性方面均具有一定的优势. 关键字:差分进化算法;约束优化问题;多目标优化问题; 中图分类号:TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算 法的出现和发展,用进化算法求解优化问题已成为一个研 究的热点[1-3].但目前研究最多的却是无约束优化问题.然而,在科学研究和工程实践中,许多实际问题最终都归结 为求解一个带有约束条件的函数优化问题,因此研究基于 进化算法求解约束优化问题是非常有必要的.不失一般

性,以最小化问题为例,约束优化问题(Constrained Optimization Problem ,COP )可定义如下: )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ (1) 其中)(x F 为目标函数,)(),(x h x g j i 称为约束条件, n n R x x x x ∈=),,,(21 称为n 维决策向量.将满足所有约束条件的 解空间S 称为(1)的可行域.特别的,当1=k 时,(1)为单目 标优化问题;当1>k 时,(1)为多目标优化问题.)(x g i 为 第i 个不等式约束,)(x h j 是第j 个等式约束.另一方面,对于等式约束0)(=x h j 可通过容许误差(也称容忍度)0>δ将它转 化为两个不等式约束: ?????≤--≤-0)(0)(δδx h x h j j (2) 故在以后讨论问题时,仅考虑带不等式约束的优化问题.进一步,如果x 使得不等式约束0)(=x g i ,则称约束() x g i 在x 处是积极的.在搜索空间S 中,满足约束条件的决策变量x 称为可行解,否则称为不可行解. 定义1(全局最优解)()**2 *1*,,,n x x x x =是COP 的全局最优解,是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标 函数)(y F ,表示为)( )(*y F x F . 对于单目标优化问题, )( )(*y F x F 等价为)()(*y F x F ≤,而对于多目标优化问题是指不 存在y ,使得)(y F Pareto 优于)(*x F . 目前,进化算法用于无约束优化问题的文献居多,与 之比较,对约束优化问题的研究相对较少[4-6]。文[7] 对当前基于进化算法的各种约束处理方法进行了较为详细的综述. 对于约束优化问题的约束处理方法基本上分为两类:基于 罚函数的约束处理技术和基于多目标优化技术的约束处理

约束优化设计

行域 φ 内,选择一个初始点 X 然后确定一个可行 得一个目标函数有所改善的可行的新点 X 即完成了 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题,大多属于约束优化设计问题,其数学模型为: s .t . min f (x ) g u (x ) ≤ 0 h v (x ) = 0 x ∈ R n u = 1, 2,..., m v = 1, 2,..., p < n 根据求解方式的不同,可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于 这类方法的有:随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路: 在由 m 个不等式约束条件 gu(x )≤0 所确定的可 0 搜索方向 S ,且以适当的步长沿 S 方向进行搜索,取 1 一次迭代。以新点为起始点重复上述搜索过程,每次 均按如下的基本迭代格式进行计算: X k+1=X k +α k S k (k=0,1,2,..) 逐步趋向最优解, 直到满足终止准则才停止迭代。 直接解法的原理简单,方法实用,其特点是: 1) 由于整个过程在可行域内进行,因此,迭代计算 不论何时终止,都可以获得比初始点好的设计点。 2) 若目标函数为凸函数,可行域为凸集,则可获得全域最优解,否则,可能存在多个局 部最优解,当选择的初始点不同,而搜索到不同的局部最优解。 3) 要求可行域有界的非空集

φ(X,μ1,μ2)=F(X)+∑μ 1 G??g j X)??+∑μ2H??h k(X)?? a)可行域是凸集;b)可行域是非凸 集 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法,并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后,和目标函数 结合起来,构成一个新的目标函数,即将原约束优化问题转化为一个或一系列的无约束优 化问题。 m l j=1k=1 新目标函数 然后对新目标函数进行无约束极小化计算。 加权因子 间接法是结构优化设计中广泛使用的有效方法,其特点: 1)由于无约束优化方法的研究日趋成熟,为间接法提供可靠基础。这类算法的计算效率和数值计算的稳定性大有提高; 2)可以有效处理具有等式约束的约束优化问题; 3)目前存在的主要问题,选取加权因子较为困难,选取不当,不仅影响收敛速度和计算精度,甚至导致计算失败。

差分进化算法介绍

1.差分进化算法背景 差分进化(Differential Evolution,DE)是启发式优化算法的一种,它是基于群体差异的启发式随机搜索算法,该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。近年来,DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。 差分算法的研究一直相当活跃,基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。它的全局寻优能力和易于实施使其在诸多应用中取得成功。 2.差分进化算法简介 差分进化算法采用实数编码方式,其算法原理同遗传算法相似刚,主要包括变异、交叉和选择三个基本进化步骤。DE算法中的选择策略通常为锦标赛选择,而交叉操作方式与遗传算法也大体相同,但在变异操作方面使用了差分策略,即:利用种群中个体间的差分向量对个体进行扰动,实现个体的变异。与进化策略(Es)采用Gauss或Cauchy分布作为扰动向量的概率密度函数不同,DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小,自适应好;DE 的变异方式,有效地利用了群体分布特性,提高了算法的搜索能力,避免了遗传算法中变异方式的不足。 3.差分进化算法适用情况 差分进化算法是一种随机的并行直接搜索算法,最初的设想是用于解决切比雪夫多项式问题,后来发现差分进化算法也是解决复杂优化问题的有效技术。它可以对非线性不可微连续空间的函数进行最小化。目前,差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题,但是,差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。 4.基本DE算法 差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量,这一操作称为“变异”。然后,变异向量的参数与另外事先确

最新高维多目标进化算法总结

高维多目标进化算法 二、文献选读内容分析及思考 (一)Borg算法 Borg算法是基于ε-MOEA算法(Deb,2003)的一种全新改进算法[32],下面将从创新点、原理、算法流程和启发思考四方面进行阐述。 1.创新点 1)在ε支配关系的基础上提出ε盒支配的概念,具有能同时保证算法收敛性与多样性的特点。 2)提出了ε归档进程,能提高算法计算效率和防止早熟。 3)种群大小的自适应调整。 4)交叉算子的自适应选择。由于处理实际问题时,是不知道目标函数具有什么特性,前沿面如何,在具有多个交叉算子的池子里,根据进程反馈,选择不同的交叉算子,使产生的后代具有更好的特性针对要研究的问题。 2. Borg算法原理 1)ε盒支配:通过对目标空间向量的每一维除以一个较小的ε,然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格(2目标时),当点处于不同的网格时,按pareto支配关系比较;当处于同一网格时,比较哪个点距离中心点(网格最左下角)最近。这样一来,网格内都只有一个点。 2)ε归档进程 如图1所示,黑点表示已经归档的,想要添加到档案集的新解用×表示,阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解1、解2加入归档集属于ε归档进程,解3加入归档集就不属于ε归档进程。 图1 ε支配网格 在这个过程中设置了一个参数c,表示每一代中加入归档集解得个数,每隔一定迭代次数检测c有没有增加,如果没有增加表明算法停滞,重启机制启动。 3)重启 自适应种群大小:重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值,这个值也用于第二步中,如果γ值没超过1.25,重启机制也启动。启动后,γ人为设定为固定值,种群被清空,填充归档集的所有个体,不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。 4)交叉算子的自适应选择 摒弃以往采用单一的交叉算子,采用包含各类交叉算子的池子,比如有K

差分进化算法-入门

基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法,是在求解有关切比雪夫多项式的问题时提出来的,是基于群体差异的进化计算方法。它的整体结构类似于遗传算法,一样都存在变异、交叉和选择操作,但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上,如: 1、传统的遗传算法采用二进制编码,而差分进化算法采用实数编码。 2、在遗传算法过两个父代个体的交叉产生两个子个体,而在差分进化算法过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中,子代个体以一定概率取代其父代个体,而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作,它是基于群体的差异向量来修正各个体的值,其基本原理是通过把种群中两个个体的向量差加权后,按一定的规划与第三个个体求和来产生新个体,然后将新个体与当代种群中某个预先决定的个体相比较,如果新个体的目标值优于与之相比较的个体的目标值,则在下一代中就用新个体取代,否则,旧个体仍保存下来。 差分进化算法其基本思想是:首先由父代个体间的变异操作构成变异个体;接着按一定的概率,父代个体与变异个体之间进行交叉操作,生成一试验个体;然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作,保留较优者,实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ,群体规模为NP ,空间维数为D ,当前种群为 {}12(),, ,t t t NP X t x x x =,()12,, ,T t t t t i i i iD x x x x =为种群中的第i 个个体。在进化过程 中,对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,, ,)t t t t T i i i iD v v v v =,则 123() 1,2, ,D t t t t ij r j r j r j v x F x x j =+-= (1) 其中111112(,,,)t t t t T r r r r D x x x x =,222212(,,,)t t t t T r r r r D x x x x =和333312(,, ,)t t t t T r r r r D x x x x =是群 体中随机选择的三个个体,并且123r r r i ≠≠≠;1t r j x ,2t r j x 和3t r j x 分别为个体1r ,2r 和3r 的第j 维分量;F 为变异因子,一般取值于[0,2]。这样就得到了变异个体t i v 。

多目标进化算法总结

x 是第 t 代种群中个体,其 rank 值定义为: rank (x ,t ) =1+p (t ) p (t )为第t 代种群中所有支配x 的个体数目 适应值 (fitness value )分配算法: 1、 将所有个体依照 rank 值大小排序分类; 2、 利用插值函数给所有个体分配适应值(从 rank1 到 rank n * N ),一般采用线性函数 3、 适应值共享:rank 值相同的个体拥有相同的适应值, 保证后期选择时同一 rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme ): 向量y a =(y a ,1,,y a ,q )和y b =(y b ,1,,y b ,q )比较 分为以下三种情况: k =1,,q -1; i =1,,k ; j =k +1,,q ; (y a ,i g i )(y a ,j g j ) i =1, ,q ; (y a ,i g i ) 当 y a 支配 y b 时,选择 y a 3、j =1, ,q ; (y a ,j g j ) 当 y b 支配 y a 时,选择 y b 优点:算法思想容易,效率优良 缺点:算法容易受到小生境的 大小影响 理论上给出了参数share 的计算方法 goal vector : g = (g 1, ,g q ) 1、 2、

基本思想: 1、初始化种群 Pop 2、锦标赛选择机制:随机选取两个个体 x 和 x 和一个 Pop 的 子集 CS(Comparison Set)做参照系。若 x 被 CS 中不少于一 个个体支配,而 x 没有被 CS 中任一个体支配,则选择 x 。 3、其他情况一律称为死结(Tie ),采用适应度共享机制选择。 个体适应度: f i 小生境计数(Niche Count ): m =j Pop Sh d (i , j ) 共享适应度(the shared fitness ): 选择共享适应度较大的个体进入下一代 优点:能够快速找到一 些好的非支配最优解域 能够维持一个较长的种群更新期 缺 点:需要设置共享参数 需要选择一个适当的锦标赛机制 限制 了该算法的实际应用效果 1- 共享函数: Sh (d ) = d share 0, d share d share

基于TSP的改进差分进化算法

龙源期刊网 https://www.wendangku.net/doc/747433610.html, 基于TSP的改进差分进化算法 作者:朱宇航伏楠 来源:《硅谷》2012年第17期 摘要: 针对TSP问题,提出一种改进的差分进化算法:利用贪心算法产生初始种群,定义特有的编码匹配函数进行变异操作,排序法修复变异个体,并采用顺序交叉,在变异操作之后,加入新的选择机制,防止交叉操作破坏变异出的优良个体,实验结果表明改进后的差分进化算法能够高效地解决TSP问题,体现良好的优化性能。 关键词: 差分进化算法;TSP;进化算法 0 引言 差分进化算法(DE:Differential Evolution)是一种模拟自然进化法则的仿生智能计算方法,在解决复杂的全局优化问题方面,DE的性能更加优秀,过程也更为简单,受控参数少[1],但由于DE 特有的差分操作的限制,DE被成功应用的领域多集中在连续优化领域,在离散优化领域的应用还相对较少[2]。 TSP(旅行商问题)作为典型的离散优化问题,是解决很多实际问题的最终转化形式,同时也是著名的NP难题,在短时间内求出其最优解非常困难,现有解法[3-4]在求解中都各有缺点.因此,研究将DE经过必要的改进后应用于TSP的求解具有重要意义。 1 改进DE算法 1.1 编码及匹配函数 适应度定义为:负的路径长度,使得路径长度越短,适应度值越大。 1.2 贪婪初始化 为提高初始种群的质量,采用贪婪的初始化方法.对于初始种群的每个个体,产生方法如下: step1:初始化待走城市列表List为包含所有城市的列表; step2:随机选择一个城市A作为起点,并将此点作为当前城市T,从List中移除; step3:从List中选择距离城市T最近的城市作为新的当前城市T,并将T从List中移除; step4:判断List是否为空,若是,则结束;若否,则转step3。

约束优化设计

第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题,大多属于约束优化设计问题,其数学模型为: 根据求解方式的不同,可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于这类方法的有:随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路: 在由m 个不等式约束条件g u (x )≤0所确定的可行域φ内,选择一个初始点0 X 然后确定一个可行搜索方向S ,且以适当的步长沿S 方向进行搜索,取得一个目标函数有所改善的可行的新点1 X 即完成了一次迭代。以新点为起始点重复上述搜索过程,每次均按如下的基本迭代格式进行计算: k+1k k k =+S (k=0,1,2,..)X X α逐步趋向最优解, 直到满足终止准则才停止迭代。 直接解法的原理简单,方法实用,其特点是: 1) 由于整个过程在可行域内进行,因此,迭代计算不论何时终止,都可以获得比初始点好 的设计点。 2) 若目标函数为凸函数,可行域为凸集,则可获得全域最优解,否则,可能存在多个局部 最优解,当选择的初始点不同,而搜索到不同的局部最优解。 3) 要求可行域有界的非空集 1,2,...,1,2,...,u m v p n ==

间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法,并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后,和目标函数结合起来,构成一个新的目标函数,即将原约束优化问题转化为一个或一系列的无约束优化问题。 然后对新目标函数进行无约束极小化计算。 间接法是结构优化设计中广泛使用的有效方法,其特点: 1) 由于无约束优化方法的研究日趋成熟,为间接法提供可靠基础。这类算法的计算效率和 数值计算的稳定性大有提高; 2) 可以有效处理具有等式约束的约束优化问题; 3) 目前存在的主要问题,选取加权因子较为困难,选取不当,不仅影响收敛速度和计算精 度,甚至导致计算失败。 a) 可行域是凸集;b)可行域是非凸集 () ()()()121211 ,,m l j k j k X F X G g X H h X φμμμμ==??=++? ?????∑∑ 新目标函数 加权因子

MOEAD(基于分解的多目标进化算法)

摘要:在传统的多目标优化问题上常常使用分解策略。但是,这项策略还没有被广泛的应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目标优化问题分解为一组单目标优化问题并对它们同时优化。通过利用与每一个子问题相邻的子问题的优化信息来优化它本身,这是的该算法比MOGLS和非支配排序遗传算法NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明:在0-1背包问题和连续的多目标优化问题上,利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现的更加出色或者表现相近。实验也表明目标正态化的MOEA/D算法可以解决规模范围相异的多目标问题,同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。最后,MOEA/D在较小种群数量是的性能,还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。 I.介绍 多目标优化问题可以用下面式子表示: Maximize F(x)=((f1(f)…...f f(f))f subject to x∈Ω 其中Ω是决策空间,F:Ω→f f,包含了m个实值目标方法,f f被称为目标区间。对于 可以得到的目标集合成为{F(x)|x∈Ω}。 如果x∈R m,并且所有的目标函数都是连续的,那么Ω则可以用 Ω={x∈f f|h f(x)≤0,j=1……m} 其中hj是连续的函数,我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥,那么同时对所有目标函数求最优解往往是无意义的。有意义的是获得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义Pareto最优。 令u, v∈Rm,如果f f≥f f对于任意的i,并且至少存在一个f f≥f f(i,j∈{1…..m}),那么u支配v。如果在决策空间中,没有一个点F(y)能够支配F(x)点,那么x就是Pareto最优,F(x)则被称为Pareto最优向量。换句话说,对于Pareto最优点在某一个目标函数上的提高,都会造成至少一个其余目标函数的退化。所有Pareto最优解的集合称为Pareto集合,所有最优向量的集合被称为Pareto前沿。 在许多多目标优化的实际应用中,通过选择器选择一个接近Pareto最优前沿的解作为最后的解。大多数多目标优化问题都有许多甚至是无穷个Pareto最优向量,如果想要获得一个完整的最优前沿,将是一件非常耗时的事情。另一方面,选择器可能不会专注于获得一个过于庞大的最优解向量集合来解决问题,因为信息的溢出。因此,许多多目标优化算法往往是获得一个均匀分布在Pareto最优前沿周围的最优解向量,这样就具有更好的代表性。许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。 一般来说,在温和控制下多目标优化问题的Pareto最优解,可以看做是一个标量优化问题的最优解(其中目标函数是fi的集合)。因此,Pareto最优前沿的近似求解可以被分解为一组标量目标优化子问题。这个想法是建立在许多传统的对最优前沿求近似解的数学编程方法上的。现在有许多的聚合方法,最流行的是切比雪夫法和加权法。最近,边界交叉方法也引起了许多的关注。 如今多目标进化算法并没有将分解这一概念引入当前的主要发展领域。这些算法将多目标优化问题看成一个整体。他们并没有通过任何特别的标量优化将每一个解相互联系在一起。在一个标量目标优化问题中,所有的解都可以通过他们的目标函数值进行对比,而挑战

多目标进化算法总结

i x 是第t 代种群中个体,其rank 值定义为: ()(,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值(fitness value )分配算法: 1、 将所有个体依照rank 值大小排序分类; 2、 利用插值函数给所有个体分配适应值(从rank1到 rank * n N ≤),一般采用线性函数 3、 适应值共享:rank 值相同的个体拥有相同的适应值, 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme ): 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector :() 1,,q g g g =??? 分为以下三种情况: 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时,选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时,选择b y 优点:算法思想容易,效率优良 缺点:算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法

基本思想: 1、初始化种群Pop 2、锦标赛选择机制:随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配,而2x 没有被CS 中任一个体支配,则选择2x 。 3、其他情况一律称为死结(Tie ),采用适应度共享机制选择。 个体适应度:i f 小生境计数(Niche Count ):(),i j P o p m S h dij ∈ = ??? ?∑ 共享函数:1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度(the shared fitness ): i i f m 选择共享适应度较大的个体进入下一代 优点:能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点:需要设臵共享参数 需要选择一个适当的锦标赛机制 限制了该算法的实际应用效果

相关文档