//
you're reading...
Algorithms & Heuristics

Cuckoo Search

I had earlier written on the Ant Colony Optimization and the Genetic Algorithm.

Another interesting bio inspired heuristic is the Cuckoo Search that has been developed by Xin-She Yang and Suash Deb in 2009. This technique adapts from the parasitic brood behaviour exhibited by the cuckoo bird. The cuckoo bird cannot complete its life cycle properly as it is not capable of raising its young. So the solution adopted by the cuckoo bird was to lay eggs in the nest of other birds. This can be accompanied by removing the eggs of the unwitting host. While certain host birds do detect the intrusion and abandon the nest or remove the alien eggs. This however interestingly is countered by certain cuckoos by employing mimicry and its eggs actually look like the eggs of the chosen hosts! This is very well explained in this blog post by Jerry A Coyne, author of the book “Why Evolution is True”. See how close and faithful is the copy. After all Charles Colton did mention imitation is the sincerest form of flattery.

This phenomenon has been exploited to solve certain problems. The basic steps in the Cuckoo Search heuristic are:

  1. Assume a objective function F(x) where x can take many values under its own constraints.
  2. Begin
    1. Generate initial population of host nests meaning list of some set of x.
    2. Choose a cuckoo that is going to lay an egg in other words a new x. If the new fitness value is more than the fitness exhibited by the host nest then the host eggs are abandoned and the new value x is put in.
    3. Repeat step b for a certain number of cuckoos.
    4. After a round of generation is over then lets us assume some of the hosts are clever enough to find the substitution with a probability they abandon the nest and make a new nest. This means the cuckoo’s eggs are thrown out put and new host egg is created.
    5. We are now left with the output of a new generation which in turn becomes the initial set for the next generation.
    6. Repeat steps 2.1 through 2.5 until some stopping criteria is reached.
  3. End

Of course the steps are simple. Sophistication and complexity can be introduced by making the new cuckoo generation follow Lévy Flights then a simple random walk. The cuckoos can be made to lay two eggs one each in two different host nests.

Applications

This heuristics has been used in nurse scheduling, engineering problems such as spring design optimisation and welded beam design. In software engineering it has been demonstrated in test case prioritization.

Advertisements

Discussion

3 thoughts on “Cuckoo Search

  1. More or a less a probability problem used for logistics

    Posted by Karthik Eswaran | March 10, 2012, 9:29 pm
  2. What is the real world problem that you can solve using this algorithm

    Posted by Udayan Banerjee | March 11, 2012, 8:05 am
    • Has proved effective in Engineering problems with non linear function with many instances of local minima/maxima, where hill climbing may not work as expected.

      Posted by eswarann | March 11, 2012, 11:28 am

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 66 other followers

%d bloggers like this: