Traveling Salesman Problem by Genetic Algorithm
Definition of the problem:This is a simple combinatorial problem. For a small value of n, one can easily find the solution by having a permutation of the cities which is the minimum distance tour. But for larger n, it would be impracticable as there are (n-1)!/2 ways to visit the cities.
Many approaches have been proposed for the problem. Of these, Genetic Algorithms can produce reasonable solutions in a short span of time.
Genetic Algorithm:
Genetic Algorithm (GA) is based on the famous theory “Survival for the
fittest”. The steps of a GA are:
In my program, I have used Partial Matching Crossover (PMX) and Swap Mutation. For fitness calculation, the inverse of the distance of a tour is used. The selection has two options: Roulette wheel and Tournament selection; whereas for replacement, either CHC or Elitism method is used. User may choice either of them.
Encoding Method:
For TSP, order encoding is used. Here every tour is a permutation of
cities; for example {0,1,2,5,4,9,7,8,6,3},{1,9,6,0,3,8,7,5,4,2} are two possible
tours, i.e. two possible solutions (chromosomes) of a 10-city TSP.
Selection of Parents:
There are a lot of selection methods of the parents to produce
children such as Roulette wheel, Tournament and Rank selection
methods. The first two are used in my program.
In Roulette wheel selection, parents are selected according to their fitness. The better the chromosome, the more chances are to be selected. If we place all the chromosomes on a roulette wheel, and let everyone occupy the place according to its fitness, the best chromosome will have larger area. How is it done? I have assigned relative fitness to each individual. Then randomly a number is generated; the relative fitness of the individuals are summed until it becomes greater than the random value; the index of the individual where it halts is returned.
In Tournament Selection, two (or more, possibly 7) chromosomes are selected randomly; the one that has the better fitness is returned as a parent .
Partially Matched Crossover (PMX):
In Partially Matched Crossover (PMX), two crossing points are
selected randomly;
let us call it i&j (i<j).We have to swap the digits between the positions
i &j
including. But this may produce illegal children. So what to do? Follow the
following steps:
Replace duplicate values according to the replacement values.
Step 1 is the important part of a PMX. This can be better understood by an example.
Consider two parents with values of genes as 21384576 and 87263415 and the
crossover points as indicated in the figure:
2 | 1 | 3 | 8 | 4 | 5 | 7 | 6 | ||
8 | 7 | 2 | 6 | 3 | 4 | 1 | 5 |
Next create a temporary list to hold the values for replacement. In the list, put values in those cells corresponding to the values in the second parent between two crossover points. So the list will hold values at cell no. 2,6,3 and 4 and the values are from the first parent, which are 3,8,4 and 5 respectively. The values of other cells are –1. So the initial replacement list will look like:
Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Replacement values | -1 | 3 | 4 | 5 | -1 | 8 | -1 | -1 |
Next scan the list like a tree starting from the left. Whenever you scan a cell, check whether it is –1 or other value. If other value, make the content of this cell –1 and go in recursive fashion. When you get –1, set the value of the root node the number of the cell where you get –1. So the steps are as follows:
Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Replacement Values |
-1 | -1 | 4 | 5 | -1 | 8 | -1 | -1 |
-1 | -1 | -1 | 5 | -1 | 8 | -1 | -1 | |
-1 | 5 | -1 | -1 | -1 | 8 | -1 | -1 | |
-1 | 5 | -1 | -1 | -1 | 8 | -1 | -1 |
That is 2 and 6 in the first parent will be replaced by 5 and 8 respectively while in the second parent 5 and 8 will be replaced by 2 and 6 respectively. So the generated offspring is:
5 | 1 | 2 | 6 | 3 | 4 | 7 | 8 |
6 | 7 | 3 | 8 | 4 | 5 | 1 | 2 |
But if you get the value of the starting point, you have to make all values in the cycle –1 because the values between crossover points are permutation of one another. Consider another example:
2 | 5 | 1 | 3 | 8 | 4 | 7 | 6 | ||
1 | 5 | 2 | 8 | 4 | 3 | 6 | 7 |
Look at here the values between two crossover points are just permutation of one another. As usual build initial replacement list and do successive steps until you get starting value:
Positions | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Replacement values | -1 | -1 | 4 | 8 | -1 | -1 | -1 | 3 |
-1 | -1 | -1 | 8 | -1 | -1 | -1 | 3 | |
-1 | -1 | -1 | -1 | -1 | -1 | -1 | 3 | |
-1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
In the last step of the above example, you get the initial value of 3, that is a cycle and you do not need to replace any value outside of crossover points. So the generated offspring are:
2 | 5 | 1 | 8 | 4 | 3 | 7 | 6 |
1 | 5 | 2 | 3 | 8 | 4 | 6 | 7 |
Swap Mutation:
Normal Mutation is not possible for TSP. Because if you mutate one digit with
another, it will produce an illegal tour. For example, if in the tour
{1,4,3,5,0,9,8,6,7,2} digit 5 is mutated with 4, the new tour would be
{1,4,3,4,0,9,8,6,7,2} which is illegal. So what may be done? Use Swap
Mutation. In Swap Mutation, two random points are selected and the two digits at
these positions are interchanged. For example, suppose the random points are i=3,j=6;
the digits at positions 3 and 6 are 3 and 9, respectively. Swapping them,
produce {1,4,9,5,0,3,8,6,7,2}.
Replacement Strategy:
At the last stage of Genetic Algorithm, previous population must be
updated by the newer individuals (offspring) in the hope they may produce better
results. I have used two replacement strategy: CHC and Elitism.
CHC Replacement:
In CHC replacement method, N offspring (children) are
created by Roulette wheel selection method of parents. Then these N
offspring are combined with N parents to give 2N individuals, then they
are sorted according to fitness, and the best N individuals are selected
for the next generation to serve as parents. This is of course elitism, because
better parents would not be lost.
Elitism replacement:
In Elitism replacement, some percent of the best individuals of population
will remain along with newly created offspring.
Copyright@2004, Topon Kumar Paul. All
rights reserved. Last update:01/14/2005 02:08:01 PM