Hybrid Ant Colony Algorithm Using Improved Circle Strategy for TSP Problem

Introduction

The Traveling Salesman Problem (TSP) is an optimization problem that finds the shortest loop through all nodes in a closed network and passes through each node only once. It is a well-known and one of the most studied problems in the field of combinatorial optimization. At the same time, it is also a very important problem, which can be applied to many fields such as production, life, and logistics. Since the 1950s, numerous researchers have been trying to develop and improve various algorithms in the hope of reaching optimal or near-optimal solutions. Dorigo et al. (1996) proposed the Ant Colony Algorithm (ACO), which is a heuristic algorithm based on population. After that, Gambardella et al. (1995) proposed the Ant-Q algorithm, which combined the local pheromone update mechanism with the elite ant strategy, which significantly improved the search ability of the ant colony. Deng et al. (2019) introduced a multi-swarm strategy, co-evolution mechanism, pheromone update strategy, and pheromone diffusion prohibition into ant colony algorithm, and proposed a new multi-swarm co-evolution ant colony optimization algorithm (Improved Co-evolution Multi-Population Ant Colony Algorithm, ICMPACO). Inspired by biological evolution in nature, Holland et al. (1987) proposed a Genetic Algorithm (GA). Qiao et al. (2006) proposed a genetic algorithm based on local competition selection operator based on individual differences, which enhance the performance of the algorithm. Gao et al. (2016) proposed a clustering ant colony algorithm to solve the dynamic location routing problem. Kashef et al. (2015) proposed an advanced binary ant colony algorithm for feature selection of important tasks such as data analysis, data mining, and information retrieval processing. Mahi et al. (2015) proposed a hybrid algorithm that uses particle swarm optimization to optimize the parameters of the ant colony algorithm and adds a 3-Opt algorithm to improve local solutions. Yi et al. (2020) proposed an ant colony algorithm based on an improved distributed CPS task management model, which enhanced the local search ability and improved the quality of solving task scheduling problems. Tabakhi et al. (2014) proposed an unsupervised feature selection method based on ant colony optimization, which finds the optimal feature subset through multiple iterations without any learning algorithm. Zhan et al. (2003) discussed the principle of setting parameters in the basic ant colony algorithm through simulation experiments and gave the effective value range of the parameters, but the values of the parameters are still rough, and it is difficult to obtain the optimal parameter combination. In recent years, many other methods have also been proposed.

It can be seen from the above analysis that the researchers have achieved remarkable results in the study of the TSP problem, but the ant colony algorithm has a slow convergence speed and is easy to fall into the local optimum. Therefore, more in-depth research on the ant colony algorithm is needed. This paper combines the improved circle strategy (Wang, 2005) with the ant colony algorithm and proposes a new hybrid ant colony optimization algorithm.

In the hybrid ant colony algorithm proposed in this paper, the improved circle algorithm is used to optimize the solution obtained by the ants to improve the search ability of the algorithm, and the uniform design method (Fang et al., 2001) is used to obtain the optimal combination of algorithm parameter settings and determine the experimental plan.