0
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi! I am working on real-valued optimizations with binary encoding. I use tournament selection with replacement. I have run OneMAX, and the more time (or iterations) I give to it, more ones I get in chromosome. I will try with some of functions you have proposed. Any specific ones you would recommend for this kind of problem? Thanks for your input. $\endgroup$ – azec-pdx Aug 25 '11 at 11:30
  • $\begingroup$ It depends on what you're trying to do. If you have a real problem you're trying to solve, benchmarks like this won't be as useful as just testing it on examples of your problem. If you're trying to build a better search algorithm to publish it, then all of them. $\endgroup$ – deong Aug 27 '11 at 2:11
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.