Genetic Algorithms

What is a Genetic Algorithm?

A GA, and more generally an Evolutionary Algorithm (EA) mimics natural evolution processes in order to solve computational problems (ususally large, difficult and complex optimization problems). These algorithms evolve a population of potential solutions with help of stochastic operator.

Why and how to use a GA

For a given optimization problem (see an example):

	Identify the search space
	Design a coding scheme for the points of the search space: genetic representation
	Design a function to evaluate potential solutions: the fitness function. The only requirement for this function is to yield a positive value to the selection process (no continuity nor derivability required).
	The fitness function is maximized during the evolution process. Sucessive populations of solutions are built, that fit increasingly well.

How to mimic evolution

	Start from a set of potential solutions: i.e. a population of individuals
	Successively construct new populations, each one being generated from the previous one with help of stochastic operators: selection and genetic operators

Characteristics of the individuals

Genotype: encoding of the parameter(s) as a bit string (there exists other EA based on non binary encoding), also called chromosome. A particular bit of the string is called a gene and the possible values are called alleles (in our case "0" or "1")

	Phenotype: expression of the genotype in the problem context, i.e. a point of the search space.
	Fitness value: express the quality of the individual with respect to the problem to be solved

Selection

Some indivuals are chosen among the population in order to build the next generation. Individuals are randomly chosen according to their fitness value, the high-fitted individuals being often selected. This process can be seen as a succession of roulette-wheel drawings: each individual corresponding to an aera of size proportional to its fitness value.

Genetic operators

They are the exploration tools of GA. New individuals are created from the current population. The selection step is intended to choose fit individuals (parents) to be reproduced and the genetic operators create new offsprings from their genetic material. The most commom operators are the one point crossover and the bit-flip mutation :

One point crossover: mixes the genes of the two parents, using a randomly chosen point on the chromosome

Bit-flip mutation: produces a minor perturbation of the genotype. Each gene can be flipped with a small probability p_m

There exists numerous classical or problem specific operators, see for example for details.

A simple example

Consider the following problem: find the maximum of the function

f(x₁,x₂)= x₁*x₂ , with (x₁,x₂) in [0,1]*[0,1]

x₁ and x₂ are the parameters. If we decide to sample the intervalle [0,1] on 8 bits, then the encoding is a 16 bit string, and the fitness function is directly f(x₁,x₂). An individual has the following characteristics:

	genotype: 16 bit sting
	phenotype: the couple (x₁,x₂), x₁ being decoced from the 8 first bit and x₂ from the others.
	fitness value: f(x₁,x₂)

Basic bibliography:

L. Davis. Genetic Algorithms and Simulated Annealing. Pittman, London, 1987.

D. A. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, January 1989.

J. H. Holland. Adaptation in Natural and Artificial System. Ann Arbor, University of Michigan Press, 1975.

J. R. Koza. Genetic Programming. MIT Press, 1992.

Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, 1992.