多种群合作学习的多模态多目标路径规划算法

A multimodal multi-objective path planning algorithm based on multi-swarm cooperative learning

为同时规划出满足多种目标需求的多条可行路径,提高规划路径的鲁棒性与实用性,提出一种基于多种群合作学习的路径规划算法。基于粒子群算法的基本思想,先针对单一种群在多维目标空间内搜索时容易陷入局优的问题,提出基于多目标分解的子种群划分策略,平衡算法在目标空间内各个维度上的搜索能力。再依据地图中栅格点的出入度信息提取关键路径点。在编码阶段,根据关键路径点提供的维度信息,利用实数编码的方式初始化种群,降低解空间大小;在解码阶段,提出利用精英解的解码经验指导可行解的快速搜索,使解码经验能够被有效传递,降低解码的不确定性,提高了算法的寻优能力。最后,将多个种群的搜索结果进行非支配排序,得到满足优化目标的所有路径。实验结果表明:与标准粒子群算法相比,基于解码经验表指导的多种群合作学习算法具有更强的搜索能力和寻优能力,能够解决多模态多目标路径规划问题。

An algorithm based on multi-swarm cooperative learning was proposed to plan multiple optimal paths to meet multiple objectives,which can improve the robustness and practicability of the planned paths.The concept of the particle swarm optimization algorithm served as the algorithm's guidance.First,to address the issue that a single population is easy to trap in local optimum in the multi-dimensional target space,a strategy of sub-swarm division was proposed.The population was divided into many sub-swarms according to the number of objectives,balancing the searching ability of the algorithm in each dimension of the target space.Second,key path points were extracted according to the in-degree and out-degree of the path points in the map.In the coding process,real coding was used to initialize the population.The dimension of the path code was equal to the number of key path points,reducing the size of the solution space.In the decoding process,the decoding experience of the elite solutions guided the fast search for feasible solutions.This method can transfer the decoding experience efficiently and reduce the uncertainty of decoding,which improved the optimization ability of the algorithm.Finally,the search results of all sub-swarms were sorted by the non-dominated sorting method to obtain the paths satisfying the planning objectives.The path planning algorithm based on the multi-swarm cooperative learning outperforms the standard particle swarm optimization algorithm in terms of search and optimization ability and is capable of solving the multimodal multi-objective path planning problem.