a r X i v :1003.1466v 1 [m a t h .O C ] 7 M a r 2010Firefly Algorithms for Multimodal Optimization Xin-She Yang Department of Engineering,University of Cambridge,Trumpington Street,Cambridge CB21PZ,UK Abstract Nature-inspired algorithms are among the most powerful algorithms for op-timization.This paper intends to provide a detailed description of a new Firefly Algorithm (FA)for multimodal optimization applications.We will compare the propod firefly algorithm with other metaheuristic algorithms such as particle swarm optimization (PSO).Simulations and results indicate that the propod firefly algorithm is superior to existing metaheuristic algorithms.Finally we will discuss its applications and implications for further rearch.Citation detail:X.-S.Yang,“Firefly algorithms for multimodal optimiza-tion”,in:Stochastic Algorithms:Foundations and Applications ,SAGA 2009,Lecture Notes in Computer Sciences,Vol.5792,pp.169-178(2009).1Introduction Biologically inspired algorithms are becoming powerful in modern numerical optimization [1,2,4,6,9,10],especially for the NP-hard problems such as the travelling salesman problem.Among the biology-derived algorithms,the multi-agent metaheuristic algorithms such as particle swarm optimization form hot rearch topics in the start-of-the-art algorithm development in optimiza-tion and other applications [1,2,9].
Particle swarm optimization (PSO)was developed by Kennedy and Eber-hart in 1995[5],bad on the s
warm behaviour such as fish and bird schooling in nature,the so-called swarm intelligence.Though particle swarm optimization has many similarities with genetic algorithms,but it is much simpler becau it does not u mutation/crossover operators.Instead,it us the real-number randomness and the global communication among the swarming particles.In this n,it is also easier to implement as it us mainly real numbers.This paper aims to introduce the new Firefly Algorithm and to provide the comparison study of the FA with PSO and other relevant algorithms.We will first outline the particle swarm optimization,then formulate the firefly algorithms and finally give the comparison about the performance of the algorithms.The FA optimization ems more promising than particle swarm optimization in the n that FA can deal with multimodal functions more
naturally and efficiently.In addition,particle swarm optimization is just a special class of thefirefly algorithms as we will demonstrate this in this paper. 2Particle Swarm Optimization
2.1Standard PSO
The PSO algorithm arches the space of the objective functions by adjusting the trajectories of individual agents,called particles,as the piecewi paths formed by positional vectors in a quasi-stochastic manner[5,6].There are now as many as about20different variants of PSO.Here we only describe the simplest and yet popular standard PSO.
The particle movement has two major components:a stochastic component and a deterministic component.A particle is attracted toward the position of the current global best g∗and its own best location x∗i in history,while at the same time it has a tendency to move randomly.When a particlefinds a location that is better than any previously found locations,then it updates it as the new current best for particle i.There is a current global best for all n particles.The aim is tofind the global best among all the current best solutions until the objective no longer improves or after a certain number of iterations.
For the particle movement,we u x∗i to denote the current best for particle i,and g∗≈min or max{f(x i)}(i=1,2,...,n)to denote the current global best. Let x i and v i be the position vector and velocity for particle i,respectively. The new velocity vector is determined by the following formula
v t+1
i
=v t i+αǫ1⊙(g∗−x t i)+βǫ2⊙(x∗i−x t i).(1) whereǫ1andǫ2are two random vectors,and each entry taking the values between0and1.The Hadamard product of two matrices u⊙v is defined as the entrywi product,that is[u⊙v]ij=u ij v ij.The parametersαandβare the learning parameters or acceler
ation constants,which can typically be taken
as,say,α≈β≈2.The initial values of x t=0
i can be taken as the bounds or
limits a=min(x j),b=max(x j)and v t=0
i =0.The new position can then be
updated by
x t+1 i =x t i+v t+1
i
默认软件设置
.(2)
Although v i can be any values,it is usually bounded in some range[0,v max].
There are many variants which extend the standard PSO algorithm,and the most noticeable improve
回春操ment is probably to u inertia functionθ(t)so that v t i is replaced byθ(t)v t i whereθtakes the values between0and1.In the simplest ca,the inertia function can be taken as a constant,typicallyθ≈0.5∼0.9. This is equivalent to introducing a virtual mass to stabilize the motion of the particles,and thus the algorithm is expected to converge more quickly.
3Firefly Algorithm
3.1Behaviour of Fireflies
Theflashing light offireflies is an amazing sight in the summer sky in the tropical and temperate regions.There are about two thousandfirefly species, and mostfireflies produce short and rhythmicflashes.The pattern offlashes is often unique for a particular species.Theflashing light is produced by a process of bioluminescence,and the true functions of such signaling systems are still debating.However,two fundamental functions of suchflashes are to attract mating partners(communication),and to attract potential prey.In addition,flashing may also rve as a protective warning mechanism.The rhythmicflash, the rate offlashing and the amount of time form part of the signal system that brings both xes together.Females respond to a male’s unique pattern of flashing in the same species,while in some species such as photuris,female fireflies can m
imic the matingflashing pattern of other species so as to lure and eat the malefireflies who may mistake theflashes as a potential suitable mate.
We know that the light intensity at a particular distance r from the light source obeys the inver square law.That is to say,the light intensity I de-creas as the distance r increas in terms of I∝1/r2.Furthermore,the air absorbs light which becomes weaker and weaker as the distance increas. The two combined factors make mostfireflies visible only to a limited dis-tance,usually veral hundred meters at night,which is usually good enough forfireflies to communicate.
不好吃的英文
Theflashing light can be formulated in such a way that it is associated with the objective function to be optimized,which makes it possible to formulate new optimization algorithms.In the rest of this paper,we willfirst outline the basic formulation of the Firefly Algorithm(FA)and then discuss the implementation as well as its analysis in detail.
3.2Firefly Algorithm
Now we can idealize some of theflashing characteristics offireflies so as to developfirefly-inspired algorithms.For simplicity in describing our new Fireflire Algorithm(FA),we now u the following three idealized rules:1)allfireflies are unix so that onefirefly will be attracted to otherfireflies regardless of
their x;2)Attractiveness is proportional to their brightness,thus for any twoflashingfireflies,the less brighter one will move towards the brighter one. The attractiveness is proportional to the brightness and they both decrea as their distance increas.If there is no brighter one than a particularfirefly, it will move randomly;3)The brightness of afirefly is affected or determined by the landscape of the objective function.For a maximization problem,the brightness can simply be proportional to the value of the objective function. Other forms of brightness can be defined in a similar way to thefitness function in genetic algorithms.
Bad on the three rules,the basic steps of thefirefly algorithm(FA)can be summarized as the pudo code shown in Fig.1.
Firefly Algorithm
Figure1:Pudo code of thefirefly algorithm(FA).
In certain n,there is some conceptual similarity between thefirefly al-gorithms and the bacterial foraging algorithm(BFA)[3,7].In BFA,the at-traction among bacteria is bad partly on theirfitness and partly on their distance,while in FA,the attractiveness is linked to their objective function and monotonic decay of the attractiveness with distance.However,the agents in FA have adjustable visibil
ity and more versatile in attractiveness variations, which usually leads to higher mobility and thus the arch space is explored more efficiently.
3.3Attractiveness
In thefirefly algorithm,there are two important issues:the variation of light intensity and formulation of the attractiveness.For simplicity,we can always assume that the attractiveness of afirefly is determined by its brightness which in turn is associated with the encoded objective function.
In the simplest ca for maximum optimization problems,the brightness I of afirefly at a particular location x can be chon as I(x)∝f(x).However, the attractivenessβis relative,it should be en in the eyes of the beholder or judged by the otherfireflies.Thus,it will vary with the distance r ij between firefly i andfirefly j.In addition,light intensity decreas with the distance from its source,and light is also absorbed in the media,so we should allow the attractiveness to vary with the degree of absorption.In the simplest form, the light intensity I(r)varies according to the inver square law I(r)=I s/r2 where I s is the intensity at the source.For a given medium with afixed light absorption coefficientγ,the light intensity I varies with the distance r.That is I=I0e−γr,where I0is the original light intensity.In order to avoid the singularity at r=0in the expression I s/r2,the combined effect of both the
inver square law and absorption can be approximated using the following Gaussian form
I(r)=I0e−γr2.(3) Sometimes,we may need a function which decreas monotonically at a slower rate.In this ca,we can u the following approximation
I(r)=
I0
2γ2r4+...,
1
桥头堡1+γr2
.Equation(6)defines a characteristic
distanceΓ=1/√
Γm
四季风光
.
3.4Distance and Movement
蒸鱼的做法The distance between any twofireflies i and j at x i and x j,respectively,is the Cartesian distance
r ij=||x i−x j||=
(x i−x j)2+(y i−y j)2.
The movement of afirefly i is attracted to another more attractive(brighter)firefly j is determined by
内眼角有痣>拉菲尔x i=x i+β0e−γr2ij(x j−x i)+α(rand−1
