http://cs.felk.cvut.cz/~xobitko/ga/
Genetic algorithms are inspired by Darwin's theory
of evolution. Solution to a problem solved by genetic
algorithms is evolved.
Algorithm is started with a set of solutions
(represented by chromosomes) called population.
Solutions from one population are taken and used to
form a new population. This is motivated by a hope, that
the new population will be better than the old one.
Solutions which are selected to form new solutions
(offspring) are selected according to their fitness - the
more suitable they are the more chances they have to
reproduce.
This is repeated until some condition (for example
number of populations or improvement of the best
solution) is satisfied.
Example
As you already know from the chapter about
search space, problem solving can be often
expressed as looking for extreme of a function.
This is exactly what the problem shown here is.
Some function is given and GA tries to find
minimum of the function.
Outline of the Basic Genetic Algorithm
1.[Start] Generate random population of n
chromosomes (suitable solutions for the problem)
2.[Fitness] Evaluate the fitness f(x) of each
chromosome x in the population
3.[New population] Create a new population by
repeating following steps until the new population is
complete
1.[Selection] Select two parent chromosomes from
a population according to their fitness (the better
fitness, the bigger chance to be selected)
Take the best solutions (elitism to new population)
without crossover or mutation.
Then weight the rest based proportional to fitness.
2.[Crossover] With a crossover probability cross
over the parents to form a new offspring
(children). If no crossover was performed,
offspring is an exact copy of parents.
3.[Mutation] With a mutation probability mutate
new offspring at each locus (position in
chromosome).
4.[Accepting] Place new offspring in a new
population
4.[Replace] Use new generated population for a
further run of algorithm
5.[Test] If the end condition is satisfied, stop, and
return the best solution in current population
6.[Loop] Go to step 2
Encoding of a Chromosome
The chromosome should in some way contain
information about solution which it represents. The most
used way of encoding is a binary string. The
chromosome then could look like this:
Chromosome 1
1101100100110110
Chromosome 2
1101111000011110
Each chromosome has one binary string. Each bit in
this string can represent some characteristic of the
solution. Or the whole string can represent a number -
this has been used in the basic GA applet.
Crossover
After we have decided what encoding we will use, we
can make a step to crossover. Crossover selects genes
from parent chromosomes and creates a new offspring.
The simplest way how to do this is to choose randomly
some crossover point and everything before this point
point copy from a first parent and then everything after
a crossover point copy from the second parent.
You can have a crossover probability.
Mutation
After a crossover is performed, mutation take place.
This is to prevent falling all solutions in population into a
local optimum of solved problem. Mutation changes
randomly the new offspring. For binary encoding we can
switch a few randomly chosen bits from 1 to 0 or from 0
to 1. Mutation can then be following:
Original offspring 1
1101111000011110
Original offspring 2
1101100100110110
Mutated offspring 1
1100111000011110
Mutated offspring 2
1101101100110110
You can have a mutation probability.
Example of Problem: Knapsack problem
The problem: There are things with given value
and size. The knapsack has given capacity. Select
to maximize the value of things in
knapsack, but do not extend knapsack capacity.
Encoding: Each bit says, if the corresponding
thing is in knapsack.
Example of Problem: Travelling salesman
problem (TSP)
The problem: There are cities and given
distances between them.Travelling salesman has
to visit all of them, but he does not have to travel very
much. Find a sequence of cities to minimize
travelled distance.
Encoding: Chromosome says order of cities, in
which salesman will visit them.