Cuckoo Search via Lévy Flights – Yang et al. 2010

Another nature inspired optimisation algorithm today – and this time it’s the turn of the cuckoos coupled with the flight pattern of fruit flies (which follow a Lévy flight) A Lévy flight is a random walk in which the step-lengths follow a heavy-tailed probability distribution.

A recent study by Reynolds and Frye shows that fruit flies or Drosophila melanogaster, explore their landscape using a series of straight flight paths punctuated by a sudden 90^o turn, leading to a Lévy-flight-style intermittent scale free search pattern. Studies on human behaviour such as the Ju/’hoansi hunter-gatherer foraging patterns also show the typical feature of Lévy flights. Even light can be related to Lévy flights. Subsequently, such behaviour has been applied to optimization and optimal search, and preliminary results show its promising capability.

Cuckoos lay their eggs in the nests of other birds (host birds).

Some host birds can engage direct conflict with the intruding cuckoos. If a host bird discovers the eggs are not their own, they 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 colour and pattern of the eggs of a few chosen host species. This reduces the probability of their eggs being abandoned and thus increases their reproductivity. In addition, the timing of egg-laying of some species is also amazing. Parasitic cuckoos often choose a nest where the host bird just laid its own eggs. In general, the cuckoo eggs hatch slightly earlier than their host eggs. Once the first cuckoo chick is hatched, the first instinct action it will take is to evict the host eggs by blindly propelling the eggs out of the nest, which increases the cuckoo chick’s share of food provided by its host bird. Studies also show that a cuckoo chick can also mimic the call of host chicks to gain access to more feeding opportunity.

Each egg in a nest will represent a solution. A cuckoo egg represents a candidate new solution, and the aim is to use the new and potentially better solutions to replace not-so-good solutions in the nests. To keep things simple we assume that each nest has only one egg. When generating a new solution for a cuckoo i, a Lévy flight is performed:

x_i^t+1 = x_i^t + α ⊕Lévy(λ)

…where α > 0 is the step size which should be related to the scales of the problem of interest. In most cases, we can use α = 1. The above equation is essentially the stochastic equation for random walk. In general, a random walk is a Markov chain whose next status/location only depends on the current location (the first term in the above equation) and the transition probability (the second term). The product⊕means entrywise multiplications. This entrywise product is similar to those used in PSO, but here the random walk via Lévy flight is more efficient in exploring the search space as its step length is much longer in the long run.

We start by generating an initial population of host nests, and then each iteration proceeds as follows:

• Get a cuckoo randomly by Lévy flights, evaluate its fitness function
• Choose a nest randomly, and if the new cuckoo performs better than the egg in the nest, replace the egg in the nest with the new cuckoo
• Choose some fraction p_a of the worst nests: abandon those nests and build new ones.

Cuckoo search compares favourably against genetic algorithms and PSO (as did bats and fireflies – I wish we could get some comparison of these against each other… ).

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 p_a. Furthermore, our simulations also indicate that the convergence rate is insensitive to the parameter p_a. 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 meta-heuristic algorithms.

It seems to me that the fruit fly Lévy flight behaviour is more significant in this solution than the cuckoo part. So we could easily have called this the Fruit Fly Algorithm too.