基于混沌的动力学演化算法

2006年6月安阳工学院学报June. 2006第3期(总第21期)Journal of Anyang Institute of TechnologyNo, 3( Gen. No 21)基于混沌的动力学演化算法李彦勤王侃(河南经贸职业学院,河南郑州45000)摘要:文章在现有动力学演化算法的基础上提出基于混沌的演化算子。除有效地防止过早收敛并且保持解的均匀分布外,新算法充分利用混沌对于初始值敏感性和遍历性的特点,还具有更快的收斂速度和更小的计算量。数值鲒聚显示在解决多峰值问题时新算法不仅有很好的性能和高可靠性,而且优于作者已知的其他已出版的结果。关键词:动力学演化算法;过早收敛;混沌初始化;混沌变异;种群多样性中图分类号:TP01文献标识码:A文章编号:1673-2928(2006)03-0052-030引言系统中的粒子x1,x2,…xN演化算法中的演化代数从20世纪90年代初期开始,演化计算与生物在此记为时间t。学、计算机科学、数学、物理学以及其他学科的交义下面介绍一下动力学演化算法中的相关概念。研究在理论和应用方面都取得了很大进展134,粒子x,在t时刻的动量p(t,x)被定义为但是仍然有一些问题尚未解决,首先是过早收敛p(t, xi)=f(t, x: )-f(1.2)(在演化早期阶段丧失种群的多样性),以及缺乏合f(t,x1)是在t时刻示粒子x1的目标函数值适的停止准则的问题。定义了一个活动量a(t,x,),如果在t时刻x参考文献[5]中提出了一种基于统计力学理论被选择参加进化操作,则粒子x1在t时刻的活动量的动力学演化算法。它把种群看作一个动力学系被定义为,把种群中的个体看作是粒子,系统中每个粒子(t,x1)=a(t-1,x;)+1(1.3)有一个动量p(k,x)和一个活动量a(t,x1)以模拟否则保持不变分子运动,这两个参数联合控制选择操作并驱使粒综合这两个参数我们定义了一个新的选择策子在解空间内移动搜寻,提出了基于最优控制论的略。两个停止准则来测试系统是否在统计力学意义上slet(t,x)=λ∑p(k,x)|+(1-λ)a(t,取得它的最低的能量或者最大的熵的状态)(k=0,1,…t)混沌是自然界里一种很常见的现象,它有随机权重λ(∈(0,1))用来均衡两条件的比重。在性,遍历性和对起始条件的敏感性等特点。所有这迭代过程中,slet(t,x)(i=1,2…N)被按照从小到些使得混沌可以被用来解决优化问题6。利用它大的顺序排序DEA的选择策略是:一个粒子的动量的积累变陷人局部最优。本文中的新算法利用混沌的随机化量越小,以往被选择的次数越少,在本次迭代中性,遍历性和对初始条件敏感性的特点克服了传统它被选择的可能性越大。因此在迭代的过程中,全的随机初始化方法的不足。由于对交叉、变异概率部粒子都将可能被选择,即DEA的选择策略将驱动等参数选择的不精确性,传统的随机初始化方法难系统内的全部粒子运动搜寻最优解,正如粒子时刻以保证解集的范围,引起重要基因的丢失,导致过到处移动一样。也正是因为这一点,我们将新算法早的收敛。而基于混沌的演化算法使得种群具有称为动力演化的算法。真正的随机性,已有一系列的基于混沌的演化算法另外,DEA还根据动量提出两条新的停止准被提出,事实证明加入混沌思想的算法更高效。则。第一条准则是算法描述如果1.1动力学演化算法的描述∑lp(t,x,)|<东(i=1,2,…N)(1.5)设有一个最小值优化问题演化停止,这里是一个事先给定的误差准许min f(x)(1.1)值学四心味着全部粒子移动f(x)是目标函数,S是它的可行的解的集合和消中国煤化工能量最低状态。在新算法中,将N个已编码的解类比为动力学CNMHG收稿日期:2006-04-07作者简介:李彦勤(1981-)女,河南经貿职业学院教师。如果Step 1:用新初始化策略初始化种群r,计算rMax∑lp(k,x)|>M(k=0,1,…t;x∈中粒子的函数值且设置p(t,x)=0,a(t,x)=0,(1.6)x∈r,计算sc(t)并按大小排序,保存最好的粒子,则算法停止。M是给定的一个适当大的数,例 Gennum=0;如,M可被取为最大的目标函数值和最小的目标函Step2:选择排在slet( GenNum)最前部的a个数值的差。但在实际应用中要确定一个适当的M粒子;值是困难,必须经过多次仔细的试验。Step3:对这n个粒子实施新的进化操作;1.2混沌操作和动态变异概率Step4:修改这n个粒子的评价函数值,动量和新箅法提出新的初始策略和新的变异算子来活动量的;加快收敛。数字实验显示IDEA能保持种群多样Step5:保存最好的粒子和它们的函数值,修改性,避免过早收敛,并且是快速可靠的slct( GenNum)并排序,1.2.1新初始化策略( GenNum)← Gen Num+1根据混沌的随机性,遍历性和对初始条件的敏Step6: P= Pm *(1-Gen Num *0. 01/maxGen)感性等特点,我们利用 logistic方程引入新的初始化Step7:如果不停止,回到Step2策略根据新算法,产生分布均匀的初始种群,在迭1=μx1(1-x1)(H=4(17)代过程中全部粒子都将被选择参加演化操作,选择N个初始化值随机产生算子和动态变异算子Pn也使种群均匀分布且避免N∈[0陷入局部最优k是优化函数的自变量的个数,N是种群规模。2实验结果然后利用(1.7)式产生作为演化的混沌种群。在这个部分里,我们利用IDEA解决一些典型比如,y可以通过将y作为混沌序列的初始的数值优化问题。这些例子经常被用于测试演化值,由(1.7)式反复迭代得到(k代表迭代的次数)。的算法的性能。在本程序中,我们把种群大小N然后使用下面的映射函数得到一个均匀分布定为100,使用第一个停止准则。以下的3个函数被的种群:x,;=a1+(b-a,)y,x,;∈[馮,b];用验证新算法的效率。1,2,…,N(1.8)(1)Six-hump Camel Back Function1.2.2基于混沌的变异算子minf(x1,x2)=(4-2.1x12+1/3x1)x12+变异操作在Gas中属于辅助性操作,它起到保x1x2+(-4+4x2)x2持种群多样性的作用。通常,低的变异率能防止演where-3≤x1≤3,umnd-2≤x2≤2化过程中单个基因的丢失;太高的变异率会把CAs这个函数有6个局部最优解,并在两个不同的变成纯随机检索。通常,变异率P。是在0.001左点取得全局最优解:(x,x2)=(-0.0898,0.7126)和(x1,x2)=(0.0898,-0.7126)。基本的变异操过程如下最大迭代次数设置为200,0=10-3。在这些1)使用预先确定的变异率P决定是否执行变设置下,我们连续执行程序10次,结果如下表所异操作示2)将已确定执行变异操作的个体x;根据下式表映射到区间[0,1]上:F-min-valX,=(xa)(a1-b,),i=1,2,…k;j-]0316280.0899330712390019995.831833E4(1.9)然后用(7)式得到1,通过(18)式再映射10316280089930.71271021556321314E4回去得到新个体的x。比较x,和x,保留较优1031628|00900712526121973370812E4103162900898420712647018474480823E51.2.3动态的变异率P103162900898420471265522924258演化算法中,交叉操作是主要操作,但是它过1.03162200910380-071234425392.128796E5度的依赖于当前的种群情况,容易陷于局部最优10316908407126540241869368E4变异操作能有效地摆脱局部最优但是由于变异的101890912413913034官目性,它仅仅在演化的早期阶段有效,当算法开10124100910120181254始接近最优解集时,变异操作几乎不起作用。为了1031638093012594212842116加快收敛速度我们需要动态改变变异概率Pn。从表中可看出,两个点以等概率取得且我们得利用下列公式来动态改变变异概率到的最小值均小干-1.0316结果表明,新算法快P= P*(1-Gen Num *0.01/ maxGen速、准中国煤化工Gen Num是当前演化代数, maxGen是最大代CNMHG数0.3c09(3丌x1)1.24IDEA算法0.4cos(4x2)+0.753其中-50≤x1,x2≤50。这个函数在(0,0)有一3小结个全局最优解0。结果如下表所示。本文根据动力学理论和混沌理论提出新的算表2法。混沌序列对于初始值的敏感性一方面使得算F-min-va法很容易跳出局部最优,另一方面混沌本身的特点01.288464-1484388El1737使得算法克服了纯随机函数的局限性,使算法更接8.24822371544426E7973近于自然界中的进化过程。新算法提出基于混沌2433083E111.71990E-11861理论的初始化策略和变异策略驱动全体解向最优5422493E12-1.251275E-11754解移动。新的演化策略可以在演化过程中有效的1067623E-138405404E8128628E8避免陷入局部最优。通过3个典型的数值优化问287683E144274502E8-8564709题证明了新算法的高效性。但是由于IDEA与传统9860141E64412475E4458819E4675演化算法的区别,更多相关的收敛理论有待进一步1.245244008190461E7251探讨。557667E126091238E94.074859E75742140027E-117395142E12961参考文献:[1]Mitchell,M.An(3)Press, Cambridge, Massachusetts, 1996min f(x,y)=-[x sin(9y)+y cos (25x)+ [2] Baeck, T, Fogel, D. and Michalewicz, Z. Handbook ofevolutionary computation, Volume 1. Oxford University其中x2+y2≤81,-10≤x,y≤10Press, Oxford, England, 1997这个函数在点(y,x)=(04400-6.02780)取得全局最小值-32.7179。结果如下and hyperplane- defined function, Evolutionary Computa-2000,8,p373-391表所示4] Michalewicz Z, Genetic algorithms +Data structures =E表3volution prograrns, Springer Verlag, Berlin, Germany327164462730475[5]Yuanxiang Li, xiufen Zou. Solving Global Optimal problem327179-6440-627803554by using a Dynamical Evolutionary Algorithm. Proceedings32686865200-6166855274of the Fifth International Conference on Algorithms and Ar-chitectures for Parallel Processing, the IEEE Press, 2002ppl70-173.7000-62000-650007561[6]Haijun Yang, Minqiang Li. Dynamical Behavior of Genetic32,7964001-627804283Algorithms with Finite Population. Acta Automatica sinica327179-64400627802964Nov.,2004,Vol.30,No,6327116440262795271327142-6,44006.2792The Dynamical Evolutionary Algorithm Based on the ChaoticLI Yan -gin WANG KanHenan Vocational College of Economy and Trade, Zhengzhou 45000, China)Abstract: This paper proposes an improved dynamical evolutionary algorithm (IDEA) based on the theory of statistical mechanics anovel chaotic operation. Besides preventing premature convergence effectively and keeping the population in good distribution, the newalgorithm makes full use of initial value sensitivity and track ergodicity of chaos, overcoming the disadvantage of big searching deadzone existed in conventional chaotic mutation model. The numerical results show IDEA not only has good performance and a high de-gree of reliability while dealing with various complex problems, but also is superior to any other published results known by the authorsKey Words: dynamical evolutionary algorithm; premature convergence; chaotic mutation; population diversity中国煤化工编辑郝安林CNMHG