萤火虫算法及其应用研究

兰州交通大学毕业设计(论文)I摘 要萤火虫算法(Firefly Algorithm,FA)是受自然界中的萤火虫通过荧光进行信息交流这种群体行为的启发演变而来。它是由剑桥大学的 Xin-She Yang 教授在 2009 年提出的，它作为一种新颖的仿生群智能优化算法，有较大的研究空间。近几十年来随着越来越多的仿生群智能算法的提出，人们对于这些算法的认识和研究也逐步加深。本文先介绍群智能优化算法的理论概念，然后着重通过对萤火虫算法仿生原理的了解，从数学的角度对萤火虫算法进行合理的描述和过程的定义，最后编写该算法的matlab 代码实现对 3 个峰值函数进行仿真测试，得出其测试结果。同时用遗传算法对同样的测试函数也进行仿真测试，得出其测试结果。最后通过测试结果比较萤火虫算法和遗传算法分别在对峰值函数寻优结果的精确度。在比较过程中，可以根据测试结果发现，萤火虫算法在对峰值函数的寻优结果的精确度优于遗传算法。这表明了萤火虫算法在连续空间优化的可行性和有效性，同时也表明了萤火虫算法具有良好的应用前景。关键词： 萤火虫算法，仿生群智能优化算法，优化分析，遗传算法兰州交通大学毕业设计(论文)IIABSTRACTThe Firefly Algorithm (FA) is affected by the nature of the Firefly exchange of information through a fluorescence inspired this kind of crowd behavior has evolved. It is made by Xin - She Yang professor at the university of Cambridge in 2009, as a novel bionic swarm intelligent optimization algorithm, has a large research space. In recent decades as more bionic swarm intelligent algorithm is put forward, people also gradually deepen to the understanding and research of those algorithms. First，it is introduced in this paper theoretical concepts of swarm intelligence optimization algorithm, and then emphatically through the understanding of firefly algorithm bionic principle, from the perspective of mathematical descriptions of firefly algorithm is reasonable and the definition of the process, finally ,writes matlab code of the algorithm to realize the three peak function simulation test, to test results. At the same time with the genetic algorithm on the same test function, simulation test, to test results. Finally by comparing test results of firefly algorithm and genetic algorithm in the accuracy of the optimization results of peak function respectively. In the process of comparison, according to the result of test, it can shows that the firefly algorithm on the accuracy of the optimization results of peak function is superior to genetic algorithm. It shows that the feasibility and effectiveness of firefly algorithm in the continuous space optimization, but also shows that the firefly algorithm has a good application prospect. Keywords: firefly algorithm, The bionic swarm intelligent optimization algorithm, Optimization analysis, genetic algorithm兰州交通大学毕业设计(论文)III目 录摘 要 .IABSTRACT.II目 录 .III第一章 绪论 .1一、 研究的背景及意义 .1二、 群智能优化算法的研究现状 .1三、 本论文的内容和结构 .2第二章 群智能优化理论 .4一、 群智能优化算法的概述 .4二、 模拟退火算法 .4三、 遗传算法 .5四、 蚁群算法 .7五、 粒子群优化算法 .8六、 人工萤火虫群优化算法 .9七、 人工鱼群算法 .11第三章 萤火虫算法 .13一、 萤火虫算法的概念 .13二、 萤火虫算法的国内外研究现状 .13三、 萤火虫算法的仿生原理 .14四、 萤火虫算法的数学描述与分析 .15五、 萤火虫算法的流程 .16六、 实现萤火虫算法的 matlab 代码 .16第四章 仿真实验与分析 .22一、 三个测试函数的介绍 .22二、 FA 和 GA 对 F1(x)的仿真测试 .22三、 FA 和 GA 对 F2(x)的仿真测试 .25四、 FA 和 GA 对 F3(x)的仿真测试 .27五、 测试结果分析 .30兰州交通大学毕业设计(论文)IV结论 .31致谢 .32参考文献 .33兰州交通大学毕业设计(论文)1第一章 绪论一、 研究的背景及意义在现实生活中，许多优化问题要求人们不仅要计算出其极值，还要得出其最优值。这类问题对传统的算法造成的严峻的挑战。在这种情况下，越来越多的群智能算法相继的提出，其中萤火虫算法就是近几年来提出的一种新颖的仿生群智能优化算法。萤火虫算法是模拟自然界中萤火虫成虫发光的生物学特发展而来，也是基于群体搜索的随机优化算法。关于萤火虫算法目前文献有两种版本。一种是印度学者 Krishnanand 等人提出，称为 GSO(glowworm swarm optimization)；另一种由剑桥学者 Xin-She Yang 提出，称为 FA(firefly algorithm)。两种算法的仿生原理相同，但在具体实现方面有一定差异。本文着重研究由剑桥学者 Yang 提出的萤火虫算法(firefly algorithm,FA)。萤火虫算法经过近几年的发展，在连续空间的寻优过程和一些生产调度方面具有良好的应用前景。二、 群智能优化算法的研究现状近几十年来，国内外学者通过研究或模仿群体生活的昆虫、动物的社会行为特征，提出了一系列模拟生物系统中群体生活习性的群智能优化算法。其中较具有代表性的群智能优化算法主要有遗传算法、蚁群算法、粒子群算法、蜂群算法、人工鱼群算法、萤火虫算法等。1975 年，美国的 J.Holland 教授借鉴生物界的进化规律提出的遗传算法 (Genetic Algorithm,GA)。遗传算法目前已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。1991 年，意大利学者 Dorigo M.等人通过模拟蚂蚁的群体行为提出了蚁群算法 (Ant Colony Algorithm, ACA)，并用于解决复杂的组合优化问题。1995 年，Kennedy 和 Eberhart 等人提出了粒子群优化算法(Particle Swarm Optimization,PSO)。粒子群算法可应用于非线性复杂约束规划、作业调度优化、经济分配和数据挖掘等。1995 年，Theraulaz 提出了蜜蜂通过与环境之间的信息交互实现安排工作的模型，即蜂群算法(Wasp Colony Algorithm,WCA)。该算法可用于解决作业车间调度问题等。兰州交通大学毕业设计(论文)22002 年，李晓磊等人通过观察鱼类在水中游弋觅食的行为特点提出人工鱼群算法(Artificial Fish-swarm Algorithm,AFSA)。人工鱼群算法目前已用于组合优化、参数估计、PID 控制器的参数整定、神经网络优化等。2005 年，印度学者 K.N. Krishnanand 和 D. Ghose 提出一种新的群智能优化算法，人工萤火虫群优化(Glowworm Swarm Optimization, GSO)算法。迄今为止，人工萤火虫群优化算法在多模态函数优化问题、多信号源追踪问题、多信号源定位问题、有害气体泄漏定位问题、组合优化等方面得到成功的应用，且表现出良好的性能。2009 年，剑桥学者 Xin-She Yang 根据自然界中萤火虫的发光行为提出萤火虫算法(Firefly algorithm,FA)。萤火虫算法在生产调度、路径规划等方面具有良好的应用前景。三、 本论文的内容和结构本论文的主要内容有以下几个方面：1、对群智能优化算法的基本介绍。2、研究萤火虫算法的基本原理。3、通过数学角度对萤火虫算法的描述和分析。4、用萤火虫算法编写 matlab 算法对 3 个经典函数进行测试，并与遗传算法进行比较。5、通过测试数据分析得出结论。本论文共五章，其内容编排结构如下：第一章 绪论本章主要是简单的介绍下本论文的研究背景及意义、群智能优化算法的研究现状，最后又介绍了本论文的内容和结构。第二章 群智能优化理论本章先是对群智能优化算法进行概述，然后对模拟退火算法、遗传算法、蚁群算法、粒子群算法、人工萤火虫群优化算法、人工鱼群算法进行原理的了解和阐述。第三章 萤火虫算法本章先是对萤火虫算法进行概念介绍，然后再对萤火虫算法的优化机理进行阐述，其中包括萤火虫算法国内外研究现状和萤火虫算法的仿生原理两个方面，然后用数学角度对萤火虫算法进行描述与分析，接着对萤火虫算法的流程进行优化，最后完成萤火虫算法 matlab 代码的实现。兰州交通大学毕业设计(论文)3第四章 仿真实验与分析本章先是对 3 个测试函数的介绍，然后分别用萤火虫算法和遗传算法编写 matlab代码对这 3 个测试函数进行测试，得出相应的结果，最后比较分析这两种算法的测试结果，得出结论。结论本章通过第四章测试结果分析，得出了萤火虫算法在连续空间优化的可行性和有效性的结论，这表明了萤火虫算法具有良好的应用前景。兰州交通大学毕业设计(论文)4第二章 群智能优化理论一、 群智能优化算法的概述群智能优化算法是近年来计算智能领域出现一种新型的优化技术，这种技术具有良好的优化效果和简洁的数学理论，越来越受到人们极大的关注。群智能优化作为优化算法的方向之一，其主要的思想是源自于模拟自然界各种社会性动物、植物等的群体行为，利用群体个体之间的共同协助和信息交换来实现最终寻优的目的。相对于传统的优化算法，群智能优化算法的特点是理论简单、易于实现、寻优效果更优等优点。虽然群智能优化算法在近些年的研究中有了很大发展，但总体来说，这种新型的优化算法仍然存在很多不足，还有很多问题有待于进一步研究解决，如数学理论支撑薄弱、如何使得算法的优化效果更好和寻优速度更快，以及怎么样能更广泛的应用到实际问题中去等等。以下对几种典型的群智能优化算法进行简要的概述。二、 模拟退火算法模拟退火算法 7(Simulated Annealing,SA)是 1983 年由 Kirkpatrick 首次提出的一种组合优化算法。该算法来源于固体退火原来，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温度上升变为无序状态，内能增大。而徐徐冷却时粒子渐趋有序，每个温度都达到平衡状态，最后在常温时达到基态，内能减为最小。模拟退火算法借鉴热力学中的能量方程，同时又引入了 Metropolis 准则，粒子在温度 T 时趋于平衡的概率为： ，其中 E 为温度 T 时的内能， 为其改变量，k 为ekTEBoltzmann 常数。算法的基本思想是从一个给定解开始，从领域中随机产生另一个解，接受准则允许目标函数在有限范围内变换，以一定概率接受较差的解。用固体退火模拟组合优化问题，将内能 E 模拟为目标函数值 f，温度 T 演化成控制参数 t，即得到解组合优化问题的模拟退火算法：由初始解 i 和控制参数初值 t 开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减 t 值，算法终止时的当前解即为所得近似最优解，模拟退火算法已经被证明是一种依赖于概率 1 收敛于全局最优解的优化方法。模拟退火算法的迭代搜索过程以 Boltzmann 分布概率接受函数目标的 “劣化解” ，兰州交通大学毕业设计(论文)5所以模拟退火算法具有脱离局部最优陷阱的能力，而且具有高效、鲁棒、通用、灵活的优点。但其参数难以控制，如初始温度 T 的设置太大，算法要花费大量的时间，设置太小，则全局搜索性能可能受到影响。还有退火速度问题，也要做合理的设置。模拟退火算法的应用很广泛，在求解最大截问题(Max Cut Problem)、0-1 背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等方面效率较高。三、 遗传算法遗传算法 8(Genetic Algorithm,GA)是群智能优化算法中思想起源较早的算法之一。它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。1975 年，美国Michigam 大学的 J.Holland 教授参照“适者生存” 的生物进化法则和种群的思想提出一些解决复杂优化问题的理论和方法。遗传算法模拟生物进化的基本过程，用数码串来类比生物中的染色个体，通过选择、交叉、变异等遗传算子来仿真生物的基本进化过程，利用适应度函数来表示染色体所蕴涵问题解的质量的优劣，通过种群的不断“更新换代” ，从而提高每代种群的平均适应度，通过适应度函数引导种群的进化方向，并在此基础上，使得最优个体所代表的问题解逼近问题的全局最优解。遗传算法求解问题的基本思想是维持由一群个体组成的种群 p(t) (t 代表遗传代数)，每一个体均代表问题的一个潜在解，每一个体都被评论优劣并得到其适应值。个体通过遗传算子产生新的个体，新产生的个体继续被评论优劣，从父代种群和子代种群中选择比较优秀的个体形成新的种群。在若干代以后，算法收敛到一个最优个体，该个体很可能代表着问题的最优解或次优解。在遗传算法中，每个问题的可行解对应于一个染色体。通常可以用特定编码方式（如二进制编码）生成的编码串来表示染色体，而其中每一个编码单元则成为基因。采用遗传算法求解问题时，首先需要将问题的解用染色体来表示。完成编码表示之后，在染色体的表示空间中随机产生一个初始种群，然后通过迭代的选择操作、基因重组操作和变异操作对染色体集合进行进化。在达到终止条件后对最优的染色体进行编码，便可以得到待求解问题的最优解或者相似最优解。遗传算法的流程包括下列六个步骤。第一步：初始化过程。该步骤首先初始化算法的参数，包括搜索空间的范围、种群的大小，以及交叉率和变异率等。然后在搜索空间中随机生成一个初始种群。第二步：适应度评估。这一步对初始种群进行适应度评估。个体的适应度体现了兰州交通大学毕业设计(论文)6该个体的优劣程度，是执行后续选择操作的依据。适应度函数通常由问题的优化目标确定。例如在求函数最大值时，可以直接将目标函数值作为适应度函数。这样，函数值越大，相应的适应度也越大。不过在实际的应用中，为了提高算法的搜索效率，通常需要对目标函数进行相应的处理，如执行缩放变换和平移变换等。对于没有显示数学表达公式的问题（TSP 问题等组合问题） ，可以通过对解建模，从而求得一个函数值作为适应度（如计算解路径的长度等） 。第三步：选择操作。选择是优胜劣汰的过程。在计算出每个个体的适应度后，较优的个体将以较大的概率生存下来，而较差的个体将很可能被