Travelling Salesperson Problem

The TSP is a very important problem in the context of Ant Colony Optimization because it is the problem to which the original AS was first applied, and it has later often been used as a benchmark to test a new idea and algorithmic variants. We describe an artificial ant colony capable of solving the traveling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph.

Ant Colony Algorithm

Ant are the agents that

1.  Choose next town to go according to the probability that is a function of distance of town and amount of pheromone on edge.

2.   Legal tours are “forced” by use of a tabular list; an ant can only visit a town once. Each ant has its own “tour memory”.

3.    When the tour is complete, a pheromone is laid down on the trail.

4.   Iteration is defined to be m moves -- one by each ant. Tour completes in n moves i.e. n iterations.

Ant System TSP 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 tabu k(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 

Flowchart

Conclusion

The key to the application of ACS to a new problem is to identify an appropriate representation for the problem (to be represented as a graph searched by many artificial ants), and an appropriate heuristic that defines the distance between any two nodes of the graph. Then the probabilistic interaction among the artificial ants mediated by the pheromone trail deposited on the graph edges will generate good, and often optimal, problem solutions.