Limitations of Existing Mutation Rate Heuristics and How a Rank GA Overcomes Them

Using a set of different search metrics and a set of model landscapes we theoretically and empirically study how optimal mutation rates for the simple genetic algorithm (SGA) depend not only on the fitness landscape, but also on population size and population state. We discuss the limitations of current mutation rate heuristic, showing that any fixed mutation rate can be expected to be suboptimal in terms of balancing exploration and exploitation. We then develop a mutation rate heuristic that offers a better balance by assigning different mutation rates to different subpopulations. When the mutation rate is assigned through a ranking of the population, according to fitness for example, we call the resulting algorithm a Rank GA. We show how this Rank GA overcomes the limitations of other heuristics on a set of model problems showing under what circumstances it might be expected to outperform a SGA with any choice of mutation rate.