Ant colony algorithm can better deal with combinatorial optimization problems, but it is still difficult to balance the solution accuracy and convergence speed facing large-scale TSP. Nowadays, most scholars focus on the route information of better ants for improvement, while ignoring the route information of general ants with a large base. So, this study proposes the multiple ant colony algorithm combining community relationship network (CACO) by collecting route information of all ants and constructing a route relationship network to improve the accuracy of the solution. The network is divided into a number of small communities that reflect the affinity of multiple colony ants to different cities through community detection with modularity. Within the communities, CACO use the excellent roue exploration ability of the ant colony algorithm to identify high-quality route segments, integrating the pheromones of high-quality segments in the communities to provide pheromone feedback to the multiple colony ants for better route exploration. The three parts of route information collection, community detection and pheromone feedback form a feedback loop, which keeps cycling when multiple populations ants explore, and each cycle will drive the result closer to the optimal solution. Meanwhile, CACO proposes a mutual assistance strategy to improve the exploration ability of multiple colony ants by complementing each other according to the different states of superior and inferior populations. To test the performance of CACO, 28 TSP instances are compared with the well-known improved algorithms are compared and results show CACO outperforms other improved algorithms significantly, especially in large-scale TSP.
Keywords: Ant colony algorithm; Community detection; Modularity; Route relation network; TSP.
© King Fahd University of Petroleum & Minerals 2022.