This talk is available at http://www.mcs.drexel.edu/~shartley/geneticAlgorithms.html. It has been brazenly excerpted (without permission) from Section 2.6 of a recent book, Concurrent Programming: The Java Programming Language, © 1998 Oxford University Press.

Biology

Genetic algorithms are used in search and optimization, such as finding the maximum of a function over some domain space.

• In contrast to deterministic methods like hill climbing or brute force complete enumeration, genetic algorithms use randomization.
• Points in the domain space of the search, usually real numbers over some range, are encoded as bit strings, called chromosomes.
• Each bit position in the string is called a gene.
• Chromosomes may also be composed over some other alphabet than {0,1}, such as integers or real numbers, particularly if the search domain is multidimensional.
• GAs are called ``blind'' because they have no knowledge of the problem.

An initial population of random bit strings is generated.

• The members of this initial population are each evaluated for their fitness or goodness in solving the problem.
• If the problem is to maximize a function f(x) over some range [a,b] of real numbers and if f(x) is nonnegative over the range, then f(x) can be used as the fitness of the bit string encoding the value x.

From the initial population of chromosomes, a new population is generated using three genetic operators: reproduction, crossover, and mutation.

• These are modeled on their biological counterparts.
• With probabilities proportional to their fitness, members of the population are selected for the new population.
• Pairs of chromosomes in the new population are chosen at random to exchange genetic material, their bits, in a mating operation called crossover. This produces two new chromosomes that replace the parents.
• Randomly chosen bits in the offspring are flipped, called mutation.

The new population generated with these operators replaces the old population.

• The algorithm has performed one generation and then repeats for some specified number of additional generations.
• The population evolves, containing more and more highly fit chromosomes.
• When the convergence criterion is reached, such as no significant further increase in the average fitness of the population, the best chromosome produced is decoded into the search space point it represents.

Genetic algorithms work in many situations because of some hand waving called The Schema Theorem.

• ``Short, low-order, above-average fitness schemata receive exponentially increasing trials in subsequent generations.''

Example

To illustrate the manipulation of chromosomes by the genetic operators reproduction, crossover, and mutation, we will look at some sample program output for a very simple problem.

• Maximize the number of ones in a bit chromosome of length 10.
• The population consists of four chromosomes.
• One-point crossover is applied with a probability of 0.7. The crossover genetic operator exchanges genes between two chromosomes.
  • Two other versions are uniform and n-point.
• Each gene mutates with a probability of 0.1.
• The population is printed every generation.
• The genetic algorithm runs for three generations.

We first see the randomly generated initial population, in which the best fitness is 5.

The GA parameters are:
  populationSize      = 4         numXoverPoints      = 1
  crossoverRate       = 0.7       mutationRate        = 0.1
  doElitism           = false     printPerGens        = 1
  maxGenerations      = 3         Debug.flag          = true
  logFileName         = bit.out
BitCountChromosome: chromosome length is 10
GA: chromosome length = 10
GA: mainLoop
Known solution fitness is 10.0
p0: 0000110100 this chromosome has 3 bits set fitness= 3.0
p1: 1100010110 this chromosome has 5 bits set fitness= 5.0
p2: 1111001000 this chromosome has 5 bits set fitness= 5.0
p3: 0101011001 this chromosome has 5 bits set fitness= 5.0
currentBest (generation=0):
   1100010110 this chromosome has 5 bits set fitness= 5.0
Initial population:
   generation=0 best value=5.0 avg=4.5 stddev=1.0

A proportional selection algorithm called the roulette wheel method is used for reproduction.

• The cumulative fitness values of the chromosomes are computed.
• Then four random numbers between 0 and 1 are generated to select the new population members.
• The cumulative fitness values that bracket each random number determine which chromosome gets selected.
• It is possible for a chromosome to be selected multiple times.

  mem=0, cfitness=0.16666666666666666
  mem=1, cfitness=0.4444444444444444
  mem=2, cfitness=0.7222222222222222
  mem=3, cfitness=1.0
  p=0.07431843256287485, selected 0
  p=0.25792751503513034, selected 1
  p=0.6502614780006086, selected 2
  p=0.3749322338318496, selected 1
  p0: 0000110100 this chromosome has 3 bits set fitness= 3.0
  p1: 1100010110 this chromosome has 5 bits set fitness= 5.0
  p2: 1111001000 this chromosome has 5 bits set fitness= 5.0
  p3: 1100010110 this chromosome has 5 bits set fitness= 5.0
  

Now that we have the new population, it is time to apply crossover and then mutation.

• For each chromosome, a random number between 0 and 1 is generated.
• If the random number is less than the crossover probability input parameter, the chromosome is picked for crossover.
• Each time two chromosomes have been picked, one-point crossover is applied and the two resulting chromosomes replace the original ones in the new population.
• Only one crossover occurs in the first generation: chromosomes 2 and 3 exchange their genes to the left of bit position 3.

  111 | 1001000	are replaced by	110 | 1001000
  110 | 0010110		111 | 0010110

• After the one crossover, the new population is listed.

  crossing 2 and 3
  OnePointCrossover: just crossed at 3
  p0: 0000110100 this chromosome has 3 bits set fitness= 3.0
  p1: 1100010110 this chromosome has 5 bits set fitness= 5.0
  p2: 1101001000 this chromosome has 4 bits set fitness= 4.0
  p3: 1110010110 this chromosome has 6 bits set fitness= 6.0
  

Each chromosome is now given the chance to mutate by generating a random number between 0 and 1 for each of its genes.

• If the random number is less than the mutation probability input parameter, the value of the gene is changed from 0 to 1 or 1 to 0.

  mutation, i=0, gene=3: 0001110100
     this chromosome has 4 bits set fitness= 4.0
  mutation, i=0, gene=6: 0001111100
     this chromosome has 5 bits set fitness= 5.0
  mutation, i=1, gene=9: 1100010111
     this chromosome has 6 bits set fitness= 6.0
  mutation, i=2, gene=5: 1101011000
     this chromosome has 5 bits set fitness= 5.0
  mutation, i=2, gene=7: 1101011100
     this chromosome has 6 bits set fitness= 6.0
  mutation, i=3, gene=3: 1111010110
     this chromosome has 7 bits set fitness= 7.0
  mutation, i=3, gene=6: 1111011110
     this chromosome has 8 bits set fitness= 8.0
  

• After the seven gene mutations, the new population is listed.

  Report: generation=1 best value=8.0 avg=6.25 stddev=1.258...
  most fit (previous generation=1):
     1111011110 this chromosome has 8 bits set fitness= 8.0
  number of crossovers and mutations: 1 and 7
  p0: 0001111100 this chromosome has 5 bits set fitness= 5.0
  p1: 1100010111 this chromosome has 6 bits set fitness= 6.0
  p2: 1101011100 this chromosome has 6 bits set fitness= 6.0
  p3: 1111011110 this chromosome has 8 bits set fitness= 8.0
  

This completes the first generation.

• Notice that both the average fitness of the population and the best fitness in the population have increased.

After two more generations, the population is again listed.

• The average fitness has increased, but the most fit chromosome generated so far has disappeared from the population.
• The elitism option can be used to retain the best chromosome generated so far from generation to generation.

  Report: generation=3 best value=7.0 avg=6.75 stddev=0.5
  most fit (previous generation=1):
     1111011110 this chromosome has 8 bits set fitness= 8.0
  number of crossovers and mutations: 3 and 12
  p0: 1111001100 this chromosome has 6 bits set fitness= 6.0
  p1: 1111001110 this chromosome has 7 bits set fitness= 7.0
  p2: 1101011110 this chromosome has 7 bits set fitness= 7.0
  p3: 1111001110 this chromosome has 7 bits set fitness= 7.0
  

Click here for the output of one run of the program on a more difficult version of this problem: 100 bits in each chromosome. The fitness is the square of the percentage of bits set to give the GA better guidance.

Applications

Genetic algorithms have been very successful at solving many types of problems.

• Maximizing discontinuous, multimodal, multidimensional functions.
• They have also been used on discrete problems, including the traveling salesperson, bin packing, and job-shop scheduling.

Here are two example problems, one discrete and one continuous, that are more realistic.

1. For an arbitrary expression in n Boolean variables, find an assignment of true and false values to the Boolean variables in the expression that make the expression true, if such an assignment exists.
   • This is called the Boolean satisfiability problem (SAT).
   • Each assignment of true and false values to the variables can be encoded in a bit string of length n, 0 for false and 1 for true.
   • The fitness of such a chromosome is how ``close'' to being true the assignment makes the Boolean expression, such as how many clauses in the expression are individually made true by the assignment.
   • Some (in Postscript) SATs are very hard for GAs.
2. Maximize the function
   f(x₁, x₂, x₃) = 21.5 + x₁ sin (4 pi x₁) + x₂ sin (20 pi x₂) + x₃
   for x₁ in [-3.0,12.1], x₂ in [4.1,5.8], and x₃ in [0.0,1.0].
   • This function is highly multimodal.
   • A chromosome can be encoded in three real numbers, one for each of x₁, x₂, and x₃, over their respective ranges.
   • The fitness of a chromosome is the value of f(x₁,x₂,x₃) for the x₁, x₂, and x₃ encoded in the chromosome.
   • Click here for the output of one run of the program on this problem.

Difficulties

Hitchhiking.

• This may cause a GA to perform poorly.
• Once a schema attains high fitness in a population, then the members of the population containing the schema will proliferate.
• Bit values in positions not in the schema will hitchhike along with the schema as it propagates and will delay the discovery of high-fitness schemas with different values in those other bit positions.
• For example, consider these 8 schemas.

11111111........................................................
........11111111................................................
................11111111........................................
........................11111111................................
................................11111111........................
........................................11111111................
................................................11111111........
........................................................11111111

• Define a fitness function f(x) where x is a 64-bit string to be 8 times the number of these schemas it contains.
• So f(all 64 bits 1) = 64, f(all 64 bits 0) = 0.
• A GA performs poorly relative to hill-climbing on this because of hitchhiking.
• Click here for the output of one run of the program on this problem.

Deception.

• A problem is called deceptive if the average fitness of schemata not in the global optimum is greater than the average fitness of those that are.
• For example, chromosome length = 3, f(x) = fitness of x
  f(111) = 1.0
  f(011) = f(101) = f(110) = 0.05
  f(001) = f(010) = f(100) = 0.95
  f(000) = 0.20
  f(*0*) = f(**0) = f(0**) = (.2+.95+.95+.05)/4 = .5375
  f(1**) = f(*1*) = f(**1) = (1+.05+.05+.95)/4 = .5125
  f(00*) = f(*0*) = f(*00) = (.2+.95)/2 = .575
  f(11*) = f(1*1) = f(*11) = (1+.05)/2 = .525
  

Java Applet

A very nice Java applet: http://www.taygete.demon.co.uk/java/ga/index.html.

Java Application

An application (stand-alone program) written in Java using genetic algorithms to illustrate various features of object oriented programming: http://www.mcs.drexel.edu/~shartley/ConcProgJava/sequential.html#SIMGA

References and Related Material

A two-part overview of genetic algorithms with an academic, theoretical, and research orientation (in Postscript): Part 1, Part 2.

David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, 1996.

Genetic Algorithms FAQ.
Where to try to get the FAQ if the above does not work.
Other GA sites (this file is a year old so some links in it may not work).
Another GA Web site.
GA archive Web site.