第25卷第12期 计算机应用与软件Vol125No.12
2008年12月 ComputerApplicationsandSoftwareDec.2008
一种自适应差分演化算法毛润宇1 王小平1 薛小平21(同济大学计算机科学与技术系 上海200092)
2(同济大学信息与通信工程系 上海200092)
收稿日期:2008-01-22。国家自然科学基金项目(60475019)。毛润宇,硕士生,主研领域:计算机网络。
摘 要 差分演化算法是一类基于种群的启发式全局搜索技术,对于实值参数的优化具有很强的鲁棒性。为了提高差分演化算法的寻优速度、克服启发式算法常见的早熟收敛问题,提出了一种自适应的方法来调整控制参数。实验表明,算法的收敛速度和寻优能力得到很大的提高。
关键词 差分演化 自适应 优化
ANADAPTIVEDIFFERENTIALEVOLUTIONALGORITHMMaoRunyu1 WangXiaoping1 XueXiaoping21(DepartmentofComputerScienceandTechnology,TongjiUniversity,Shanghai200092,China)
2(DepartmentofInformationandCommunicationEngineering,TongjiUniversity,Shanghai200092,China)
Abstract Differentialevolution(DE)isanewheuristicglobalsearchingtechniquebasedonpopulation,whichhasbeenfoundtobeveryrobustforrealparameter’soptimization.InordertoacceleratetheconvergencespeedofDEalgorithminoptimalsearchingandtoovercometheprematureconvergencewhichisfrequentlyexistedinheuristicalgorithms,inthispaperitproposedanadaptivedifferentialevolutionalgo2rithmtoadjustthescalefactorandthecrossoverprobabilityadaptively.Theexperimentindicatedthatthisalgorithmimprovesremarkablytheconvergencespeedandoptimalsearchingability.
Keywords Differentialevolution Adaptive Optimization
0 引 言差分进化DE(DifferentialEvolution)是一种基于群体差异的启发式随机搜索算法,该算法是RainerStorn和KennethPrice于1995年共同提出的,是一种采用实数矢量编码在连续空间中进行随机搜索的优化算法[1]。差分进化算法因原理简单、受控参数少、鲁棒性强等特点,引起了越来越多的学者关注[2,3]。但是DE算法也有它的不足之处,随着进化代数的增加,个体间的差异逐渐降低,特别是过早地收敛到局部极值附近时,会导致DE算法早熟。为了提高DE的寻优能力、加快收敛速度、克服启发式算法常见的早熟收敛问题,许多学者对DE算法进行了改进[4-6]。本文提出了一种用于复杂函数优化的自适应差分演化算法ADE(AdaptiveDifferentialEvolution)。该算法随着搜索过程的进行自适应地调整缩放因子和交叉概率,以减少算法控制参数的人为因素影响。1 标准差分演化算法DE进化流程与遗传算法相同,包括变异、交叉和选择的进化操作。DE算法的选择操作通常为贪心选择的过程,交叉操作方式与遗传算法大体相同,变异操作使用了一种差分策略,这种差分策略从当前种群中随机选择三个点,以其中一个点为基础、另两个点为参照做一个扰动,实现个体的变异。这种算法有效地利用了群体分布特性,提高了算法的搜索能力,避免了遗传算法中变异操作的不足[7]。对于优化问题:
minf(x1,x2,…,x
D)
s.t xmin≤xi≤xmax
i=1,2,…,D
(1)
式中,D为变量的个数,xmin和xmax分别表示第i个变量xi取值范围的上界和下界。DE算法包括以下几个方面:
(1)初始化
根据具体问题给定的变量初始寻优区间[x
min,xmax]
,利用
如下线性变换:
xij(0)=xmin+rand(0,1)·(xmax-xmin)(2)
式中,
x
ij(0)表示第0代的第i个个体的第j个变量。NP表示
种群大小,rand(0,1)为在[0,1]均匀随机数。(2)变异操作
选取g的3个互不相同的个体x
r1(g),xr2(g)和xr3(g)按
照以下的方法产生扰动向量v
i(g+1)
:
vi(g+1)=xr1(g)+F(xr2(g)-xr3(g))
i≠r1≠r2≠r3(3)
式中,F为缩放因子控制个体差值的幅值,
x
i(g)表示第g代种
群中第i个个体。
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
8 计算机应用与软件2008年
在进化过程中,为了保证解的有效性,必须判断个体中各变量是否满足边界条件,如果不满足边界条件,则变量用随机的方法重新生成。实际上,Price和Storn提出了十余种不同的差分策略来实现变异操作[8]。上述的变异方法是最常用的一种。(3)交叉操作
对第g代种群{x
i(g)}及其变异的中间体{vi(g+1)
}
进
行个体间的交叉操作:
uij(g+1)=
vij(g+1) rand(0,1)≤CRorj=j
rand
xij(g)
(4)
式中,CR为交叉概率,jrand为[1,2,…,D]的随机整数,用于确保vi(g+1)有至少一个变量遗传给ui(g+1)。(4)选择操作
DE采用贪婪算法来选择适应度高的个体进入下一代种群,
xi(g+1)=ui(g+1) f(ui(g+1))≤f(xi(g))xi(g)(5)
2 自适应差分演化算法差分演化算法的主要控制参数有种群规模NP、缩放因子F、交叉概率CR三个。通常做法是根据经验选取一组固定参数,种群规模NP∈[5D,10D],缩放因子F∈[0,1],交叉概率CR∈[0,1]。这种方法有一定局限性,在演化的不同阶段,由于个体在搜索空间所处的位置不同,个体的差异性亦不同,无法满足不同阶段算法的性能要求。国内外对于控制参数选取的研究已有很多,例如ChangCS和XuDY[9]提出一种线性变化策略;Mendes和Mohais提出了F和CR的随机选取原则[10,11]等等。本文提出一种自适应的控制参数选取方法。由于F和CR
的选择是影响差分演化算法行为和性能的关键所在,直接影响算法的收敛性,因此,应考虑F和CR能够随着适应度以及演化代数动态调整。2.1 缩放因子的自适应当种群内的个体适应度趋于一致或者收敛于局部最优解时,使F增加;而当群体适应度比较分散时,使F减小。同时对于适应度大于平均适应度的个体,对应大的F值,使该解被淘汰掉;相反对于适应度低于平均适应度的个体,越接近平均适应度的个体对应越大的F值确保多样性。因此,自适应的缩放因子能够提供相对于每个解的最佳F值。自适应差分演化算法在保持群体多样性的同时,保证差分演化算法的收敛性。F按式(6)进行自适应调整,
F=1-
favg-f′
favg-fbest
f′
avg
1,f′≥f
avg
(6)
式中,f′为待变异个体的适应度值;favg为群体的平均适应度值;fbest为群体中最大的适应度值。算法开始阶段favg和fbest差距很大,所以几乎不存在局部收敛的可能,则当f′越小,即F越小,良好的基因可能会保持下来。随着演化代数的增加favg和fbest差距减小,F有减小的趋势,
向最优解收敛的速度逐步加快。由于收敛速度是逐步加快的,
所以减少了局部收敛的危险。
2.2 交叉概率的自适应交叉概率用于表示待变异个体的基因选入新个体的概率。本文提出的CR自适应函数根据演化的代数动态改变CR的值。开始时CR比较小为CR
0,以较小的交叉概率保持群体的多样性,
随着演
化的进行,个体开始逐步收敛,此时增加CR的值,不仅提高变异个体基因选入新个体的概率,并且加快了收敛速度。当CR=CR
1,
不
再增加CR的值保持CR的稳定。CR按式(7)进行调整:
CR=G1000-G
+CR0 CR
CR1 CR≥CR1
(7)
式中,G为演化代数。经过多次实验确定CR
0=0.4,CR1=0.
9
。逐步增加CR
的值,既可以保持较快的收敛速度又可以防止局部收敛的发生。
3 计算结果分析本文选取了4个常用的多变量测试函数,如表1所示。验证ADE算法的性能,并与标准的差分演化算法进行比较。其中Sphere函数为单峰二次函数;Rosenbrock函数是一个非凸、病态函数,难以全局最小化求解;Generaltest函数在可行域内有210
个局部最优解,其全局最优值为278.3323;Rastrigin函数为多峰函数,在xi∈[-5.12,5.12]范围内大约存在10n个局部极小值。
表1 常用的多变量测试函数函数名称函数表达式
SphereF=∑Di=1x2i |xi|≤100 D=30
RosenbrockF=∑D-1i=1[100(xi+1-x2i)2+(xi-2)2]|xi|≤100 D=10GeneraltestF=1D∑Di=1(x4i-16x2i+5xi) |xi|≤100 D=10
RastriginF=∑Di=1(x2i-10cos(2πxi)+10) |xi|≤5.12 D=10提高算法的收敛速度是本文对于差分演化算法改进的一个重要目标。本文以适应度的最差值和最优值的差作为收敛界限,实验中将收敛界限设置为1E26,将NP设置为100,选取最大演化代数500作为停止条件。分别用DE和ADE两个算法测试4个函数,每次实验执行20次,统计平均最优解的收敛情况。计算结果如图1和表2所示。对于不同函数ADE算法的收敛性能基本都能维持在较高的水平,特别是对于一些DE算法需要长时间演化的函数,ADE算法也可以快速的收敛。从图1中可以看出ADE算法的收敛速度是随着演化代数的增加逐步加快的。如表3所示,ADE的最优解优于DE算法求解的值,并且达到或非常接近理论解。总体而言,ADE对于4个测试函数都能很快收敛到全局最优解,而且算法很稳定。