Traveling Salesman Problem by Genetic Algorithm

Definition of the problem:
A salesman wants to visit n cities cyclically. He wants to visit each city once and return to the city where he starts. In which way should he visit the cities so that the distance traveled by him will be minimum?

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:

  1. First create many random tours of cities
  2. Pick up two best fittest parents (tours) to make a new tour
  3. Crossover them and mutate each according to some probability
  4. Replace some individuals of the old population according to replacement strategy in the hope the new tours will provide better solution.
The key function here is minimum distance of a tour which acts as fitness.

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:

  1. Build a list of values for replacement between two crossover points
  2. Exchange values between two parents and between crossover points
  3. 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