萤火虫算法及其应用研究 - 图文

兰州交通大学毕业设计(论文)

第三章 萤火虫算法

一、 萤火虫算法的概念

萤火虫算法(Firely Algorithm,FA)是一种启发式算法，这种算法启发于晚上萤火虫发光的行为。萤火虫的闪光，其主要目的是作为一个信号系统，以吸引其他的萤火虫。剑桥大学的Xin-She Yang教授在2009年提出了萤火虫算法，其假设为：

1、萤火虫不分性别，它将会被吸引到所有其他比它更亮的萤火虫那去； 2、萤火虫的吸引力和亮度成正比，对于任何两只萤火虫，其中一只会向着比它更亮的另一只移动，然而，亮度是随着距离的增加而减少的；

3、如果没有找到一个比给定的萤火虫更亮，它会随机移动。 二、 萤火虫算法的国内外研究现状

萤火虫算法是剑桥大学的Xin-She Yang教授于2009年提出的一种新型的群智能优化算法。

目前，国外关于萤火虫算法的研究工作主要有：

1、在2009年，剑桥大学的Xin-She Yang教授根据自然界中萤火虫的行为首次提出一种新型的群智能优化算法——萤火虫算法。

2、在2010年4月，Xin-She Yang发表对于萤火虫算法的随机优化的研究报告。 3、在2010年5月，Xin-She Yang发表研究了萤火虫算法的多模优化问题。 4、在2010年11月，Theofanis Apostolopoulos和Aristidis Vlachos发表研究了应用萤火虫算法解决经济排放负荷调度问题。

5、在2012年1月，Mohammad Asif Zaman和Md. Abdul Matin发表研究了基于萤火虫算法的非均匀间隔的线性阵列天线设计。

6、在2012年10月，Surafel Luleseged Tilahun和Hong Choon Ong提出萤火虫算法的优化问题。

国内关于萤火虫算法的研究工作主要有：

1、在2011年7月，王迎菊和周永权提出了一种基于荧光素扩散的 人工萤火虫算法。

2、在2011年9月，刘长平和叶春明发表介绍了萤火虫算法。

13

兰州交通大学毕业设计(论文)

3、在2012年3月，彭伟和汪镭提出了基于萤火虫算法的神经网络CPI预测模型。 4、在2012年6月，刘长平和叶春明发表了置换流水车间调度问题的萤火虫算法求解。

5、在2012年6月，周季华和叶春明发表了应用萤火虫算法求解PFSP问题。 6、在2012年8月，袁际军发表基于多目标萤火虫算法的可调节产品族优化设计。 7、在2012年9月，杨娇和叶春明发表了应用新型萤火虫算法求解Job-shop调度问题。

8、在2013年1月，周季华和叶春明提出了应用萤火虫算法求解置换流水线问题。 9、在2013年3月，曾冰、李明富、张翼等人发表了基于萤火虫算法的装配序列规划研究。

10、在2013年4月，李铁、姚晔等人发表了基于改进型人工萤火虫算法的云计算资源研究。

从萤火虫算法的国内外研究现状来看，萤火虫算法不断进行优化改进并已经逐步应用于各种领域。但毕竟萤火虫算法是近几年刚刚提出的，在许多方面也有待于改进完善。 三、 萤火虫算法的仿生原理

自然界中约有2000种萤火虫，多数种类的萤火虫会发出短促、有节奏的荧光，不同种类的萤火虫发光目的不同，其真实原因仍在探讨当中。一般认为，萤火虫成虫发光的生物学意义是利用物种特有的闪光信号来定位并吸引异性，借此完成求偶交配及繁殖的使命；少数萤火虫利用闪光信号进行捕食；还有一种作用是作为警戒信号，即当萤火虫受到刺激时会发出亮光。萤火虫优化算法就是模拟自然界中萤火虫的发光行为构造出的随机优化算法，但在算法中舍弃了萤火虫发光的一些生物学意义，只利用其发光特性来根据其搜索区域寻找伙伴，并向邻域结构内位置较优的萤火虫移动，从而实现位置进化。

在该算法中，萤火虫彼此吸引的原因取决于两个要素，即自身亮度和吸引度。其中，萤火虫发出荧光的亮度取决于自身所在位置的目标值，亮度越高表示所处的位置越好，即目标值越佳。吸引度与亮度相关，越亮的萤火虫拥有越高的吸引力，可以吸引视线范围内亮度比其弱的萤火虫往这个方向移动。如果发光亮度相同，则萤火虫各自随机移动。亮度和吸引度与萤火虫之间的距离成反比，都随着距离的增加而减小，这相当于模拟了荧光在空间传播时被传播媒介吸收而逐渐衰减的特性。

萤火虫算法是通过模拟萤火虫的群体行为构造出的一类随机优化算法。其仿生原理

14

兰州交通大学毕业设计(论文)

是：用搜索空间中的点模拟自然界中的萤火虫个体，将搜索和优化过程模拟成萤火虫个体的吸引和移动过程，将求解问题的目标函数度量成个体所处位置的优劣，将个体的优胜劣汰过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。 四、 萤火虫算法的数学描述与分析

如上所述，萤火虫算法包含两个要素，即亮度和吸引度。亮度体现了萤火虫所处位置的优劣并决定其移动方向，吸引度决定了萤火虫移动的距离，通过亮度和吸引度的不断更新，从而实现目标优化。从数学角度对萤火虫算法的优化机理进行如下描述：

定义5 萤火虫的相对荧光亮度为 I?I0?e??rij 式(5)

其中：I0为萤火虫的最大萤光亮度，即自身(r =0处)荧光亮度，与目标函数值相关，目标函数值越优自身亮度越高；?为光强吸收系数，因为荧光会随着距离的增加和传播媒介的吸收逐渐减弱，所以设置光强吸收系数以体现此特性，可设为常数；rij为萤火虫i与j之间的空间距离。

定义6 萤火虫的吸引度为

???0?e2??rij 式(6)

其中：?0为最大吸引度，即光源处(r=0处)的吸引度；?为光强吸收系数，因为荧光会随着距离的增加和传播媒介的吸收逐渐减弱，所以设置光强吸收系数以体现此特性，可设为常数；rij为萤火虫i与j之间的空间距离。

定义7 萤火虫i被吸引向萤火虫j移动的位置更新由公式(7)决定：

xi?xi???(xj?xi)???(rand?1/2) 式(7) 其中，xi、xj为萤火虫i和j所处的空间位置；?为步长因子，是?0,1?上的常数；rand为?0,1?上服从均匀分布的随机因子。

算法实现优化的过程是：先将萤火虫群体随机散布在解空间，每一只萤火虫因为所处位置不同发出的荧光亮度也不同，通过比较(根据式(5)),亮度高的萤火虫可以吸引亮度低的萤火虫向自己移动，移动的距离主要取决于吸引度的大小(根据式(6))。为了加大搜索区域，避免过早陷入局部最优，在位置更新过程中增加了扰动项??(rand?1/2)，根据式(7)来计算更新后的位置。这样通过多次移动后，所有个体都将聚集在亮度最高的萤火虫的位置上，从而实现寻优。

15

兰州交通大学毕业设计(论文)

五、 萤火虫算法的流程

综上所述，萤火虫优化算法流程如下：

1、初始化算法基本参数。设置萤火虫数目n,最大吸引度?0，光强吸收系数?，步长因子?,最大迭代次数MaxGeneration或搜索精度?。

2、随机初始化萤火虫的位置，计算萤火虫的目标函数值作为各自最大萤光亮度I0。 3、由式(5)、(6)计算群体中萤火虫的相对亮度I和吸引度?，根据相对亮度决定萤火虫的移动方向。

4、根据式(7)更新萤火虫的空间位置，对处在最佳位置的萤火虫进行随机扰动。 5、根据更新后萤火虫的位置，重新计算萤火虫的亮度。

6、当满足搜索精度或达到最大搜索次数则转下一步；否则，搜索次数增加1，转第三步，进行下一次搜索。

7、输出全局极值点和最优个体值。

算法的时间复杂度为O(n2)，n是萤火虫数目。 六、 实现萤火虫算法的matlab代码

参数的设置：萤火虫数目n=12；光吸收强度系数?=1.0；步长因子?=0.2；最大吸引度?0=1.0；迭代次数MaxGeneration=100。 测试函数为： F(x)?exp(?(x1?4)2?(x2?4)2)?exp(?(x1?4)2?(x2?4)2)?2?exp(?x12?(x2?4)2) ?2?exp(?x12?x22),x?5 用萤火虫算法求解函数F(x)的最优解的matlab代码为如下： % Firefly Algorithm by X S Yang (Cambridge University) %Usage:ffa_demo([number_of_fireflies,MaxGeneration]) % eg: ffa_demo([12,100]); function [best]=firefly_simple(instr) % n=number of fireflies % MaxGeneration=number of pseudo time steps if nargin<1, instr=[12 100]; end n=instr(1); 16