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:
- Assume a objective function F(x) where x can take many values under its own constraints.
- Generate initial population of host nests meaning list of some set of x.
- 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.
- Repeat step b for a certain number of cuckoos.
- 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.
- We are now left with the output of a new generation which in turn becomes the initial set for the next generation.
- Repeat steps 2.1 through 2.5 until some stopping criteria is reached.
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.
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.