一种改进的极值动力学优化算法

信息技术农业阌络信息2014年第11期AGRICULTURE NETWORK INFORMATION种改进的极值动力学优化算法张千(重庆交通大学管理学院,重庆400074)摘要:针对基本的极值动力学优化算法容易陷入局部最优解、数值寻优能力较差甚至不能寻优等缺点,提出一种带柯变异的基于种群的极值动力学优化算法。改进后的算法不仅具有局部搜索能力还具有全局搜索能力,同时提高了收敛速度和精确度。键词:极值动力学优化算法;种群;柯西变异中图分类号:TP315文献标识码:A文章编码:1672-6251(2014)11-0044-04An Improved OptimizationAlgorithmwith Extremal DynamicsZHANG QianSchool of Management, Chongqing Jiaotong University, Chongqing 400074Abstract: Aization algorithm with extremal dynamics was proposed based on the shortcomings and thinsufficiency of classical extremal optimization algorithm, which was easy to fall into local optimal solution, and had poor ability ofnumerical optimization, sometimes even had no optimal solution. The algorithm was called population-basedextremal optimizationalgorithm with Cauchy mutation. The improved algorithm not onlyhas the local search ability, but also has the global search abilityand the convergence speed and accuracy were improvedKey words: extremal dynamics optimization algorithm; population; Cauchy mutation极值动力学优化(EO算法是从统计物理学基础本文在实现基本EO算法的基础上,针对基本EO上发展而来的一种新颖的启发式优化方法,能有效地算法存在的不足,提出相应的改进措施,以提高算法解决复杂的组合优化问题,近年来受到了国内外研究的性能;同时针对典型的复杂测试函数,研究改进算学者越来越多的关注。该算法具有易于实现、局部搜法寻优性能,并通过多次仿真实验比较原算法和改进索能力强、无可调参数或可调节参数少等特点。EO算法的结果,证实算法的有效性和可行性。算法源于复杂系统自组织临界的思想,算法从优化问基本极值动力学优化算法(EO)的实现题内部变量之间的联系出发,将问题本身作为一个演1.1EO算法的机理化的复杂系统,变量之间的相似性构成了变量之间比EO算法是从BS模型发展而来,其研究对象为较、竞争、交流的条件、变量在局部寻优的过程中,单一个体,个体由组员构成,各个内部组元之间有着驱动整个系统向最优解运动,EO算法具有独特的视直接或间接的相互作用或关联,故由多个组元构成的角,为算法的研究提供了新的思路。个体就可以被看作成一个复杂系统。本文EO算法的EO算法实现简单,算法效率高,应用前景广阔。研究对象均称为“个体”,其内部组成元素均称为目前EO算法和其改进算法已经被成功地应用于求解“组元”。些组合优化问题,如图的二分问题、图着色、自旋般地,EO算法根据个体内部组元对个体目标玻璃问题、旅行商问题、可满足问题,以及一些工程函数值的贡献大小来赋予每个组元的适应度,适应度优化问题,与其他智能优化算法的比较研究表明,EO最小的组员就是最差组元。在每次迭代中,EO总是算法是解决NP组合优化难题的一种有效方法选择适应度最差的组元及其邻居来进行随机的变异,作者简介:张千(1987-),男,硕士,研究方向:物流系统分析方法和技术中国煤化工收稿日期:2014-09-25CNMHG《农业网络信息》2014年第11期信息技术从而使得所有组元都能协同进化,个体的适应度不断1.23适应度函数地得到改善,从而实现个体的自我完善。不管个体初对于只有边界约束(不含等式约束和不等式约始状态如何,在只给定组员总数N的情况下,系统会束)的问题,当前个体中组元x的适应度入定义为其演化到一种临界状态,最终可以找到近似最优解或最变异后对整体目标函数值的贡献大小,即A=OBJ(S优解。OBJ(Sbes,其中S是只对x进行变异而保持其它组1.2EO算法条件的选择元不变时产生的子个体,OBJS)是S的目标函数值基本EO算法的条件选取有几个方面,包括测试OBJ(hest是迄今为止找到的近似最优解 Shest所对应函数、乘法函数、适应度函数的选取,针对极小化问的目标函数值。对于含有等式约束和不等式约束的问题,具体条件选取如下3方面题,所有违背约束条件的惩罚函数值之和,即Q(S)1.2.1测试函数∑□1P(S)应该加入到组元x的适应度函数中去。因从文献[2]中选择1个 Benchmark问题(g09)作为测试函数。这些试函数对于一般的进化算法都是此,当前个体中组x的适应度函数如下非常难解的。该函数的数学表达如下A;=OBJ(S)-OBJ(Sbest)+Q(;)(7)测试函数g091.3EO算法的实现f(x)=(x1-10)2+5(x2-12)2-x24+10x”+7x62+x不是一般性,对于一个极小化问题,基本EO算法流程如下约束条件(1)随机产生一个个体(向量)S=(x1,x…x)g1(x)=-127+2x12+3x24+x3+4x42+5x5≤0设迄今为止找到的最优解为S,其目标函数值为CS),则初始S=S,CS)=CS);g2(x)=-282+7x1+3x2+10x32+x4-x5≤0(2)对于当前的个体S,进行如下操作:①分别g2(x)=-196+23x1+x2+6x62-8x7≤0对S中的各个组员进行非均匀算子变异,在对各个组g4(x)=4x12+x2+3x1x2+2x2+5x-11x员进行变异的时候,保持其他组员不变。②对生成的其中:-10≤x≤10(i=1,2,…7)最优解为x*=n个向量的适应度λ,i∈{1,2…,n}进行计算,找出适(23304,19513,-047754.3657,-062441.0381,1.5942)应度最小的那个向量S。③无条件接收无条件地接受最小值为f(x*)=680.6300S=S;④如果当前的目标函数CS)小于迄今为止找到22惩罚函数的最优目标函数值C(S)并且惩罚函数的值为0,则令般的,一个约束连续优化问题可以如下定S'=S,C(S)=C(S)(3)重复执行步骤(2),直到满足终止条件(即Optimize f(X),X=(x(2)当前代数达到最大迭代次数,或近似解满足精度要其中,f(X)为寻优函数,X∈S∩F,X∈R"是n维求)决策变量空间,该空间的所有变量都有以下约束(4)返回最优解S和最优目标函数值CS)。le≤xe≤ue,c=1,…,n基本EO算法的流程见图1。其中,1和u分别是x的上界和下界。集合F∈由上述基本EO算法的实现流程可以看出,基本R"定义了可行域,由以下rr≥0个约束条件来决定:的EO算法寻优时不需要调节任何参数,而且只有g(X)≤0.i=1,…,q(4)个变异算子,没有交叉算子,因此,基本的EO算法h1(X=0.i=q+1.…,r(5)操作简单,容易实现,免去了调节参数的麻烦很显然F∈S;2基于种群的带柯西变异的极值动力学优化通常采用惩罚函数法来处理约束连续优化问题。(PEO)算法对于最小化问题,当决策向量Ⅹ不满足第i个约束条由于基本EO算法总是选择最差组元来进行变异,件时,其对应的惩罚函P(X)为基本的EO算法较易陷人局部极值点。对基本EO算PO=/max0.g(X),1≤i≤q法进行改进,提中国煤化工题的新算hiOX2,q+l≤i≤r(6)法-带柯西变异HaCNMHGPopulation《农业网络信息》2014年第11期信息技术开始Gaussian(0, 1)0.35随机产生一个向量S=(x1,x2,…,xn),令其为迄今为止的0.30最优解即s’=S,C(S)=C(S)025Cauchy(o, 1)0.20分别对S中的各个组员进行非均匀算子变异,变异时保持其他组员不变,得到n个向量,计算n个向量的适应度,找出适应度最小的那个向量S图2柯西和高斯分布概率密度函数杏令S=S,若目标函数值C(S)小于迄今为止找到的最优目标函数值C(S)并且惩罚函数值为0,则令向上越接近水平轴,变得越缓慢,柯西分布可以看作S=S, C(S)=C(S)是无限的,这样基于高斯分布的邻域函数产生小波动的概率较大而产生大波动的概率几乎为零,基于柯西是否满足终止条件(迭代次数达到最大或满足精度要求)分别的领域产生小波动的能力相对高斯分布有所下降而产生大波动的能力增强,这样经过柯西变异就更有可能跳出局部最小值,从而增强了算法的全局搜索能返回最优解S·和最优目标函数值C(S')力。因此虽然柯西变异的局部搜索能力不如高斯变异,但柯西变异适合于粗调而且当搜索点离全局最优结束点很远时,采用柯西变异可以获得更好的结果。综上图1基本EO算法流程图所述:柯西变异算子与高斯变异算子不同之处在于based External Optimization,PEO)。由基本EO算法的柯西变异算子适合全局搜索,高斯变异算子更适合局实现过程起我们可以看出,基本EO算法在演化过程部搜索。因此本章采用引入种群的概念和柯西变异以中只有一个个体,没有种群。而PEO引人了种群的概使搜索点快速地向全局最优点靠拢,从而加快了收敛念即引人较大数量的个体同时进行演变。另外,本章过程并且跳出局部最优的PEO算法还采用了柯西变异算子以增加其全局搜索般的柯西变异算子的思想是:对于个体S=(x1能力,使得改进后的算法不仅具有局部搜索能力还具ⅹ3…x),对该个体的柯西变异是根据以下公式进行操有全局搜索能力。通过分别利用基本EO算法和带柯作西变异的PEO算法求解一个经典的约束连续优化问S=S+αC(0,1)题,来证实其有效性其中:α为控制变异步长的常数,C(O,1)是由2.1带柯西变异的PEO算法条件的选择t=1的柯西分布函数产生的随机数。为方便同基本EO算法相比较,本章所介绍的2.2带柯西变异的PEO算法的实现PEO算法条件选取除增加了基于种群的柯西变异之外不失一般性,对于一个约束最小化问题,带柯西与前章所述基本EO算法条件相同变异的PEO算法的具体流程如下维柯西密度函数集中在原点附近,其定义为(1)随机生成一个均匀分布的初始种群,种群大小0为比例参数,相应的分布函数定义为F(x)(2对于种群中每一个个体S,执行以下操作:①对每个组员X,j∈{1,…m},实施柯西变异操作,同由图2可见,柯西分布概率密度函数f(x)类似于时保持其他组元不变,就可以得到n个子个体S,j∈高斯分布概率密度函数,其差异主要表现为:柯西分{1,…川;②给每布在垂直方向略小于高斯分布,而柯西分布在水平方A=入=OBJ(S)-OEH中国煤化工试予适应度CNMHG个体的适应《农业网络信息》2014年第11期信息技术度进行排序,找出具有最差适应度的个体S,w∈{1,行30次。};④S取代当前个体S,即S=S,同时,令OBJ3.2实验仿真和结果分析(S)=OBJ(S);⑤如果OBJ(S)