What is the most computationally efficient genetic algorithm?

Question

In researching genetic algorithms, it seems that there are various methods of selection and other operator methods that can significantly change the performance. For example, this picture contains some of the methods that could be used:

Presumably, you can mix & match these operators to optimize whatever problem you're trying to solve.

What most people care about is how many iterations it takes to get to the target. This is understandable, but I've seen things that would be inefficient in real systems such as:

• using sort on the current population $\mathcal{O}(n \log n)$ and picking the first n members for the mating pool

• appending to a constantly resizing slice to create a mating pool instead of rewriting on the current array

What I am looking for is, how can I arrive at the target using the least amount of computation and memory possible. The number of iterations and the time taken to get there is still a secondary priority.

It's possible that it may be the process of picking the right operators, but what I am also considering is how parallelizable the implementation could be as well.

Answer 1

First of all, for a lot of realistic problems, the fitness function evaluation is usually orders of magnitude greater in complexity than the rest of the genetic algorithm. This is not always true, but often is true (e.g. imagine trying to optimise a simulation where you need to execute the simulation completely to obtain the fitness). So optimising the GA itself might only be helpful when the fitness function is lightweight (e.g. it's a mathematical function as used in some competitions).

While your diagram shows a lot of operators, it doesn't show variations of the GA itself. Here are two:

• generational: selects a new population at each iteration after performing mutation and crossover on the existing population to generate offspring (which are usually more in number than the population size)
• steady state: maintains a single population and replaces only individuals during each iteration with their offspring according to selection/replacement rules, so uses less memory than a traditional GA

If you really wanted to maximise efficiency in the GA, a steady state approach would probably work best combined with tournament selection, as tournament selection does not require any sorting. The mutation/crossover operators you list are likely to all be quite efficient, but simpler methods are likely to to be the most efficient (e.g. bit flip mutation+1 point crossover). For a realistic problem, however, problem-specific operators usually work best.