,其中x
n
和x
为变量的上下边界,i=1,…,n,n为变量维数。
f(x)、
g(x)、
h(x)均为ℜ
上的n元函数,f(x)为目标函数,g(x)≤0为第j个不等式约束条件,
hj(x)=0为第j个等式约束条件,l表示不等式约束条件的个数,有m-l个等式约束条件。
Ω在S中的补集为
(1)的不可行域,可行域中的解称为可行解,不可行域中的解称为不
可行解。
如果任一不等式约束条件满足gj(x)=0
(j∈{1,…,l}),则称gj(x)在x处活跃
(active)。
显然,所有的等式约束条件h(x)(j=l+1,…,m)关于可行域Ω中的任意点均活跃。
3差分进化算法以及在约束优化中的应用
差分进化算法同其它进化算法一样,也是对候选解的种群进行操作,首先在问题的解空
间随机初始化种群X
=(X,X
"X
),其中NP为种群规模,然后对当前的种群进行变
异和交叉操作,产生中间种群,利用基于贪婪思想的选择操作对原种群以及中间种群进行一对一的选择产生新一代种群。
但是作为一种新兴的进化算法,DE的种群繁殖方案(变异和交叉操作)与其它进化算法不同,一般的进化算法(实值编码)中其变异操作多采用高斯变异、柯西变异或其混合变异策略,而在DE中,其变异操作是采用把种群中两个个体向量之
间的加权差向量加到第三个被变异的个体向量上来产生新个体向量,设X
X,X是从
k代中随机选取的互不相同的三个个体,经差分变异后得新个体V,即:
V=X+F∗(X−X)
(2)
其中,F∈[0,2]是控制误差变量的放大作用的实参数。
将变异个体的参数与另外预先确定的父代个体参数按一定规则混合来产生新个体,该操
作即为DE算法的交叉操作,设D是实变量的维数,且:
U=(U,U,",U)
⎧⎪V
if(rand(j)≤CR)orj=j
U=⎨Xif(rand(j)>CR)orj≠j
i=1,2,"NP,j=1,2,"D
(3)
其中rand(j)是产生[0,1]间的一个均匀随机数,j是随机产生一个1到D之间的自然数,CR∈[0,1]的一个实参数。
DE算法的选择操作采用一对一的贪婪选择,即若当前的种群中个体对应的目标函数值比它们的父代较优,该个体就在下一代中代替父代个体。
种群中所有个体必须被作为父代个体进行这样的一次操作,以便在下一代中出现相同个竞争者。
上面阐述的是基本DE算法的步骤,在实际的运用中出现了几种DE的变形形式[17],用符号DE/x/y/z加以区分,其中:
x表示当前被变异的向量是“随机的”或“最佳的”;y是所利用的差向量的个数;z是指交叉操作的方式,上面所叙述的交叉操作的方法表示为“bin”。
利用这个表示方式,上述的基本DE算法可以描述为DE/rand/1/bin。
DE还有其他形式,如:
DE/best/1/bin,其中:
V=X
+F∗(X
−X)
(4)
DE/best/2/bin,其中:
V=X
+F∗(X−X
+X−X)
(5)
DE/rand/2/bin,其中:
V
=X+F∗(X
−X+X
−X)
(6)
作为一类简单而有效的进化算法[18],DE算法已被成功用于求解优化问题,包括有约
束与无约束优化,目前基于DE算法求解约束问题的大部分的算法所采用的约束处理技术是罚函数法。
本节只对近年来基于DE在约束优化方面工作做简单的总结Lampinen和Zelink[19]利用DE算法来解决工程设计问题,提出了“软约束”的方法来处理问题的约束条件,这一方式本质上是一种静态罚函数法,并通过三个重要的工程设计问题来验证算法的有效性。
该算法尽管避免了传统罚函数法在惩罚因子方面的弱点,但其对罚因子的设置要求很高,另一方面罚函数的定义非常复杂。
Efrén和Coello[20]使用了一种比较的选择准则来进化种群,并且加入了把少量不可行解保留的多样性机制,从而来扩大搜索空间,避免陷入局部最优,这种方法对那些最优解在约束边界的问题,取得了不错的效果。
Storn和Price[21]为了使所有初始群体成为可行解都落在可行域而在处理约束时采用了一种自适应机制,一方面是对可行域的扩张,从而使所有初始解可行,另一方面,自适应的对伪可行域进行收缩,同时在DE算法中利用基于衰老因子和重复生成子代的策略,缺点是算法中增加的用户的参数使得算法的计算量大大增加。
Becerra[22]等将文化算法的信任空间的知识源引入DE算法中,并将其用于求解约束优化问题,由于算法的信任空间对算法的搜索产生较高的选择压力,导致算法易陷入局部最优。
Sarimveis[23]等提出了一种排列的DE算法,算法中采用增广拉格郎日方法处置约束,罚因子与拉格郎日乘子随进化进程而调整,同时根据个体的适应度在种群中的排序来确定DE交叉变异的程度。
本文在差分进化算法中引入随机排序的方式来求解约束优化问题,并通过实验验证算法的性能。
4随机排序差分进化算法(SRDEA)
约束条件处置
关于
(1)式的约束优化问题,一般罚函数法中经常使用的以下的方式将约束优化转化成为如下无约束优化问题:
ψ(x)=f(x)+rφ(g(x))
其中ϕ≥0是实值函数,其由罚因子r决定各个约束的惩罚程度,且,
(7)
⎧max{0,g(x)}
j=1,...,l
⎨
ϕ(f(x))=⎪
(h(x))
j=l+1,...,m
(8)
约束违反度的值被用来惩罚不可行解,使得可行解能在进化的过程中受到优待而保留。
尽管罚函数法是处理约束优化中最常用方法,但它们的主要的一个缺点就是罚因子r的选取比较困难,若罚因子r过小,则属于欠惩罚,此时,群体可能收敛到不可行解;若罚因子r
过大,则属于过惩罚,此时,群体难以利用不可行解所提供的一些有用信息,而易陷入局部最优。
所以无论过惩罚或欠惩罚都不是好的约束处理方法,要解决这一问题,必需要平衡目标函数与罚函数以使算法在可行域里向最优解搜索,而不是在不可行域或组合可行域搜索最优解。
随机排序处理约束确实是基于这一思想提出的[8],其基本思想是:
若在可行解空间内,对
应目标函数值小的个体占优;在非可行解空间,引入一个随机数P,以概率P使对应目标
函数值小的个体占优,以概率1−P使违反约束函数值小的个体占优.通过这种概率的方式,
来达到平衡目标函数和约束函数的目的。
当P=0时,个体的排序处于过惩罚状态,此时,若一个可行解和一个不可行解比较,可行解占优;两个可行解或两个非可行解比较,以对应目标函数值小的占优,这样的方法就类似于文献[15]中采用的比较准则.当P=1时,个体排序处于亚惩罚状态,此时,个体的优劣只取决于个体对应的目标函数值,忽略了约束条件的作用。
一样来说,基于进化算法的约束处置技术只处置不等式约束条件。
关于等式约束
h(x)=0,通常的处置方法是把它们转变为不等式约束h(x)≤δ,其中,δ为等式约束条件
的容忍值。
容忍值的选取方式有两种,一种是动态容忍值,另一种是静态容忍值[20]。
动态容
忍度值方法是指δ随着进化代数的增加,越来越趋近于一个近似于0很小的正数,在进化的最后时期,此时的不等式约束就近似于等式约束。
静态容忍度值方法就是直接令δ等于一个
近似于0很小的正数,本文采用的是静态容忍度值方式。
随机排序差分进化算法(StochasticRankingbasedDifferentialEvolution
Algorithm,SRDEA)
本文提出的随机排序差分进化算法(SRDEA)基于DE算法的改进,同时采纳随机排序处置约束的方法,算法具体步骤如下。
Step1:
随机生成NP个个体组成初始群体X=(X,X,"X),这些个体从给定边
界的约束内随机进行选择,一样假定其符合均匀概率散布;设置算法初始参数:
变异参数F,
交叉参数CR、最大进化代数G和随机数P;
Step2:
计算各个个体的目标函数值,并判断搜索是否结束,否则转到第3步;
Step3:
采用进行
(2)式和(3)式进行差分变异操作和差分交叉操作,以生成新个体;
Step4:
选择操作。
由于处理约束采用的随机排序的方式是一种类似冒泡排序的方式,针对这个方法的特点,本文对传统的DE算法的贪婪选择做了改进。
SRDEA中将交叉变异后新产生的种群与先前的种群混合在一起重新排序,得到新种群进入下一代,而不是当前个体与其父辈个体做一对一的贪婪选择。
算法流程如下图1所示:
f(x)
x
∀i,i=1,2,",NP
∀i,i=1,2,",NP
r≠r≠r
j=randint(1,D)
≤
u=v=x+F∗(x−x)
u=x
I=[x;u]
φ(I)=φ(I)=0
f(I)>f(I)
I,I
rand(j)≤P
φ(I)>φ(I)
I,I
x=I(1:
1:
NP)
图1:
SRDEA算法流程(randint是在区间(1,D)随机产生一个整数的函数)
5仿真实验与结果分析
本小节将对提出算法的性能进行全面测试,实验分为两部分,第一部分本文算法与其它算法比较测试,同时考察算法的收敛速度,第二部分对算法中的几个重要参数进行了分析。
比较测试实验
为了测试算法的性能,将本文算法对与目前比较典型的四个算法诸如采用动态处惩函数的进化策略[14](EvolutionaryAlgorithmbasedonHomomorphousMaps,indicatedbyEAHM)、采纳人工免疫响应约束进化策略[15](ArtificialImmuneResponseConstrainedEvolutionaryStrategy,indicatedbyAIRCES)、采纳可行性规则的差分进化算法[16](ConstraintHandlingDifferentialEvolution,indicatedbyCHDE),采纳随机排序的进化策略[8](ESwithStochasticRanking,indicatedbyESSR)进行了比较,测试采用国内外经常使用的13个标准测试函数.这些测试函数是用进化算法很难取得全局最优解的一些很具代表性的函数,关于这些函数的具体特征,例如可行域的特性和约束条件的类型等,在文献[8]中有详细的描述,其具体表达式见附录。
算法用Matlab实现,各算法均运行在Intel(R)Core(TM)2CPU,2GB内存,
WindowsXP操作系统的PC机上。
每个测试函数独立运行30次,统计SRDEA的30次运行中获得的最优结果、中值、平均结果、最差结果、以及标准差。
本文中的参数设置与CHDE[14]维持一致,具体参数设置如下:
NP=60,G=5800,变异参数F取[,]之间均匀随机数,交叉参数CR取[,]之间均匀随机数,P=。
EAHM与AIRCE的参数设置见文献[18]。
等式约束h(x)=0被转变为不等式约束h(x)≤δ,其中对问题g05,δ=;对问题g03,g11和g13,δ=。
表1给出了SRDEA算法运行30次得到的结果,其中“Optimal”是问题已知的最好的解。
由表1看出,对13个测试问题,除了问题g07、g13,其余问题都能取得最优解;对g05、g11得到了比现有最优解更好的结果,其原因把等式约束转换成了不等式约束,扩大了搜索范围。
表1:
SRDEA的测试结果
问题
Optimal
最优结果
中值
平均结果
最差结果
标准差
g01
-15
0
g02
0.
0.
g03
1
g04
g05
g06
g07
g08
0.
0.
0.
0.
0.
g09
0.
g10
g11
g12
1
1
1
1
1
0
g13
0.
0.
图2给出了SRDEA算法对13个函数算法的进化曲线。
在13个测试函数中g02、g03、
g08和g12为求最大值优化问题,其余函数为求最小值优化问题。
为了方便进化曲线的表示,咱们把这四个求最大值优化问题取反转化成求最小值问题。
其中每个函数都独立运行30次,每隔五百代取一个点,得到函数此时的最优解的均值与标准差,其中在该点的各个函数的最优解的均值用圆圈表示,标准差用在该点的上下竖直线表示。
从图2可以看出除函数g02、g07、g13外,其余函数均能在给定代数内收敛到最优解,而且进化速度快,稳固性较好。
meanandstd
meanandstd
-15
0200040006000
)
0200040006000
generation(g02)
0
meanandstd
x10
meanandstd
-1
0200040006000
0200040006000
generation(g04)
meanandstd
meanandstd
26
0200040006000
generation(g05)
meanandstd
0200040006000
generation(g06)
meanandstd
25
24
0200040006000
0200040006000
generation(g08)
meanandstd
7500
7400
7300
meanandstd
0200040006000
functionvalue
7200
7100
7000
0200040006000
generation(g10)
-1
meanandstd
-1
-1
-1
-1
meanandstd
0200040006000
generation(g11)
-1
0200040006000
generation(g12)
meanandstd
0
0200040006000
generation(g13)
图2SRDEA的收敛曲线
表2分别就EAHM、AIRCES、CHDE、ESSR和SRDEA30次运行获得的最优结果,
平均结果和最差结果进行比较。
其中“---”表示找不到可行解,“NA”表示不可用;“No”
表示文献中未给出结果。
表2:
EAHM,AIRCES,CHDE,ESSR和DEASR的统计结果比较
问题最优解统计项EAHMAIRCESCHDEESSRSRDEA
最优结果
g01g020.g03g04g05g06
g07
平均结果-14.最差结果-12.最优结果0.0.0.0.平均结果0.0.0.0.最差结果0.0.0.0.最优结果平均结果0.最差结果0.最优结果平均结果最差结果最优结果---No平均结果---No5128-881最差结果---No最优结果平均结果最差结果最优结果No平均结果No最差结果No
g080.最优结果0.0.0.0.0.
平均结果
0.
0.
0.
0.
0.
最差结果
0.
0.
0.
0.
0.
最优结果
g09
平均结果
最差结果
最优