一种新的改进的混合蛙跳算法

1、2011-1-12收稿日期:2010-10-20基金项目:国家自然科学基金资助项目(the National Natural Science Foundation of China under Grant No.60974082;商洛学院科研基金项目(ScientificResearch Foundation of Shangluo University under Grant No. 09SKY011,10SKY024作者简介:赵鹏军 (1979-,男,陕西渭南人,硕士,讲师,主要研究方向:最优化理论与方法,智能计算及其应用;邵泽军 (1981-,男,山东临沂人,硕士,助教,主要研究方向:智

2、能交通管理.一种新的改进的混合蛙跳算法赵鹏军1,邵泽军21.商洛学院 数学与计算科学系,商洛 7260002.北京化工大学北方学院 三河 0652011.Department of Mathematics and Computational Science, Shangluo University, Shangluo 726000, China2.North College of Beijing University of Chemical Technology, Sanhe 065201,ChinaZHAO Peng-Jun 1, SHAO Ze-Jun 2. Novel Improved

3、Shuffled Frog Leaping AlgorithmAbstract: To overcome the drawbacks of local optima and instability involved in Shuffled Frog Leaping Algorithm (SFLA, an improved SFLA is proposed. The proposed algorithm employs opposition based learning (OBL to generate the initial population, which can obtain fitte

4、r initial candidate solutions. During the course of evolvement, the differential evolution (DE is embedded in SFLA organically to maintain the population diversity, Numerical results show that the proposed SFLA has a better capability to solve complex functions than other algorithms. Keywords: shuff

5、led frog leaping algorithm(SFLA; opposition; differential evolution(DE摘 要: 针对混合蛙跳算法在优化过程中受初始值影响较大且容易陷入局部最优的缺陷,提出了一个改进的混合蛙跳算法,该算法利用基于对立学习的策略产生初始种群,提高了产生解的质量;在进化过程中,将差分进化有机地嵌入其中,维持了种群的多样性。数值结果表明,改进的混合蛙跳算法对复杂函数优化问题具有较强的求解能力。 关键词:混合蛙跳算法;对立策略;差分进化 中图法分类号:TP18 文献标识码:A1 引言混合蛙跳算法1 (Shuffled Frog Leaping Alg

6、orithm, SFLA最早是由Eusuff 和Lansey 于2000年提出,源于对青蛙觅食行为的研究,具有概念简单,参数少,计算速度快,全局寻优能力强,易于实现等特点,并且简单易用,已在多个领域取得了成功1-4。然而,和其他智能优化算法一样,SFLA 同样存在易收敛到局部最优,在求解部分函数优化问题时效果不够理想的缺陷。对立策略是提高算法优化性能的一种新方法5,文献6将其应用于差分进化(Differential Evolution, DE算法中,数值结果验明了其有效性。文献7将其引入进化计算,提出一种基于对立策略的种群初始化方法,即用种群对立产生方式来取代传统的种群随机生成方式。在进化过程

7、中同时考虑随机点和其对立点,比单纯地使用随机方法更有效。DE 算法6最初由Store 和Price 于1995年提出,该算法通过变异、杂交、选择操作来更新随机产生的初始种群,经过逐步迭代,不断进化,可实现全局最优解的搜索。SFLA 和DE 算法都是基于群体智能和随机策略、并依据各自的搜索机制进行寻优。为提高SFLA 的性能,本文利用对立策略和DE ,提出了一种基于对立策略和差分进化的混合蛙跳算法(记为ODSFLA ,可有效改善SFLA 的求解效率,为求解优化问题提供一种新的优化工具。 2 混合蛙跳算法SFLA 是通过个体间的协作与竞争来实现在多维空间中对最优解的搜索。下面以函数最小化为例,说明

8、SFLA 的基本步骤。设青蛙种群规模为P ,其中第i 个个体在n 维空间中的坐标为12(,i i i ni x x x x ,计算个体的适应度(i f x ,根据适应度将其按递减顺序排列。然后将整个种群划分为S 个子群,每个子群中包含N 个个体,即满足关系P S N ,在进化过程中,第一个解放入第一个子群,第二个解放入第二个子群,一直分配下去,直到第S 个解放入第S 个子群。然后,第1S 个解又放入到第一个子群,第2S 个解放入到第二个子群,这样循环分配下去,直到所有解分配完毕。在每一个子群中,适应度最优和最差的解分别记为12(,b b b nb x x x x 和12(,w w w nw x

9、 x x x ;种群中适应度最优的解记为12(,g g g ng x x x x 。在每次进化中,对w x 进行更新操作,其更新策略为:(j b w D r x x ! (1'w w j x x D (max max j D D D ! (2其中r 为0,1之间的均匀随机数,1,2,j S ,max D 为最大移动步长。如果'w x 的适应度优于w x 的适应度,则用'w x 代替w x ;如果没有改进,则用gx 替换bx 重复执行式(1、(2;如果仍没有改进,则从搜索空间中随机产生一个新解取代原来的w x ,在指定迭代次数It 内继续执行以上操作,这样也就完成了SFL

10、A 的一次进化。 3 改进的混合蛙跳算法 3.1 对立策略对立策略同时考虑当前点和其对立点,从中选择较优点。文献6已经证明了利用对立点的信息比利用随机信息能更快找到最优解,同时实验也表明对立搜索可比随机搜索更有效。对立点定义5如下:设12(,n P x x x ,i i i x l u #,1,2,i n ,为n 维搜索空间中的一个点,i i l u 分别为i x 的下界和上界,其对立点可表示为12(,n P x x x ,其中 网络出版时间:2011-5-19 14:35i i i i x l u x !,1,2,i n (33.2 改进的混合蛙跳算法ODSFLA 算法的主要思想如下:为提高

11、初始种群的质量,用对立策略初始化种群,即随机生成P 个初始解,按式(3对每个初始解求其对立解,比较该初始解和其对立解的适应度,从2P 个解中选取适应度较好的P 个解作为初始种群;为提高群体的多样性,将DE 有机地嵌入SFLA 中,充分利用了SFLA 和DE 搜索机制的互补性,增加搜索过程发现新解的概率,进而能有效避免搜索陷入局部最优。在这里选取基本的DE 算法(DE/rand /1/bin ,其详细步骤见文献6,由于SFLA 在搜素过程中存在子群内更新和子群外的混合迭代两种形式, 式。本文提出的两种算法1 (记为子群数S For i = 1 : max N If mod 用SFLA Else用

12、基本的End End算法2 (记为子群数S For i = 1 : max N For j = 1 :If mod 用ElseEnd End其中mod ( 为取余函数,R 为控制参数,从以上过程可以看出,在进化初期,由于提高了初始种群的质量,因此有利于算法快速定位于较好搜索区域;而随着进化的进行,SFLA 和DE 的交替搜索在一定程度上维持了种群的多样性,使各子群中保留更多有利信息,有利于算法的持续寻优。 4 仿真实验为验证ODSFLA 的性能,实验选取Sphere, Rosenbrock, Rastrigin, Griewank, Ackley 和Schaffers f7六个典型函数作为测试

13、对象,文中对SFLA 、DE 、ODSFLA1和ODSFLA2分别进行测试,为增强可比性,以下所有测试的公共参数设置均相同。200P ,20S ,10It ,5R ,4个算法分别运行30次,其他参数见表1。表1 参数设置函数n 搜索空间 max N Sphere 20 -5.12 5.12n 500Rosenbrock 20 -30 30n 500Rastrigin 20 -5.12 5.12n500 Griewank 20 -600 600n 500 Ackley 20 -32 32n 500Schaffers f7 20 -100 100n500表2列出了以上4种算法求解优化问题的测试结果

14、,由表2可知,本文的两种算法由于采用了对立策略进行初始化种群,提高了产生解的质量;而在进化过程中SFLA 和DE 的交替操作有效地维持了种群的多样性,对上述6个典型测试函数的优化结果优于SFLA ,也基本上优于DE ,且ODSFLA2的寻优效果优于ODSFLA1。与文献3中的数据相比,由于文献中使用随机判别条件对不同维数上的分量进行更新,因而本文算ODSFLA2 1.5853e-4 4.2555e-4 2.2199e-4 Schaffers f7 SFLA DE ODSFLA1 ODSFLA2 2.6773e-1 8.1243e+0 5.5428e-1 2.2405e-1 6.4839e+0

15、1.0434e+1 4.6010e+0 4.7082e+0 4.5383e+09.8752e-1 2.7987e+02.6177e+0图1 6是上述6个函数采用4种算法运行30次后求得的平均最优适应度进化曲线。由图可以看出,在其中5个测试函数上,本文算法的收敛速度好于SFLA 和DE ,对于Rosenbrock 函数,本文算法的收敛速度也好于SFLA 。这主要是因为新算法能够一直较好地保持多样性,从而为SFLA 的更新操作提供更好更有效的信息。 图1 Sphere 函数进化曲线 图5 Ackley 函数进化曲线图6 Schafferf7函数进化曲线综上所述,本文所提算法不论对单峰函数或多峰函数都有较好的收敛性能,是一种有效可靠的全局优化算法。 5 结束语SFLA 是一种新的随机搜索算法,本文将对立策略和差分进化嵌入其中,对6个测试函数的仿真结果表明新算法相对于SFLA 和DE 的性能有了一定的提高,有很强的全局搜索能力,能有效避免早熟收敛,而且算法的收敛速度快,稳定性好。接下来我们将研究本文算法的实际应用。 参考文献:1 Elbeltagi E, H