Cuckoo search
Encyclopedia
Cuckoo search is an optimization
algorithm
developed by Xin-she Yang
and Suash Deb
in 2009. It was inspired by the obligate brood parasitism
of some cuckoo
species by laying their eggs in the nests of other host birds (of other species). Some host birds can engage direct conflict with the intruding cuckoos. For example, if a host bird discovers the eggs are not their own, it will either throw these alien eggs away or simply abandon its nest and build a new nest elsewhere. Some cuckoo species such as the New World
brood-parasitic Tapera have evolved in such a way that female parasitic cuckoos are often very specialized in the mimicry in colors and pattern of the eggs of a few chosen host species
Cuckoo search idealized such breeding behavior, and thus can be applied for various optimization problems. It seems that it can outperform other metaheuristic algorithms in applications.
Another seemingly unrelated algorithm for a completely different area of applications is called cuckoo hashing
which was developed by Rasmus Pagh and Fleming Friche Rodler in 2001.
Each egg in a nest represents a solution, and a cuckoo egg represents a new solution. The aim is to use the new and potentially better solutions (cuckoos) to replace a not-so-good solution in the nests. In the simplest form, each nest has one egg. The algorithm can be extended to more complicated cases in which each nest has multiple eggs representing a set of solutions.
CS is based on three idealized rules:
In addition, Yang and Deb discovered that the random-walk style search is better performed by Lévy flight
s rather than simple random walk
.
The pseudo-code can be summarized as:
Objective function:
Generate an initial population of
host nests;
While (t
Evaluate its quality/fitness
[For maximization,
];
Choose a nest among n (say, j) randomly;
if (
),
Replace j by the new solution;
end if
A fraction (
) of the worse nests are abandoned and new ones are built;
Keep the best solutions/nests;
Rank the solutions/nests and find the current best;
Pass the current best solutions to the next generation;
end while
Post-processing the results and visualization;
An important advantage of this algorithm is its simplicity. In fact, comparing with other population- or agent-based metaheuristic
algorithms such as particle swarm optimization
and harmony search
, there is essentially only a single parameter
in CS (apart from the population size 
). Therefore, it is very easy to implement.
where
is drawn from a standard normal distribution with zero mean and unity standard deviation for random walks, or drawn from Levy distribution for Levy flights. Obviously, the random walks can also be linked with the similarity between a cuckoo's egg and the host's egg which can be tricky in implementation. Here the step size 
determines how far a random walker can go for a fixed number of iterations. The generation of Levy step size is often tricky, and a good algorithm is Mantegna's algorithm.
If s is too large, then the new solution generated will be too far away from the old solution (or even jump out side of the bounds). Then, such a move is unlikely to be accepted. If s is too small, the change is too small to be significant, and consequently such search is not efficient. So a proper step size is important to maintain the search as efficient as possible.
As an example, for simple isotropic random walks, we know that the average distance
traveled in the d-dimension space is
where
is the effective diffusion coefficient. Here 
is the step size or distance traveled at each jump, and 
is the time taken for each jump. The above equation implies that
For a typical length scale L of a dimension of interest, the local search is typically limited in a region of
. For 
and t=100 to 1000, we have 
for d=1, and 
for d=10. Therefore, we can use s/L=0.001 to 0.01 for most problems. Though the exact derivation may require detailed analysis of the behaviour of Levy flights.
Algorithm and convergence analysis will be fruitful, because there are many open problems related to metaheuristics
where K=rand(size(nest))>pa and pa is the discovery rate. A standard CS matlab can be found here http://www.mathworks.com/matlabcentral/fileexchange/29809-cuckoo-search-cs-algorithm
An object-oriented software implementation of cuckoo search was provided by Bacanin On the other hand, a modified cuckoo search algorithm is also implemented for unconstrained optimization problems.
An open source implementation of Modified Cuckoo Search can be found here http://code.google.com/p/modified-cs/
Subsequently, the modified cuckoo search has been applied to optimize unstructured mesh which reduces computational cost significantly. In addition, another interesting improvement to cuckoo search is the so-called quantum-inspired cuckoo search with convincing results
This approach uses random weights to combine multiple objectives to a single objective. As the weights vary randomly, Pareto fronts can be found so the points can distributed diversely over the fronts.
swarm-based algorithms such as PSO. For example, a hybrid CS-PSO algorithm seems to remedy the defect of PSO.
A new quantum-inspired cuckoo search was developed to solve Knapsack problems, which shows its effectiveness.
A conceptual comparison of the cuckoo search with PSO, DE and ABC suggest that CS and DE algorithms provide more robust results than PSO and ABC. An extensive detailed study of various structural optimization problems suggests that cuckoo search obtains better results than other algorithms. In addition, a new software testing approach has been developed based on cuckoo search. In addition, cuckoo search is particularly suitable for large scale problems, as shown in a recent study. Cuckoo search has been applied to train neural networks with improved performance. Furthermore, CS is successfully applied to train spiking neural models. Cuckoo search has also been used to optimize web service composition process and planning graphs.
Cuckoo search is a reliable approach for embedded system design and design optimization. An interesting application of cuckoo search is to solve boundary value problems.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
developed by Xin-she Yang
Xin-she Yang
Xin-She Yang has a DPhil in applied mathematics from Oxford UniversityHe is currently a Senior Research Scientist at National Physical Laboratory, andis the Editor-in-Chief of Int...
and Suash Deb
in 2009. It was inspired by the obligate brood parasitism
Obligate parasite
An obligate parasite is a parasitic organism that cannot complete its life cycle without dependence on its host.-See also:*Obligate intracellular parasite*Parasitism*Parasitic plant*Facultative parasite...
of some cuckoo
Cuckoo
The cuckoos are a family, Cuculidae, of near passerine birds. The order Cuculiformes, in addition to the cuckoos, also includes the turacos . Some zoologists and taxonomists have also included the unique Hoatzin in the Cuculiformes, but its taxonomy remains in dispute...
species by laying their eggs in the nests of other host birds (of other species). Some host birds can engage direct conflict with the intruding cuckoos. For example, if a host bird discovers the eggs are not their own, it will either throw these alien eggs away or simply abandon its nest and build a new nest elsewhere. Some cuckoo species such as the New World
New World
The New World is one of the names used for the Western Hemisphere, specifically America and sometimes Oceania . The term originated in the late 15th century, when America had been recently discovered by European explorers, expanding the geographical horizon of the people of the European middle...
brood-parasitic Tapera have evolved in such a way that female parasitic cuckoos are often very specialized in the mimicry in colors and pattern of the eggs of a few chosen host species
Cuckoo search idealized such breeding behavior, and thus can be applied for various optimization problems. It seems that it can outperform other metaheuristic algorithms in applications.
Another seemingly unrelated algorithm for a completely different area of applications is called cuckoo hashing
Cuckoo hashing
Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table. Cuckoo hashing was first described by Rasmus Pagh and Flemming Friche Rodler in 2001...
which was developed by Rasmus Pagh and Fleming Friche Rodler in 2001.
Cuckoo search
Cuckoo search (CS) uses the following representations:Each egg in a nest represents a solution, and a cuckoo egg represents a new solution. The aim is to use the new and potentially better solutions (cuckoos) to replace a not-so-good solution in the nests. In the simplest form, each nest has one egg. The algorithm can be extended to more complicated cases in which each nest has multiple eggs representing a set of solutions.
CS is based on three idealized rules:
- Each cuckoo lays one egg at a time, and dumps its egg in a randomly chosen nest;
- The best nests with high quality of eggs will carry over to the next generation;
- The number of available hosts nests is fixed, and the egg laid by a cuckoo is discovered by the host bird with a probability
. Discovering operate on some set of worst nests, and discovered solutions dumped from farther calculations.
In addition, Yang and Deb discovered that the random-walk style search is better performed by Lévy flight
Lévy flight
A Lévy flight is a random walk in which the step-lengths have a probability distribution that is heavy-tailed. When defined as a walk in a space of dimension greater than one, the steps made are in isotropic random directions...
s rather than simple random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
.
The pseudo-code can be summarized as:
Objective function:
Generate an initial population of
host nests;While (t
Evaluate its quality/fitness
[For maximization,
];Choose a nest among n (say, j) randomly;
if (
),Replace j by the new solution;
end if
A fraction (
) of the worse nests are abandoned and new ones are built;Keep the best solutions/nests;
Rank the solutions/nests and find the current best;
Pass the current best solutions to the next generation;
end while
Post-processing the results and visualization;
An important advantage of this algorithm is its simplicity. In fact, comparing with other population- or agent-based metaheuristic
Metaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
algorithms such as particle swarm optimization
Particle swarm optimization
In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
and harmony search
Harmony search
In computer science and operations research, harmony search is a phenomenon-mimicking algorithm inspired by the improvisation process of musicians...
, there is essentially only a single parameter
in CS (apart from the population size ). Therefore, it is very easy to implement.Random Walks and the Step Size
An important issue is the applications of Levy flights and random walks in the generic equation for generating new solutions
where
is drawn from a standard normal distribution with zero mean and unity standard deviation for random walks, or drawn from Levy distribution for Levy flights. Obviously, the random walks can also be linked with the similarity between a cuckoo's egg and the host's egg which can be tricky in implementation. Here the step size determines how far a random walker can go for a fixed number of iterations. The generation of Levy step size is often tricky, and a good algorithm is Mantegna's algorithm.If s is too large, then the new solution generated will be too far away from the old solution (or even jump out side of the bounds). Then, such a move is unlikely to be accepted. If s is too small, the change is too small to be significant, and consequently such search is not efficient. So a proper step size is important to maintain the search as efficient as possible.
As an example, for simple isotropic random walks, we know that the average distance
traveled in the d-dimension space is
where
is the effective diffusion coefficient. Here is the step size or distance traveled at each jump, and is the time taken for each jump. The above equation implies that
For a typical length scale L of a dimension of interest, the local search is typically limited in a region of
. For and t=100 to 1000, we have for d=1, and for d=10. Therefore, we can use s/L=0.001 to 0.01 for most problems. Though the exact derivation may require detailed analysis of the behaviour of Levy flights.Algorithm and convergence analysis will be fruitful, because there are many open problems related to metaheuristics
Implementation
The pseudo code was given in a sequential form, but Yang and Deb provides a vectorized implementation which is very efficient. In the real world, if a cuckoo's egg is very similar to a host's eggs, then this cuckoo's egg is less likely to be discovered, thus the fitness should be related to the difference in solutions. Therefore, it is a good idea to do a random walk in a biased way with some random step sizes. For Matlab implementation, this biased random walk can partly be achieved by- stepsize=rand*(nest(randperm(n),:)-nest(randperm(n),:));
- new_nest=nest+stepsize.*K;
where K=rand(size(nest))>pa and pa is the discovery rate. A standard CS matlab can be found here http://www.mathworks.com/matlabcentral/fileexchange/29809-cuckoo-search-cs-algorithm
An object-oriented software implementation of cuckoo search was provided by Bacanin On the other hand, a modified cuckoo search algorithm is also implemented for unconstrained optimization problems.
An open source implementation of Modified Cuckoo Search can be found here http://code.google.com/p/modified-cs/
Modified Cuckoo Search
A modification of the standard Cuckoo Search was made by Walton et al. with the aim to speed up convergence. The modification involves the additional step of information exchange between the top eggs. It was shown that Modified Cuckoo Search (MCS) outperforms the standard cuckoo search and other algorithms, in terms of convergence rates, when applied to a series of standard optimization benchmark objective functions.Subsequently, the modified cuckoo search has been applied to optimize unstructured mesh which reduces computational cost significantly. In addition, another interesting improvement to cuckoo search is the so-called quantum-inspired cuckoo search with convincing results
Multiobjective Cuckoo Search (MOCS)
A multiobjective cuckoo search (MOCS) method has been formulated to deal with multi-criteria optimization problems.This approach uses random weights to combine multiple objectives to a single objective. As the weights vary randomly, Pareto fronts can be found so the points can distributed diversely over the fronts.
Hybridization
Though cuckoo search is a swarm-intelligence-based algorithm, it can be still hybridized with otherswarm-based algorithms such as PSO. For example, a hybrid CS-PSO algorithm seems to remedy the defect of PSO.
Applications
The applications of Cuckoo Search into engineering optimization problems have shown its promising efficiency. For example, for both spring design and welded beam design problems, CS obtained better solutions than existing solutions in literature. A promising discrete cuckoo search algorithm is recently proposed to solve nurse scheduling problem. An efficient computation approach based on cuckoo search has been proposed for data fusion in wireless sensor networks.A new quantum-inspired cuckoo search was developed to solve Knapsack problems, which shows its effectiveness.
A conceptual comparison of the cuckoo search with PSO, DE and ABC suggest that CS and DE algorithms provide more robust results than PSO and ABC. An extensive detailed study of various structural optimization problems suggests that cuckoo search obtains better results than other algorithms. In addition, a new software testing approach has been developed based on cuckoo search. In addition, cuckoo search is particularly suitable for large scale problems, as shown in a recent study. Cuckoo search has been applied to train neural networks with improved performance. Furthermore, CS is successfully applied to train spiking neural models. Cuckoo search has also been used to optimize web service composition process and planning graphs.
Cuckoo search is a reliable approach for embedded system design and design optimization. An interesting application of cuckoo search is to solve boundary value problems.