A Short Survey of Genetic Algorithms (GAs)
© Lorenzo Casaccia, 2002
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:
Move a population of chromosomes to a new one.
A chromosome is a string of "0" and "1", each of which is an allele.
- "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
A chromosome is a candidate solution.
GAs assume that "high-quality" parents can produce high-quality "offspring"
Quality is measured against a fitness function.
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
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).
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).
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
(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.
(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.
Find patterns and "rules" within huge amount of datas.
(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
(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)
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.
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)