Background

In university, I was invited to be part of a team working on the application of metaheuristics. This was not a topic covered in any of my available classes, so I found it to be a good opportunity to tackle something outside of coursework. Our actual task was to implement a hybrid of metaheuristics¹ with direct solvers, but that contact with metaheuristics made me interested in doing something related for my graduation project.

What is it?

Ant Colony Optimization is a metaheuristic technique inspired by the behavior of real ants. It imagines the problem space as a graph, with a collection of mostly-independent agents (artificial ants) trying to find a path. The ants walk through the graph in a probabilistic manner, depositing "pheromones" wherever they go, proportional to the quality of the solution they find. The pheromones influence the probability that a later ant will make the same movement. Over time, the colony will converge towards good solutions.

One thing I found interesting about ACO was how its structure can be easily transferred to parallel execution in quite a few different ways. I decided to study that as part of my Bachelor's thesis, and as part of that I wanted to see how application of one model (master-slave) works out for the two most popular ACO variants (ACS and MMAS) in a multicore architecture (as most research still focuses on computer clusters).

Details

The project is implemented in Rust, using Rayon. The Travelling Salesman Problem was picked for testing as it's the prototypical problem for which ACO is implemented.

The implementation is relatively straightforward, though there is a bit of ugly code repetition in a couple of places. There is a trait Colony which defines the basic behavior an ant colony supports, and 3 implementors, Mmas, Acs, and AcsPar. Once the colony is initialized, they all follow the basic ACO loop, which, in pseudocode, is:

while not done: // time and/or iteration limit
    construct_solutions()
    update_pheromones()

For all colonies, pheromones are stored in a matrix of f64s (the values are wrapped in RwLocks in AcsPar), alongside heuristic information on the problem instance (an additional heuristic that advantages edges with lesser weight, calculated once on initialization). There is an additional matrix that combines both the pheromone and metaheuristic values so that the ants do not have to make the calculation every time they read the data.