Recently, I was talking to a rather intelligent chap who was quizzing me on some research I did many years ago. I gave him a simplistic explanation of discrete optimization and genetic algorithms and he fired back a very good question... how do you measure how good a genetic optimization algorithm is? Clearly, you test it on something that you know the global optimum of and see if the algorithm can find it. But there is more to it than that. We also need to use a problem that makes it hard for the algo to get to the "global optima". There are 2 such functions that come to mind that are often used precisely for this purpose...
The Rastrigin Function
where x can range from -5.12 to +5.12.
But it's best visualised as a plot:
As you can see, the external variable A controls the amplitude of the peaks. It should also be clear that this is a non-linear, multimodal function that is not convex. In other words, this function has been custom made to contain many "local minima". A local minimum is a value that is the smallest value in a given area but is not the global minimum. These local minima are the blue-shaded "valleys" in the plot. The global minimum is obviously the smallest value of the function over the entire area. In the case of the Rastrigin function the global minimum is 0 at (0,0) in the two-dimension version of this function.
At any local minimum other than (0,0) the value of Rastrigin's function is greater than 0. In fact, the farther the local minimum is from the origin the larger the value of the function is at that point. The presence of all of these local minima is precisely why this function is often used to test genetic algorithms, because the numerous local minima make it difficult for standard, gradient-based methods to find the global minimum.
You can read more about it at Wikipedia but again it's best illustrated with a plot:
From Wikipedia, "The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial, however to converge to the global minimum is difficult."
There are others, but these 2 functions are a damn good test for any genetic / evolutionary algo you need to shake out.
14 Dec 2010 Damien Wintour