The evolution of ant colony optimization : An empirical evaluation on the quality and cost ofan evolving algorithm

This paper evaluates the quality and cost of three Ant Colony Optimization (ACO) algorithms. In particular Ant System (AS), Max-Min Ant System (MMAS), and Focused Ant Colony Optimization (FACO) are used on the Travelling Salesman Problem (TSP). The algorithms were tested on various problem instance sizes. Results indicate that FACO outperforms both AS and MMAS in solution quality, consistently producing the closest to optimal solutions for all test cases it executed. FACO achieves 30 times more optimal solutions than AS and 15 times more than MMAS, benefiting from its elitist ant mechanism, focused search strategy, and local search. Execution time analysis reveals that FACO is faster than AS and MMAS, with improvements attributed to efficient trail intensity updates, focused edge selection, and multithreading. However, FACO's memory usage is significantly higher than MMAS due to its multithreaded architecture and data storage requirements. The thesis highlights the potential of overall improvements whilst also showcasing that there exists a point where an algorithm may have to sacrifice one metric when aiming to improve in regards to another, and identifies opportunities for further research.