![]() |
|||
![]()
|
![]() |
![]() |
![]() |
2.4.2. Mutation Mutation is used to inject an element of diversity into the population of genotypes. A GA that uses mutation will randomly select a genotype, and, within that genotype, randomly select a gene to mutate. If the genotype is using binary encoding, then the selected gene is complemented. If real numbers are used, then a number is selected at random within the range used to replace the mutated gene. This operation is done probabilistically at a very low rate. Typical mutation rates are low, in the range of less than 6%. This element of randomness will hopefully create new genotypes that may prove to be of better fitness than what is currently in the population. A good strategy to follow is to keep the mutation rate low in the earlier trials. As the GA settles in a particular region and does not seem to progress, the mutation rate can be increased to perhaps enable the GA to jump out of the local minima. Mutation is not necessary for a GA; however, it may prove to be of value if the GA is trapped in a local maxima. Referring to Figure 3, one could inject mutation by taking one of the genotypes in the population, such as 11010, and mutate it to 11110. Now a new genotype is added to the population that may prove to be of better fitness. Be careful with increasing the mutation rate. Too high an increase will create genotypes that jump all around the fitness landscape and the GA will not converge.
Typically, binary encoding is used for genotype creation. An alternate method is to use Gray Codes, an encoding scheme that differs from binary encoding in that only one position is changed when enumerating. Some GAs use Gray Codes because only one position is switched when moving from one number to the next to lessen the effect of mutation. Table 2 illustrates the differences between the two encoding schemes. This is not always the case for binary encoding (e.g., moving from 1 to 2 entails changing two positions). The effects of mutation can be multiplied depending on which gene is complemented. For example, moving from decimal 3 (binary 011) to decimal 4 (binary 100) requires complementing every bit position. This can make it more difficult for mutation to help move a near optimal solution to the optimal solution. There is a trade-off, though. In Gray Codes, fewer mutations lead to much larger jumps. For example, changing the left-most bit in decimal 7 (Gray 100) results in decimal 0 (Gray 000). Some might see this as an advantage, since most mutations will cause small changes, and some mutations will induce larger changes or jumps to explore new regions. A GA's performance can be highly domain specific. Do not be afraid to try different combinations of the selection operators described here. Many times, experience will be the best guide for a successful implementation. 2.5. TERMINATIONGAs will continually evolve until some terminating condition is reached. Some typical terminating conditions include:
If using the delta terminating condition, a good strategy is to increase the mutation rate once the GA stops. Hopefully this will move some genotypes into previously unexplored regions of the problem space.
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |