Understanding Mutation

Mutation in genetic algorithms

As with most of the other aspects of a genetic algorithm, mutation has a loose analogy to a real biological process. In biology, mutation is a random change in an individual’s DNA sequence that often manifests itself in physical traits. For example, blue eyes are a genetic mutation.

Mutation in genetic algorithms works in much the same way. It’s a random change to some or all of the genes in a chromosome. The purpose of mutation is to introduce genetic diversity into the population.

Recall that the algorithm we wrote to solve the One-Max problem in the lesson The Evaluation, Selection and Crossover Steps, struggled to find the best solution until we added mutation. When dealing with binary genotypes, premature convergence is more common because genes can only take on one of two values. The possibility of premature convergence increases when dealing with small population sizes relative to our search space.

Stimulating change

Mutation works by stimulating change — it prevents the algorithm from becoming complacent. Imagine rolling a ball down a small hill. Halfway down the hill, there’s a slight rise in elevation, but afterward, the hill declines again very sharply. Even by rolling the ball down the hill, there isn’t enough momentum to make it over the bump. What do we do then? We give it a little push.

The following image might help in visualizing this: