This page will give a more detailed description of the ACS algorithm.

Each edge (r,s) on the graph has a cost (its length) d(r,s), and a pheromone measure t(r,s) which is updated every time an ant walk over this edge.

Each ant builds a complete tour, by choosing its next city according to a probabilistic transition rule - better odds are given to cities connected by short edges with high amount of pheromone. After each step, the pheromone on all edges is updated according to a local pheromone updating rule. Once all ants have completed a tour, a global pheromone updating rule is applied.

Transition rule:

An ant located at city r, will choose its next city s, according to the following equations:

Where j_k(r) is the set of cities that remain to be visited by ant k positioned in city r.
h(r,u) is 1/d(r,u), and b is a parameter setting the relative importance of pheromone vs. distance.

q is a random number, and q₀ is the parameter (0 < q < 1, 0 < q₀ < 1) setting the exploitation vs. exploration. if q < q₀ , the ant simply chooses the best path according to pheromone and h. If q > q₀ , the ant will choose its next city according to the next probability equation:

P_k(r,s) is the chance of city s to be chosen by ant k positioned in city r. Since we multiply the pheromone on the edge with h, which depends on d, we give better odds to shorter edges with more pheromone.

Local and global updating rule:

The local updating rule follows this equation:

t(r,s) ¬ (1 - r) * t(r,s) + r *Dt(r,s)

Where r is the local evaporation parameter 0 > r > 1, and Dt(r,s) is the sum of all pheromone left by ants that used this edge in their last step. An ant using edge (r,s), is leaving 1/d(r,s) pheromone on the edge.

The global updating rule follows this equation:

t(r,s) ¬ (1 - a) * t(r,s) + a * Dt(r,s)

Where a is the global evaporation parameter, 0 > a > 1.
Dt(r,s) is 1/(length of global best tour), if (r,s) belongs to this global best tour, and 0 if not.

In addition to this, according to a boolean parameter, all ants might leave global trail, adding 1/(length of their tour) to each edge belongs to their last tour.

Run time:

The parameters referred in this part are:
n = Number of cities
m = Number of ants
k = Number of cycles

In each step, each ant has to decide which way to go. From every city, it can go to any city it hasn't been in yet. This means it has to decide from among ~n cities. Before deciding, it has to calculate the probability of each path, according to the equations above. This part also takes ~n calculations. So one step sums at ~m*n calculations. To complete 1 cycle, one ant must go through all n cities, which means it has to complete n steps. This brings us to ~m*n*n calculations for each cycle.
It is obvious that there are also a constant number of calculations each ant has to perform in each step.

Bottom line - run time is O(m*n²*k), which is much better for big graphs then the recursive solution - O(n!)