一种新颖的仿生群智能优化算法_萤火虫算法

第28卷第9期2011年9月计算机应用研究

ApplicationResearchofComputersVol．28No．9Sep．2011

一种新颖的仿生群智能优化算法：

萤火虫算法

1，21

刘长平，叶春明

（1．上海理工大学管理学院，上海200093；2．淮阴工学院，江苏淮安223001）

摘

要：萤火虫算法是受自然界中的萤火虫通过荧光进行信息交流这种群体行为的启发演变而来。作为一种

分析了萤火虫算法的仿生原理，从数学角度对算法实现优化过程进行了定义。通新颖的仿生群智能优化算法，

过典型的函数优化和组合优化问题对算法进行了仿真测试，测试结果表明了萤火虫算法在连续空间和离散空间优化的可行性和有效性，具有良好的应用前景。

关键词：群智能；萤火虫算法；仿生原理；函数优化；组合优化中图分类号：TP301.6

文献标志码：A

文章编号：1001-3695（2011）09-3295-03

doi：10．3969/j．issn．1001-3695．2011．09．024

Novelbioinspiredswarmintelligenceoptimizationalgorithm：

fireflyalgorithm

LIUChang-ping1，，YEChun-ming1

（1．ManagementSchool，UniversityofShanghaiforScience＆Technology，Shanghai200093，China；2．HuaiyinInstituteofTechnology，Hua-ianJiangsu223001，China）

Abstract：Inspiredbysocialbehavioroffirefliesandthephenomenonofbioluminescentcommunication，fireflyalgorithm

（FA）isdevelopedasanovelbionicswarmintelligenceoptimizationmethod．Thispaperanalyzedthebionicprincipleoffireflyalgorithmanddefinedthemechanismofoptimizationbymathematics．TestedtheFAbybenchmarkfunctionsandcombinatorialoptimizationinstances．Simulationsandresultsindicatethatthenewbioinspiredalgorithmhasbetterfeasibilityandvalidityforcontinuousspaceoptimizationanddiscretespaceoptimization．

Keywords：swarmintelligence；fireflyalgorithm；bionics；functionoptimization；combinatorialoptimization

0引言

群智能优化算法是近几十年发展起来的仿生模拟进化算

法的仿生原理，并从数学角度对算法实现优化过程进行定义，通过几个典型的函数优化和组合优化问题的测试，对该算法的可行性和有效性进行验证。

法，具有操作简单、宜于并行处理、鲁棒性强等特点，典型算法如蚁群算法、粒子群算法等

［1，2］

。这类算法将问题的所有可能

1.1

萤火虫算法的优化机理

算法仿生原理

自然界中约有2000种萤火虫，多数种类的萤火虫会发出

从代表问题可能解的一个子集开始，通过对解集看做解空间，

该子集施加某种算子操作产生新的解集，并逐渐使种群进化到包含最优解或近似最优解的状态。在进化过程中仅需要目标函数的信息，不受搜索空间连续或可微的限制就可以找到最优解，因此，被广泛应用于模式识别择

［5，6］

［3］

［4］

、自动控制、网络路由选

［7，8］［9，10］［11，12］

、、机器人路径规划组合优化以及社会科学

短促、有节奏的荧光，不同种类的萤火虫发光目的不同，其真实原因仍在探讨当中。一般认为，萤火虫成虫发光的生物学意义借此完成求偶是利用物种特有的闪光信号来定位并吸引异性，

交配及繁殖的使命；少数萤火虫利用闪光信号进行捕食；还有即当萤火虫受到刺激时会发出亮一种作用是作为警戒信号，

光。萤火虫优化算法就是模拟自然界中萤火虫的发光行为构但在算法中舍弃了萤火虫发光的一些生造出的随机优化算法，

物学意义，只利用其发光特性来根据其搜索区域寻找伙伴，并向邻域结构内位置较优的萤火虫移动，从而实现位置进化。

在该算法中，萤火虫彼此吸引的原因取决于两个要素，即自

等多个领域。

萤火虫算法是模拟自然界中萤火虫成虫发光的生物学特性发展而来，也是基于群体搜索的随机优化算法。关于该算法

［13］

目前文献有两种版本：a）由印度学者Krishnanand等人提

出，称为GSO（glowwormswarmoptimization）；b）由剑桥学者Yang［14］提出，称为FA（fireflyalgorithm）。两种算法的仿生原理相同，但在具体实现方面有一定差异。本文分析了萤火虫算

收稿日期：2011-03-16；修回日期：2011-04-29

基金项目：国家教育部人文社会科学规划基金项目（10YJA630187）；高校博士点专项科

研基金项目（[1**********]008）；上海市重点学科建设资助项目（S30504）

作者简介：刘长平（1974-），男，河南洛阳人，讲师，博士研究生，主要研究方向为智能优化、工业工程（lcp_mail@163．com）；叶春明（1964-），男，安徽宣城人，副院长，教授，博导，博士，主要研究方向为智能优化、工业工程．

·3296·

计算机应用研究第28卷

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

萤火虫算法是通过模拟萤火虫的群体行为构造出的一类随机优化算法。其仿生原理是：用搜索空间中的点模拟自然界中的萤火虫个体，将搜索和优化过程模拟成萤火虫个体的吸引将求解问题的目标函数度量成个体所处位置的优和移动过程，

劣，将个体的优胜劣汰过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。1.2

算法的数学描述与分析

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

［15，16］

b）随机初始化萤火虫的位置，计算萤火虫的目标函数值作为各自最大萤光亮度I0。

c）由式（1）（2）计算群体中萤火虫的相对亮度I和吸引度β，根据相对亮度决定萤火虫的移动方向。

d）根据式（3）更新萤火虫的空间位置，对处在最佳位置的萤火虫进行随机扰动。

e）根据更新后萤火虫的位置，重新计算萤火虫的亮度。f）当满足搜索精度或达到最大搜索次数则转g）；否则，搜索次数增加1，转c），进行下一次搜索。

g）输出全局极值点和最优个体值。

m是萤火虫数目。算法的时间复杂度为O（m），

3仿真实验

本文选用了几个典型的函数优化和组合优化问题来测试

萤火虫算法的性能。3.1

函数优化问题仿真测试

参数设置：萤火虫算法中，萤火虫数m=100；光强吸收系数γ=1．0；最大吸引度β0=1．0；步长因子α=0．02；迭代次数maxT=200。粒子群算法中，17］中粒子数m=100；采用文献［Wmin=0．2；学习因所提出的线性减少的惯性权重：Wmax=0．9，

子：C1=C2=1．4962；迭代次数maxT=200；每种算法独立运行20次，FA表示结果如表1所示。PSO表示基本粒子群算法，基本萤火虫算法。

表1

函数f1（x）

维数2210

群体数100100100

：

I=I0×e－γrij

（1）

定义1萤火虫的相对荧光亮度为

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

定义2

萤火虫的吸引度为

β=β0×e

－γr2ij

函数优化问题测试结果

平均最优值/（寻优率/%）PSO

－0．9246（21．5%）

FA－0．9981（87%）

（2）

f2（x）f3（x）

－1．6922e+002（29．5%）－1．7232e+002（39%）

18．8370（0%）

15．6553（0%）

rij意其中：β0为最大吸引度，即光源处（r=0处）的吸引度；γ、义同上。

定义3（3）决定：

xi=xi+β×（xj－xi）+α×（rand－1/2）

（3）

测试函数如下：

萤火虫i被吸引向萤火虫j移动的位置更新由式

a）SchafferF6function

minf1（x）=

sin2

［1+0．001（

1+x2

x21

－0．5

+x22）］

－0．5，xi∈［－100，100］

xi、xj为萤火虫i和j所处的空间位置；α为步长因子，其中，是［0，1］0，1］上的常数；rand为［上服从均匀分布的随机因子。

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

b）Hansenfunction

minf2（x）=∑i×cos（（i－1）×x1+i）×∑j×cos（（j+1）×x2+j）

i=1

j=1

xi∈［－10，10］

c）Rastriginfunction

minf3（x）=∑［x2，xi∈［－5．12，5．12］i－10cos（2πxi）+10］

i=1D

SchafferF6函数是具有强烈振荡的多峰函数，理论最优值为－1，算法搜索到的最优解小于－0．9999时认为寻优成功。Hansen函数也是一个多峰函数，局部极值点有760个，理论最优值为－176．5417。Rastrigrin函数为高度多模态函数，在解空间内存在大约10n个（n为解空间维数）局部极小点，理论最优值为0。测试表明，在相同维数和群体数条件下，对于测试函2，FA算法的寻优精度、数1、寻优率和收敛速度均高于PSO算法。对于测试函数3，两种算法均未搜索到最优解，但FA算法寻优精度要高于PSO算法，反映出这两种算法对于高维多峰函数的优化效果还不理想，但考虑到采用的均是基本算法，优

2算法流程

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

a）初始化算法基本参数。设置萤火虫数目m，最大吸引度

β0，光强吸收系数γ，步长因子α，最大迭代次数maxT或搜索精度ε。

第9期刘长平，等：一种新颖的仿生群智能优化算法：

萤火虫算法·3297·

化结果是可以接受的。两种算法对三个函数的测试寻优曲线分别如图1～3所示

。

了理论分析，该算法模拟自然界中萤火虫发光的生物特性，将利用进化的方式来实多智能体系统与进化算法的机制相结合，

现智能体的行为以达到优化的目的。算法参数少，实现简单，具有本质并行性。通过几个典型的函数优化和组合优化问题表明了萤火虫算法在连续空间和离散空间优化的的仿真测试，

可行性和有效性，具有良好的应用前景。参考文献：

［1］彭喜元，．电子学报，2003，彭宇，戴毓丰．群智能理论及应用［J］

32（12）：1982-1988．

［2］李学梅，．计算机张素琴．基于仿生理论的几种优化算法综述［J］

2009，26（6）：2032-2034．应用研究，

［3］NEZHINSKYAE，VERBEEKFJ．Patternrecognitionforhigh

throughputzebrafishimagingusinggeneticalgorithmoptimization［C］//Procofthe5thIAPRInternationalConferenceonPatternReco-gnitioninBioinformatics．2010：301-312．

［4］DUANHai-bin，MAGuan-jun，LUODe-lin．Optimalformationrecon-figurationcontrolofmultipleUCAVsusingimprovedparticleswarmoptimization［J］．JournalofBionicEngineering，2008，5（4）：340-347．

［5］OIDAK，SEKIDOM．ARS：anefficientagent-basedroutingsystemfor

QoSguarantees［J］．ComputerCommunications，2000，23（14）：1437-1447．

J］．［6］林国辉，马正新，王勇前．基于蚂蚁算法的拥塞规避路由算法［

2003，43（1）：1-4．清华大学学报，

［7］金飞虎，洪炳熔，高庆吉．基于蚁群算法的自由飞行空间机器人路

．机器人，2002，24（6）：526-529．径规划［J］

［8］孙波，陈卫东，席裕庚．基于粒子群优化算法的移动机器人全局路

．控制与决策，2005，20（9）：1052-1060．径规划［J］

［9］MANIEZZOV，COLORNIA．Theantsystemappliedtothequadratic

3.2组合优化问题仿真测试

组合优化问题就是在给定的约束条件下找出离散事件的

最优变量组合问题，典型问题如旅行商、加工调度、图着色等，这些问题通常有很强的工程代表性，但最优化求解非常困难，大多数的组合优化问题已被证明是NP难问题。

本文选取了加工调度问题中的置换流水线调度问题（PF-［18］

SP）作为萤火虫算法的测试用例，测试数据采用由Carlier设

计的Car类问题。参数设置：萤火虫数m=40；光强吸收系数γ=1．0；最大吸引度β0=1．0；步长因子α=0．3；迭代次数maxT=1000。算法独立运行20次，结果如表2所示。

表2

PCar1Car2Car5Car6

n，m

组合优化问题测试结果

寻优率/%100401．550

最优相对误差/%

0000

平均相对误差/%

01．230．690．71

5703811，13，4716610，677208，9

8505

n表示工件数，m表示机器数，C表中P表示问题类型，

assignmentproblem［J］．IEEETransonKnowledgeandDataEn-gineering，1999，11（5）：769-778．

［10］PANQuan-ke，TASGETIRENMF，LIANGYC．Adiscreteparticle

swarmoptimizationalgorithmfortheno-waitflowshopschedulingproblem［J］．ComputersandOperationsResearch，2008，35（9）：2807-2839．

［11］张波，陈睿君，路璐．粒子群算法在投资组合中的应用［J］．系统

2007，25（8）：108-110．工程，

［12］刘晓峰，陈通，张连营．基于微粒群算法的最佳证券投资组合研究

［J］．系统管理学报，2008，17（2）：221-224，234．

［13］KRISHNANANDKN，GHOSED．Detectionofmultiplesourceloca-tionsusingaglowwormmetaphorwithapplicationstocollectiverobo-tics［C］//ProcofIEEESwarmIntelligenceSymposium．Piscataway：IEEEPress，2005：84-91．

［14］YANGXin-she．Nature-inspiredmetaheuristicalgorithms［M］．［S．

l．］：LuniverPress，2008：83-96．

［15］YANGXin-she．Fireflyalgorithmsformult-imodaloptimization［C］//

Procofthe5thInternationalSymposiumonStochasticAlgorithms：FoundationsandApplications．2009：169-178．

［16］YANGXin-she，DEBS．Eaglestrategyusinglévywalkandfireflyal-gorithmsforstochasticoptimization［J］．StudiesinComputationalIntelligence，2010，284：101-111．

［17］SHIYu-hui，EHERHARTR．Amodifiedparticleswarmoptimizer

［C］//ProcofIEEEInternationalConferenceonComputationalIntel-

表示最小化完工时间。从测试结果可以看出，对选取的四类问题算法均找到了最优解，而且寻优精度也比较高，表明萤火虫算法求解置换流水线调度问题是有效的，反映出该算法应用于Car5、Car6问题的寻优组合优化方面的可行性。算法对Car2、曲线分别如图4～6所示

。

4结束语

——萤火虫算法进行本文对一种新颖的仿生群智能算法—

ligence．Piscataway：IEEEPress，1998：69-73．

［18］CARLIERJ．Schedulingwithdisjunctiveconstraints［J］．RAIRORe-chercheOperationnelle，1978，12（4）：333-350．