Evolution and Genetic Algorithms

Evolution

What's needed for evolutionary computation (abstract or real) to work
- "Creatures" which
  1. Give birth to other creatures, passing on their traits to them
  2. Die
- A way for traits to be passed on: an inherited genotype, in interaction with the environment, results in a phenotype
- A way of evaluating the creatures' traits: some aid in survival or reproduction, others don't ("survival of the fittest")
- A way of generating new traits: mutation
How it works
- Each creature is born with some combination of traits; it may not be possible to simply figure out what combination works best for the environment of the creatures.
- Creatures live their lives. Some survive long enough to reproduce and have offspring.
- If a particular trait or combination of traits helps creatures reproduce or live longer, creatures with that trait (those traits) will tend to have more offspring.
- Creatures pass on (at least some of) their traits to their offspring. In sexual reproduction, they pass on a combination of the parents' traits.
- The percentage of creatures with the good traits should increase on each generation.
- There is a small probability that a new creature will end up with some random traits which it did not inherit from its parent(s). In this way new traits or combinations of traits can be tried out in the world.

Genetic Algorithms

A parameter-oriented search technique based on evolution
- Searches from a population of states in parallel
- Uses fitness information only, no prior information about the domain
- Uses probabilistic transition rules to get from one state to the next
Used for
- General-purpose parameter-oriented search
- Modeling evolution
- Designing a suitable initial architecture for cognition (say, a neural network)
The basics
- Genetic encoding: How are traits represented in the genome?
  - Genome is usually a binary string. Features which are not binary may be encoded in sets of positions.
- Development: How is a genome transformed into a phenome?
  - The genome may be the phenome (the fitness function is applied directly to it).
  - The genome may be translated into the phenome in a deterministic way.
  - (Rarely) the genome may turn into the phenome through interaction with the environment.
- Fitness function: How are individuals evaluated?
  - Usually a function assigns a numerical score to each phenome.
  - Alternately individuals may survive some length of time, enabling reproduction.
- Selection procedure: How are individuals selected for reproduction (crossover) on the basis of their fitness?
  - Selection is usually indirect: individuals' chance of reproducing depends directly on their fitness.
    - One possible: weighted roulette wheel. Parents are selected probabilistically on the basis of their proportion of the total fitness of the population.
  - Direct selection: more successful individuals are able to "find" mates.
- Mutation: With what frequency are genes randomly altered?

Last updated: 16 April 1996
URL: http://www.indiana.edu/~gasser/Q351/ga1.html
Comments: gasser@salsa.indiana.edu
Copyright 1996, The Trustees of Indiana University