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 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

Previous slide

Next slide

Back to first slide

View graphic version