改进的混合蛙跳算法|动态规划算法 经典实例

　　 文章编号:1001-9081(2012)01-0234-04 doi:10.3724/SP.J.1087.2012.00234 　　 　　摘 要: 为提高混合蛙跳算法在优化问题求解中的性能,提出了一种改进混合蛙跳算法。改进算法在原算法基础上加入了变异算子,并根据算法进化过程的不同阶段和进化过程中候选解分布情况，利用模糊控制器对变异算子的变异尺度进行调整，实现了变异算子在解空间中搜索范围的动态调整。通过对优化问题中4个典型测试函数的仿真实验表明,与基本蛙跳算法和已有改进算法相比，改进算法在寻优精度、收敛速度和求解成功率上均有一倍以上的提高,尤其在高维复杂优化问题求解中体现出较强的寻优能力。
　　�关键词:
　　模糊控制器；混合蛙跳算法；变异算子；变异尺度
　　�中图分类号: TP18 文献标志码:A
　　 �
　　�
　　Abstract: To enhance the performance of Shuffled Frog Leaping Algorithm (SFLA) in solving optimization problems，this paper proposed an improved shuffled frog leaping algorithm. By adding mutation operator to the original algorithm, the improved algorithm regulated the scale of mutation operator via fuzzy controller, made a dynamic adjustment of mutation operator in the searching range of solution space with different phase and candidate solution distribution of evolution process. The simulation results of four typical functions of optimization problems show that the proposed algorithm can attain above twice improvement on accuracy, convergent speed and success rate, and it demonstrates a better optimization capability especially in solving the high dimensional complex optimization problem, in comparison with the basic shuffled frog leaping algorithm and the known improved algorithm.
　　
　　
　　 Key words: fuzzy controller; Shuffled Frog Leaping Algorithm (SFLA); mutation operator; mutation scale
　　
　　0 引言�
　　混合蛙跳算法［1］(Shuffled Frog Leaping Algorithm, SFLA)是由Eusuff等于2003年提出的一种结合了模因算法(Memetic Algorithm, MA)和粒子群优化算法(Particle Swarm Optimization, PSO)的全新进化算法。该算法具有概念简单、易于实现等特点,常被用来解决各种优化问题［2-3］。为了提高混合蛙跳算法解决复杂优化问题的性能,国内外学者对其进行了大量的研究。如：Zhang等［4］在子群内部搜索策略中加入“认知分量”,提高了算法的求解成功率和跳出局部最优的能力;赵鹏军等［5］在子群内部搜索策略中结合吸引排斥机制,有效避免了算法早熟收敛;Elbeltagi等［6］在子群内部搜索策略中通过引入“搜索加速因子”,提高了算法的全局寻优能力。不难看出,以上学者均是对子群内部搜索策略作一定的改变来提高算法性能。本文不修改原算法的子群内部搜索策略,而是在全局信息交换过程中增加变异算子,并根据算法运行的状态,采用模糊控制器［7］调整变异尺度。仿真结果表明,本文算法在收敛速度和求解精度上都能取得较好的效果,算法性能得到了有效提升。�
　　1 混合蛙跳算法�
　　混合蛙跳算法是一种受自然生物模仿启示而产生的协同进化算法,它模拟了青蛙群体寻找食物时按子群分类进行信息交换的过程:先随机从解空间中产生一组初始解(种群),再将整个种群分为多个子群,子群中的青蛙按照一定搜索策略执行子群内部搜索。在已定义的子群内部搜索次数结束之后,又混合全部青蛙,然后排序再分子群,使各个子群间的信息得到全局交换。各子群内部搜索和全局信息交换一直持续交替进行到满足收敛条件或达到最大进化代数为止。以下简要介绍混合蛙跳算法的数学模型。�
　　�1)子群划分。�
　　设种群内青蛙(候选解)个数为N,子群数为k,子群内候选解个数为n。用X�j=(x��j1�,x��j2�,…，x��jD�)表示第j(0≤j≤N)个候选解,D表示候选解的维数。对于随机产生的初始种群S=(X�1,X�2,…，X�N),按适应度f(X)降序排序后,使第1个候选解分入第1子群,第2个候选解分入第2子群,…,第k个候选解分入第k子群,第k+1个候选解又分入第1子群,第k+2个候选解分入第2子群,依次重复直到N个候选解分配完毕。�
　　
　　2)子群内部搜索。�
　　设X�b为一个子群中适应度最好的候选解,X�w为一个子群中适应度最差的候选解,X�m为整个种群中适应度最好的候选解。对每个子群进行内部搜索,即对子群中的X�w进行更新,搜索策略如式(1)所示:�
　　X′���=X��w�+R×(X��b�-X��w�)(1)�
　　其中：X′为式(1)产生的新解,R是0到1之间的随机数。如果X′优于X�w,则X�w=X′；否则,式(1)中的X�b换为X�m,重复执行搜索策略(式(1))。若X′仍然不能优于X�w,则随机产生一个候选解取代X�w。重复上述步骤,到搜索次数大于设定的最大子群内部搜索次数时终止。��
　　3)全局信息交换。�
　　当所有子群内部更新完成后,重新执行子群划分和子群内部搜索,如此反复直到满足终止条件为止(收敛到最优解或达到最大进化代数)。�
　　
　　2 算法改进�
　　
　　2.1 变异算子�
　　在进化算法中,变异操作是一种提高求解性能的有效手段［8］。本文在原算法的全局信息交换过程中增加变异操作,设计如下变异算子。�
　　�X���new��=X+R×M×(X�b－X)(2)�
　　其中：X���new��表示变异后产生的新解,X表示当前被执行变异操作的解,R是0到1之间的随机数,M为变异尺度控制量,X�b为当前种群的最优解。�
　　从式(2)中可以看出,变异算子是对解空间的进一步搜索,其搜索范围受到变异尺度(M）取值的影响。如:M值较大时,对应较大的变异步长,能扩大搜索范围；相反则会缩小搜索范围。而算法在解空间内搜索范围过小易陷入局部最优,搜索范围过大则易导致收敛速度降低变成完全随机搜索。因此,本文根据算法运行状态来动态调整搜索范围(即通过控制变异算子中M的取值来实现)。具体如下：对于算法进化过程的不同阶段,在初期,应尽可能地扩大寻优范围,使算法定位到较好的搜索区域;而随着算法的运行,在进化的中后期,应逐渐缩小搜索范围,确保深度寻优能持续进行。另外也需考虑进化过程中候选解的分布情况,如过于集中说明有陷入局部收敛的可能,应适当扩大搜索范围;相反过于分散则可能导致收敛速度慢或无法收敛,应适当缩小搜索范围。�
　　
　　基于以上分析不难发现,M的取值应该由“算法进化阶段”和“候选解分布情况”共同控制,但其中存在许多很难用传统的数学方法来精确度量的模糊概念(如:“算法运行初期”、“候选解分布过于集中”),而模糊控制技术正是能有效处理这类不确定性问题的数学工具,并且作为一种模拟人近似推理和综合决策过程的智能控制技术,已成功用于提高进化算法性能的实践中［9］。为此本文引入模糊控制技术,即采用模糊控制器来实现对式(2)中M取值的控制。��
　　
　　2.2 模糊控制器设计�
　　�设模糊控制器的输入为T、E,输出为M,如图1。其中：T表示算法进化阶段测量值，E表示候选解分布测量值，M表示变异尺度控制量。��
　　
　　�1)针对算法进化阶段测量值T,设i表示当前算法运行代数(即全局信息交换次数),G表示算法运行的总代数,用�式(3)�表示:�
　　T(i)=i/G(3)�
　　T(i)较小说明算法处于进化早期,可以扩大搜索范围(�Large�);T(i)较大表示算法已经处于进化中后期,�应逐渐减小搜索范围(Small),以保证深度搜索。因此选择模糊化语言变量{Large,Normal,Small}作为�T�的语言值,其三角形隶属函数如图2。�
　　
　　�2)针对候选解分布测量值E,采用文献［10］提出的分布熵来表示。设N为种群中候选解总数,将解空间划分成Q个相等区域,对于第i代种群统计每个区域所包含的候选解数目,记为Z�1,Z�2,…,Z�Q,则候选解出现在第k个区域的概率为�q�k=�Z�k/N,其中k=1,2,…,Q,候选解的分布熵记为:�
　　E(i)=－∑Qk=1q�k�ln� q�k(4)�
　　其中：E(i)越小说明候选解分布越集中,需要适当增大搜索范围(�Large�);相反,E(i)越大则说明候选解分布越分散,应适当缩小搜索范围(�Small�)。因此选择模糊化语言变量{�Large,Normal,Small�}作为E的语言值,并参照文献［11］,采用初始种群分布熵作为分布熵最大值,记作Em(若E(i)>Em则令E(i)=Em),其三角形隶属函数如图3。��
　　
　　3)针对变异尺度控制量�M�,当其取值不同时,变异算子可对应不同的搜索范围,用模糊化语言变量{Large,Normal,Small}作为�M�的语言值,分别表示解搜索范围的大、中、小,其三角形隶属函数如图4。�
　　
　　�最后,由表1得到的模糊控制器输出语言值需要进行去模糊化处理,转化为具体的变异尺度取值范围(即M的取值区间)。结合M语言变量的三角形隶属函数(图4),对每种语言值取三角形底部的左右顶点来对应M的取值区间。具体规则如表2。��
　　
　　2.3 改进后的算法流程�
　　�设群体中候选解个数为N、子群数为k、最大子群内部搜索次数为P、最大全局信息交换次数为G,候选解的适应度为f(X)。以最小值优化问题为例,本文提出的改进混合蛙跳算法流程用伪码表示如下：�
　　
　　程序前
　　�
　　随机产生�N�个候选解组成初始群体�S�；�
　　求�S�里各候选解的适应度�f�(�X�j�)；�
　　for(�i�=1;�i�［6］的改进算法(Modified Shuffled Frog Leaping Algorithm, MSFLA)、基本混合蛙跳算法SFLA作对比,选择如下4个典型的函数优化问题［10,12］进行测试。�
　　�设D代表解的维数, f�1代表�Sphere�函数, f�2代表�Rosenbrock�函数, f�3代表�Griewank�函数, f�4代表�Schaffer� �F�7函数,4个测试函数的理论最优值均为0。�
　　f�1(x)=∑Di=1x�2; x�i∈［－200,200］�
　　f��2�(x)=∑D-1i=1［100(x��i+1�-x�2��i�)�2+(x��i�-1)�2］; x��i�∈［-5,5］�
　　f��3�(x)=1+∑Di=1x�2��i�4�000-∏Di=1(�cos�x��i�i); x��i�∈［-600,600］�
　　f��4�(x)=∑D-1i=1(x�2��i�+x�2��i+1�)��0.25�［�sin��2(50(x�2��i�+x�2��i+1�)��0.1�)+1］;�x��i�∈［-100,100］��
　　实验的硬件环境为:AMD 64位双核2.6�GHz CPU，�2�GB�内存。�参数设置为：种群中解个数N=300,子群数k=30,子群内解个数n=10,子群内部搜索次数P=10。实验从3个方面进行:��
　　1)根据平均最优适应度比较三种算法的求解精度；�
　　2)通过平均进化曲线比较三种算法的收敛速度；�
　　3)固定收敛精度,结合平均进化代数为全文统一，此处是否应该改为“进化代数”？请明确。来比较三种算法的求解成功率。�
　　
　　3.2 实验结果及分析�
　　1)算法求解精度对比。�
　　设定全局信息交换次数(即算法进化代数)�G�=400,针对每一函数独立进行20次实验,表3~6分别给出了求解精度结果。其中第2~5列分别给出在不同维数下算法求得的平均最优适应度�
　　
　　从表3~6中实验结果可以看出,随着测试函数维数的增加,特别是在30维的情况下,ISFLA求得平均最优适应度都比另外两种算法小。说明ISFLA对于高维复杂优化问题有较高的求解精度。�
　　2)算法收敛性能对比。�
　　为了对比算法收敛性能,设定全局信息交换次数(即算法进化代数)�G�=400,每一函数独立进行20次实验,下面的图5~8是4个测试函数(变量维数�D�=30）的平均进化曲线。其中：横坐标代表算法进化代数�G�，纵坐标代表了进化过程中每一代的平均最优适应度因之前未对F作这样交代，所以现在补充在这里，是否合适？请明确。另外，“”是为了我们查找问题，后期会删除。。同时为了较直观地考查各种算法的进化趋势,对其计算结果取自然对数。�
　　
　　从图5~8中可看出,ISFLA与SFLA和MSFLA相比收敛速度更快,在进化初期就能迅速收敛到理论最优解附近,然后保持向理论最优解靠近的趋势,具有较好的收敛性能。�
　　
　　3)算法求解成功率对比。�
　　指定各测试函数收敛精度如表7,变量维数为30,算法独立运行10次后结果如表8。其中成功率=100%×(达到精度的实验次数/总实验次数)。为了避免算法因局部收敛而使程序无法结束,本实验设最大全局信息交换次数(即算法进化代数)为500,如在500次迭代内程序未能结束,则认为算法无法收敛到指定精度。�
　　
　　
　　由表8中结果可以看出,对于4个测试函数,在指定收敛精度下,ISFLA均能在200次迭代内达到90%以上的成功率。与SFLA和MSFLA相比,ISFLA在求解高维复杂优化问题中能以较少的迭代次数达到较高的成功率。�
　　综上分析,本文提出的改进算法收敛性能、求解精度和求解成功率均获得了较满意的效果。尤其在高维优化问题的求解中,更体现出了本文改进算法的优越性。�
　　
　　4 结语�
　　本文改进了混合蛙跳算法，通过增加变异算子,并结合模糊控制器修改变异尺度,实现了变异算子在解空间内搜索范围的动态调整。实验结果表明,本文提出的改进算法有效提高了算法收敛速度和求解精度,增强了算法的寻优性能,尤其在高维复杂优化问题求解中体现出较强的求解能力。
　　
　　
　　�参考文献:�
　　[1]
　　EUSUFF M �M,� LANSEY K �E.� Optimization of water distribution network design using the shuffled frog leaping algorithm ［J］. Water Resources Planning and Management, 2003, 129(3): 210- 225.
　　�[2]
　　ELBEHAIRY H, ELBELTAGI E. Comparison of two evolutionary algorithms for optimization of bridge deck repairs ［J］. Computer-Aided Civil and Infrastructure Engineering, 2006, 21(8): 561- 572.
　　�[3]
　　AMIRI B, FATHIAN M, MAROOSI A. Application of shuffled frog-leaping algorithm on clustering ［J］. The International Journal of Advanced Manufacturing Technology, 2009, 45(1/2): 199-209.
　　�[4]
　　ZHANG �XUNCAI,� HU �XUEMEI,� CUI �GUANGZHAO.� An �im-�proved shuffled frog leaping algorithm with cognitive behavior ［C］// Proceedings of the 7th World Congress on Intelligent Control and Automation. Washington, DC: IEEE Computer Society, 2008: 6197-6202.
　　�[5]
　　赵鹏军，刘三阳.求解复杂函数优化问题的混合蛙跳算法［J］.计算机应用研究，2009，26(7): 2435-2437.
　　�[6]
　　ELBELTAGI E, HEGAZY T, GRIERSON D. A modified shuffled frog-leaping optimization algorithm applications to project management ［J］. Structure and Infrastructure Engineering, 2007, 3(1): 53-60.
　　�[7]
　　郭文成,师五喜,郭利进.一类不确定非线性系统的自适应模糊控制［J］.系统工程与电子技术,2010,32(2):351-354.
　　�[8]
　　冀俊忠,黄振,刘椿年.基于变异和信息素扩散的多维背包问题的蚁群算法［J］.计算机研究与发展,2009,46(6):644-654.
　　�[9]
　　喻寿益,邝溯琼.嵌套式模糊自适应遗传算法［J］.控制工程,2010,17(1):75-80.
　　�[10]
　　邵增珍，王洪国，刘弘.具有启发式探测及自学习特征的降维对称微粒群算法［J］.计算机科学,2010,37(5):219-222.
　　�[11]
　　王新亮，倪世宏.基于改进PSO的规则提取方法［J］.计算机工程,2008,34(20):221-223.
　　�[12]
　　陶新民,刘福荣,刘玉，等.定向多尺度变异克隆选择优化算法［J］.控制与决策,2011,26(2):175-181.
　　
　　
　　 收稿日期:2011-06-20;修回日期:2011-08-22。
　　
　　 基金项目:
　　四川师范大学青年基金资助项目(10QNL04)。�
　　
　　作者简介:
　　葛宇(1981-)，男，四川西昌人，讲师，硕士，CCF会员，主要研究方向:计算智能； 王学平(1965-)，男，四川遂宁人，教授，博士生导师，博士，主要研究方向:不确定性的数学理论及算法； 梁静(1979-)，女，四川泸州人，讲师，硕士，CCF会员，主要研究方向:图形图像。

推荐访问:蛙跳 算法 混合 改进的混合蛙跳算法 混合蛙跳算法