第1页 / 共45页
第2页 / 共45页
第3页 / 共45页
第4页 / 共45页
第5页 / 共45页
第6页 / 共45页
第7页 / 共45页
第8页 / 共45页
萤火虫算法的综述.pdf
1 Introduction
2 Firefly algorithm
2.1 Biological foundations
2.2 Structure of the firefly algorithm
2.3 Characteristics of the firefly algorithm
3 Studies on Firefly Algorithms: Classifications and Analysis
3.1 Classical firefly algorithms
3.2 Modified firefly algorithms
3.3 Hybrid firefly algorithms
3.4 Why Firefly Algorithms are so Efficient
4 Applications of Firefly Algorithms
4.1 Optimization
4.2 Classification
4.3 Engineering applications
5 Discussion and further work
6 Conclusions
3
1
0
2
c
e
D
3
2
]
E
N
.
s
c
[
1
v
9
0
6
6
.
2
1
3
1
:
v
i
X
r
a
A comprehensive review of firefly algorithms
Iztok Fistera,∗, Iztok Fister Jr.a, Xin-She Yangb, Janez Bresta
aUniversity of Maribor, Faculty of electrical engineering and computer science,
bSchool of Science and Technology, Middlesex University, London NW4 4BT, UK.
Smetanova 17, 2000 Maribor, Slovenia.
Abstract
The firefly algorithm has become an increasingly important tool of Swarm
Intelligence that has been applied in almost all areas of optimization, as well
as engineering practice. Many problems from various areas have been suc-
cessfully solved using the firefly algorithm and its variants. In order to use
the algorithm to solve diverse problems, the original firefly algorithm needs
to be modified or hybridized. This paper carries out a comprehensive re-
view of this living and evolving discipline of Swarm Intelligence, in order to
show that the firefly algorithm could be applied to every problem arising in
practice. On the other hand, it encourages new researchers and algorithm
developers to use this simple and yet very efficient algorithm for problem
solving. It often guarantees that the obtained results will meet the expecta-
tions.
Citations details: I. Fister, I. Fister Jr., X.-S. Yang, and J. Brest, A
comprehensive review of firefly algorithms, Swarm and Evolutionary Com-
putation, vol. 13, pp. 34-46, 2013.
Keywords: firefly algorithm, swarm intelligence, nature-inspired algorithm,
optimization.
∗Corresponding author
Email addresses: iztok.fister@uni-mb.si (Iztok Fister),
iztok.fister2@uni-mb.si (Iztok Fister Jr.), x.yang@mdx.ac.uk (Xin-She Yang),
janez.brest@uni-mb.si (Janez Brest)
December 24, 2013
1. Introduction
Swarm Intelligence (SI) belongs to an artificial intelligence discipline (AI)
It is inspired
that became increasingly popular over the last decade [1].
from the collective behavior of social swarms of ants, termites, bees, and
worms, flock of birds, and schools of fish. Although these swarms consist
of relatively unsophisticated individuals, they exhibit coordinated behavior
that directs the swarms to their desired goals. This usually results in the self-
organizing behavior of the whole system, and collective intelligence or swarm
intelligence is in essence the self-organization of such multi-agent systems,
based on simple interaction rules. This coordinated behavior is performed
due to interaction between individuals, for example, termites and worms are
able to build sophisticated nests, whilst ants and bees also use this collective
behavior when searching for food. Typically, ants interact with each other
via chemical pheromone trails in order to find the shortest path between their
nest and the food sources. In a bee colony, the role of informer is played by
so-called scouts, i.e., individual bees that are responsible for searching for
new promising areas of food sources. Here, the communication among bees
is realized by a so-called ’waggle dance’, through which the bee colony is
directed by scouts. During this discovery of the new food sources, a trade-
off between exploration (the collection of new information) and exploitation
(the use of existing information) must be performed by the bee colony [2].
That is, the bee colony must be aware when to exploit existing food sources
and when to look for new food sources so as to maximize the overall nectar
intake while minimizing the overall foraging efforts.
The swarm of individuals shows collective behavior; for example, where
to forage, when to reproduce, where to live, and how to divide the necessary
tasks amongst the available work force [2]. In fact, these decisions are made
in a decentralized manner by individuals based on local information obtained
from interactions with their intermediate environments.
Swarm intelligence refers to a research field that is concerned with a col-
lective behavior within self-organized and decentralized systems. This term
was probably first used by Beni [3] in the sense of cellular robotic systems
consisting of simple agents that organize themselves through neighborhood
interactions. Recently, methods of swarm intelligence are used in optimiza-
tion, the control of robots, and routing and load balancing in new-generation
mobile telecommunication networks, demanding robustness and flexibility.
Examples of notable swarm-intelligence optimization methods are ant colony
2
optimization (ACO) [4] [5], particle swarm optimization (PSO) [6], and ar-
tificial bee colony (ABC) [7] [8]. Today, some of the more promising swarm-
intelligence optimization techniques include the firefly algorithm (FA) [9] [10]
[11] [12], cuckoo-search [13], and the bat algorithm [14], while new algorithms
such as the krill herd bio-inspired optimization algorithm [15] and algorithms
for clustering [16] [17] also emerged recently.
FA is one of the recent swarm intelligence methods developed by Yang [9]
in 2008 and is a kind of stochastic, nature-inspired, meta-heuristic algo-
rithm that can be applied for solving the hardest optimization problems (also
NP-hard problems). This algorithm belongs to stochastic algorithms. This
means, it uses a kind of randomization by searching for a set of solutions.
It is inspired by the flashing lights of fireflies in nature. Heuristic means ‘to
find’ or ‘to discover solutions by trial and error’ [9]. In fact, there is no guar-
antee that the optimal solution will be found in a reasonable amount of time.
Finally, meta-heuristic means ’higher level’, where the search process used in
algorithms is influenced by certain trade-off between randomization and local
search [9]. In the firefly algorithm, the ‘lower level’ (heuristic) concentrates
on the generation of new solutions within a search space and thus, selects
the best solution for survival. On the other hand, randomization enables the
search process to avoid the solution being trapped into local optima. The
local search improves a candidate solution until improvements are detected,
i.e., places the solution in local optimum.
Each meta-heuristic search process depends on balancing between two
major components: exploration and exploitation [18]. Both terms were de-
fined implicitly and are affected by the algorithm’s control parameters. In the
sense of the natural bee colony, the actions of exploration and exploitation
has yet to be explained. For the meta-heuristic algorithms [19], the explo-
ration denotes the process of discovering the diverse solutions within the
search space, whilst exploitation means focusing the search process within
the vicinities of the best solutions, thus, exploiting the information discovered
so far.
Note that FA is population-based. The population-based algorithms
have the following advantages when compared with single-point search al-
gorithms [20]:
• Building blocks are put together from different solutions through crossover.
• Focusing a search again relies on the crossover, and means that if both
parents share the same value of a variable, then the offspring will also
3
have the same value of this variable.
• Low-pass filtering ignores distractions within the landscape.
• Hedging against bad luck in the initial positions or decisions it makes.
• Parameter tuning is the algorithm’s opportunity to learn good param-
eter values in order to balance exploration against exploitation.
The rest of this section will discuss briefly the characteristics of fireflies
that have served as an inspiration for developing the firefly algorithm.
The main characteristic of fireflies is their flashing light. These lights have
two fundamental functions: to attract mating partners and to warn potential
predators. However, the flashing lights obey more physical rules. On the one
hand, the light intensity I decreases as the distance r increases according to
the term I ∝ 1/r2. This phenomenon inspired Yang [9] to develop the firefly
algorithm. On the other hand, the firefly acts as an oscillator that charges
and discharges (fires) the light at regular intervals, i.e., at θ = 2π. When
the firefly is placed within the vicinity of another firefly, a mutual coupling
occurs between both fireflies. This behavior of fireflies especially inspired
the solution of graph coloring problems. On this basis, a distributed graph
coloring algorithm was developed by Lee [21]. Recently, the similar and
greater researched behavior of Japanese tree frogs inspired Hern´andez and
Blum [22] into developing a more useful distributed graph coloring algorithm.
Therefore, the further development of the algorithm based on the oscillatory
behavior of fireflies has diminished. Therefore, in this paper we are focused
on Yang’s firefly algorithm.
An aim of this paper is twofold: to present areas where FA has been
successfully applied, and thus to broaden the range of its potential users.
The structure of this paper is as follows: Section 2 discusses the biological
foundations of the firefly algorithm. Main characteristics of this algorithm
are then exposed, and finally, the algorithmic structure is presented. Section
3 provides an extensive review of application areas to which this algorithm
has already been applied. Let us mention only the most important areas
of its application: continuous, combinatorial, constraint and multi-objective
optimization, and optimization in dynamic and noisy environments. Beside
optimization, it is applicable for solving classification problems arose in areas
like machine learning, data mining, and neural network. Additionally, many
applications cover an area of engineering applications and solve real-world
4
problems. Section 4 brings the discussion of FA behavior and directions for
further development of this algorithms are covered. This paper concludes
with an overview of the work that has been performed within the discipline
of swarm intelligence.
2. Firefly algorithm
2.1. Biological foundations
Fireflies (Coleoptera: Lampyridae) are amongst the most charismatic
of all insects, and their spectacular courtship displays have inspired poets
and scientists alike [23]. Nowadays, more that 2,000 species exist worldwide.
Usually, fireflies live in a variety of warm environments and they are most
active in summer nights. A lot of researchers have studied firefly phenomena
in nature and there exist numerous papers researching fireflies, for example,
[24, 25, 26, 27, 28].
Fireflies are characterized by their flashing light produced by biochemi-
cal process bioluminescence. Such flashing light may serve as the primary
courtship signals for mating. Besides attracting mating partners, the flashing
light may also serve to warn off potential predators. Note that in some firefly
species some adults are incapable of bioluminescence. These species attract
their mates due to pheromone, similarly to ants.
In fireflies, bioluminescent reactions take place from light-producing or-
gans called lanterns. The most bioluminescent organisms provide only slowly
modulated flashes (also glows). In contrast, adults in many firefly species
are able to control their bioluminescence in order to emit high and discrete
flashes. The lanterns’ light-production is initialized by signals originating
within the central nervous system of firefly.
Most firefly species rely on bioluminescent courtship signals. Typically,
the first signalers are flying males, who try to attract flightless females on the
ground. In response to these signals, the females emit continuous or flashing
lights. Both mating partners produce distinct flash signal patterns that are
precisely timed in order to encode information like species identity and sex.
Females are attracted according to behavioral differences in the courtship
signal. Typically, females prefer brighter male flashes. It is well-known that
the flash intensity varies with the distance from the source. Fortunately, in
some firefly species females cannot discriminate between more distant flashes
produced by stronger light source and closer flashes produced by weaker light
sources.
5
Firefly flash signals are highly conspicuous and may therefore deter a
wide variety of potential predators.
In the sense of natural selection [29],
where only the strongest individual can survive, flash signals evolve as defense
mechanisms that serve to warn potential predators.
Two features are characteristics for swarm intelligence: self-organization
and decentralized decision making. Here, autonomous individuals live to-
gether in a common place as, for example, bees in hives, ants in anthills, etc.
In order to live in harmony, some interaction or communication is needed
amongst group members who live together (sociality). In fact, individuals
within a group cannot behave as if they are solitary, but must adapt to the
overall goals within the groups. The social life of fireflies is not just dedicated
to foraging, but more to reproduction. These collective decisions are closely
connected with the flashing light behavior that served as the main biological
foundation for developing the firefly algorithm.
2.2. Structure of the firefly algorithm
As mentioned in Section 1, this paper focuses on Yang’s [9] implementa-
tion of the firefly algorithm. This algorithm is based on a physical formula
of light intensity I that decreases with the increase of the square of the dis-
tance r2. However, as the distance from the light source increases, the light
absorption causes that light becomes weaker and weaker. These phenomena
can be associated with the objective function to be optimized. As a result,
the base FA can be formulated as illustrated in Algorithm 1.
Algorithm 1 Pseudo code of the base Firefly algorithm
1: t = 0; s∗ = ∅; γ = 1.0;
2: P (0) = InitializeFA();
3: while (t
• Their attractiveness is proportional to their light intensity.
• The light intensity of a firefly is affected or determined by the landscape
of the fitness function.
The population of fireflies is initialized by the ‘InitializeFA’ function.
Typically, this initialization is performed randomly. The firefly search process
comprises the inside of the while loop (lines 3-10 in Algorithm 1) and is com-
posed of the following steps: Firstly, the ‘AlphaNew’ function is dedicated to
modify the initial value of parameter α. Note that this step is optional in the
firefly algorithm. Secondly, the ‘EvaluateFA’ function evaluates the quality
of the solution. The implementation of a fitness function f (s) is performed
inside this. Thirdly, the ‘OrderFA’ function sorts the population of fireflies
according to their fitness values. Fourthly, the ‘FindTheBestFA’ function
selects the best individual in population. Finally, the ‘MoveFA’ function
performs a move of the firefly positions in the search space. Note that the
fireflies are moved towards the more attractive individuals.
The firefly search process is controlled by the maximum number of fitness
function evaluations MAX FES.
2.3. Characteristics of the firefly algorithm
In order to design FA properly, two important issues need to be defined:
the variation of light intensity and the formulation of attractiveness. These
two issues enable developers to tailor different firefly algorithms in such a
manner that they are best suited to the demands of the problems to be
solved.
In the standard firefly algorithm, the light intensity I of a firefly
representing the solution s is proportional to the value of fitness function
I(s) ∝ f (s), whilst the light intensity I(r) varies according to the following
equation:
where I0 denotes the light intensity of the source, and the light absorption is
approximated using the fixed light absorption coefficient γ. The singularity
at r = 0 in the expression I/r2 is avoided by combining the effects of the
inverse square law and an approximation of absorption in Gaussian form.
The attractiveness β of fireflies is proportional to their light intensities I(r).
Therefore, a similar equation to Eq. (1) can be defined, in order to describe
the attractiveness β:
I(r) = I0e−γr2,
β = β0e−γr2,
7
(1)
(2)
where β0 is the attractiveness at r = 0. The light intensity I and attrac-
tiveness β are in some way synonymous. Whilst the intensity is referred to
as an absolute measure of emitted light by the firefly, the attractiveness is a
relative measure of the light that should be seen in the eyes of the beholders
and judged by other fireflies (Yang, 2008).
The distance between any two fireflies si and sj is expressed as Euclidean
distance by the base firefly algorithm, as follows:
k=n
rij = si − sj =
(sik − sjk)2,
(3)
k=1
where n denotes the dimensionality of the problem. The movement of the
i-th firefly is attracted to another more attractive firefly j. In this manner,
the following equation is applied:
si = si + β0e−γr2
ij (sj − si) + αi,
(4)
where i is a random number drawn from Gaussian distribution. The move-
ments of fireflies consist of three terms: the current position of i-th firefly,
attraction to another more attractive firefly, and a random walk that consists
of a randomization parameter α and the random generated number from in-
terval [0, 1]. When β0 = 0 the movement depends on the random walk only.
On the other hand, the parameter γ has a crucial impact on the convergence
speed. Although the value of this parameter can theoretically capture any
value from interval γ ∈ [0,∞), its setting depends on the problem to be
optimized. Typically, it varies from 0.1 to 10.
In summary, FA is controlled by three parameters: the randomization pa-
rameter α, the attractiveness β, and the absorption coefficient γ. According
to the parameter setting, FA distinguishes two asymptotic behaviors. The
former appears when γ → 0 and the latter when γ → ∞. If γ → 0, the
attractiveness becomes β = β0. That is, the attractiveness is constant any-
where within the search space. This behavior is a special case of particle
swarm optimization (PSO). If γ → ∞, the second term falls out from the
Eq. (4), and the firefly movement becomes a random walk, which is essen-
tially a parallel version of simulated annealing. In fact, each implementation
of FA can be between these two asymptotic behaviors.
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
