Research on improved ant colony optimization for traveling salesman problem
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 natu...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2022-06-01
|
| Series: | Mathematical Biosciences and Engineering |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/mbe.2022381?viewType=HTML |
| _version_ | 1818253533466591232 |
|---|---|
| author | Teng Fei Xinxin Wu Liyi Zhang Yong Zhang Lei Chen |
| author_facet | Teng Fei Xinxin Wu Liyi Zhang Yong Zhang Lei Chen |
| author_sort | Teng Fei |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T16:41:35Z |
| format | Article |
| id | doaj.art-1fd60062a11046dbbbd872e646daf15c |
| institution | Directory Open Access Journal |
| issn | 1551-0018 |
| language | English |
| last_indexed | 2024-12-12T16:41:35Z |
| publishDate | 2022-06-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | Mathematical Biosciences and Engineering |
| spelling | doaj.art-1fd60062a11046dbbbd872e646daf15c2022-12-22T00:18:33ZengAIMS PressMathematical Biosciences and Engineering1551-00182022-06-011988152818610.3934/mbe.2022381Research on improved ant colony optimization for traveling salesman problemTeng Fei 0Xinxin Wu1Liyi Zhang2Yong Zhang3Lei Chen41. Institute of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China2. College of Science, Tianjin University of Commerce, Tianjin 300134, China1. Institute of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China1. Institute of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China1. Institute of Information Engineering, Tianjin University of Commerce, Tianjin 300134, ChinaAs 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.https://www.aimspress.com/article/doi/10.3934/mbe.2022381?viewType=HTMLtraveling salesman problemant colony optimizationgraph convolutional networkdynamic pheromone volatility factor3-opt algorithm |
| spellingShingle | Teng Fei Xinxin Wu Liyi Zhang Yong Zhang Lei Chen Research on improved ant colony optimization for traveling salesman problem Mathematical Biosciences and Engineering traveling salesman problem ant colony optimization graph convolutional network dynamic pheromone volatility factor 3-opt algorithm |
| title | Research on improved ant colony optimization for traveling salesman problem |
| title_full | Research on improved ant colony optimization for traveling salesman problem |
| title_fullStr | Research on improved ant colony optimization for traveling salesman problem |
| title_full_unstemmed | Research on improved ant colony optimization for traveling salesman problem |
| title_short | Research on improved ant colony optimization for traveling salesman problem |
| title_sort | research on improved ant colony optimization for traveling salesman problem |
| topic | traveling salesman problem ant colony optimization graph convolutional network dynamic pheromone volatility factor 3-opt algorithm |
| url | https://www.aimspress.com/article/doi/10.3934/mbe.2022381?viewType=HTML |
| work_keys_str_mv | AT tengfei researchonimprovedantcolonyoptimizationfortravelingsalesmanproblem AT xinxinwu researchonimprovedantcolonyoptimizationfortravelingsalesmanproblem AT liyizhang researchonimprovedantcolonyoptimizationfortravelingsalesmanproblem AT yongzhang researchonimprovedantcolonyoptimizationfortravelingsalesmanproblem AT leichen researchonimprovedantcolonyoptimizationfortravelingsalesmanproblem |