Advancements in Rank-Based Ant System: Enhancements for Improved Solution Quality in Combinatorial Optimization

This work builds on the Rank-based Ant System (AS-Rank), an extension of Ant System, which despite its generally good performance and rapid convergence, has been overshadowed by other Ant System variants such as Max-Min Ant System (MMAS) and Ant Colony System (ACS), known for their superior performance. This paper enhances AS-Rank by incorporating diversification strategies that significantly improve the quality of solutions. Specifically, it introduces a pheromone smoothing strategy and a rank-based strategy that rewards the originality of an ant’s tour compared to the paths followed by previous ants. These additions aim to encourage diversification in the search process and prevent early convergence to sub-optimal solutions, facilitating a more efficient exploration of the problem space. Rigorous tests conducted, focused on instances of the Traveling Salesman Problem from the TSPLIB benchmark, demonstrate that the proposed method achieves quick convergence to high-quality solutions and outperforms the original AS Rank, as well as other ACO algorithms such as MMAS and ACS.