A Short Survey of Genetic Algorithms (GAs)

© Lorenzo Casaccia, 2002

 


Prelude: Story of Evolutionary Computation and Birth of GAs

1960s
Evolution strategies (Rechenberg): optimize real-time parameters
Evolutionary Programming (Fogel, Owens, Walsh)
Genetic Algorithms (Holland): computational parallelism

It turns out that Genetic Algorithms are useful for:


John Holland's Genetic Algorithm

Move a population of chromosomes to a new one.
A chromosome is a string of "0" and "1", each of which is an allele.

Tools:
- "Natural-selection" (fitness function)
- Selection, crossover, mutation, inversion

Selection chooses two chromosomes that couple to reproduce. The highest the quality of the chromosomes, the higher the probability they are chosen.

Crossover exchanges two subparts of two chromosomes

Mutation randomnly changes the allele value in some locations

Inversion reverses the order of a contiguous section of the chromosome


Basic Principles

A chromosome is a candidate solution.
GAs assume that "high-quality" parents can produce high-quality "offspring"

Quality is measured against a fitness function.

  1. Start with a large, random-like, population of size N.
  2. Calculate the fitness of each element of the population
  3. Choose the evolving chromosomes (the probability of being chosen is an increasing function of fitness)
  4. Find the crossover point
  5. Find out whether there is mutation
  6. Place the offspring in the new population
  7. Go again to 3 until N offspring have been created (when this happens you have a new generation)
  8. Replace the old population with the new population.

Several generation must be yielded to converge to a solution (cfr. the example that attempts to find the best strategy for the Prisoner's Dilemma)
A solution is a chromosome of a particular generation that solves the problem

Advanced Principles

Coevolution
(Hillis, 1990)
Evolve the fitness function together with the population (host-parasite principle).
This is to avoid that the search gets stuck at local optima (basically it keeps making the search more challenging).

Adaptive Mutation
(Kitano, 1990)
The probability of mutation of a offspring depends on the number of mismatches (Hamming distance in case of "1" and "0" between the two parents).

Adaptive Encoding
How to encode the chromosomes? To find the best possible encoding is very similar to already know the solution!
Linkage: one wants to have functionally related loci in the chromosome to "stay together", i.e. not to get separated upon crossover
Variable Length: (Lindgren, 1992)
Messy GAs: (Goldberg et al, 1989-1992)

Variations on the Theme and Applications

Genetic programming
(Koza, 1992, 1994)
Automatically create a computer program (basically, an algorithm, block by block) that correctly solves a task.
The point is to choose a set of possible functions that the program can use and to start with a random population. Each member of the population has some of the functions connected at random.
The genetic algorithm evolves on two fronts: which functions are present and how they are connected.
Fitness is measured on a number of test cases for which the output must be known.

Cellular Automata
(Mitchell and others, 1992, 1993, 1994)
Genetic Algorithms could be used to better understand how cellular automata evolve.
Some hype on cellular automata has been raised in 2002 by Wolfram's book with a popular science approach.

Data Analysis
(Packard 1990)
Find patterns and "rules" within huge amount of datas.

Neural Networks
(Montana, Davis, 1989): Evolving the weights in a Neural Network
(Miller, Todd, Hedge, 1989): Evolving the architecture of a NN with Direct Encoding
(Kitano, 1990): Evolving the architecture of a NN with Grammatical Encoding

Study of the Baldwin Effect
Baldwin (1896): if learning increases the probability of survival then the organisms best able to learn will have the most offspring thus increasing the frequency of the genes responsible for learning (Baldwin effect or organic selection).
GAs have been used to study the Baldwin effect.
(Ackley and Littman, 1992)
Simulation of a "survival" scenario with many "agents" (characters).
The GA is used to simulate a large number of generations. Performed a study about what matters more: the "ability to learn" something or the "ability to do" something.

Study of Sexual Selection
(Kirkpatrick, 1982)
(Collins and Jefferson, 1992)
A GA is used to study how sexual selection interacts with natural selection (for example, if there is a trait which increases the fitness for the sexual selection but reduces the fitness for the natural selection, i.e. it reduces the chances of survival but makes the agent who has the trait more sexually appealing).
The study concludes that the power of sexual selection if stronger than the one of natural selection.

Study of Ecosystems
(Holland, 1975, 1994)
Echo

Incorporating various ideas from Genetic and Ecological Interactions
It's one the most recent frontiers.

Understanding the GAs

Traditional Mathematical Approach
Several examples. Very complicate.

Statistical-Mechanics
Study the GA at the macroscopic level ("mean fitness", "degree of symmetry", and so on)
Selection causes the standard deviation of the distribution of the population to be lowered (the population tends to have lower mean energy and to be more converged)

 

 

 

.