Topic: Introduction to Genetic Algorithms

Based on Natural Selection

• The algorithm operates on a population of individuals
• Each individual is a potential solution to a given problem and is typically represented as a fixed-length binary string which equates to a chromosome in real organisms
• After an initial population is randomly generated, the algorithm evolves the population through three operators:
  1. selection which equates to survival of the fittest;
  2. crossover which represents mating between individuals;
  3. mutation which introduces random modifications.

• Key idea: give preference to better individuals, allowing them to pass on their genes to the next generation
• The goodness of each individual depends on its fitness
• Fitness may be determined by an objective function or by a subjective judgement

• Two individuals are chosen from the population using the selection operator
• A crossover site along the bit strings is randomly chosen
• The values of the two strings are exchanged up to this point
  If S1=000000 and S2=111111 and the crossover point is 2
  then S1'=110000 and S2'=001111
• The two new offspring created from this mating are put into the next generation of the population
• By recombining portions of good individuals, this process is likely create even better individuals

• With some low probability, a portion of the new individuals will have some of their bits flipped
• Its purpose is to maintain diversity within the population and inhibit premature convergence

• Using selection alone will tend to fill the population with copies of the best individual from the initial population
• Using selection and crossover will tend to cause the algorithm to converge on a good but sub-optimal solution
• Using mutation alone induces a random walk through the search space
• Using selection and mutation creates a parallel, noise-tolerant, hill climbing algorithm

1. randomly initialize population(t)
2. determine fitness of population(t)
3. repeat
   1. select parents from population(t)
   2. perform crossover on parents creating population(t+1)
   3. perform mutation on population(t+1)
   4. determine fitness of population(t+1)
4. until best individual is good enough

• Computer-aided design
• Criminal justice
• Financial prediction
• Scheduling
• Oil exploration
• Robot control
• Combined with neural networks