1. Application of Hybrid Algorithm Based on Ant Colony Optimization and Sparrow Search in UAV Path Planning
- Author
-
Yangyang Tian, Jiaxiang Zhang, Qi Wang, Shanfeng Liu, Zhimin Guo, and Huanlong Zhang
- Subjects
TSP ,Fusion ,Pheromone ,Dynamic ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2024
- Full Text
- View/download PDF