An Improved Ant Colony System Based on Dynamic Candidate Set and Entropy for Traveling Salesman Problem

Abstract

The Ant Colony Optimization (ACO) is a metaheuristic algorithm used for combinatorial optimization problems. It is a good choice for many hard combinatorial problems because it is more efficient and produces better solutions than greedy algorithms. However, ACO is computationally expensive and it can still trap in local optima, take a long time to compute a solution on large problem sets and premature convergence problem. The main idea of the modification is to limit the number of elements choices to a sensible subset, or candidate list, which can limit the selection scope of ants at each step and thus substantially reduce the size of search space and to measure the uncertainty of the path selection and evolution by using the information entropy self-adaptively. Simulation study and performance comparison on Traveling Salesman Problem show that the improved algorithm can converge at global optimum with a high probability. It also shows a faster convergence to the solutions than the standard algorithm.