Travelling Salesman Problem
12 Temmuz 2007
Travelling Salesman Problem
Using Genetic Algorithms
I have developed a method of solving the Travelling Salesman Problem (TSP) using Genetic Algorithms (GA). In the Travelling Salesman Problem, the goal is to find the shortest distance between N different cities. The path that the salesman takes is called a tour.
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, using crossover, to create 2 new solutions children in the hope that they create an even better solution. Crossover is performed by picking a random point in the parent’s sequences and switching every number in the sequence after that point.
The idea of Genetic Algorithms is to simulate the way nature uses evolution. The GA uses Survival of the Fittest with the different solutions in the population. The good solutions reproduce to form new and hopefully better solutions in the population, while the bad solutions are removed.
Eventually, the GA will make every solution look identical. This is not ideal. There are two ways around this. The first is to use a very large initial population so that it takes the GA longer to make all of the solutions the same. The second method is mutation. Mutation is when the GA randomly changes one of the solutions. Sometimes a mutation can lead to a better solution that a crossover would not have found.
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. Every number in parent 1 before the crossover point is copied into the same position in child 1. Then, every number after the crossover point in parent 2 is put into child 1. The opposite is done for child 2.
Parent 1
1 2 3 4 5
Parent 2
3 5 2 1 4
Child 1
1 2 3 1 4
Child 1
3 5 2 4 5
As you can see, the city 1 is used twice and city 5 is missing in child 1. A more complicated form of encoding (or a more complicated crossover) must be used. This form of encoding should ensure that that city adjacencies in the list are preserved from the parents to the children. This method should also realize that the tours 1 2 3 4 5 and 3 2 1 5 4 are the same. The method I have used does both.
Time for some technical jargon.
In my GA, the tours are encoded as a 2-dimensional array (a NxN matrix) of bits that store city adjacencies in both directions. A set bit indicates a city connection. If element [ X, Y ] is set, then city X connects to city Y. Only 2 bits will be set in every row and column.
Every iteration, a number of tours are chosen from the list of tours. This is the tournament set. The best 2 of these tours from the tournament will be combined to form 2 new tours using crossover. These two new solutions will replace the worst 2 tours from the tournament.
A greedy crossover operation combines the 2 tours to hopefully form 2 better tours. All adjacencies that are shared by the parent are placed in both children. This is done by performing a binary AND on the two parent matrices. When the parents disagree, the children alternate which parent they will get an adjacency from. If an adjacency produces a conflict ( city used twice or incomplete tour ), then a random city is used instead.
Due to the complexity of the encoding method, no mutation is done.
There is also a graphical display with the program where the current best solution is displayed as a bunch of lines connecting different cities.
This code used X/Motif and a Unix shell script, so it will only compile on a Unix Workstation. With some minor changes, the code could be made to work on a PC.
Source Code
Unix Version
PC Versions
tsp.tar.gz
tsp.zip
tsp.zip
Source Code Only
Executable
Full VC++ Project
On a Unix system
to extract files:
gunzip tsp.tar.gz
tar -xf tsp.tar
On a PC,
use Pkunzip or Winzip
The file tsp.in defines the locations of the cities. The file params.r defines the GA parameters. The file tsp.h defines upper limits for the parameters.
The params.c and params.h are generated by the params.d and the make-params script. Basically, params.r is a header file that can be changed without forcing a recompiling of the program.
Kategori: Genel kültür