Genetic
algorithms are used to solve problems connected with optimalization,
recognizing images, predicting movements on the stock exchange, creating
computer graphic as well as projects of buildings and machines.
:: Travelling problem::
In the Travelling
Salesman Problem, the goal is to find the shortest distance between N different
cities.
Testing every possibility for an N city tour would be N! math additions. A 30 city tour would be 2.65 X 1032 additions. Assuming 1 billion additions per second, this would take over 8,000,000,000,000,000 years. Adding one more city would cause the number of additions to increase by a factor of 31. Obviously, this is an impossible solution.
A genetic algorithm can be used to find a solution is much less time. Although it probably will not find the best solution, it can find a near perfect solution in less than a minute. There are two basic steps to solving the travelling salesman problem using a GA. First, create a group of many random tours in what is called a population. These tours are stored as a sequence of numbers. Second, pick 2 of the better (shorter) tours parents in the population and combine them, to create 2 new solutions children in the hope that they create an even better solution.
The idea of Genetic Algorithms is to simulate the way nature uses evolution. The good solutions reproduce to form new and hopefully better solutions in the population, while the bad solutions are removed.
The difficulty in the TSP using a GA is encoding the solutions. The encoding cannot simply be the list of cities in the order they are travelled. As shown below, the crossover operation will not work. The crossover point is the 3rd number
|
Parent 1 |
1 2 3 4 5 |
|
Parent 2 |
3 5 2 1 4 |
|
Child 1 |
1 2 3 1 4 |
|
Child 2 |
3 5 2 4 5 |
As you can see, the city 1 is used twice and
city 5 is missing in child