APPLICATION : TRAVELLING SALESMAN PROBLEM

The travelling salesman problem (TSP) is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are classified as NP-hard.
1 Problem statement
Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
2 Observation
The size of the solution space is ((n-1)/2)! for n > 2, where n is the number of cities. This is the number of Hamiltonian cycles in a complete graph of n nodes, that is, closed paths that visit all nodes exactly once.
Let us see the implementation of the problem using ant colony optimization.
3 FORMULA
1.At the beginning of the search process, a constant amount of pheromone is assigned to all arcs. When located at a node i an ant k uses the pheromone trail to compute the probability of choosing j as the next node:



where is the neighborhood of ant k when in node i.

2. When the arc (i,j) is traversed , the pheromone value changes as follows:


By using this rule, the probability increases that forthcoming ants will use this arc.

3.After each ant k has moved to the next node, the pheromones evaporate by the following equation to all the arcs:


where is a parameter. An iteration is a completer cycle involving ants’ movement, pheromone evaporation, and pheromone deposit

4 ALGORITHM

1. Initialize
set t:= 0
set NC:= 0 {number of cycles}
For every edge (i,j) set an initial value Tij(t) for trail intensity and d Tij = 0. Place m ants on the n nodes.

2. Set s:= 1 { tabu list index)
for k:= 1 to m do
Place starting town of the kth ant in tabuk(s).

3. Repeat until tabu list full
Set s := s + 1
for k:=1 to m do
Choose the town j to move to with probability pijk (t)
Move the kth ant to the town j.
Insert town j in tabuk(s).
4. For k:=1 to m do
Compute the length Lk of the tour described by tabuk(s). Update the shortest tour found.
For every edge (i,j)
For k:=1 to m do
d Tij = d Tij + d Tijk
5. For every edge (i,j), compute
Tij(t+n) = e Tij(t) + ë Tij
Set t:=t+n
Set NC:=NC+1
For all edges(i,j), set ë Tij=0
6. If NC < Ncmax
empty tabu lists, go to 2
else
print shortest tour; stop

5 CONCLUSION

The advantages of using the ant colony optimization on the traveling salesman problem are

1. For TSPs (Traveling Salesman Problem), relatively efficient

– for a small number of nodes, TSPs can be solved by exhaustive search
– for a large number of nodes, TSPs are very computationally difficult to solve (NP-hard) – exponential time to convergence

2. Performs better against other global optimization techniques for TSP (neural net, genetic algorithms, simulated annealing)

3. Compared to GAs (Genetic Algorithms):
– less affected by poor initial solutions (due to combination of random path selection and colony memory)


Fig. flowchart for implementing traveling salesman problem using ACO


– retains memory of entire colony instead of previous generation only

However the disadvantages are
1. Theoretical analysis is difficult:
– Due to sequences of random decisions (not independent)
– Probability distribution changes by iteration
– Research is experimental rather than theoretical

2. Convergence is guaranteed, but time to convergence uncertain