An implementation of Ant Colony Optimization algorithms for the Travelling Salesman problem, done as part of my Bachelor's thesis. Max-Min Ant System (MMAS) and Ant Colony System (ACS) were implemented in single-threaded and multi-threaded versions to analyze efficiency gains. The parallel versions use a Master-Slave model, in which the main thread controls the overrall algorithm and slave threads handle tasks. Rayon was used to handle the thread pool and parallel execution through its parallel iterators.

The algorithms were tested on TSPLIB instances (currently, only able to read NODE_COORD_SECTION instances as those were the ones I used for the thesis). A json file is taken as input with a sequence of "run descriptions," such that the program can take a single file to determine multiple instances to be run multiple times for different algorithms with different parameters, and then be left alone executing without additional input.

Notes on implementation:

• Since ants in MMAS are entirely independent and only read from current data and pheromone update is done on the main thread between iterations, they don't need any aditional form of synchronization (through locks, etc).
• In ACS, ants do need to modify data as part of their execution through the local pheromone update, so the parallel version of ACS uses a Matrix of RwLocks (plus an additional Mutex used before acquiring the locks) to avoid having one ant's modifications be overwritten by another. In theory, this is not strictly necessary because having a few lost updates does not affect the overall flow of the algorithm, and there is some research where avoiding synchronization leads to better results as it removes overhead allowing the algorithm to be run much faster. For this implementation, I decided to just try to keep the behavior closer to the single-threaded version, though I might try the other type of implementation in the future.