The Travelling Salesman(t)

[Update 2018: I've noticed this post gets quite a few views each month, so I think I'll follow up with some similar posts this year! Leave a comment if there's anything you would like to see in particular :) ]

This is my first more in-depth post, any feedback is welcome.

PYTHON ANT COLONY OPTIMIZATION IMPLEMENTATION

Ant Colony Optimization (ACO) is a biomimetic algorithm which was designed around the natural foraging behaviour of Ants (as the name might suggest), and was first developed in Marco Dorigo in '92.

It is best known for it's travel planning applications in Travelling Salesman Poblems; however it has seen application in many related areas such as telecommunications routing, as well as more abstract applications such as in protein folding. 

I've put together a Python 2.7 implementation of the ACO algorithm which can provide the shortest route to visit all cities in a given list of cities. If you stop reading at the github URL, one thing to keep in mind, as discussed below, is that resultant routes are not always guaranteed to be optimal.

To get the code, visit my github here: https://github.com/aransena/paco (paco, as in python aco), plus you'll also need NumPy to learn more about ACO and TSP, read on!   

The Travelling Salesman

The travelling salesman problem, as described on Wikipedia, can be summed up as:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
shortest_route1.png

The wiki page claims this problem was first formulated in 1930 and first mathematically formulated in the 1800s by W.R. Hamilton; however I'd argue that the consideration of optimal routing can be traced back at least a little bit earlier to Euler's graph theoric solution to the Seven Bridges of Königsberg problem in 1736. Further back than these examples, I'd guess it's pretty likely that the travelling salesman in some form or another has been a problem on people's minds for as long as there have been goods to move around, and a cost to moving those goods.

The issue with the travelling salesman problem is that it is an NP-Hard problemThe ACO approach isn't guaranteed to provide the absolute optimal path; however it can when we constrain the number of cities. If the number of cities/locations were large (e.g. >1,000,000), it would be very difficult to 1) find the optimal path, and 2) prove the path found was in fact optimal.

Path planning and routing is a problem which has generated a lot of research interest over recent decades, and continues to draw attention, due to not only the cost of logistics to large companies, but also due to the ever increasing availability of data which companies can use to drive their planning and the discovery of new application areas for these algorithms outside of logistics. An interesting example of new optimization factors showed up just this year, with a new app for lorry route planning which avoids left turns in the hope it creates safer roads for cyclists, and applications have been found in diverse fields such as genomics.

Ant Colony Optimization

Source:  Wikipedia

Source: Wikipedia

Ants are able to locate food in their environment, and coordinate retrieving it, all without having an obvious direct form of communication to the greater colony. Bees, for example are able to communicate food location through dance. However communication among the ants must take place, as colonies can be observed to coordinate their food foraging behaviours. It was found that ants communicate through the use of pheromone, a method of indirect communication categorized as stigmergy.

As ants explore their environment, they begin in a somewhat random fashion; however as soon as food has been discovered, the paths of the ant colony will eventually converge on the shortest path to the food. This is possible due to the ants depositing a breadcrumb trail of pheromone along the path between the food and their nest. As more pheromone builds up, more ants will follow the discovered trail to food.

This behaviour can be replicated in code, as originally described by Dorigo, in roughly the following steps:

  1. Populate the beginning city with a colony of ants.
  2. For each ant, send the ant on a tour of all cities where they visit each city only once. The selection for which city to visit next is initially effectively random. After the first run, the next city selection becomes gradually more influenced by the amount of pheromone on a possible trail.
  3. Once all ants have completed a tour of the world, deposit pheromone on each city path. The amount of pheromone deposited by each ant is proportional to the length of the path traveled by the given ant.

At each city, a probability distribution for next city selection from a list of possibilities is generated according to the following:

Where:

  • x is the current city
  • y is an unvisited city
  • tau is the amount of pheromone on the trail between city x and city y
  • eta is the desirability of city y relative to city x (often formulated as the inverse of the distance between x and y)
  • alpha is a weighting factor for the pheromone
  • beta is a weighting factor for the desirability
  • z is a city from the list of unvisited cities

In the python implementation, this features like so:

for ant in ants:
    current_city = ant.current_city
    transition_probabilities=[]
    for city in unvisited:
        denominator = 0
        numerator = (pow(tau[current_city][city],alpha)*(eta[current_city][city], beta))
        for city in unvisited:
            denominator += (pow(tau[current_city][city],alpha)*(eta[current_city][city], beta))
        
        p_ij = numerator/float(denominator)
        transition_probabilities.append(p_ij)
    
    next_city = numpy.choice(unvisited, 1, transition_probabilities)  

In the code found in my github, next_city selection also features uniformly random city selection a small percentage of the time, epsilon. This is a technique often used in learning systems to encourage state-space exploration, and helps to explore a greater range of possible paths in the environment.

When using the code and algorithm, the key parameters which you will need to experiment with and tune are:

  • Number of ants and the number of steps: These will affect the likelihood of finding an optimal path, and the duration of the optimization process 
  • Alpha: This will affect the importance of pheromone in the optimization process
  • Beta: This will affect the importance of desirability/distance in the optimization process
  • Epsilon: Used for setting how often the ants will take a uniformly random decision, as opposed to a decision guided by pheromone and distance
  • Rho - Evaporation Constant: Affects how much pheromone is removed in between steps in the process
  • Pheromone Amount: Affects how much pheromone is deposited in between steps in the process

With the pheromone update, it is important to note that the pheromone for a given trail is only updated if the ant actually used the transition. While every city will be visited, not every path will be visited. Pheromone evaporation will however affect all paths.

Conclusion

My testing seems to provide reasonable results; however I'll be continuing to tinker with the code. It currently runs excessively slow due to amount of loop based calculations needed for each ant at each step, so the next update to this will hopefully factor in some multiprocessing based parallelisation.

Note that there is a stable Python 3 implementation of the ACO algorithm, which can be found here: https://pypi.python.org/pypi/ACO-Pants/0.5.2

Further Reading

Links

Books

  • Marco Dorigo and Thomas Stützle. 2004. Ant Colony Optimization. Bradford Co., Scituate, MA, USA.

  • David Corne, Marco Dorigo, Fred Glover, Dipankar Dasgupta, Pablo Moscato, Riccardo Poli, and Kenneth V. Price (Eds.). 1999. New Ideas in Optimization. McGraw-Hill Ltd., UK, Maidenhead, UK, England.

Papers

  • M. Dorigo, Optimization, Learning and Natural Algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, [in Italian], 1992.; M.Dorigo

  • Haijuan Guo; Qiang Lü; Jinzhen Wu; Xu Huang; Peide Qian, "Solving 2D HP Protein Folding Problem by Parallel Ant Colonies," in Biomedical Engineering and Informatics, 2009. BMEI '09. 2nd International Conference on , vol., no., pp.1-5, 17-19 Oct. 2009