17-05-2012, 11:05 AM
Cuckoo Search via Levy Flights
_reading7 Cuckoo search.pdf (Size: 875.33 KB / Downloads: 211)
Abstract
—In this paper, we intend to formulate a new metaheuristic
algorithm, called Cuckoo Search (CS), for solving
optimization problems. This algorithm is based on the obligate
brood parasitic behaviour of some cuckoo species in combination
with the L´evy flight behaviour of some birds and fruit flies. We
validate the proposed algorithm against test functions and then
compare its performance with those of genetic algorithms and
particle swarm optimization. Finally, we discuss the implication
of the results and suggestion for further research.
Index Terms—algorithm; cuckoo search; L´evy flight; metaheuristics;
nature-inspired strategy; optimization;
I. INTRODUCTION
More and more modern metaheuristic algorithms inspired
by nature are emerging and they become increasingly popular.
For example, particles swarm optimization (PSO) was inspired
by fish and bird swarm intelligence, while the Firefly Algorithm
was inspired by the flashing pattern of tropical fireflies
[2], [3], [6], [21], [22]. These nature-inspired metaheuristic
algorithms have been used in a wide range of optimization
problems, including NP-hard problems such as the travelling
salesman problem [2], [3], [6], [8], [10], [21].
The power of almost all modern metaheuristics comes from
the fact that they imitate the best feature in nature, especially
biological systems evolved from natural selection over millions
of years. Two important characteristics are selection of the
fittest and adaptation to the environment. Numerically speaking,
these can be translated into two crucial characteristics of
the modern metaheuristics: intensification and diversification
[3]. Intensification intends to search around the current best
solutions and select the best candidates or solutions, while
diversification makes sure the algorithm can explore the search
space efficiently.
CUCKOO SEARCH
For simplicity in describing our new Cuckoo Search, we
now use the following three idealized rules: 1) Each cuckoo
lays one egg at a time, and dump its egg in randomly chosen
nest; 2) The best nests with high quality of eggs will carry over
to the next generations; 3) The number of available host nests
is fixed, and the egg laid by a cuckoo is discovered by the host
bird with a probability pa ∈ [0, 1]. In this case, the host bird
can either throw the egg away or abandon the nest, and build
a completely new nest. For simplicity, this last assumption can
be approximated by the fraction pa of the n nests are replaced
by new nests (with new random solutions).
CONCLUSIONS
In this paper, we have formulated a new metaheuristic
Cuckoo Search in combination with L´evy flights, based on the
breeding strategy of some cuckoo species. The proposed algorithm
has been validated and compared with other algorithms
such as genetic algorithms and particle swarm optimization.
Simulations and comparison show that CS is superior to these
existing algorithms for multimodal objective functions. This
is partly due to the fact that there are fewer parameters to
be fine-tuned in CS than in PSO and genetic algorithms. In
fact, apart from the population size n, there is essentially one
parameter pa. Furthermore, our simulations also indicate that
the convergence rate is insensitive to the parameter pa. This
also means that we do not have to fine tune these parameters
for a specific problem. Subsequently, CS is more generic and
robust for many optimization problems, comparing with other
metaheuristic algorithms.