Ant Colony Optimization Algorithms : Pheromone Techniques for TSP

Abstract: Ant Colony Optimization (ACO) uses behaviour observed in real-life ant colonies in order to solve shortest path problems. Short paths are found with the use of pheromones, which allow ants to communicate indirectly. There are numerous pheromone distribution techniques for virtual ant systems and this thesis studies two of the most well known, Elitist and Max-Min. Implementations of Elitist and Max-Min ACO algorithms were tested using instances of the Traveling Salesman Problem (TSP). The performance of the different techniques are compared with respect to runtime, iterations and approximation quality when the optimal solution could not be found. It was found that the Elitist strategy performs better on small TSP instances where the number of possible paths are reduced. However, Max-Min proved to be more reliable and better performing when more paths could be chosen or size of the instances increased. When approximating solutions for large instances, Elitist was able to achieve high quality approximations faster than Max-Min. On the other hand, the overall quality of the approximations were better when Max-Min was studied after a slightly longer runtime, compared to Elitist.