CODEWITHSUNDEEP
optimizationartificial-intelligencegenetic-algorithm
user11406
user11406

Reputation: 1258

Optimizing a genetic algorithm?

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?

Upvotes: 6

Views: 1831

Answers (3)

Z. Zhang
Z. Zhang

Reputation: 757

This is a very broad question; I suggest to use the R galgo package for this purpose.

Upvotes: 0

John Newcombe
John Newcombe

Reputation: 384

One thing I have done is to limit the number of fitness calculations. For example, where the landscape is not noisy i.e. where a recalculation of fitness would result in the same answer every time, don't recalculate simply cache the answer.

Another approach is to use a memory operator. The operator maintains a 'memory' of solutions and ensures that the best solution in that memory is included in the GA population if it is better than the best in the population. The memory is kept up to date with good solutions during the GA run. This approach can reduce the number of fitness calculations required and increase the performance.

I have examples of some of this stuff here:

http://johnnewcombe.net/blog/gaf-part-8/ http://johnnewcombe.net/blog/gaf-part-3/

Upvotes: 1

manlio
manlio

Reputation: 18972

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).

Upvotes: 5

Related Questions