Institute of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China.
College of Science, Tianjin University of Commerce, Tianjin 300134, China.
Math Biosci Eng. 2022 Jun 6;19(8):8152-8186. doi: 10.3934/mbe.2022381.
As one of the most popular combinatorial optimization problems, Traveling Salesman Problem (TSP) has attracted lots of attention from academia since it was proposed. Numerous meta-heuristics and heuristics have been proposed and used to solve the TSP. Although Ant Colony Optimization (ACO) is a natural TSP solving algorithm, in the process of solving it, there are also some shortcomings such as slow convergence speed and prone to fall into local optimum. Therefore, this paper proposes an improved ant colony optimization based on graph convolutional network: Graph Convolutional Network Improved Ant Colony Optimization (GCNIACO). The graph convolutional network is introduced to generate a better solution, and the better solution is converted into the pheromone on the initial path of the ACO. Thereby, the guiding effect of the pheromone concentration for the ants at the beginning of the algorithm is enhanced. In the meantime, through adaptive dynamic adjustment of the pheromone volatility factor and the introduction of the 3-opt algorithm, the algorithm's ability to jump out of the local optimum is enhanced. Finally, GCNIACO is simulated on TSP datasets and engineering application example. Comparing the optimization results with other classical algorithms, it is verified that the graph convolutional network improved ant colony optimization has better performance in obtaining the optimal solution.
作为最受欢迎的组合优化问题之一，旅行商问题（TSP）自提出以来一直受到学术界的广泛关注。已经提出并使用了许多元启发式和启发式算法来解决 TSP。虽然蚁群优化（ACO）是一种自然的 TSP 求解算法，但在求解过程中也存在收敛速度慢、容易陷入局部最优等缺点。因此，本文提出了一种基于图卷积网络的改进蚁群优化算法：图卷积网络改进蚁群优化算法（GCNIACO）。引入图卷积网络来生成更好的解决方案，并将更好的解决方案转换为 ACO 初始路径上的信息素。从而增强算法开始时信息素浓度对蚂蚁的引导作用。同时，通过自适应动态调整信息素挥发因子和引入 3-opt 算法，增强算法跳出局部最优的能力。最后，在 TSP 数据集和工程应用实例上对 GCNIACO 进行了模拟。将优化结果与其他经典算法进行比较，验证了改进的图卷积网络蚁群优化算法在获得最优解方面具有更好的性能。
