Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


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.


FIGURE 2 Crossover operation.


FIGURE 3 Mutation.

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. TERMINATION

GAs will continually evolve until some terminating condition is reached. Some typical terminating conditions include:

  • Temporal. Run the GA for a certain amount of time.
  • Objective. Run the GA until some fitness value is reached.
  • Delta. Run the GA until no difference is detected between the best evaluated fitness of each generation.

TABLE 2
Gray Codes
 
Decimal Binary code Gray code
 
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100

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.


Previous Table of Contents Next

footer nav
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.