Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning
Abstract The Traveling Salesman Problem (TSP) is a classic problem in combinatorial optimization, aiming to find the shortest path that traverses all cities and eventually returns to the starting point. The ant colony optimization algorithm has achieved significant results, but when the number of ci...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2024-11-01
|
| Series: | International Journal of Computational Intelligence Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s44196-024-00652-z |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850064856299864064 |
|---|---|
| author | Yangyang Tian Jiaxiang Zhang Qi Wang Shanfeng Liu Zhimin Guo Huanlong Zhang |
| author_facet | Yangyang Tian Jiaxiang Zhang Qi Wang Shanfeng Liu Zhimin Guo Huanlong Zhang |
| author_sort | Yangyang Tian |
| collection | DOAJ |
| description | Abstract The Traveling Salesman Problem (TSP) is a classic problem in combinatorial optimization, aiming to find the shortest path that traverses all cities and eventually returns to the starting point. The ant colony optimization algorithm has achieved significant results, but when the number of cities increases, the ant colony algorithm is prone to fall into local optimal solutions, making it difficult to obtain the global optimal path. To overcome this limitation, this paper proposes an innovative hybrid ant colony algorithm. Our main motivation is to introduce other optimization strategies to improve the global search ability and convergence speed of the ant colony algorithm in solving TSP problems. We first incorporate the iterative solution of the sparrow search algorithm (SSA) into the ant colony algorithm to provide a better initial pheromone distribution. Second, we improve the pheromone update method to enhance the algorithm’s diversity during the search process and reduce the risk of falling into local optima. Finally, we define a dynamic pheromone evaporation factor to adjust the pheromone evaporation rate according to real-time changes in the search process. Through simulation tests on large-scale TSP problems and practical applications, we find that the hybrid ant colony algorithm outperforms the ant colony algorithm in both accuracy and running time. In Eg.2, the average accuracy of ISSA-ACO is improved by 12%, and the average running time is reduced by 45.6%. This study not only provides a new and effective method for solving large-scale TSP problems but also provides valuable references and insights for the application of ant colony algorithms in solving other complex optimization problems. At the same time, our research further verifies the effectiveness of improving heuristic algorithms by fusing different optimization strategies, providing new ideas and directions for future algorithm design and optimization. |
| format | Article |
| id | doaj-art-0ab8408312ab4181bd5691359f1b942e |
| institution | DOAJ |
| issn | 1875-6883 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Springer |
| record_format | Article |
| series | International Journal of Computational Intelligence Systems |
| spelling | doaj-art-0ab8408312ab4181bd5691359f1b942e2025-08-20T02:49:09ZengSpringerInternational Journal of Computational Intelligence Systems1875-68832024-11-0117112310.1007/s44196-024-00652-zApplication of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path PlanningYangyang Tian0Jiaxiang Zhang1Qi Wang2Shanfeng Liu3Zhimin Guo4Huanlong Zhang5State Grid Henan Electricity Research InstituteCollege of Electrical and Information Engineering, Zhengzhou University of Light IndustryState Grid Henan Electric Power CompanyState Grid Henan Electricity Research InstituteState Grid Henan Electricity Research InstituteCollege of Electrical and Information Engineering, Zhengzhou University of Light IndustryAbstract The Traveling Salesman Problem (TSP) is a classic problem in combinatorial optimization, aiming to find the shortest path that traverses all cities and eventually returns to the starting point. The ant colony optimization algorithm has achieved significant results, but when the number of cities increases, the ant colony algorithm is prone to fall into local optimal solutions, making it difficult to obtain the global optimal path. To overcome this limitation, this paper proposes an innovative hybrid ant colony algorithm. Our main motivation is to introduce other optimization strategies to improve the global search ability and convergence speed of the ant colony algorithm in solving TSP problems. We first incorporate the iterative solution of the sparrow search algorithm (SSA) into the ant colony algorithm to provide a better initial pheromone distribution. Second, we improve the pheromone update method to enhance the algorithm’s diversity during the search process and reduce the risk of falling into local optima. Finally, we define a dynamic pheromone evaporation factor to adjust the pheromone evaporation rate according to real-time changes in the search process. Through simulation tests on large-scale TSP problems and practical applications, we find that the hybrid ant colony algorithm outperforms the ant colony algorithm in both accuracy and running time. In Eg.2, the average accuracy of ISSA-ACO is improved by 12%, and the average running time is reduced by 45.6%. This study not only provides a new and effective method for solving large-scale TSP problems but also provides valuable references and insights for the application of ant colony algorithms in solving other complex optimization problems. At the same time, our research further verifies the effectiveness of improving heuristic algorithms by fusing different optimization strategies, providing new ideas and directions for future algorithm design and optimization.https://doi.org/10.1007/s44196-024-00652-zTSPFusionPheromoneDynamic |
| spellingShingle | Yangyang Tian Jiaxiang Zhang Qi Wang Shanfeng Liu Zhimin Guo Huanlong Zhang Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning International Journal of Computational Intelligence Systems TSP Fusion Pheromone Dynamic |
| title | Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning |
| title_full | Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning |
| title_fullStr | Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning |
| title_full_unstemmed | Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning |
| title_short | Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning |
| title_sort | application of hybrid algorithm based on ant colony optimization and sparrow search in uav path planning |
| topic | TSP Fusion Pheromone Dynamic |
| url | https://doi.org/10.1007/s44196-024-00652-z |
| work_keys_str_mv | AT yangyangtian applicationofhybridalgorithmbasedonantcolonyoptimizationandsparrowsearchinuavpathplanning AT jiaxiangzhang applicationofhybridalgorithmbasedonantcolonyoptimizationandsparrowsearchinuavpathplanning AT qiwang applicationofhybridalgorithmbasedonantcolonyoptimizationandsparrowsearchinuavpathplanning AT shanfengliu applicationofhybridalgorithmbasedonantcolonyoptimizationandsparrowsearchinuavpathplanning AT zhiminguo applicationofhybridalgorithmbasedonantcolonyoptimizationandsparrowsearchinuavpathplanning AT huanlongzhang applicationofhybridalgorithmbasedonantcolonyoptimizationandsparrowsearchinuavpathplanning |