An Improved Ants Colony Algorithm for NP-hard Problem of Travelling Salesman

摘要

ACO (Ants Colony Optimization) algorithm has already obtained promising effect on solving many problems of combinatorial optimization due to its high efficiency, well robustness, positive feedback and the simultaneous-ness. Unfortunately the main defects of slow convergence and easy stagnancy in ACO low its applications. Fully employing the advantages of ACO, the paper proposes the novel tactics of updating the whole and local pheromone to avoid early stagnancy. Furthermore, the constraint satisfaction techniques are used to solve the problems of slow convergence by reducing the search space, accelerating search rate and enhancing efficiency. Finally, the case study for travelling salesman problem demonstrates the validation and efficiency of the improved ants colony algorithm.