Q1.1: What's a Genetic Algorithm (GA)?

The GENETIC ALGORITHM is a model of machine learning which derives its behavior from a metaphor of some of the mechanisms of EVOLUTION in nature. This is done by the creation within a machine of a POPULATION of INDIVIDUALs represented by CHROMOSOMEs, in essence a set of character strings that are analogous to the base-4 chromosomes that we see in our own DNA. The individuals in the population then go through a process of simulated "evolution".

Genetic algorithms are used for a number of different application areas. An example of this would be multidimensional OPTIMIZATION problems in which the character string of the chromosome can be used to encode the values for the different parameters being optimized.

In practice, therefore, we can implement this genetic model of computation by having arrays of bits or characters to represent the chromosomes. Simple bit manipulation operations allow the implementation of CROSSOVER, MUTATION and other operations. Although a substantial amount of research has been performed on variable- length strings and other structures, the majority of work with genetic algorithms is focussed on fixed-length character strings. We should focus on both this aspect of fixed-lengthness and the need to encode the representation of the solution being sought as a character string, since these are crucial aspects that distinguish GENETIC PROGRAMMING, which does not have a fixed length representation and there is typically no encoding of the problem.

When the genetic algorithm is implemented it is usually done in a manner that involves the following cycle: Evaluate the FITNESS of all of the individuals in the population. Create a new population by performing operations such as crossover, fitness-proportionate REPRODUCTION and mutation on the individuals whose fitness has just been measured. Discard the old population and iterate using the new population.

One iteration of this loop is referred to as a GENERATION. There is no theoretical reason for this as an implementation model. Indeed, we do not see this punctuated behavior in populations in nature as a whole, but it is a convenient implementation model.

The first generation (generation 0) of this process operates on a population of randomly generated individuals. From there on, the genetic operations, in concert with the fitness measure, operate to improve the population.

PSEUDO CODE


Algorithm GA is

// start with an initial time t := 0;

// initialize a usually random population of individuals initpopulation P (t);

// evaluate fitness of all initial individuals of population evaluate P (t);

// test for termination criterion (time, fitness, etc.) while not done do

// increase the time counter t := t + 1;

// select a sub-population for offspring production P' := selectparents P (t);

// recombine the "genes" of selected parents recombine P' (t);

// perturb the mated population stochastically mutate P' (t);

// evaluate its new fitness evaluate P' (t);

// select the survivors from actual fitness P := survive P,P' (t); od end GA.


[Previous question] [Next question] [HHGTEC main contents page]

Mistakes in this page?
Hitch Hiker's Guide to Evolutionary Computation, Issue 9.1, released 12 April 2001
Copyright © 1993-2001 by J. Heitkötter and D. Beasley, all rights reserved.