The Travelling Sales-Ant Problem

An introduction to Ant Colony Optimization for Java Developers

Photo by Lorenz Lippert on Unsplash

America is a beautiful, diverse, and humongous continent. Let’s imagine you’re organizing a big-American trip, with five major cities to visit. In the following table, we have listed the flight distance between these cities, in kilometres:

You need to visit all the cities, and you want to know the best way to do it. Given that time is money, it’s in your best interest to visit them in an order that keeps travel distance at minimum. Going technical, given a list of cities, you want to find a permutation of them that minimises cost, where cost is expressed as travel distance.

As a first attempt, we can try what’s called a brute-force search: 1) we generate all the possible orders to visit the 5 cities, 2) per order, we calculate the travelled distance, and 3) we select the order with the minimum travelled distance. In Java, this looks like this:

This is a method from the class BruteForceTsp. If you want to take a look at the brute-force search code, you can check this GitHub repository. Along with BruteForceTsp, we use PermutationGenerator for generating all the permutations for a list of strings (the cities) and TravellingHelper to calculate the total travel distance, using the values from the map distanceMap. distanceMap is a container for the information in the table.

Now that we have an algorithm, let’s put it to work. You can clone the repository and run the code in your computer, or run it on the cloud using Repl.it. For our five-city itinerary, we obtain the following result on Repl.it:

Solving a very small problem 
Optimal route: [Houston, Denver, Edmonton, Caracas, Buenos Aires]
Optimal distance (kilometers): 22609
Execution time (milliSeconds): 54

The brute-force search has taken 54 milliseconds to produce an itinerary of 22,609 kilometres to visit 5 cities. Given that we explored all the possibilities, we are sure that 22,609 kilometres is the best we can do.

Given these encouraging results, let’s get ambitious and plan to visit 10 American cities: Buenos Aires, Caracas, Denver, Edmonton, Houston, Lima, Los Angeles, Mexico City, Montreal, and New York. The flight distance information is available at engineeringtoolbox.com. We load this information into a new instance of distanceMap, run the algorithm in Repl.it, and you can see the following:

Solving a small problem 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
...
...
aco.intro.PermutationGenerator.generatePermutations(PermutationGenerator.java:27)
    at aco.intro.PermutationGenerator.getAllPermutations(PermutationGenerator.java:11)
    at aco.intro.BruteForceTsp.findOptimalRoute(BruteForceTsp.java:13)
    at aco.intro.Main.solveTsp(Main.java:14)
    at aco.intro.Main.main(Main.java:27)

By adding 5 extra cities, we made Repl.it fail. And from the error message, it seems related to the code that generates the permutations. The number of permutations of a list is the factorial of the number of items (n!). When we planned to visit 5 cities, the number of permutations generated was 5! = 1 * 2 * 3 * 4 * 5 = 120. Now that we expanded our trip to 10 cities, this number is 10! = 1 * 2 * … * 9 * 10 = 3628800. That’s a massive jump in complexity for just doubling the number of cities. Let’s imagine we are going really big and plan to visit 100 cities: the number of potential routes (100!) is larger than the number of atoms in the observable universe.

Our trip planning problem is an instance of the Travelling Salesman Problem (TSP). TSP is a non-deterministic polynomial hard problem (NP-hard). For the purpose of this article, it means there’s no algorithm that can solve the TSP problem quickly for an arbitrarily large input. So, it’s everything lost? Not really: although it’s not possible to find the route with the minimum distance, we can find a route that’s close to it.

Students planning trips are not the only ones facing optimization problems. Actually, humans are not the only living beings dealing with optimization. Let’s take ants, for example: they traverse our kitchens looking for food, to then take it back to their nest. Given their limitations, it would be great if they could do this while minimising travel distance. This image illustrates what they actually do:

Source : “Nanocomputers and Swarm Intelligence”, Jean-Baptiste Waldner, John Wiley & Sons, 2008. Taken from Wikimedia Commons.

Over time, the ants converge towards the shortest path between the food source and their nest. They do this without big brains and with very limited sensory skills. The way they accomplish this is very simple and very elegant. When an ant is out there looking for food, it drops pheromones over its path. Pheromone is a chemical that’s attractive to ants: the more pheromone in a path, the more ants are attracted to it. The most successful ants will have paths with more pheromone than the ants that are struggling. On the same timebox, an ant on a short path makes more two-way trips from food to source, than an ant on a longer path. The ants with shorter paths will drop more pheromones over them: this will attract the other ants, they will make the pheromone trail more intense and, over time, the whole colony will be using the shortest path.

This is a fine example of swarm intelligence: cooperation from very simple agents can produce complex behaviours. Inspired by natural ants optimising their path to food, we can use artificial ants to solve computational problems. This technique is called Ant Colony Optimisation (ACO). For our American trip problem, it would require the following:

1. We define an artificial ant colony, and we place each ant in a random city. The ant’s job is to construct a solution. In our case, it’s a permutation of the cities to visit.
2. Then, the ant starts adding cities to its solution. Selection is made using probabilities, and this probability depends on two factors: 1) how close a city is to the ant’s current location, and 2) how much pheromone is present in the link to that city. This way, we ensure that our artificial ants are attracted towards pheromones, like their natural cousins.
3. For this problem, we store pheromones in every link between two cities. So, we have a pheromone value for Houston — Lima, and another one for Houston — Edmonton.
4. Once the ant has visited all the cities, it proceeds to deposit pheromone. The pheromone value depends on solution quality: the shorter the distance, the more pheromone to deposit over its links. We want to deposit more pheromone on the city links that belong to the best solutions.
5. The ants generate solutions for several iterations. Once all the iterations finish, we report the best solution found.

We can code this in plain Java, or take advantage of a library like Isula, with several building blocks ready to use. An Isula based program for the American trip problem looks like this:

The complete code is available at GitHub. Also, you can execute it on the cloud on Repl.it. There, you can check that the ants have found a solution for the 10-cities American trip.

Optimal route: [Denver, Houston, Mexico City, Lima, Buenos Aires, Caracas, New York, Montreal, Edmonton, Los Angeles]
Optimal distance (kilometers): 25647
Execution time (milliSeconds): 1629

This time, the 500 MB available in Repl.it were enough. Even better, the ants have actually found the optimal solution: you can check it by running the brute-force search code on your computer. However, we cannot always count on this: swarm intelligence can find a solution for an optimization problem, but we have no guarantees that this solution is actually the best one. In some scenarios, like planning a trip, this is enough. Another caveat of techniques like ACO is that they depend on multiple parameters, and these parameters affect how good it performs. How many ants do you need? How many iterations? How much pheromone should I use at the beginning? You need to answer these questions before using ACO. To review all the parameters of our ACO implementation, check the SimpleTspConfiguration class.

Finally, ants are not the only source of inspiration for swarm intelligence algorithms. Some techniques are based on bees, fireflies and even amoebas.