This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
Genetic Algorithms are based on the principles of survival of the fittest;
sometimes called natural selection. GA's, informally, work as follows.
Many potential solutions to the problem are created. Each solution is evaluated
to see how good it is. The best solutions are allowed to breed with each other.
This cycle continues in the hope that, as we are breeding with the good solutions,
we will gradually breed better and better solutions. And the evidence supports
that this is the case for a wide variety of problems.
As GA's have their origins in genetics the terms have carried through into the computer counterparts.
Each solution is normally called a chromosome (or an individual). Each chromosome
is made up of genes, which are the individual elements that represent the problem.
The collection of chromosomes is called a population.
In a problem such as the travelling salesman problem (TSP) the genes would be individual cites. A chromosome would be a complete tour and the population would be a number of complete tours.
As stated above, GA's work by breeding the best individuals from the current population. Let's consider this is a bit more detail.
It is common to have a population of one hundred. We'll work with that figure for now.
The initial population of one hundred chromosomes is normally created randomly.
Many problems are represented as bit strings, but this need not be the case
and other representations have been used.
The individuals that make up the population are then evaluated. That is, some
function considers each chromosome and assigns it a value depending on how good
an answer it is to the problem. The chromosomes are then allowed to breed. But
what does this mean?
Firstly we need to choose suitable "parents." Overall we want to
choose the fittest members of the population to breed but, as in life, everybody
must be given the chance to breed. Just because an individual has a low evaluation
does not mean he/she does not have something to contribute to society.
Therefore, in choosing parents, it is normally done in such a way that they are chosen in proportion to their evaluation rating. In doing this the fitter individuals are more likely to breed but the weaker members of the population also have the opportunity.
Having chosen our parents we now allow them to breed. This means (normally) two offspring are produced from the two parents. The children consist of genetic material taken from both parents. How the genetic material is distributed can be done in a number of ways, which we discuss below.
However, we do not breed all the time. There is a probability associated with each breeding pair as to whether they produce children or not. The probability of breeding is usually set to something like sixty percent but other figures are often experimented with.
Occasionally, as in life, a mutation occurs and GA's also mimic this.
Mutation happens with low probability and how the mutation occurs depends on the coding that is being used. If the problem is being represented by bit strings then mutation is fairly easy to implement. It can simply look at each bit in the chromosome and decide (with some low probability) if the bit should be replaced with a randomly produced bit.
The last point that should be made about GA's is that they have no knowledge
about the problem it is trying to solve. The only part of the GA that has some
domain knowledge is the evaluation function. This function is given a chromosome
and passes back an evaluation for the chromosome. It is this evaluation rating
that the breeding mechanism uses in deciding which chromosomes should breed.
The breeding mechanism has no knowledge about the problem. In its simplest form a GA is just manipulating bit strings
| Previous Page | Index Page | Next Page |
.
Last Updated : 25/01/2002