The inspiration: biological evolution

• What it requires
  • Organisms which give birth to other creatures, passing on their traits to their offspring, and which ultimately die
  • A way for traits to be passed on: an inherited genome, which, in interaction with the environment, results in a phenome, an actual body and set of traits.
  • A way the organisms' traits get evaluated, a fitness function: some aid in survival or reproduction, others are harmful, still others may be irrelevant
  • A way of generating new traits: mutation, a process by which some of the elements of the genome are randomly changed

A canonical evolutionary algorithm

• Environment: fitness, fitness function
• Encoding
  • Way of representing an "individual" (a problem state) in a genome
  • In genetic algorithms, often as a bit string (the genome)
  • Usually no separate phenome
• Procedures
  • Means by which individuals are replaced
    • In GAs, usually children of parents who mate (sometimes along with some fit survivors) replace the old generation all at once
  • Selection operator
    • Select individuals in the population for mating on the basis of the individuals' fitness
    • One common option in GAs: fitness-proportionate selection: the probability of selecting an individual is its relative fitness (implemented through "roulette-wheel sampling")
  • Usually mutation operator
    • Make random changes in the genome of an individual
    • In GA usually with a small probability, flip each bit in the genome.
  • Usually recombination operator
    • Combine the genomes of two parents to produce the genome of one or more offspring
    • In GAs usually crossover: select a position and exchange the substrings before and after that locus between two genomes to create two offspring
• A minimal set of parameters
  • n individuals in the population
  • l loci in each genome
  • Probability of crossover: p_c (often something like .7)
  • Probability of mutation: p_m (often something like .001)
• Algorithm for a simple GA
  • For each run
    • Start with a population of n randomly generated genomes
    • For each generation
    • Evaluate each of the individuals with the fitness function
    • Until n offspring have been created,
      • Using the selection operator, choose a pair of parents from the population
      • Produce two offspring Use the crossover operator with probability p_c. Otherwise produce copies of the parents
      • For each locus in each new offspring, apply the mutation operator with probability p_m
      • Place the resulting offspring in the new population
    • Replace the old population with the new

Trivial GA example

Evolution in a more realistic environment

• Agents have physical location
• The "fitness function" is real survival: how often the agent has a chance to reproduce
  • Finding and eating food
  • Avoiding predators and dangerous objects
  • Finding or attracting potential mates
• Replacement of individuals
  • New individuals added when they are born; old individuals removed when they die
  • Birth depends on when reproduction happens
  • Death depends on strength and/or age
• Selection (reproduction)
  • Asexual (copying, only mutation), sexual (mating, both crossover and mutation)
  • Mating depends on physical location (can lead to speciation)
  • Mating probability can also depend on
    • Some function of couple's strengths
    • Some function of couple's ages
    • Whether one or the other has recently mated
    • The genetic similarity of the couple (preventing incest)
    • An agent's decision to mate