Optimizing a genetic algorithm?

Question

I've been playing with parallel processing of genetic algorithms to improve performance but I was wondering what some other commonly used techniques are to optimize a genetic algorithm?

Answer 1

Since fitness values are frequently recalculated (the diversity of the population decreases as the algorithm runs), a good strategy to improve the performance of a GA is to reduce the time needed to calculate the fitness.

Details depend on implementation, but previously calculated fitness values can often be efficiently saved with a hash table. This kind of optimization can drop computation time significantly (e.g. "IMPROVING GENETIC ALGORITHMS PERFORMANCE BY HASHING FITNESS VALUES" - RICHARD J. POVINELLI, XIN FENG reports that the application of hashing to a GA can improve performance by over 50% for complex real-world problems).

A key point is collision management: you can simply overwrite the existing element of the hash table or adopt some sort of scheme (e.g. a linear probe).

In the latter case, as collisions mount, the efficiency of the hash table degrades to that of a linear search. When the cumulative number of collisions exceeds the size of the hash table, a rehash should be performed: you have to create a larger hash table and copy the elements from the smaller hash table to the larger one.

The copy step could be omitted: the diversity decreases as the GA runs, so many of the eliminated elements will not be used and the most frequently used chromosome values will be quickly recalculated (the hash table will fill up again with the most used key element values).