Study and implementation of modified ant colony optimization for travelling salesman problem

Abstract

The paper explores and visualizes a modified Ant Colony Optimization (ACO) algorithm to solve the Travelling Salesman Problem (TSP), implemented in Python. The TSP, a classic optimization problem, requires finding a Hamiltonian path that visits each city exactly once and returns to the starting point while minimizing the total distance travelled. Our approach introduces dynamic random thresholds for node selection and fixed pheromone update, which adapts based on the algorithm’s performance. This probabilistic component enhances exploration and reduces the likelihood of premature convergence, diverging from traditional ACO methods. The implementation features an interactive, grid-based environment where users can select nodes representing cities. The modified ACO algorithm iteratively identifies a local optimal Hamiltonian path by simulating multiple generations of ant colonies, with customizable parameters such as the number of ants and generations. Key features include real-time visualization of the best path found and dynamic pheromone updates. This paper provides a basis for further research into adaptive evolutionary intelligence algorithms for optimization problems. It offers insights into applying ACO to find Hamiltonian paths in complex graphs.