毕业设计（论文）萤火虫算法的函数优化问题研究.doc

论文题目: 萤火虫算法的函数优化问题研究 学 院： 计算机与信息学院 专业年级： 软件工程2008级 学 号： 姓 名： 指导教师、职称： 2012 年 5 月 18 日 FireFly Algorithm for Function OptimizationProblems College: Computer and Information Science Specialty and Grade: Software engineering， 2008 Number: 081181067 Name: Guo Yu Dan Advisor: Lecturer Lin Xiao Yu Submitted Time: May 18， 2012 目 录摘要IAbstractII1引言11.1 本课题的研究意义11.2 本论文的目的、内容及作者的主要贡献11.3 研究方法与论文结构安排12萤火虫算法22.1 群智能算法22.2 萤火虫算法生物学原理22.3 萤火虫算法描述33萤火虫算法改进与仿真43.1 萤火虫算法改进43.2 仿真用的函数43.3 参数设置53.4 函数优化测试结果63.5 实验结论94总结11参考文献12致谢13摘要萤火虫算法是受自然界中的萤火虫通过荧光进行信息交流这种群体行为的启发演变而来的。它作为一种新颖的仿生群智能算法，有很大的改进空间。改进其算法必须分析它的仿生原理，从数学角度对算法进行合理优化与过程的定义。本文通过引入对萤火虫更新位置择优选择（Preferred FireFly Algorithm ，PFA）与对萤火虫空间距离进行归一化处理（Normalization FireFly Algorithm ，NFA）的策略，并通过4个典型的函数优化对算法进行仿真测试，测试结果表明了改进后的萤火虫算法在连续空间函数的可行性和有效性，具有良好的应用前景。关键词：萤火虫算法；函数优化；群智能算法；仿真测试AbstractThe fireflies algorithm is inspired by fireflies in nature to the behavior of the exchange of information of such groups by fluorescence evolved. As a novel bionic swarm intelligence algorithm, there is much room for improvement. Improve the algorithm must analyze the bionic principle, with the definition of the processof rational optimization algorithm from a mathematical point of view. In this paper, the introduction of updated position on the firefly choose the best (of Preferred FireFly Algorithm of PFA) with the firefly space distance normalized(Normalization the FireFly Algorithm, the NFA) of the strategy, and simulation test by fourtypical function optimization algorithm,the test results show the feasibility and effectiveness of the fireflies in the improved algorithm in continuous space function, has a good application prospects.Key words: firefly algorithm; function optimization; swarm intelligence algorithm; Simulation test1 引言1.1 本课题的研究意义在现实生活中，许多工程优化问题人们不仅要求出其最优值，而且希望获得其极值。这类问题对于传统的进化算法提出了严峻的挑战。为此，人们通过引入对传统进化算法的改进，使这类问题在一定程度上得到了解决。但这些方法在实际应用中存在一定缺陷，如精度不高，时间耗费多等等，于是寻找更有效的算法仍是研究者们追求的目标1。1.2 本论文的目的、内容及作者的主要贡献群智能算法作为仿生模拟算法，具有操作简单、并行、鲁棒性强等特点，他们根据生物各自的特性及其仿生原理，从数学上利用算法，把所有可能的解集作为空间范围，并从其中一个代表问题出发，根据空间范围中的一个解集，引入某种算子，并产生新的解集，由此逐步演化到求最优解的状态2。其中，萤火虫算法在众多算法中表示较为突出，其思想来源于萤火虫发光的生物学特性，萤火虫的亮度越高，吸引力就越大，吸引力又控制着萤火虫的移动。根据这种生物习性，而设计出的一种仿生算法，该算法在求解多极值函数优化问题方面取得很好的效果。但是随着函数极值点的增多，萤火虫数量也要大量增加，这样就导致了运算时间急剧增长。本文就该问题进行了研究，从数学的角度对算法进行重新定义，提出了一种基于萤火虫算法的改进算法，并验证其有效性与可行性3。1.3 研究方法与论文结构安排本论文先通过对萤火虫算法的概要描述，让读者了解萤火虫仿生的原理，再通过仔细的算法描述与流程讲解，细化萤火虫算法的概要内容，让算法的流程与原理更加清晰易懂。然后通过对传统的萤火虫算法进行改进算法实验，通过对4个函数的仿生实验，验证算法改进的优劣，比较与传统算法的效率，通过图表的验证，表达出在相同的迭代次数中，若改进算法与传统算法对目标值存在不同的数量级，则表示算法的改进存在优越性，比传统的萤火虫算法具有更好地寻优率，更高的精度，更快的收敛度。反之，若目标值属于同一数量级，则实验验证失败，改进算法对实际应用不起影响。2 萤火虫算法2.1 群智能算法群智能算法是一种新兴的演化计算技术，已成为越来越多研究者的关注焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系4。群智能理论研究领域主要有两种算法：蚁群算法和粒子群算法。蚁群算法是对蚂蚁群落食物采集过程的模拟，已经成功应用于许多离散优化问题。粒子群优化算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具5。群智能算法作为仿生模拟算法，具有操作简单、并行、鲁棒性强等特点，他们根据生物各自的特性及其仿生原理，从数学上利用算法，把所有可能的解集单做空间范围，并从其中一个代表问题出发，根据空间范围中的一个解集，引入某种算子，并产生新的解集，由此逐步演化到求最优解的状态6。2.2 萤火虫算法生物学原理萤火虫算法在众多算法中表示较为突出，其思想来源于萤火虫发光的生物学特性，萤火虫的亮度越高，吸引力就越大，吸引力又控制着萤火虫的移动。根据这种生物习性，而设计出的一种仿生算法，该算法在求解多极值函数优化问题方面取得很好的效果。传统的萤火虫算法利用其生物特性，通过互相吸引、寻路，对每一个随机分布进行比较，达到寻找其最优解得结果。但是随着函数极值点的增多，萤火虫数量也要大量增加，这样就导致了运算时间急剧增长，精度不高等，所以对算法的改进成了当务之急。在自然界2000多种萤火虫中，大部分都会萤火虫都会发光，而萤火虫就是靠着自身发光的习性进行信息传递。并且根据不同的闪光进行求偶、警戒，捕食等行为。萤火虫算法就是根据这种生物习性，排除生物物理上的意义，演变的仿生优化算法。通过这种算法，使得在一定规模范围内对随机的位置进行搜寻优化，并在范围内向位置最优解移动，通过一定的迭代次数，最终找到接近最值的最优位置7。在萤火虫算法中有两个要素，一个是萤火虫的亮度，一个是萤火虫的吸引度。在算法中萤火虫的亮度表现为其函数所在位置目标值，亮度越高位置就越佳，即目标值就越大，同时，目标值比较差得向目标值比较好的方向吸引。因为本论文是测试寻找最小值的函数效率，所以函数目标值越小的吸引度就越大，目标值比较大的向目标值比较小的方向吸引。萤火虫的吸引度通过相互的距离因素，影响着移动的位置。萤火虫之间的距离越大，则相互的吸引力就越小8。通过在萤火虫算法反复的随机实验，在这种多次随机点移动的过程中，亮度与吸引度反复更新，随机分布的点也逐渐向某一最值点靠近，在一定的迭代次数下，排除移动过程中的位置比较劣势的点，优化结果的取值，从而达到寻求最优位置点的效果，同时也比较了多种算法在相同的迭代次数下地优劣效率。2.3 萤火虫算法描述综上所述，用于函数优化问题的萤火虫算法的伪代码如下所述9：1、初始化基本参数。设置萤火虫初始化数目n、最大迭代次数MAX_GENERATION、搜索精度b、最大吸引度beta0、光强吸引系数gama、步长因子alpha、确定目标函数f，保证目标函数在一定的范围内有连续的波峰或波谷，并确定其范围的定义域，确定目标函数的维度D。2、随机初始化萤火虫位置，并计算其函数的目标值、相互的距离及萤火虫吸引度。多维函数两点间的距离公式为，若是二维函数，则两点间的距离r为，萤火虫吸引度beta为beta0 * 。3、比较各个点之间的目标值优劣，明确劣势点向优势点移动。在实验中则表示为if ( f ( i ) > f ( j ) ) then move i to j 。4、更新移动后的位置，并增加干扰项。二维函数更新后的位置表达式为xj * (1 - beta) + xi * beta + alpha* (Math.random() - 0.5)，其中alpha* (Math.random() - 0.5)为随机干扰项，避免过早陷入局部最优。5、当满足最大迭代次数或搜索精度时则进行下一步，否则继续第3步骤，同时迭代次数加一。6、进行循环实验，输出每次实验找到最优个体值和总平均个体值。3 萤火虫算法改进与仿真3.1 萤火虫算法改进传统的萤火虫算法（FA）在众多优化函数中存在一定的优越性，但在实际的一些应用中还是存在一定缺陷，如精度不高，时间耗费多等问题。基于这些问题，从数学的角度进行合理的分析，找到了对萤火虫位置更新公式的改进，位置更新公式的的条件判定，萤火虫搜索半径的可视化范围，对于萤火虫吸引度过小的归一化处理，基于惯性权重的合理分析改进等。每一种改进算法都是基于传统的萤火虫算法原理，配合实际过程中变量因子的合理改进。目的在与提高萤火虫算法的效率，精度，收敛度等10。对萤火虫位置更新公式的改进：在传统萤火虫算法的流程中的第4步“更新移动后的位置，并增加干扰项”，修改位置更新公式为下xi+(xj-xi)* beta* alpha* (Math.random() - 0.5),使得在改进的算法在整个迭代过程中保持合理的位置更新，避免了传统的萤火虫算法中迭代前期位置点距离过大而干扰项影响过小，迭代后期位置点距离过近而干扰项影响过大的问题11。对萤火虫位置更新公式的的条件判定：在传统萤火虫算法的流程中的第4步“更新移动后的位置，并增加干扰项”，加强了对传统萤火虫算法中的位置点更新后目标值的改进。使得只有在更新后的位置的目标值比原来的目标值更优的情况下才发生移动的状态，简化了算法的运行过程，在相同的迭代次数下，加强了位置点向最优点移动的可能性，提高了算法的精度12。对萤火虫搜索半径的可视化范围的改进：在传统萤火虫算法的流程中的第3步“比较各个点之间的目标值优劣，明确劣势点向优势点移动”，加入对萤火虫可视范围的判断。使得每只萤火虫在一定的范围内才发生吸引，而在范围外则是保持相对静止的状态。可视范围定于所有萤火虫到随机位置中心点得平均距离，使得更容易找到空间范围的局部最优点13。对于萤火虫吸引度过小的归一化处理：在传统萤火虫算法的流程中的第2步“计算萤火虫吸引度”，改进吸引度中由于前期萤火虫距离过大，导致吸引度趋于0的问题。引入归一化处理，对萤火虫的距离进行统一的规定，使得计算萤火虫吸引度更为合理，加强收敛度14。对基于惯性权重的合理分析改进：在传统萤火虫算法的流程中的第4步“更新移动后的位置，并增加干扰项”，由于萤火虫之间位置逐渐缩小，导致无法定位最优位置，而在极值点附近震荡的问题，引入线性递减的惯性权重，使得函数在迭代的后期具有更高的精度，有更多的位置点在极值点附近15。3.2 仿真用的函数测试函数为：Rastrigin测试函数 Min F1(x) = Rosenbrock测试函数Min F2(x) = ，Griewank测试函数Min F3(x) =,Axis hyper ellipsoid测试函数Min F4(x) =，3.3 参数设置参数设置：在萤火虫算法中，萤火虫初始化数目n=50，最大迭代次数MAX_GENERATION=200，搜索精度b=，最大吸引度beta0=1，光强吸引系数gama=1，步长因子alpha=0.2，目标函数的维度D=4。改进算法采用择优法（PFA）和归一化法（NFA）进行比较。择优法（Preferred FireFly Algorithm ，PFA）是在萤火虫算法的基础上对相互间吸引后的位置进行的改进，对更新后的位置与更新前的位置进行比较，选取最优的结果，使得每次的位置更新都更接近最优值。归一化法（Normalization FireFly Algorithm ，NFA）是通过对萤火虫吸引度beta=beta0 * 中两点间的距离r进行归一化处理r=r/max(r)，使得r的取值在0,1之间，避免因为维度和定义域的影响使得萤火虫吸引度beta在开始时趋于0。3.4 函数优化测试结果图3-1 Rastrigin函数测试结果表3-1 MAX_GENERATION = 100的仿真结果MIN F(X)MAX F(X)F(X)方差FAPFANFA4.80739965436402.51527124620071.997812859736112.965058395265610.250186067741118.90955973385746.86926719996776.36846052317677.07687801507949.505270467138.0644786233019.5543097868Rastrigin函数为高度多模态函数，在解空间存在大约10D个局部极小值（D为空间维度），理论最优值为0。由图表可知，上述实验中择优法（PFA）在Rastrigin函数中效果不明显，在相同的迭代次数下，目标函数值属于同一数量级，收敛度与精度没有明显的提高。认为改进没有达到预期的效果。归一化法（NFA）在Rastrigin函数中效果不明显，在相同的迭代次数下，目标函数值属于同一数量级，收敛度有所提高，但精度没有明显的提高。认为改进没有达到高效率的优化效果，但提高了收敛度。图3-2 Rosenbrock函数测试结果表3-2 MAX_GENERATION = 200的仿真结果MIN F(X)MAX F(X)F(X)方差FAPFANFA0.00254023530660.00141455858270.00238664156530.02013911197760.013210448257714.9506745808330.010174589640660.006999957122631.227301626899128.940586773E-52.232735919E-512.16257853358Rosenbrock函数，在=0时达到最小值，理论最优值为0。由图表可知，上述实验中择优法（PFA）在Rosenbrock函数中存在明显的效果。在同一迭代次数下，最优值的平均值与方差都有着明显的提高，说明越来越多的位置点在靠近最优值点，并且择优法（PFA）比传统的萤火虫算法首先进入收敛，存在明显的目标值数量级关系，存在更高的精度，在寻优上有着更高的效率。归一化法（NFA）在Rosenbrock函数中效果不明显，在相同的迭代次数下，目标函数值属于同一数量级，最优值的平均值与方差都比较大，说明位置分布比较零散，虽然收敛度有所提高，但精度明显没有提高。认为改进只是粗略变形，没有达到预期的效果。图3-3 Griewank函数测试结果表3-3 MAX_GENERATION = 200的仿真结果MIN F(X)MAX F(X)F(X)方差FAPFANFA3.6108837438E-69.3267891790E-65.3549971439E-61.5696827710E-47.7517905707E-51.6343592616E-57.65153731009E-52.22604768267E-58.39163229654E-62.774670776E-91.47694802E-101.27092931E-11Griewank函数为连续多模态函数，在=0时达到最小值，理论最优值为0。由图表可知，上述实验中择优法（PFA）在Griewank函数中存在明显的效果。在同一迭代次数下，择优法（PFA）比传统的萤火虫算法首先进入收敛，并且存在明显的目标值数量级关系，存在更高的精度，位置点也比较靠近最优点在相同条件下，在寻优上有着更高的效率。归一化法（NFA）在Griewank函数中效果比较明显，在相同的迭代次数下，目标函数值首先进入收敛，并且精度大大提高。最优值的平均值与方差最为精确，位置点更靠近最优点，在相同条件下，在寻优上有着更高的效率。图3-4 Axis hyper ellipsoid函数测试结果表3-4 MAX_GENERATION = 200的仿真结果MIN F(X)MAX F(X)F(X)方差FAPFANFA2.2637716962E-52.4531000523E-59.9374383148E-63.3926786028E-41.9833645368E-41.2849955089E-41.71416255136E-47.41159342022E-57.75542641321E-54.100349474E-91.570021522E-91.453180267E-9Axis hyper ellipsoid函数，单峰，在=0时达到最小值，理论最优值为0。由图表可知，上述实验中择优法（PFA）在Axis hyper ellipsoid函数中存在明显的效果。在同一迭代次数下，择优法（PFA）比传统的萤火虫算法有着更高的精度，并且存在明显的目标值数量级关系。在相同条件下，在寻优上有着更高的效率。归一化法（NFA）在Axis hyper ellipsoid函数中效果比较明显，在相同的迭代次数下，目标函数值精度大大提高。最优值的平均值与方差更精确，在相同条件下，在寻优上有着更高的效率。3.5 实验结论综上所述，择优法（PFA）与归一化法（NFA）改进在Rastrigin函数中的效果不太明显，最值，均值，方差没有明显的改变，均是在同一数量级上，而择优法（PFA）对Rosenbrock函数，Griewank函数，Axis hyper ellipsoid函数存在明显的数量级关系，精度更高，有更多的位置点在最优点附近，更有效率。归一化法（NFA）对于Rosenbrock函数，虽然效果比传统的萤火虫算法（FA）略差，最值，均值，方差都比较粗糙，但收敛的速度却是最高的。归一化法（NFA）对于Griewank函数在迭代前期效果比择优法（PFA）好，更快地接近最优，后期随着迭代次数的增加，精度和最优点的密集度都还可以提高。归一化法（NFA）对于Axis hyper ellipsoid函数与择优法（PFA）没有明显差异。另外，在实验外还进行了两者的结合算法（Normalization Preferred FireFly Algorithm，NPFA），确定萤火虫搜寻半径的（Search Radius FireFly Algorithm，SRFA），基于惯性权重的（Inertia Weight FireFly Algorithm，IWFA），基于对位置更新公式改进的（Location Update FireFly Algorithm，LUFA）等改进算法。NPFA的实验结果更趋近于NFA改进，收敛比较快，但精度略低。SRFA实验结果与FA算法相似，但由于对随机搜索范围的限定，使得精度不高。IWFA改进是对在后期的迭代次数中，由于萤火虫之间位置逐渐缩小，导致无法定位最优位置，而在极值点附近震荡的问题，引入线性递减的惯性权重，使得函数在迭代的后期具有更高的精度，有更多的位置点在极值点附近。LUFA是基于迭代前期位置更新公式中随机数影响较小，而在后期距离逐渐靠近，随机数影响较大的问题的改进，改进结果同时存在收敛快，但精度低的问题。4 总结通过上述实验测试，可以认为本文提出的择优的改进方法（PFA）与传统的萤火虫算法之间存在的一定的优越性，择优法（PFA）通过在算法中对更新后的位置进行重新判断，择优选择，排除了算法更新随机点位置中存在的劣势点位置的可能性，使得每一次的位置更新都向最优点靠近。加快了运算的速度，提高了寻优的能力，确保了寻优的精度，提高了效率，使得函数的目标值更快的接近最优值，更早的进入收敛。因此，认为该改进算法在连续空间函数的可行性和有效性，具有良好的应用前景。参考文献1 马明惠，叶春明.基于文化改进的兵行粒子群算法J.计算机工程,2008,34(2):193-195.2 彭喜元,彭宇,戴毓丰.群智能理论及应用J.电子学报.2003年S1期.3 李雪梅,张素琴,基于仿生理论的几种优化算法综述J.计算机应用研究.2009年06期.4 萤火虫算法百度词条.2011-08-01. 5 水文工具集.6 随机函数百度词条, 2011-01.7 Metropolis N.群智能优化算法M,王强.北京:清华大学出版社,2006.13-14.8 9 张波,陈睿君,路璐,粒子群算法在投资组合中的应用J.系统工程.2007年08期.10 Szymon Lukasik and Slawomir Zak. Firefly Algorithm for Continuous Constrained Optimization TasksA.Eds.N.T.Ngugen,R.Kowalczyk,S.M.Chen.ICCCI 2009,Lecture Noture in Artifical IntelligenceC.2009.97-100.11 Ming-Huwi Horng,Ren-Jean Liou.Multilevel minimum cross entropy thteshold selection based on the firefly algorithmJ.Expert Ststems with Appplications,2011,38:14805-14811.12 Ming-Huwi Horng.Vector quantization using the firefly algorithm fir image compressionJ.Expert Systems with Applications,2012,1078-1091.13 B.Rampriya,K.Mathadevan,S.Kannan.Unit commitment in deregulated power system using Lagrangian firefly algorithmA.Proc.of IEEE Int.Conf.on Communication Control and Computing Technologies(ICCCCT),pp.389-393.14 Yang Xin-She. Firefly Algorithms for Multimodal OptimizationC.Proc of the 5th International Symposium on Stochastic Algorithms:Foundaations and Applications,2009.169-178.15 于飞. 基于惯性权重的萤火虫优化算法J/OL.(2010-6-7)2012-5-7.致谢本次毕业论文能顺利完成，需要感谢我的指导老师林晓宇老师、我实习单位的同事朋友们、学校的同学朋友们以及这四年来所有教导过我的老师们。是你们的帮助，你们的教导让我能够如此顺利地完成本此毕业论文，尤其是我的导师林晓宇讲师，您细心严谨、一丝不苟的工作态度一直是我学习的榜样，您循循善诱的指导方式、不拘一格的程序思想带给我无尽的启迪，让我在开发过程中少走了许多弯路。本篇毕业论文的完成离不开你们认真的指导与检阅。感谢我的父母，是您们的支持与教导让我完成了学士学业之路，我所取得的每一分成绩都离不开您们的关爱与奉献。最后，感谢所有细心阅读本篇设计说明书的评委。