How about using GA to solve the TSP problem?

TSP is a NP complete problem. That is it is not possible to find a solution to the TSP problem in Polynomial time. However, given a solution it can be verified if it is a solution in polynomial time.

Meta-heuristic methods such as Genetic Algorithms can be investigated as a tool to solve a TSP problem because of the population based approach they operate. This way they can "process" a huge number of solutions in on run of the algorithm. To solve any problem using GAs we need to define the following:

• Fitness function
• Individual chromosome
• Crossover operator
• Mutation

Fitness function: Here the fitness function is easy to define. It should be the distance that the salesman has to traverse for a certain tour of the cities possible. We seek to minimize this in TSP.

Chromosome: A chromosome can be defined simply as following- Suppose we have five cities A,B,C,D and E. Then imagine a chromosome of length 5, with each "slot" of the chromosome containing either of the 5 cities. For eg, A,C,D,B,E is a valid chromosome in our case.

Crossover operator: A crossover operator is used in a GA to "mix" two parents with the hope to get fitter children. Various crossover operators are available in GA literature with each having a different way to achieve the same thing. For eg, consider the single point crossover. It randomly selects a crossover point and then interchanges the bits between the two. Without getting into other specialized crossover operators, let us see what would be a good crossover operator for us. In our case, two parent chromosomes will each have a permutation of A,B,C,D,E. Whatever crossover method we choose, we have to take care of one fact here: the crossover operator should not create a child in which one city is present more than once, that is a invalid chromosome. One such crossover operator is the "Order Crossover " (OX) which can be used here.

Mutation: Mutation can be as simple as simply swapping two positions in a single chromosome here.

Overall this is how a TSP using GA would work:

• You create a population of individuals with each being of size 5, and containing a permutation of A,B,C,D,E (there will be lots of repetitions of the same permutation)

• You start the GA and in every run, you evaluate each individual on the basis of the fitness function by calculating the distance using the distance parameters given to you

• Crossover, Mutation improves the individuals and finally the best solution would be the individual with the best tour, ie. the optimal permutation of A,B,C,D,E.

Hope that helps!