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.1. INITIALIZATION

First, one must decide on the best way to encode possible solutions. Each encoding is known as a chromosome or genotype, which consists of a number of genes. Typically, a binary coding is used to create a genotype, with 1 indicating the presence of an gene and 0 indicating absence. These genes are then concatenated to form a chromosome of fixed length n, where n is the number of genes. Binary encoding is normally used; however, there are cases where a real number may be appropriate. For an example, refer to Table 1.

In Table 1, each car has certain genes. In the transmission column, 0 indicates a manual transmission, while 1 indicates an automatic transmission. In the drive column, 0 indicates 2-wheel drive, while 1 indicates 4-wheel drive. In the passenger column, 0 indicates two passengers, and 1 indicates four passengers. So, the Car 1 chromosome would be encoded as 010, while the Car 2 chromosome would be encoded as 101. Thus, a population of two has just been generated. GAs are not limited to binary encoding. Real numbers or string values can also be used, as well as variable-length chromosomes. However, GAs traditionally use fixed-length encodings. The population size should be relatively small while in testing phases (<500 genotypes). Once the system matures, the population should expand as much as possible, constrained by computer resources and time. The bigger the population, the better chance that the GA will find a close-to-optimal solution.


TABLE 1
Encoding Example
 
Car Transmission Drive Passengers
Car 1 0 1 0
Car 2 1 0 1

The initial population should be diverse, since these genotypes will be combined to create new solutions that did not previously exist in the population. One of the advantages of GAs is that they can investigate new solutions that humans don't have the time to think about or generate. The initial population can be generated randomly. A better starting point for GAs, though, would be to heuristically generate an initial population. The better the starting point, the more quickly GAs can converge or find a good solution. The remaining steps attempt to improve on the overall quality of the population.

2.2. EVALUATION

The purpose of this step is to evaluate the fitness of all the genotypes in the population. This step is typically the most difficult and computationally costly, since the fitness function must be applied to each member of the population. Depending on the domain, it is also sometimes difficult to create an effective fitness function. One alternative is to partially compute the fitness, and require the user to finish evaluating potentially promising genotypes. This might prove useful for those situations where the fitness function cannot be explicitly encoded, and requires human input for accurate evaluation.

Fitness functions should be able to evaluate both the valid and invalid genotypes in the population. An invalid genotype is a solution that is not feasible or applicable for the problem. The fitness function should evaluate these invalid genotypes since they may still contain good genetic material. If your fitness function automatically discards those genotypes, then that combination of genes will be lost.

Plotting all possible genotypes and their evaluated fitness produces a fitness landscape, an n-dimensional region that contains all possible solutions. The peaks and valleys of this landscape indicate the maxima or minima that the GA is searching for.

In the car example, an example fitness function could be the decimal equivalent of the chromosome, i.e., the genotype encoded as 101 would be evaluated to have a fitness of 5. This is a trivial fitness function, and an actual implementation of a GA would certainly use a more realistic function. The result of this step is a population ordered by fitness. The determination can then be made on which genotypes will survive to the next generation, simulating the evolutionary paradigm.

2.3. SELECTION

In this step, selected members in the population reproduce and exchange genetic material. Generally, the low fitness genotypes are culled and the best are rewarded. The genotypes with better fitness can expand to take up a larger percentage of the population, while those genotypes with poor fitness will decrease in numbers. There are a variety of selection operators that can be applied:

  1. Tournament selection. This is one of the more popular selection operators. In tournament selection, genotypes are randomly paired. The individual with the higher fitness "wins" and survives to the next generation. The lower fitness individual is discarded. Variations of tournament selection include grouping n-number of genotypes to compete for survival.
  2. Roulette wheel selection. In roulette wheel selection, genotypes can expand proportionately into the next generation according to their fitness. Those with a higher fitness take up a proportionately larger section of the next generation's population.
  3. Elite selection. In elite selection, the genotypes are rank ordered according to their fitness. The bottom half of the ranking is culled, and the remaining doubled, leaving the best for the next generation.

The selection operators are not limited to those explained, as there are many variations that can exist for particular domains.

2.4. SEARCH

Now that the population has adjusted itself to take advantage of the higher fitness genotypes, search operators are used to recombine or create new genotypes. The two most popular are crossover and mutation. Crossover exchanges genetic material between genotypes, and mutation injects random changes to selected genes.

2.4.1. Crossover

The crossover operation allows genotypes to exchange genes. Crossover is not essential for success, but it does allow genotypes to essentially exchange genetic information. Figure 2 illustrates a crossover operation of length 2 acting on two genotypes of length 5. In this case, the two genotypes exchange their tails (the last two positions, hence a crossover of 2), resulting in two new and different genotypes. Crossover will not always create a new genotype that was not present in the current population, but it does allow the exchange of genes.

The crossover operation is not limited to the one explained here. Different types of problem-specific crossover operations have been implemented.


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.