Mutation operator

Mutation

Given that the previous parts of the general algorithm have measured fitness, performed selection based on fitness and then emulated the mating process, it may be assumed that enough distribution of the chromosome gene patterns has taken place to fully investigate all possible solutions. This is not so. If we consider the spread of chromosome patterns that existed with the initial random population it is possible to see that the processes carried out so far have not actually introduced any new variation in patterns.

Natures use of mutation

Mutation occurs in nature. Although this occurs very infrequently many believe this is a main driving force for evolution. The result of mutation can often result in a weaker individual. Occasionally the result might be to produce a stronger one. In each case we may assume that mutation is doing something new by subtly changing some part of the chromosome. The assumption is also made that such changes occur spontaneously and with no reference or affect from other members of the population. In general mutation is something new that is happening.

If the change is beneficial to the general population then that individual will tend to survive and will pass the changed gene onto future generations. If the change causes a weakness then it is likely the individual (and any offspring) will die out.

Replicating mutation within a GA

Because of the way that GAs represent individuals this process is a very simple one and a typical mutation operator is easy to implement. A typical approach is to select a single bit in a chromosome and flip it. This means that if it is a 12 it now becomes a 02 and vice versa. As with crossover operators there are in fact may ways to approach this operation. The most important aspects are that it should occur rarely and that one individual should have its pattern adjusted very slightly. It is also important to remember that mutations should occur very infrequently otherwise they will have a disruptive effect on the fitness of the overall population.

Image of: Fig 4. A typical mutation method

Fig 4. A typical mutation method

Example

Figure 4 shows a typical approach. To perform mutation we iterate through the entire population. For each individual we first select a random value between 0 and 1 and compare this with the mutation probability fact Pm. Since mutation occurs very infrequently this is usually set very low (typically Pm = 0.001). If the random value is greater than Pm the individual is left alone. If the value is less than Pm (which is very rare) we perform a mutation operation on the individual.

In the example in Figure 4, we have selected two random values corresponding to the bit length of the chromosome. In this case 3 and 8 have been selected. We then simply take the bits from the chromosome and swap them. The result is that the fitness value of the example has been changed. In this case it has been made stronger, although it could just as easily have been made weaker. The net result of this occasional operation is that the chromosome patterns of the population are adjusted so that the potential exists for the full search space to be investigated.

Contact the EDC

For further details of the EDC's activities please get in touch with us through our contact page.

Commercial Research at Newcastle University

A full list of commercially available research facilities for Newcastle University can be found on the Services for Business web pages.