|
The
Genetic Algorithm:
Introduction and Case Study
by Richard Jones
(Up to General
AI)
|
|
A genetic algorithm tries to mimic the process of evolution to evolve a solution to a problem. An initial population is devised and this is manipulated using evolution operators. These include mating and mutation. After several generators the population as a whole should be fitter and nearer a solution to the problem. Genetic algorithms have been used successfully on many optimisation problems most notably the "Travelling Salesman Problem".
The field of genetic algorithms is vast. There is much debate about different methods that can be use and much argument as to there success.
The genetic algorithm available to download has a simple form and uses specific operators. There are many more operators than were used here. However there use can be problem dependent and my genetic algorithm solves the problem more than adequately.
Firstly there is a population of 100 chromosomes. Each of these chromosomes is a possible solution to the problem. The problem in this case is to get each value with the chromosome to add up to a user specified value. There are five alleles within each chromosome each representing one number. Hence each chromosome has five numbers associated with it. For this explanation we shall assume the desired number is 15.
Each of the chromosomes is given a fitness value according to how close its solution is to 15. For example if one chromosome's answer is 5 and another is 14 then the second will be considered "fitter" because it is nearer the final solution.
After each chromosome has been assigned a fitness value then chromosomes are selected to reproduce to form a new population; the next generation. The choice of chromosome is decided upon by its fitness value. The roulette wheel method is used here to decided which chromosome is chosen. This method dictates that if a one chromosome is twice as fit as another then it is twice as likely to be chosen and so on.
Reproduction is achieved by obtaining two parents. Sections of each chromosome are then taken to produce the new child. The chromosomes in this example consists of five alleles each with a number associated with it. The child's first two alleles might be obtained from the first parent and the remaining three might be obtained from the second parent. Uniform crossover was used to decide where the boundary was to stop reading from one parent and switch to another. There are various other crossover methods. In addition it is possible to produce two children from the two parents. In this case though just one child was produced.
A mutation operator was also used. There is a 0.001% chance that a mutation will occur to a chromosome. So like in biological systems the chance of mutation is very small but is still there.
Once 100 children are produced then this is the new population and a generation has occurred. The process is then repeated until a solution to the problem is found.
As mentioned previously genetic algorithms have had much success is problems where other optimisation techniques have failed. The traveling salesman problem, is as follows:
Given a finite number of "cities" along with the cost usually considered distance, of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point.
It is the problem a travelling salesman would have if he had to visit many places and wanted to do it by traveling the shortest distance. This problem is a "non-polynomial complete (NP Complete)" problem. That is the time to solve the problem is a function of an exponential. That is each time an axon (a city in this case) is added the problem takes much longer. With the speed of computers today the problem can soon become unmanageable. Using genetic algorithms this problem can be solved very quickly and efficiently without the need for exhaustive search which was the method employed by many other methods.
Please note that the views expressed in this essay
does not necessarily reflect the views of AI Horizon, but only that
of the author cited.
Home 
