下载

0下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 萤火虫算法及其应用研究

萤火虫算法及其应用研究.doc

萤火虫算法及其应用研究

蓝白色回忆00
2017-12-11 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《萤火虫算法及其应用研究doc》,可适用于综合领域

萤火虫算法及其应用研究摘要萤火虫算法(FireflyAlgorithm,FA)是受自然界中的萤火虫通过荧光进行信息交流这剑桥大学的XinSheYang教授在年提出的种群体行为的启发演变而来。它是由它作为一种新颖的仿生群智能优化算法有较大的研究空间。近几十年来随着越来越多的仿生群智能算法的提出人们对于这些算法的认识和研究也逐步加深。本文先介绍群智能优化算法的理论概念然后着重通过对萤火虫算法仿生原理的了解从数学的角度对萤火虫算法进行合理的描述和过程的定义最后编写该算法的matlab代码实现对个峰值函数进行仿真测试得出其测试结果。同时用遗传算法对同样的测试函数也进行仿真测试得出其测试结果。最后通过测试结果比较萤火虫算法和遗传算法分别在对峰值函数寻优结果的精确度。在比较过程中可以根据测试结果发现萤火虫算法在对峰值函数的寻优结果的精确度优于遗传算法。这表明了萤火虫算法在连续空间优化的可行性和有效性同时也表明了萤火虫算法具有良好的应用前景。关键词:萤火虫算法仿生群智能优化算法优化分析遗传算法ABSTRACTTheFireflyAlgorithm(FA)isaffectedbythenatureoftheFireflyexchangeofinformationthroughafluorescenceinspiredthiskindofcrowdbehaviorhasevolvedItismadebyXinSheYangprofessorattheuniversityofCambridgein,asanovelbionicswarmintelligentoptimizationalgorithm,hasalargeresearchspaceInrecentdecadesasmorebionicswarmintelligentalgorithmisputforward,peoplealsograduallydeepentotheunderstandingandresearchofthosealgorithmsFirstitisintroducedinthispapertheoreticalconceptsofswarmintelligenceoptimizationalgorithm,andthenemphaticallythroughtheunderstandingoffiref、FA和GA对F(x)的仿真测试三、FA和GA对F(x)的仿真测试四、FA和GA对F(x)的仿真测试五、测试结果分析结论致谢参考文献第一章绪论一、研究的背景及意义在现实生活中许多优化问题要求人们不仅要计算出其极值还要得出其最优值。这类问题对传统的算法造成的严峻的挑战。在这种情况下越来越多的群智能算法相继的提出其中萤火虫算法就是近几年来提出的一种新颖的仿生群智能优化算法。萤火虫算法是模拟自然界中萤火虫成虫发光的生物学特发展而来也是基于群体搜索的随机优化算法。关于萤火虫算法目前文献有两种版本。一种是印度学者Krishnanand等人提出称为GSO(glowwormswarmoptimization)另一种由剑桥学者XinSheYang提出称为FA(fireflyalgorithm)。两种算法的仿生原理相同但在具体实现方面有一定差异。本文着重研究由剑桥学者Yang提出的萤火虫算法(fireflyalgorithm,FA)。萤火虫算法经过近几年的发展在连续空间的寻优过程和一些生产调度方面具有良好的应用前景。二、群智能优化算法的研究现状近几十年来国内外学者通过研究或模仿群体生活的昆虫、动物的社会行为特征提出了一系列模拟生物系统中群体生活习性的群智能优化算法。其中较具有代表性的群智能优化算法主要有遗传算法、蚁群算法、粒子群算法、蜂群算法、人工鱼群算法、萤火虫算法等。年美国的JHolland教授借鉴生物界的进化规律提出的遗传算法(GeneticAlgorithm,GA)。遗传算法目前已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。年意大利学者DorigoM等人通过模拟蚂蚁的群体行为提出了蚁群算法(AntColonyAlgorithm,ACA)并用于解决复杂的组合优化问题。年Kennedy和Eberhart等人提出了粒子群优化算法(ParticleSwarmOptimization,PSO)。粒子群算法可应用于非线性复杂约束规划、作业调度优化、经济分配和数据挖掘等。年Theraulaz提出了蜜蜂通过与环境之间的信息交互实现安排工作的模型即蜂群算法(WaspColonyAlgorithm,WCA)。该算法可用于解决作业车间调度问题等。年李晓磊等人通过观察鱼类在水中游弋觅食的行为特点提出人工鱼群算法(ArtificialFishswarmAlgorithm,AFSA)。人工鱼群算法目前已用于组合优化、参数估计、PID控制器的参数整定、神经网络优化等。年印度学者KNKrishnanand和DGhose提出一种新的群智能优化算法人工萤火虫群优化(GlowwormSwarmOptimization,GSO)算法。迄今为止人工萤火虫群优化算法在多模态函数优化问题、多信号源追踪问题、多信号源定位问题、有害气体泄漏定位问题、组合优化等方面得到成功的应用且表现出良好的性能。年剑桥学者XinSheYang根据自然界中萤火虫的发光行为提出萤火虫算法(Fireflyalgorithm,FA)。萤火虫算法在生产调度、路径规划等方面具有良好的应用前景。三、本论文的内容和结构本论文的主要内容有以下几个方面:、对群智能优化算法的基本介绍。、研究萤火虫算法的基本原理。、通过数学角度对萤火虫算法的描述和分析。、用萤火虫算法编写matlab算法对个经典函数进行测试并与遗传算法进行比较。、通过测试数据分析得出结论。本论文共五章其内容编排结构如下:第一章绪论本章主要是简单的介绍下本论文的研究背景及意义、群智能优化算法的研究现状最后又介绍了本论文的内容和结构。第二章群智能优化理论本章先是对群智能优化算法进行概述然后对模拟退火算法、遗传算法、蚁群算法、粒子群算法、人工萤火虫群优化算法、人工鱼群算法进行原理的了解和阐述。第三章萤火虫算法本章先是对萤火虫算法进行概念介绍然后再对萤火虫算法的优化机理进行阐述其中包括萤火虫算法国内外研究现状和萤火虫算法的仿生原理两个方面然后用数学角度对萤火虫算法进行描述与分析接着对萤火虫算法的流程进行优化最后完成萤火虫算法matlab代码的实现。第四章仿真实验与分析本章先是对个测试函数的介绍然后分别用萤火虫算法和遗传算法编写matlab代码对这个测试函数进行测试得出相应的结果最后比较分析这两种算法的测试结果得出结论。结论本章通过第四章测试结果分析得出了萤火虫算法在连续空间优化的可行性和有效性的结论这表明了萤火虫算法具有良好的应用前景。第二章群智能优化理论一、群智能优化算法的概述群智能优化算法是近年来计算智能领域出现一种新型的优化技术这种技术具有良好的优化效果和简洁的数学理论越来越受到人们极大的关注。群智能优化作为优化算法的方向之一其主要的思想是源自于模拟自然界各种社会性动物、植物等的群体行为利用群体个体之间的共同协助和信息交换来实现最终寻优的目的。相对于传统的优化算法群智能优化算法的特点是理论简单、易于实现、寻优效果更优等优点。虽然群智能优化算法在近些年的研究中有了很大发展但总体来说这种新型的优化算法仍然存在很多不足还有很多问题有待于进一步研究解决如数学理论支撑薄弱、如何使得算法的优化效果更好和寻优速度更快以及怎么样能更广泛的应用到实际问题中去等等。以下对几种典型的群智能优化算法进行简要的概述。二、模拟退火算法模拟退火算法(SimulatedAnnealing,SA)是年由Kirkpatrick首次提出的一种组合优化算法。该算法来源于固体退火原来将固体加温至充分高再让其徐徐冷却加温时固体内部粒子随温度上升变为无序状态内能增大。而徐徐冷却时粒子渐趋有序每个温度都达到平衡状态最后在常温时达到基态内能减为最小。模拟退火算法借鉴热力学中的能量方程同时又引入了Metropolis准则粒子在温度T时趋于平衡的概率,E为:其中E为温度T时的内能为其改变量k为Boltzmann常数。eEkT,,算法的基本思想是从一个给定解开始从领域中随机产生另一个解接受准则允许目标函数在有限范围内变换以一定概率接受较差的解。用固体退火模拟组合优化问题将内能E模拟为目标函数值f温度T演化成控制参数t即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代并逐步衰减t值算法终止时的当前解即为所得近似最优解模拟退火算法已经被证明是一种依赖于概率收敛于全局最优解的优化方法。模拟退火算法的迭代搜索过程以Boltzmann分布概率接受函数目标的“劣化解”所以模拟退火算法具有脱离局部最优陷阱的能力而且具有高效、鲁棒、通用、灵活的优点。但其参数难以控制如初始温度T的设置太大算法要花费大量的时间设置太小则全局搜索性能可能受到影响。还有退火速度问题也要做合理的设置。模拟退火算法的应用很广泛在求解最大截问题(MaxCutProblem)、背包问题(ZeroOneKnapsackProblem)、图着色问题(GraphColouringProblem)、调度问题(SchedulingProblem)等方面效率较高。三、遗传算法遗传算法(GeneticAlgorithm,GA)是群智能优化算法中思想起源较早的算法之一。它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。年美国Michigam大学的JHolland教授参照“适者生存”的生物进化法则和种群的思想提出一些解决复杂优化问题的理论和方法。遗传算法模拟生物进化的基本过程用数码串来类比生物中的染色个体通过选择、交叉、变异等遗传算子来仿真生物的基本进化过程利用适应度函数来表示染色体所蕴涵问题解的质量的优劣通过种群的不断“更新换代”从而提高每代种群的平均适应度通过适应度函数引导种群的进化方向并在此基础上使得最优个体所代表的问题解逼近问题的全局最优解。遗传算法求解问题的基本思想是维持由一群个体组成的种群p(t)(t代表遗传代数)每一个体均代表问题的一个潜在解每一个体都被评论优劣并得到其适应值。个体通过遗传算子产生新的个体新产生的个体继续被评论优劣从父代种群和子代种群中选择比较优秀的个体形成新的种群。在若干代以后算法收敛到一个最优个体该个体很可能代表着问题的最优解或次优解。在遗传算法中每个问题的可行解对应于一个染色体。通常可以用特定编码方式(如二进制编码)生成的编码串来表示染色体而其中每一个编码单元则成为基因。采用遗传算法求解问题时首先需要将问题的解用染色体来表示。完成编码表示之后在染色体的表示空间中随机产生一个初始种群然后通过迭代的选择操作、基因重组操作和变异操作对染色体集合进行进化。在达到终止条件后对最优的染色体进行编码便可以得到待求解问题的最优解或者相似最优解。遗传算法的流程包括下列六个步骤。第一步:初始化过程。该步骤首先初始化算法的参数包括搜索空间的范围、种群的大小以及交叉率和变异率等。然后在搜索空间中随机生成一个初始种群。第二步:适应度评估。这一步对初始种群进行适应度评估。个体的适应度体现了该个体的优劣程度是执行后续选择操作的依据。适应度函数通常由问题的优化目标确定。例如在求函数最大值时可以直接将目标函数值作为适应度函数。这样函数值越大相应的适应度也越大。不过在实际的应用中为了提高算法的搜索效率通常需要对目标函数进行相应的处理如执行缩放变换和平移变换等。对于没有显示数学表达公式的问题(TSP问题等组合问题)可以通过对解建模从而求得一个函数值作为适应度(如计算解路径的长度等)。第三步:选择操作。选择是优胜劣汰的过程。在计算出每个个体的适应度后较优的个体将以较大的概率生存下来而较差的个体将很可能被淘汰掉。为了实现这个目标通常有轮盘赌选择法和锦标赛选择法这两种经典选择策略。第四步:交叉操作。交叉操作是父代基因重新组合的过程。基因重组的方式有单点交叉、多点交叉和均匀交叉等多种方式。第五步:变异操作。个体的基因在进化过程中会以很小的概率发生变异。变异操作给染色体种群带来了新的基因是保证算法找到最优解以及使得算法以渐进的形式逼近最优解的重要操作。第六步:评估新种群的适应度。这一步骤对新生成的种群重新进行适应度评估。此时若达到算法的终止条件则停止算法否则返回第三步继续操作。遗传算法是具有“生成检测”(generateandtest)的迭代过程的搜索算法遗传操作算子使遗传算法具有了与传统的其他搜索算法如爬山法、分支界定法、禁忌搜索算法等不同的工作机理当遇到较大规模的问题时遗传算法有着不可替代的优异性:如遗传算法并不是对问题的待优化参数本身进行操作而是通过由这些参数所编码形成的染色体进行交叉、变异和选择等操作。遗传算法操作的对象不限于一个而是对由大量对象形成的种群进行操作这种做法使得参与操作的信息量大速度快效果好使得整个优化过程容易跳出局部最优。遗传算法不依赖于问题领域的信息来指导搜索其实现简单效果良好通用性好鲁棒性强等。虽然遗传算法具有上述优点但由于遗传算法本质上是一种基于概率的启发式随机搜索方法遗传算法也有自身的缺陷:如遗传算法是对种群进行概率性操作所以在全局寻优上效果良好而在局部寻优上存在不足在算法进行的前期搜索效果良好而在算法进行的后期搜索速度缓慢遗传算法虽然实现简单但实现的效果很大程度上取决于问题的多种参数如果这些参数设置不好此时的遗传算法类似随机搜索算法甚至会出现“早熟收敛”现象。与传统方法相比遗传算法具有隐式并行性和全局搜索性两大主要特点作为强有力且应用广泛的随机搜索和优化方法遗传算法可能是当今影响最广泛的进化计算方法之一。近几十年来遗传算法主要在复杂优化问题求解和工业工程领域应用方面取得了一些令人信服的结果遗传算法成功的应用包括:函数优化、机器学习、组合优化、人工神经元网络训练、自动程序设计、专家系统、作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配等等。四、蚁群算法人工蚁群算法是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于蚁群的模拟进化算法属于随机搜索算法由意大利学者MDorigo等人于年首先提出。仿生学家经过大量细致观察研究发现蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递从而能互相协作完成复杂的任务。蚁群之所以表现出复杂有序的行为个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中能够在它所经过的路径上留下该种物质而且蚂蚁在运动过程中能够感知这种物质的存在及其强度并以此指导自己的运动方向蚂蚁倾向于朝着该物质强度高的方向移动。因此由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法正是模拟了这样的优化机制即通过个体之间的信息交流与相互协作最终找到最优解。以TSP问题为例设有n个城市m只蚂蚁d(i,j=,,…,n)表示城市i和j间的距ij离,()t表示在t时刻城市i和j之间的信息量则在t时刻蚂蚁k在i节点选择j节点ij的转移概率为:,,,,,()()ttijij,jallowed,,k,,pt(),sallowedtt,()(),,,,,ijisis,,otherwise,其中allowedk={,,…,n}tabuk表示蚂蚁k下一步允许选择的城市tabuk(k=,,…,m)用以记录蚂蚁k以前所走过的城市集合tabuk随着进化过程作动态调整。经过n个时刻蚂蚁完成一次循环每只蚂蚁所走过的路径就是一个解。此时要根据下面公式对各路径上的信息量做更新:,,,,,()()(,)tnt,,,ijijij由上述可知蚁群算法优化过程的本质在于:、选择机制。信息量越大的路径被选择的概率越大。、更新机制。路径上面的信息量会随蚂蚁的经过而增长同时也随着时间的推移逐渐减小。、协调机制。蚂蚁之间实际上是通过信息量来互相通信、协同工作的这样的机制使得蚁群算法具有很强的发现较好解的能力。但是蚁群算法也有一些缺陷。例如由于蚁群中多个个体的运动是随机的当群体规模较大时要找出一条较好的路径需要较长的搜索时间等。意大利学者MDorigo等人充分利用蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性解决了TSP问题取得了很好的结果。随后蚁群算法被用来求解分配问题、网络路由问题、指派问题、车间作业调度问题、电力系统故障诊断等NP完全问题显示出蚁群算法在求解复杂优化问题方面的优越性。五、粒子群优化算法动物世界的群体行为神秘而有趣。无论是天空的飞鸟还是湖泊中的鱼群它们在迁徙、觅食等过程中所表现出来的高度组织性和规律性一直吸引着各领域的学者对它们展开研究。粒子群优化算法(ParticleSwarmOptimization,PSO)正是在这种研究气氛中诞生的一种新型启发式进化算法。粒子群优化算法最早是由Kenney与Eberhart于年提出的。它是模拟鸟群的捕食行为让一群鸟在空间里自由飞翔觅食每个鸟都能记住它曾经飞过最高的位置然后就随机的靠近那个位置不同的鸟之间可以互相交流它们都尽量靠近整个鸟群中曾经飞过的最高点这样经过一段时间就可以找到近似的最高点。粒子群优化算法后俩经过多次的改进去除了原来算法中一些无关的或冗余的变量又加入了一些随机变化的量使得鸟群的运动更像空间微粒的运动所以称之为粒子群算法。粒子群优化算法求解问题的基本思想是随机产生一粒子群作为初始解用粒子的位置表示待优化问题的解每个粒子性能的优劣程度取决于待优化问题目标函数确定的适应值微粒尽量靠近最优点并且有随机的变化发生使得微粒不会停留在最优点不动而是尽量靠近同时保持创新性。每个微粒记录它自己的最优位置(pbest)还要记录所有微粒的最优位置(gbest)然后通过比较当前位置和两个最优位置的差别来调整速度以确定下一步的位置。每个粒子由一个速度矢量决定其飞行方向和速率大小通过改变速度的大小和方向使随机的初始解“飞向”最优解。粒子群优化算法流程如下:第一步:随机产生N个粒子初始化每个的速度和位置并评估所有初始化粒子的适应度。将当前个体设为历史最优pBest,而全局最优个体设为gBest。第二步:更新每个粒子的速度和位置。假设当前粒子的位置信息和速度信息分别为xxx,,,和vvv,,,其中D为问题的维数。则更新后的粒子的位置和速度分,,,,DD别为:vvcrandpBestxcrandgBestx,,,,(,)()(,)()iiiiiixxv,iii第三步:评估所有粒子的适应度。第四步:更新所有粒子的历史最优信息pBest。如果粒子当前的适应度比其pBest的适应度要好则用当前粒子替换掉pBest。第五步:更新全局最优信息gBest。如果粒子当前的适应度比其gBest的适应度要好则要当前粒子替换掉gBest。第六步:若达到结束条件则结束否则返回第二步继续执行。粒子群优化算法与遗传算法都属于进化算法但粒子群优化算法避免了二进制编码的麻烦而且操作更加直观粒子群优化算法流程简单易实现算法参数简洁无需复杂的调整。粒子群优化算法的缺点是:初始化过程是随机的这虽然可保证初始解群分布均匀但个体的质量不能保证。其次粒子利用自身、个体及全局信息来更新自己的速度和位置这是一个正反馈过程当自身信息及个体信息占优势时算法易陷入局部最优。目前许多学者针对基本粒子群优化算法提出了很多种改进算法这些改进的粒子群优化算法已广泛应用于函数优化、系统识别、神经网络训练、信号处理和机器人等实际应用领域取得了丰富的成果。六、人工萤火虫群优化算法人工萤火虫群优化算法(GlowwormSwarmOptimization,GSO)是源于模拟自然界萤火虫在晚上的群聚活动的自然现象而提出的在萤火虫的群聚活动中每只萤火虫通过散发荧光素与同伴进行寻觅食物以及求偶等信息交流。一般来说荧光素越亮的萤火虫其号召力也就越强最终会出现很多萤火虫聚集在一些荧光素较亮的萤火虫周围。人工萤火虫算法就是根据这种现象而提出的一种新型的仿生群智能优化算法。在人工萤火虫群优化算法中每只萤火虫被视为解空间的一个解萤火虫种群作为初始解随机的分布在搜索空间中然后根据自然界萤火虫的移动方式进行解空间中每只萤火虫的移动。通过每一代的移动最终使的萤火虫聚集到较好的萤火虫周围也即是找到多个极值点从而达到种群寻优的目的。在基本GSO中把n个萤火虫个体随机分布在一个D维目标搜索空间中每个萤火虫都携带了萤光素li。萤火虫个体都发出一定量的萤光相互影响周围的萤火虫个体ii并且拥有各自的决策域。萤火虫个体的萤光素大小与自己所在位置的目标rrr(),,dds函数有关荧光素越大越亮的萤火虫表示它所在的位置越好即有较好的目标值反之则目标值较差。决策域半径的大小会受到邻域内个体的数量的影响邻域内萤火虫密度越小萤火虫的决策域半径会加大以便找到更多的邻居反之则萤火虫的决策域半径会缩小。最后大部分萤火虫会聚集在多个位置上。初始萤火虫时每个萤火虫个体都携带了相同的萤光素浓度和感知半径。rl定义荧光素更新式()ltltJxt()()()(()),,,,,iii其中为每只萤火虫i在t迭代的位置对应的目标函数值代表当Jxt(())lt()xt()iii前萤火虫的荧光素值为荧光素更新率。,定义概率选择选择移向领域集内个体j的概率:pt()Nt()ijiltlt()(),jipt(),式()ij(()())ltlt,,ki,()kNtiiiNtjdtrtltlt():()()()(),,,其中领域集,为萤火虫个体的感(),,rtrr,,iijdijsds知半径。定义位置更新xx,ji()()()式()xtxts,iixx,ji其中s为移动步长。定义动态决策域半径更新ii式()rtrrtnNt()min,max,()(()),,,,,,,dsdii算法流程描述如下::初始化各个参数。步骤步骤:随机初始化第i(i=,,…,n)个萤火虫在目标函数搜索范围内的位置。步骤:使用公式()把萤火虫i在第t次迭代的位置对应的目标函数值Jxt(())xt()ii转化为荧光素值。lt()i步骤:每只萤火虫在其动态决策域半径rdt()内选择荧光素值比自己高的个体组ii成其邻域集其中(),,rtr。为萤火虫个体的感知半径。rNt()isdspt()步骤:利用公式()计算萤火虫i移向邻域集内个体j的概率。ij步骤:利用轮盘赌的方法选择个体j然后移动根据公式()更新位置。步骤:根据公式()更新动态决策域半径的值。步骤:是否到达指定的代数如果达到则转向步骤,否则转向步骤。步骤:输出结果程序结束。七、人工鱼群算法人工鱼群算法(ArtificialFishSwarmAlgorithm,AFSA)是李晓磊等人于年在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法该算法根据“水域中鱼生存数目最多的地方一般就是本水域中富含营养物质最多的地方”这一特点来模仿鱼群的觅食行为而实现寻优。人工鱼群算法主要利用鱼的三大基本行为:觅食、聚群和追尾行为采用自上而下的寻优模式从构造个体的底层行为开始通过鱼群中各个体的局部寻优达到全局最优值在群体中突现出来的目的。人工鱼群算法就是一种基于动物行为的自治体寻优模式它是基于鱼类的活动特点构建起来的新型智能仿生算法。通常人们可以观察到如下的鱼类行为:、觅食行为:这是鱼趋向食物的一种活动一般认为它是通过视觉或味觉来感知水中的食物量或食物浓度来选择行动方向的。、聚群行为:大量或少量的鱼聚集成群进行集体觅食和躲避敌害这是它们在进化过程中形成的一种生存方式。、追尾行为:当某一条鱼或者几条鱼发现食物时它们附近的鱼会尾随而来导致更远处的鱼也尾随过来。、随机行为:鱼在水中随机的自由游动目的是为了更大范围的寻觅食物或者同伴。觅食行为主要认为就是循着食物多的方向游动的一种行为在寻优中则是向较优方向进行的迭代方式。聚群行为能够很好地跳出局部极值并尽可能搜索到其他的极值最终搜索到全局极值。追尾行为有助于快速的向某个极值方向前进加快寻优的速度并防止人工鱼在局部振荡而停滞不前。鱼群算法在对以上行为进行评价后自动选择合适的行为从而形成一种高效快速的寻优策略。人工鱼群算法的行为描述:X、觅食行为:设人工鱼当前状态为在其感知范围内随机选择一个状态如Xji果则向方向前进一步反之再重新随机选择状态判断是否满足前进YY,XXijjj的条件反复几次后如果仍不满足前进条件则随机移动一步。、聚群行为:人工鱼当前状态为探索当前领域内(即)的伙伴数目dVisual,nXij,fi及中心位置如果且表明伙伴中心有较多的食物并且不太拥挤YnY,,YY,Ycficic则朝伙伴中心位置方向前进一步否则执行觅食行为。如果=也执行觅食行为。nf、追尾行为:人工鱼当前状态为探索当前领域内(即)的伙伴中适dVisual,Xij,i应度值最大的伙伴且表明伙伴的状态具有较高的食物浓度XYnY,,YY,Xjjfiijj并且周围不太拥挤朝伙伴的方向前进一步否则执行觅食行为。如果=也执Xnjf行觅食行为。、随机行为:随机行为的实现比较简单就是在视野中随机选择一个状态然后向该方向移动其实它是觅食行为的一个缺省行为。基于以上描述的人工鱼行为每条人工鱼根据自身当前的目标函数变化情况和它的伙伴目标函数的变化情况依照行为选择机制选择一种较优行为移动最终多数人工鱼会集结在几个局部极值的周围。一般情况下在讨论求极小问题时拥有较小适应度函数值的人工鱼一般处于值较小的极值区域周围这有助于判断并获取全局极值。人工鱼群算法是模仿鱼类行为方式提出的一种基于动物自治体的优化方法是仿生智能思想的一个具体应用从总体的设计理念到具体的实施算法都不同于传统的设计和解决方法同时它又具有与传统方法相融合的基础。该算法已在组合优化、参数估计、电力系统无功优化、边坡稳定、前向神经网络优化、输电网规划、非线性方程求解等方面得到了很好的应用并且都取得了很好的效果。第三章萤火虫算法一、萤火虫算法的概念萤火虫算法(FirelyAlgorithm,FA)是一种启发式算法这种算法启发于晚上萤火虫发光的行为。萤火虫的闪光其主要目的是作为一个信号系统以吸引其他的萤火虫。剑桥大学的XinSheYang教授在年提出了萤火虫算法其假设为:、萤火虫不分性别它将会被吸引到所有其他比它更亮的萤火虫那去、萤火虫的吸引力和亮度成正比对于任何两只萤火虫其中一只会向着比它更亮的另一只移动然而亮度是随着距离的增加而减少的、如果没有找到一个比给定的萤火虫更亮它会随机移动。二、萤火虫算法的国内外研究现状萤火虫算法是剑桥大学的XinSheYang教授于年提出的一种新型的群智能优化算法。目前国外关于萤火虫算法的研究工作主要有:、在年剑桥大学的XinSheYang教授根据自然界中萤火虫的行为首次提出一种新型的群智能优化算法萤火虫算法。、在年月XinSheYang发表对于萤火虫算法的随机优化的研究报告。、在年月XinSheYang发表研究了萤火虫算法的多模优化问题。、在年月TheofanisApostolopoulos和AristidisVlachos发表研究了应用萤火虫算法解决经济排放负荷调度问题。、在年月MohammadAsifZaman和MdAbdulMatin发表研究了基于萤火虫算法的非均匀间隔的线性阵列天线设计。、在年月SurafelLulesegedTilahun和HongChoonOng提出萤火虫算法的优化问题。国内关于萤火虫算法的研究工作主要有:、在年月王迎菊和周永权提出了一种基于荧光素扩散的人工萤火虫算法。、在年月刘长平和叶春明发表介绍了萤火虫算法。、在年月彭伟和汪镭提出了基于萤火虫算法的神经网络CPI预测模型。、在年月刘长平和叶春明发表了置换流水车间调度问题的萤火虫算法求解。、在年月周季华和叶春明发表了应用萤火虫算法求解PFSP问题。、在年月袁际军发表基于多目标萤火虫算法的可调节产品族优化设计。、在年月杨娇和叶春明发表了应用新型萤火虫算法求解Jobshop调度问题。、在年月周季华和叶春明提出了应用萤火虫算法求解置换流水线问题。、在年月曾冰、李明富、张翼等人发表了基于萤火虫算法的装配序列规划研究。、在年月李铁、姚晔等人发表了基于改进型人工萤火虫算法的云计算资源研究。从萤火虫算法的国内外研究现状来看萤火虫算法不断进行优化改进并已经逐步应用于各种领域。但毕竟萤火虫算法是近几年刚刚提出的在许多方面也有待于改进完善。三、萤火虫算法的仿生原理自然界中约有种萤火虫多数种类的萤火虫会发出短促、有节奏的荧光不同种类的萤火虫发光目的不同其真实原因仍在探讨当中。一般认为萤火虫成虫发光的生物学意义是利用物种特有的闪光信号来定位并吸引异性借此完成求偶交配及繁殖的使命少数萤火虫利用闪光信号进行捕食还有一种作用是作为警戒信号即当萤火虫受到刺激时会发出亮光。萤火虫优化算法就是模拟自然界中萤火虫的发光行为构造出的随机优化算法但在算法中舍弃了萤火虫发光的一些生物学意义只利用其发光特性来根据其搜索区域寻找伙伴并向邻域结构内位置较优的萤火虫移动从而实现位置进化。在该算法中萤火虫彼此吸引的原因取决于两个要素即自身亮度和吸引度。其中萤火虫发出荧光的亮度取决于自身所在位置的目标值亮度越高表示所处的位置越好即目标值越佳。吸引度与亮度相关越亮的萤火虫拥有越高的吸引力可以吸引视线范围内亮度比其弱的萤火虫往这个方向移动。如果发光亮度相同则萤火虫各自随机移动。亮度和吸引度与萤火虫之间的距离成反比都随着距离的增加而减小这相当于模拟了荧光在空间传播时被传播媒介吸收而逐渐衰减的特性。萤火虫算法是通过模拟萤火虫的群体行为构造出的一类随机优化算法。其仿生原理是:用搜索空间中的点模拟自然界中的萤火虫个体将搜索和优化过程模拟成萤火虫个体的吸引和移动过程将求解问题的目标函数度量成个体所处位置的优劣将个体的优胜劣汰过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。四、萤火虫算法的数学描述与分析如上所述萤火虫算法包含两个要素即亮度和吸引度。亮度体现了萤火虫所处位置的优劣并决定其移动方向吸引度决定了萤火虫移动的距离通过亮度和吸引度的不断更新从而实现目标优化。从数学角度对萤火虫算法的优化机理进行如下描述:定义萤火虫的相对荧光亮度为,,rij式()IIe,其中:为萤火虫的最大萤光亮度即自身(r=处)荧光亮度与目标函数值相关目I,标函数值越优自身亮度越高为光强吸收系数因为荧光会随着距离的增加和传播媒介的吸收逐渐减弱所以设置光强吸收系数以体现此特性可设为常数为萤火虫irij与j之间的空间距离。定义萤火虫的吸引度为,,rij,,,e式()其中:为最大吸引度即光源处(r=处)的吸引度为光强吸收系数因为荧光会,,随着距离的增加和传播媒介的吸收逐渐减弱所以设置光强吸收系数以体现此特性可设为常数r为萤火虫i与j之间的空间距离。ij定义萤火虫i被吸引向萤火虫j移动的位置更新由公式()决定:xxxxrand,,,,,()()式()iiji,其中、x为萤火虫i和j所处的空间位置为步长因子是上的常数randx,,,ji,为上服从均匀分布的随机因子。,,算法实现优化的过程是:先将萤火虫群体随机散布在解空间每一只萤火虫因为所处位置不同发出的荧光亮度也不同通过比较(根据式()),亮度高的萤火虫可以吸引亮度低的萤火虫向自己移动移动的距离主要取决于吸引度的大小(根据式())。为了加大,,()rand搜索区域避免过早陷入局部最优在位置更新过程中增加了扰动项根据式()来计算更新后的位置。这样通过多次移动后所有个体都将聚集在亮度最高的萤火虫的位置上从而实现寻优。五、萤火虫算法的流程综上所述萤火虫优化算法流程如下:、初始化算法基本参数。设置萤火虫数目n,最大吸引度光强吸收系数步,,长因子,最大迭代次数MaxGeneration或搜索精度。,,、随机初始化萤火虫的位置计算萤火虫的目标函数值作为各自最大萤光亮度。I,、由式()、()计算群体中萤火虫的相对亮度和吸引度根据相对亮度决定萤I火虫的移动方向。、根据式()更新萤火虫的空间位置对处在最佳位置的萤火虫进行随机扰动。、根据更新后萤火虫的位置重新计算萤火虫的亮度。、当满足搜索精度或达到最大搜索次数则转下一步否则搜索次数增加转第三步进行下一次搜索。、输出全局极值点和最优个体值。算法的时间复杂度为n是萤火虫数目。On()六、实现萤火虫算法的matlab代码,参数的设置:萤火虫数目n=光吸收强度系数=步长因子=最大吸,引度=迭代次数MaxGeneration=。,测试函数为:Fxxxxxxx()exp(()())exp(()())exp(()),,,,,,,,,,,,,exp(),xxxFx()用萤火虫算法求解函数的最优解的matlab代码为如下:FireflyAlgorithmbyXSYang(CambridgeUniversity)Usage:ffademo(numberoffireflies,MaxGeneration)eg:ffademo(,)functionbest=fireflysimple(instr)n=numberoffirefliesMaxGeneration=numberofpseudotimestepsifnargin<,instr=endn=instr()MaxGeneration=instr()rand('state',)ResettherandomgeneratorFourpeakfunctionsstr='exp((x)^(y)^)exp((x)^(y)^)'str='*exp(x^(y)^)*exp(x^y^)'funstr=strcat(str,str)Convertingtoaninlinefunctionf=vectorize(inline(funstr))range=xminxmaxyminymaxrange=alpha=Randomness(highlyrandom)gamma=AbsorptioncoefficientGridvaluesareusedfordisplayonlyNgrid=dx=(range()range())Ngriddy=(range()range())Ngridx,y=meshgrid(range():dx:range(),range():dy:range())z=f(x,y)Displaytheshapeoftheobjectivefunctionfigure()surfc(x,y,z)generatingtheinitiallocationsofnfirefliesxn,yn,Lightn=initffa(n,range)Displaythepathsoffirefliesinafigurewithcontoursofthefunctiontobeoptimizedfigure()Iterationsorpseudotimemarchingfori=:MaxGeneration,startiterationsShowthecontoursofthefunctioncontour(x,y,z,)holdonEvaluatenewsolutionszn=f(xn,yn)RankingthefirefliesbytheirlightintensityLightn,Index=sort(zn)xn=xn(Index)yn=yn(Index)xo=xnyo=ynLighto=LightnTracethepathsofallroamingfirefliesplot(xn,yn,'','markersize',,'markerfacecolor','g')Moveallfirefliestothebetterlocationsxn,yn=ffamove(xn,yn,Lightn,xo,yo,Lighto,alpha,gamma,range)drawnowUse"holdon"toshowthepathsoffirefliesholdoffendendofiterationsbest(:,)=xo'best(:,)=yo'best(:,)=Lighto'AllsubfunctionsarelistedhereTheinitiallocationsofnfirefliesfunctionxn,yn,Lightn=initffa(n,range)xrange=range()range()yrange=range()range()xn=rand(,n)*xrangerange()yn=rand(,n)*yrangerange()Lightn=zeros(size(yn))Moveallfirefliestowardbrighteronesfunctionxn,yn=ffamove(xn,yn,Lightn,xo,yo,Lighto,alpha,gamma,range)ni=size(yn,)nj=size(yo,)fori=:ni,Theattractivenessparameterbeta=exp(gamma*r)forj=:nj,r=sqrt((xn(i)xo(j))^(yn(i)yo(j))^)ifLightn(i)<Lighto(j),Brighterandmoreattractivebeta=beta=beta*exp(gamma*r^)xn(i)=xn(i)*(beta)xo(j)*betaalpha*(rand)yn(i)=yn(i)*(beta)yo(j)*betaalpha*(rand)endendendforjendendforixn,yn=findrange(xn,yn,range)Makesurethefirefliesarewithintherangefunctionxn,yn=findrange(xn,yn,range)fori=:length(yn),ifxn(i)<=range(),xn(i)=range()endifxn(i)>=range(),xn(i)=range()endifyn(i)<=range(),yn(i)=range()endifyn(i)>=range(),yn(i)=range()endendFx()运行的结果如下图所示其中图为萤火虫算法求解的运行结果图为测试函数的三维效果图图为测试函数的三维效果图的底面截图图为萤火虫Fx()算法对寻优的结果。图萤火虫算法求解F(x)的运行结果图F(x)的三维效果图图F(x)的三维效果图的底面截图图萤火虫算法对F(x)寻优的结果Fx()从图中可以得出:在中当x=x=Fx()Fx()时函数取得最大值即此时=。第四章仿真实验与分析一、三个测试函数的介绍本文用萤火虫算法和遗传算法对以下三个函数进行仿真测试:Fxxxxxx()exp(()())exp(),,,,,,,,,Fxxxxxxx()exp(()())exp(()())exp(()),,,,,,,,,,,,,exp(),xxxnFxxxx()cos(),,,,,,iii,iFx()Fx()x,上述三个函数中是在的范围中具有两个峰值的函数是在Fx()x,的范围中具有四个峰值的函数而是在x,的范围中具有多个峰值的i函数。二、FA和GA对F(x)的仿真测试,参数设置:萤火虫算法中萤火虫数目n=光吸收强度系数=步长因子=最大吸引度=。遗传算法中群体规模N=交叉变异概率pc=pm=。,,两种算法分别在迭代次数T=、、时各自独立运行次。萤火虫算法和遗传算法对F(x)的测试结果分析如表所示。表FA和GA对F(x)的测试结果分析维数峰值数迭代次数平均最大值(FA)平均最大值(GA)F(x)从表中可以看出:萤火虫算法和遗传算法在对峰值数为的函数F(x)进行测试求解时在相同的迭代次数下用萤火虫算法所求得最大值的精确度要高于用遗传算法所求得的最大值。萤火虫算法运行的结果(独立运行次每次的结果都一样故只取其中一个结果)如表所示。表萤火虫算法求解F(x)运行的结果T=T=T=最大值遗传算法独立运行次的结果如表所示。表遗传算法求解F(x)运行的结果T=T=T=最大值遗传算法在对F(x)进行测试迭代次时运行一次的结果如图所示。图GA在对F(x)进行测试运行一次的结果遗传算法在对F(x)进行测试迭代次时运行一次的最优适应度进化曲线图如图所示。图GA在对F(x)进行测试运行一次的最优适应度进化曲线图F(x)的三维效果图如图所示。图F(x)的三维效果图萤火虫算法在对F(x)进行测试迭代次时运行一次的结果如图所示。图FA在对F(x)进行测试运行一次的结果萤火虫算法在对F(x)进行测试迭代次时运行一次的寻优路径的最终结果如图所示。图FA在对F(x)进行测试运行一次的寻优路径的最终结果三、FA和GA对F(x)的仿真测试,参数设置:萤火虫算法中萤火虫数目n=光吸收强度系数=步长因子=最大吸引度=。遗传算法中群体规模N=交叉变异概率pm=pc=。,,两种算法分别在迭代次数T=、、时各自独立运行次。萤火虫算法和遗传算法对F(x)的测试结果分析如表所示。表FA和GA对F(x)的测试结果分析维数峰值数迭代次数平均最大值(FA)平均最大值(GA)F(x)从表中可以看出:萤火虫算法和遗传算法在对峰值数为的函数F(x)进行测试求解时在相同的迭代次数下用萤火虫算法所求得最大值的精确度要高于用遗传算法所求得的最大值。遗传算法独立运行次的结果如表所示。表遗传算法求解F(x)运行的结果T=T=T=最大值萤火虫算法运行的结果(独立运行次每次的结果都一样故只取其中一个结果)如表所示。表萤火虫算法求解F(x)运行的结果T=T=T=最大值遗传算法在对F(x)进行测试迭代次时运行一次的最优适应度进化曲线图如图所示。图GA在对F(x)进行测试运行一次的最优适应度进化曲线图遗传算法在对F(x)进行测试迭代次时运行一次的结果如图所示。F(x)的三维效果图如第三章第六小节中的图所示。萤火虫算法在对F(x)进行测试迭代次时运行一次的结果如第三章第六小节中的图所示。萤火虫算法在对F(x)进行测试迭代次时运行一次的寻优路径的最终结果如第三章第六小节中的图所示。图GA在对F(x)进行测试运行一次的结果四、FA和GA对F(x)的仿真测试,参数设置:萤火虫算法中萤火虫数目n=光吸收强度系数=步长因子=最大吸引度=。遗传算法中群体规模N=交叉变异概率pm=pc=。,,两种算法分别在迭代次数T=、、时各自独立运行次。萤火虫算法和遗传算法对F(x)的测试结果分析如表所示。表FA和GA对F(x)的测试结果分析维数峰值数迭代次数平均最大值(FA)平均最大值(GA)F(x)多从表中可以看出:FA和GA在对峰值数为多的函数F(x)进行测试求解时在相同的迭代次数下用FA所求得最大值的精确度要高于用GA所求得的最大值。萤火虫算法运行的结果(独立运行次每次的结果都一样故只取其中一个结果)如表所示。表萤火虫算法求解F(x)运行的结果T=T=T=最大值遗传算法独立运行次的结果如表所示。表遗传算法求解F(x)运行的结果T=T=T=最大值遗传算法在对F(x)进行测试迭代次时运行一次的结果如图所示。图GA在对F(x)进行测试运行一次的结果遗传算法在对F(x)进行测试迭代次时运行一次的最优适应度进化曲线图如图所示。图GA在对F(x)进行测试运行一次的最优适应度进化曲线图F(x)的三维效果图如图所示。图F(x)的三维效果图萤火虫算法在对F(x)进行测试迭代次时运行一次的结果如图所示。图FA在对F(x)进行测试运行一次的结果萤火虫算法在对F(x)进行测试迭代次时运行一次的寻优路径的最终结果如图所示。图FA在对F(x)进行测试运行一次的寻优路径的最终结果五、测试结果分析本章是通过把萤火虫算法和遗传算法分别应用于三个测试函数进行仿真测试对测试结果进行图表分析然后得出结论。所选的三个测试函数都是具有峰值的函数。本文先从峰值数为的F(x)函数进行入手在设置好各自参数的情况下分别在迭代次数T=、、时进行测试各自独立运行次取函数最大值的平均数进行比较如表所示。然后依次对峰值数为的F(x)函数和具有多个峰值数的F(x)函数在取三个不同的迭代次数T的情况下进行同样的操作得到的结果分别如表和表所示。从表、表和表的数据比较中可以得出:萤火虫算法和遗传算法在对峰值函数进行测试求解时在相同的迭代次数下用萤火虫算法所求得的峰值函数的最大值的精确度要高于用遗传算法所求得。同时在表中可以看出当函数的峰值数较多时要求得同一精确度时萤火虫算法所迭代的次数要比遗传算法少得多。所以在求解峰值函数的最大值时萤火虫算法的效率要高于遗传算法。结论本文先是对群智能优化算法的概念进行简单的阐述接着对几个典型的群智能优化算法如:模拟退火算法、遗传算法、蚁群算法、粒子群算法、人工萤火虫群优化算法、人工鱼群算法进行原理的了解和阐述。然后着重对一种新颖的仿生群智能算法萤火虫算法进行了理论分析该算法模拟自然界中萤火虫发光的生物特性将多智能体系统与进化算法的机制相结合利用进化的方式来实现智能体的行为以达到优化的目的。算法参数少实现简单具有本质并行性。本文是通过把萤火虫算法和遗传算法分别应用于三个测试函数进行仿真测试对测试结果进行图表分析然后得出结论。所选的三个测试函数都是具有峰值的函数。从第四章的图表中可以得出:、萤火虫算法和遗传算法在对同一峰值函数进行测试求解所求得的最优解的精确度会随着其迭代次数的增大而提高。、萤火虫算法和遗传算法在对峰值函数进行测试求解时在相同的迭代次数下用萤火虫算法所求得的峰值函数的最大值的精确度要高于用遗传算法所求得。、当函数的峰值数较多时要求得其最大值的同一精确度时萤火虫算法所迭代的次数要比遗传算法少得多。、在求解峰值函数的最大值时萤火虫算法的效率要高于遗传算法。这表明了萤火虫算法在连续空间优化的可行性和有效性同时也表明了萤火虫算法具有良好的应用前景。致谢行文至此我的这篇文论已接近尾声。岁月如梭我四年的大学时光也即将敲响结束的钟声。离别在即站在人生的又一个转折点上心中难免思绪万千一种感恩之情油然而生。历经将近一个学期的时间我终于快将这篇毕业设计论文完成了。我一开始选定这个毕业设计论文时对群智能优化算法这块可谓是一无所知所以一开始就感到种种困难刚开始一段时间都想放弃重新选题。我的指导老师杜晓刚老师鼓励我继续坚持下去。他告诉我这篇毕业设计论文挺好挺有意义的。于是我就不断跑图书馆、不断上网查找有关群智能优化算法这块知识。萤火虫算法是一种新型的群智能优化算法它是在年才提出的所以现在有关这块的知识比较少研究起来比较费劲。所以我有问题就找杜老师杜老师对我的问题很有耐心并详细地一一解答还指导我从哪些方面从手比较容易。杜老师为我的研究提供了明确的方向让我在研究萤火虫算法的时候少走了很多弯路。杜老师是一位认真负责、要求严格的老师。每当我们向他汇报自己论文的进度情况时他都会认认真真、仔仔细细的看我们的论文并及时指出我们论文存在的错误和不足之处。所以我在杜老师的指导和帮助下顺利地完成了我的毕业论文为我大学四年的学习生活画上了圆满的句号。在此我再一次感谢杜晓刚老师我为我能遇到这样一个认真负责的指导老师而感动荣幸。同时我也感谢在这段期间帮助过我的同学们尤其是我的室友们。借此之际我向他们表达我最衷心的感谢。参考文献彭喜元,彭宇群智能理论及应用J电子学报年S期基于仿生理论的几种优化算法综述J计算机应用研究年期李雪梅,张素琴,王凌,刘波,微粒群优化与生产调度算法M清华大学出版社,刘长平,叶春明,一种新颖的仿生群智能优化算法:萤火虫算法J计算机应用研究年期XinSheYang,EagleStrategyUsingLevyWalkandFireflyAlgorithmsForStochasticOptimization,XinSheYang,FireflyAlgorithmsforMultimodalOptimization,康立山谢云等非数值并行算法模拟退火算法M北京:科学出版社李敏强寇纪凇等遗传算法的基本理论与应用M北京:科学出版社段海滨蚁群算法原理及其应用M北京:科学出版社周明孙树栋遗传算法原理及应用M北京:国防工业出版社段海滨王道波于秀芬几种新型仿生优化算法的比较研究J计算机仿真,():李晓磊一种新型的智能优化算法人工鱼群算法D杭州:浙江大

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/46

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利