旅行商和覆盖路径规划问题的自适应遗传算法

Adaptive Genetic Algorithm for Traveling Salesman and Coverage Path Planning Problem

针对无人机在区域覆盖中的路径规划问题,对于有障碍物的环境,一种有效方法是将环境分解为多个区域,覆盖所有区域即覆盖整个环境。访问多个区域并回到原点的最短路径看做旅行商问题(TSP),每个区域内部为覆盖路径规划问题(CPP),以上综合问题称为TSP-CPP。为进一步提高规划效率,提出了一种自适应遗传算法,设计了自适应交叉算子和变异算子,随种群个体的适应度动态调整交叉概率和变异概率,保留精英个体;变异方式改为倒置变异,保持种群多样性,加快算法地收敛速度。在4种不同障碍物设置的仿真环境下进行了实验。结果表明,当环境复杂时,上述算法比动态规划法快约3000倍,比基于改进算子的遗传算法快约2倍。

Aiming at the path planning problem of UAVs in area coverage,for the environment with obstacles,an effective method is to decompose the environment into multiple areas,covering all areas means covering the entire environment.The shortest path that visits multiple areas and returns to the origin is regarded as the traveling salesman problem(TSP),and the interior of each area is the coverage path planning problem(CPP).This comprehensive problem is called TSP-CPP.In order to further improve the planning efficiency,an adaptive genetic algorithm is proposed,and an adaptive crossover operator and mutation operator are designed.The crossover probability and mutation probability are dynamically adjusted according to the fitness of the population individuals,so as to retain elite individuals.The mutation method was changed to an inverted mutation to keep population diversity and speed up the convergence of the algorithm.Experiments were carried out in four simulation environments with different obstacle Settings.The results show that the proposed algorithm is about 3000 times faster than the dynamic programming method and about 2 times faster than the genetic algorithm based on improved operators in complex environments.