Genetic Algorithm Performance Testing

October 25, 2009 General News 0 Comments

Having laid down the foundations of the XIAS genetic algorithm engine, I decided a performance test would be necessary to get the most out of the engine. Genetic algorithms, unlike most of the other methods that I've explored, are highly impacted by small quantitative tweaks to the engine, so performance can be gained by extensive testing of parameters.

Some preliminary tests were run tonight to determine the most effective mutation rate as well as the best mutation mode. I developed two mutation modes for the engine: Mode 1 allows an allele to mutate to any other allele that has been specified as part of the allele set of the engine. Mode 2 allows an allele to mutate only to an allele that already exists on the individual. In order to test these modes, the engine ran through 1000 genetic algorithm populations, keeping track of how many sub-loops it took to optimize the population each time. Each population was allowed a maximum of 100 loops to become perfectly optimized. Obviously, the idea is for the populations to optimize before those 100 loops are up.  The population optimization times are then averaged across the 1000 populations in order to achieve more accurate results.  Note that lower numbers on the graph are better (because the population optimized faster).

A couple of notes about the engine that stem from the graph:

  • Mutation mode 1, in general, optimizes faster than mutation mode 2
  • Mutation mode 1 is most efficient with a mutation rate of around 4.5% to 5.5%
  • Mutation mode 2 is most efficient with a mutation rate of around 6% to 7%
  • Mutation mode 1 provides more consistent optimization (notice that mode 2's curve changes directions several times, whereas mode 1's curve changes direction only once, at the minimum)
  • The optimization time of each mode can be roughly approximated by a cubic curve