Death by parameters
In my previous blog post I wrote about the great flexibility and power of Genetic Algorithms. So you may have thought; why do I need help with my optimisation problems? One can just simply grab an off-the-shelf Genetic Algorithm and use it. However, as with everything, there are always two sides to every story and this time I’ll show you why optimizing with Genetic Algorithms is much harder than it seems.
The flexibility of Genetic Algorithms arises, in part, from a flexibility to choose a dizzying number of parameters. When writing your own code you potentially have to decide on things such as the number of competing optimal solutions, the number of times to improve them, the mutation and crossover probabilities, the percentage of the population to eliminate in each generation and many more.
With so many choices, choosing the parameters correctly can determine whether the algorithm bears fruit or withers and dies. This difficulty has lead to many papers on the best way to choose parameters. Unfortunately even if one is able to choose good parameters for one problem, this is no guarantee that the same parameters will work for the next problem.
So over the years researchers have searched for other powerful optimisation techniques which don’t suffer from such a parameter overload. From this research we now have a number of promising algorithms. In particular, in 2009 Xin-she Ying and Suash Deb came up with the ultimate of all parameter starved algorithms, the Cuckoo Search Algorithm. In this algorithm there is one parameter. Yes only one.
The Cuckoo Search Algorithm is inspired by the parasitic nature of some cuckoo species such as the European common cuckoo. These species lay their eggs in the nests of other host birds in an attempt to trick the host to raise their own nestlings. Sometimes this devious trick succeeds. When it doesn’t, the host bird either throws the egg over the side of the nest or simply abandons the nest altogether.
In the Cuckoo Search Algorithm the cuckoo’s ploy translates into an optimisation algorithm via four idealized rules which are repeated until the desired optimisation criteria are fulfilled. In the following algorithm each egg represents a solution and by a cuckoo laying an egg, we mean create a new random solution:
- Each cuckoo lays an egg in a random nest.
- Out of all laid eggs keep a number of the best eggs equal to the number of cuckoos.
- Abandon a fixed fraction of the worst eggs.
Find the parameter? The single, lonely parameter in the Cuckoo Search Algorithm is the fraction of the worst nests that are abandoned. This parameter affects how thorough the algorithm searches all possible solutions and so a lower value means the algorithm will find a local optimum faster (although maybe not a desired global optimum).
The avian-inspired algorithm has been used in numerous difficult problems to oust other optimisation methods out of their leadership position. For example, it has been used for spring and beam design problems , scheduling problems, the famous traveling salesman problem and even optimisation challenges in nanoelectronics! Like most other heuristic optimisation methods, the areas of application can be quite astounding.
So now that you’ve canceled the download of a promising Genetic Algorithm and started one of a new Cuckoo Search Algorithm, I thought I’d warn you again that there’s another side to this story too. Although the bird-based algorithm makes parameter choice simple, it may or may not be your best choice for a given optimisation problem. There are many heuristics for optimisation problems and choosing the right heuristic is probably much harder than choosing the right parameters for a given optimisation method. But you don’t have to worry about your precision nest eggs because luckily you’re on the website of a company competent enough to help you with this choice.