The inspiration for the ACS algorithm came from real ants, which are capable of finding the shortest path from food source to their nest. While walking, ants leave pheromone on the ground, and follow, in probability, pheromone that was left by other ants.

The Traveling Salesman Problem (TSP) is the problem of finding, in a full graph, a minimal cost closed tour, which goes through each vertex once.

fig. 1

Let's look at fig. 1: When an ant arrives to a decision point from the left, it has to decide which way to go (up or down). Since there's no way for the ant of knowing which way is better, 50% of the ants will choose the upper path, and 50% will choose the lower path. After a while, the ants went through the lower path, will arrive to the other side, while the ants went through the upper path will still be on their way. Since ants leave pheromone while walking, ants arriving from the right to the decision point, will now have pheromone on the lower path, and therefore they will choose it with greater probability. As time passes, more pheromone will accumulate on the lower path, until the probability of choosing the upper path becomes insignificant.

The idea of ACS is inspired from this behavior of ants. In order to solve the TSP problem, we're using a set of ants, working as cooperative agents. Each ant, except of deciding its next step according to pheromone, also influenced by the edge length (a property that ants in reality don't have). The path an ant will choose to its next city, will be chosen according to pheromone and length on the edges starting at its current city, with bigger probability given to shorter edges with more pheromone. While walking on the chosen edge, the ant leaves pheromone, thus contributing its experience to other ants.

The algorithm works in this way: In each step, each ant chooses its next city, from the group of cities it hasn't been to yet, according to the described algorithm. This way, after n steps (where n is the number of cities), each ant will complete a tour in all cities, and will be located back at its beginning point. From among all ants, we choose the one that has made the shortest tour, and we keep that solution. More cycles can be made to improve this solution (The solution is expected to improve since now there's already pheromone on the edges, directing the ants for better paths), and after each cycle we keep the best tour if it's better then the previous solution.