Extensions: Types of Mutation

In this paper, we do not concern ourselves with the multiplicity of crossover operations although we acknowledge that some of them are likely to achieve faster convergence in specific problem domains. We present below a list of mutation operators, which is extensive but not exhaustive.

• Random This is the mutation operator as used in a canonical EA. In a chromosome selected by some probabilistic scheme, a random gene is set to a new value randomly assigned inside that gene's domain limits. In essence, this scheme adds new information into the gene pool, although at random. It has a destructive effect on a generational EA because it moves a solution a random amount in a single dimension.
• N mutations Essentially the same as one, performed N times. Adds N times as much information but is N times as destructive to an individual chromosome. Moves the solution chromosome in a random N dimensional direction. Similar to an annealing process.
• Creep This operator, and those that follow are extensions to the random mutation operator. In creep mutation, we move the selected chromosome a known amount in a single dimension, either forward or backwards, subject to its domain constraints. It is more stable than random mutation although, depending on creep size, likely to force a gene to its domain limits.
• Directed Hill Climbing Mutation This mutation requires some memory of previous mutations. If the last mutation of this chromosome produced a better fitness function, them perform the same mutation until it becomes worse, then back off.
• Domain Limit Mutation This operator randomly pushes the gene to one or other of its domain limits. This is useful if the solution lies close to the limits of its domain.
• Non-uniform mutation This mutation operator is essentially creep mutation with a variable step size. It allows a space to be searched uniformly at first then more locally as generations proceed.

One important consideration when designing mutation operators is atomic versus complex mutation. A useful rule when designing mutations is that it is better to have mutations that do one action rather than mutations that do a combination of actions. The reason for this is that the complex mutations can usually be built from a combination of the atomic ones.