利用Alopex改进的动力学演化算法

·2·(总796)利用 Alopex改进的动力学演化算法2007年文章编号:1003-5850(2007)11-000204利用 Alopex改进的动力学演化算法An Dynamical Evolutionary Algorithm Improved by alopex姜欹1乐庆玲(武汉科技大学计算机学院武汉430081)(2湖北大学武汉430062)摘要】通过将动力学演化算法( Dynamical Evolutionary Algorithm,DEA)与一种随机优化方法—— Alopex算法相结合,提出一种改进的动力学演化算法。改进的算法改善了动力学演化算法摆脱局部极小点的能力,对典型函数的测试表明:改进算法的全局搜索能力有了显著提高,特别是对多峰函数能钞有效地避免早熟收敛问题【关键词】动力学演化算法, Alopex,进化计算中图分类号:TP301.6文獻标识码:AABSTRACT A stochastic optimization algorithm is proposed by combining dynamical evolutionary algorithm (DEA)with Alopexalgorithm that is a stochastic optimization method. The proposed algorithm improves the ability of breaking away from localminima. The experiment results demonstrate that the proposed algorithm is superior to the original dynamical evolutionaryKEYWORDS dynamical evolutionary algorithm, Alopex, evolutionary computation从20世纪90年代初期开始,演化计算与生物学;群描述成一个动力系统,种群中的所有个体被看成是计算机科学数学物理学以及其他学科的交叉研究在动力学中相互作用的粒子,它们的宏观行为可描述成理论和应用方面都取得了很大进展,但是仍然有一些一个微分方程系统将这个系统和算法策略合并在问题尚未解决,首先是过早收敛(在演化早期阶段丧失起,定义了演化算法的一个最优控制问题。利用最优控种群的多样性),以及缺乏合适的停止准则的问题。参制理论中的 Pontryagin最大值原理,对演化算法进考文献[5]中提出了一种基于统计力学理论的动力学行了最优轨线分析,提出了演化算法的最优轨线理论,演化算法(DEA)。它把种群看作一个动力学系统,把定义了一个起核心作用的 Hamilton函数。种群中的个体看作是粒子,系统中每个粒子有一个动设有一个最小值优化问题量P(,x)和一个活动量a(t,xi)以模拟分子运动这ninf(x)(x∈s)两个参数联合控制选择操作并驱使粒子在解空间内移f(x)是目标函数,S是它的可行的解的集合动搜寻,提出了基于最优控制论的两个停止准则来测在DEA中,将N个已编码的解类比为动力学系试系统是否在统计力学意义上取得它的最低的能量或统中的粒子x1,x2,x3,…,x。演化算法中的演化代数者最大的熵的状态。在此记为时间L。下面介绍一下动力学演化算法中的尽管DEA已被成功地应用于各种优化问题及实相关概念际工程领域但是当面对复杂的优化问题,尤其是多粒子x在t时刻的动量p(t,x)被定义为峰、多极值的多模态函数优化问题时,由于目标问题存p(, ti)=f(u,xi)-f(t-1,x在着众多的局部极值因此不可避免地存在着早熟、收∫(t,x)是在t时刻时粒子x的目标函数值敛速度慢等缺陷。为提高动力学演化算法对复杂问题定义了一个活动量a(t,x),如果在t时刻x被选全面最优解的探测能力,本文提出了将DEA与择参加进化操作,则粒子x在t时刻的活动量被定义Alopex相结合的思想,并设计和实现了算法。通过实为a(,x)=a(-1,xz)+1验证明,这一方法能够提高DEA的全局收敛性能否则保持不变综合这两个参数我们定义了一个新的选择策略1动力学演化算法(DEA)sla(t,x)=λ∑|p(k,x)1+(1-x)a(,x)动力学演化算法(DEA)最初是由武汉大学李元(k=0,1,…,t)(4香教授于2002年提出,其基本思想是将演化算法的种中国煤化工条件的比重。在选代CNMHG2007-08-27收到,2007-09-25改回·基金项目:武汉科技大学青年基金资助项目(No.2006XY22)“作者简介:姜毅,男1978年生,讲师在读博士,研究方向:智能计算。第20卷第11期电脑开发与应用总797)·3·过程中,slct(t,x)(=1,2,…,N)被按照从小到大的P: (n)顺序排序。DEA的选择策略是:一个粒子的动量的积1+e+4, 7T累变化量越小,以往被选择的次数越少,在本次迭代中△(n)=[x;(n-1)-x(n-2)]它被选择的可能性越大因此在选代的过程中,全部粒[f(n-1)-f(n-2)]子都将可能被选择,即DEA的选择策略将驱动系统式中:f(n)—一目标函数在第n次的取值;x内的全部粒子运动搜寻最优解,正如粒子时刻到处移(n)—目标函数的第个自变量在第n次迭代中的动一样。也正是因为这一点我们将这种新算法称为动取值;3(n)和内1(n)—第n次迭代中的自变量x随力演化的算法。另外,DEA还根据动量提出两条新的机行走的步长和向增加方向行走的概率n1—随停止准则。第一条准则是如果机数;户(n)和p(n)—正向变化概率和反向变化概∑p(,x)|<∈(i=1,2率。式(9)中正负号的选取与实际问题有关,正号使问题极小化,负号使问题极大化。实验表明,为保证算法演化停止,这里是一个事先给定的误差准许值。从统计力学的观点看它意味着全部粒子移动和消散的收敛速度,需合理选择步长和控制参数,一般b初能量使动态系统取得它的能量最低状态。始值的大小根据变量变化的范围来确定,通常取变量变化范围的几百分之一或更小,改进的 Alopex算法第二个准则是如果的收敛速度对初始值的依赖性有所降低Max∑|p(k,x)|>M(k=0.1,…,t,x∈S)(6)则算法停止,M是给定的—个适当大的数,例如,3基于 Alopex改进的动力学演化算法M可被取为最大的目标函数值和最小的目标函数值为解决大规模优化问题,充分利用动力学演化算的差但在实际应用中要确定一个适当的M值是困难法与 Alopex算法的优越性,本文提出了将改进的的,必须经过多次试验。Alopex算法加人动力学演化算法的改进算法,其基本2改进的 Alopex算法思想是:按照动力学演化算法对粒子迭代一次后,计算粒子适应度值(目标函数)的变化,根据变量的变化和Alopex算法是一种启发式与随机优化相结合的目标函数的变化,确定粒子是否继续按此改变方向进算法,它从前次自变量变化对目标函数产生的影响中行进化。进行改进的 Alopex操作,即给予新个体一定得到启发,用过程控制参数控制行走方向的概率,利用的“噪声”使其具有一定的爬坡能力,有利于动力学算噪声”来摆脱局部最优解使算法具有一定的爬坡能法在搜索中跳出局部极值同时又能根据目标函数的力在一定程度上既克服了传统启发式算法易陷入局变化加速算法的收敛。在动力学演化算法进行到一定部最优的缺陷又克服了模拟退火算法从完全随机搜代数后,种群中近似最优解占据绝大部分,使得粒子的索到梯度搜索极为缓慢的不足。它不要求目标函数可更新很难跳出局部最优,致使收敛过程放慢计算速度微且能保证求出的解满足一定的精度特点是具有快低。为了保证算法的全局收敛性,需要维持解群中个体速的搜索能力。 Alopex算法在选代过程中,各个自变的多样性避免有效信息的丢失。另一方面,为了加快量不仅可以向正向变化,而且能以一定的概率向反向收斂速度,就要使解群较快地向最优状态转移,容易陷变化,其目的是使算法跳出局部最优值。从实验得知,入局部极值点。在动力学演化算法中引进改进的为得到全局最优解,自变量正向变化的步长应小一些, Alopex算法后,由于它在产生子代时可根据粒子的信避免由于步长过大错过全局最优值;而反向变化步长息产生一定的“噪音”,使子代与父代粒子间有一定的应大一些,因为反向变化的目的是使目标函数摆脱局差异,这样会使粒子群具有一定的多样性使算法有部最优值;若反向步长过小,目标函数跳出局部最优的的爬坡能力,收敛到全局最优。另外, Alopex算法在搜概率不大,由此可能会导致目标函数在某个局部最优索过程中利用前次自变量及其函数值的变化信息将有解的一侧来回摆动,不能跳出局部最优。改进的模型利于缩短搜索时间,其“噪声”也随着收敛过程的进行为逐渐减小,有科干篁法血全局最优前进x(n)=x(n-1)+6,(n)(7)中国煤化工b,p(n)=p(n)∩p(n)≥rCNMHG2,…,x};②粒子的8,1-p(n)=p(n)∩p(n)<(8)适应值,并保留最好的粒子③设置初始动量,活动量(n)-,p(n)=p(n)∩p(n)≥r1为:p(t,x)=0,a(t,x)=0,x∈X;④令t=计+1⑤按r0;,1-p(n)=p',(n)∩p(n)