Ant Colony Optimization Based on Estimation of Distribution for the Traveling Salesman Problem

Ant Colony System algorithm is one of the best algorithms of ant colony optimization. However, the weaknesses of premature convergence and low efficiency greatly restrict its application. In order to improve the performance of the algorithm, a new Ant Colony Optimization algorithm based on Estimation of Distribution (ED-ACO) is presented. ED-ACO uses probabilistic model based on estimating the distribution of promising edges to adjust the state transition rule and the global updating rule. Furthermore, ED-ACO is significantly improved by extending with a local search procedure. We apply ED-ACO to traveling salesman problems and compare it to the previous finding. The results show that ED-ACO is an effective and efficient way to solve combinatorial optimization problems.