What Are Genetic Algorithms (GAs)?

The genetic algorithm (GA) is basically a computer program which simulates evolution. Namely, a simulated population of chromosomes is randomly created and allowed to reproduce according to the laws of evolution with the hope that a very fit individual chromosome will eventually result. These chromosomes are actually (encrypted) candidate solutions to a problem, so when a good chromosome evolves, a good solution to a problem has evolved.

How Do GAs Work?

First you create a random population of chromosomes and test the fitness of each one with a special fitness function. For example, if you are trying to minimize the time required for a signal to travel through a network, each chromosome would represent a network configuration and the fitness function would determine the fitness of that network configuration.

Although all the initial fitness values are probably very low (since the algorithm randomly created them), some are still higher than others. These chromosomes with higher fitness values are given a correspondingly higher probability to reproduce in the next generation. Thus for each generation in the evolution, a fitness function simulates natural selection by pushing the population in the direction of improved fitness (much like how natural selection nudges a biological species toward improved fitness with regards to its environment).

Reproduction in our GA is diploid (sexual), meaning that when two chromosomes are mated, pieces (genes) of each are combined in the offspring. Thus chromosomes recombine their parts at random (two point crossover) gene locations, occasionally producing a fitter chromosomes. This improvement to the gene pool is amplified by a corresponding increase in that fitter chromosome's probability to reproduce.

GA Class Libary

With our Object Pascal (Delphi) class library, you have many options, you can model your chromosomes in three different ways by subclassing one of the three main classes of GAs (each of which is a subclass of my main GA class):

1. Character strings
2. Floating point numbers
3. Sequences or lists (e.g., optimize network nodes)

You can choose among the following GA parameters:

1. chomosome size
2. population size
3. crossover probability
4. random selection probability
5. number of preliminary generations (to build better breeding stock before main GA run)
6. mutation probability
7. number of decimal points (for floating point number GAs)
8. gene space (constrain the possible values for genes)
9. crossover type (OnePoint, TwoPoint, Uniform, or Roulette)

Possible Applications Using This Class Libary

1. Get the fitness of a complex mathematical equation using TGAFloat (or TGAString where each character in the string is a digit in the solution)
2. Sequence (order) a string using TGASequenceList
   1. To optimize a network for minimal transmission time
   2. Genetic sequencing of proteins (to find minimal energy to fold a protein into a certain shape)
3. Compute the coeffients of the optimal polynomial to fit a given set of data points (curve fitting)
4. Find the maxima or minima to a complex equation

Download

The class library source code
A sample program using the class library. The sample program has examples for curve fitting, traveling salesman, maxima of an equation, and getting the maximum binary string problems.

Note: The class library is copyrighted © 2000-2002 by Jeff S Smith and SoftTech Design, Inc. It may be freely distributed for educational and non-profit use only.