Mutation Rate Modulation for Faster GAs

A Quick Introduction to GAs

The genetic algorithm (GA) is a powerful search algorithm that balances exploration against inductive search.

Genetic algorithms operate by modifying a population of binary strings and testing them against a specific fitness function. "Functions" which modify the strings are called operators. In a simple GA, three operators are used:

• reproduction,
• crossover, and
• mutation.

The GA operates as follows:

1. A random population of binary strings is created.
2. These strings are applied to a fitness function. Each string is thereby assigned a fitness value. The fitness function can be thought of as being a mapping between every possible binary string and its fitness value.
3. Each string is then assigned a probability of reproduction based on its fitness relative to the aggregate fitness of the entire string population. The next generation of strings is then created by reproducing strings that are picked with these assigned probabilities.
4. Strings are then paired randomly, and "crossover" occurs with some fixed probability. If it occurs for that particular pair of strings, the strings are sliced at a random location and their tails are swapped. The new strings are re-inserted into the population.
5. Each bit of every string in each pair is mutated (XOR'ed with 1) with some probability. Typically this probability is fixed, but here we will examine the possibility of modulating this mutation rate.
6. The strong version of Arifovic's [insert bibliographical reference here] election operator is now applied. The election operator examines each string pair to determine whether each new (crossed over and mutated) string's fitness is at least as good as each of its parents. If it is, then it is inserted into the population. If not, then the new string is discarded.
   

The election operator is not an element of all GAs, but it is used here for reasons that will be explained later.