Abstract: Ant colony algorithm (ACO) is a metaheuristic search method, which can solve efficiently NP-complete problems such as the famous traveling salesman problem (TSP). To alleviate, to some extent, ACO’s drawback of getting stuck in a local optimum, a TSP algorithm based on clustering ensemble ACO and restricted solution space is proposed in this paper. The main idea is as follows: Firstly, a triangle algorithm is presented to generate initial TSPs, which are used to construct the primitive transfer probability matrix so that the randomness of trip of ants is reduced; Secondly, to avoid premature convergence, the k-means clustering method is employed repeatedly to produce co-association matrix (CM), which can be viewed as a perturbation factor and improve the selection of the next city for each ant, namely, city pairs with high values in CM are connected closely, or vice versa; Finally, a restricted solution space, namely, the restricted connections, is reconsidered to improve the solutions produced by ACO. The experiments on 9 benchmarks from TSPLIB demonstrate that the proposed method outperforms some of the state-of-art TSP algorithms.

Key words: ant colony optimization, traveling salesman problem, co-association matrix, restricted solution space