Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I was working on parallel implementation of Genetic Algorithm with MapReduce. I have found that in many papers authors are referencing OneMAX as problem they used to test scalability and convergence of their algorithm implementations.
I would like to know more about why this problem is good for testing, and if you could recommend any other exotic and nice fitness functions I could use in tests.
Kind Regards, ZeKoU
One-max is really only suitable for testing for obvious bugs in your implementation.
There are a few widely used sets of benchmark functions, but they're of rather dubious value in general as well. You don't mention what sort of domain you're planning to work on -- there are binary problems like Knapsack problems, real-valued problems (which may or may not be represented with binary encodings in a given GA), permutation problems like TSP, QAP, and some scheduling problems, etc.
Some of the more popular benchmarks have always been real-valued function optimization problems. Griewangk's function, Rastrigin's function, Ackley's function, Rosenbrock's function, and the De Jong F1-F5 functions have all been used pretty heavily in the literature (as well as others). There are also shifted and rotated versions of several of those problems that attempt to work around some of the more obvious biases and deficiencies such as the optimum of most of them being at the origin.
There have been a few attempts at producing good sets of benchmarks. There was a 2005 CEC workshop that proposed 25 or so real-valued problems. I think there was another workshop in 2010 that might have included a different set of problems, but I'm hazy on the details now.
I haven't been able to provide you with much in the way of concrete information about particular test functions, but hopefully there's enough here to get you started with Google.
You need to be clear in your mind about what you want the test problem for. If you're just trying to test the scalability of your implementation using MapReduce, then the test problem doesn't matter much. If you're trying to test the effectiveness of the genetic algorithm itself, then it doesn't really matter that you're using MapReduce, and the specific test problem matters a lot more, and you should pick a test problem or set of test problems that resembles the real-world problem that you actually want to use the GA to optimize.
As was already said, people use OneMax because it's easy to implement and understand. It's not an all-purpose, general test problem for GAs. (Deong did a very good job of listing many of the other commonly-used testbed/benchmark functions in his response. Just keep in mind that none of those are good for all purposes, and there is still no general purpose, generally accepted set of test functions for GAs. If you're going to use any of them, then it would be good to use as wide a variety as possible.)
In general, keep in mind that in any real-world problem, the computation cost of evaluating the fitness function dominates the cost of the core GA algorithm itself. So you can (and should) separate testing your parallel implementation, and the scalability/parallelization of the fitness function evaluations using MapReduce, from testing the GA implementation itself.
Hope that helps.
-Ted
