Improved genetic algorithm based on K-Means to solve path planning problem

摘要

This paper regarded the path planning problem as a TSP problem, and an improved genetic algorithm based on K-Means was proposed. The algorithm firstly decomposes the large-scale TSP problem into multiple small TSP problems through K-Means clustering, and then optimizes each cluster separately using the improved genetic algorithm, and finally merges all clusters to obtain the final route. Experiments show that compared with the standard genetic algorithm, the improved algorithm avoids the solution falling into the local optimal solution and accelerates the convergence of the algorithm. Therefore, this algorithm can save cost and improve efficiency when applied to path planning.