**A Short Survey of Genetic Algorithms (GAs)**

© Lorenzo Casaccia, 2002

- Prelude: Story of Evolutionary Computation and Birth of GAs
- John Holland's Basic GA
- Basic Principles
- Advanced Principles
- Variations on the Theme and Applications
- Understanding the GAs

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:

- Solving difficult problems
- Modeling the natural systems that inspired their design

Move a population of chromosomes to a new one.

A **chromosom**e 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

A chromosome is a *candidate* solution.

GAs assume that "high-quality" parents can produce high-quality "offspring"

**Quality** is measured against a fitness function.

- Start with a large, random-like, population of size
*N*. - Calculate the fitness of each element of the population
- Choose the evolving chromosomes (the probability of being chosen is an increasing function of fitness)
- Find the crossover point
- Find out whether there is mutation
- Place the offspring in the new population
- Go again to 3 until
*N*offspring have been created (when this happens you have a new generation) - 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

**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.

**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)

.