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

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