基于回溯蚁群-粒子群混合算法的多点路径规划  

Multi-point path planning based on the algorithm of colony-particle swarm optimization

作　　者：刘丽珏[1] 罗舒宁 高琰[1] 陈美妃 LIU Lijue;LUO Shuning;GAO Yan;CHEN Meifei(School of Information Science and Engineering,Central South University,Changsha 410083,China)

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《通信学报》2019年第2期102-110,共9页Journal on Communications

基　　金：国家科技重大专项基金资助项目(No.2013FY110800);长沙计划科技基金资助项目(No.kq1606004)~~

摘　　要：景区多点路径规划问题是一个NP-hard问题,相当于寻找经过起始点和特定节点的最短路径。针对多点路径规划问题,提出了回溯蚁群-粒子群混合算法,该算法运用弗洛伊德(Floyd-Warshall)算法将图进行转换并且结合了蚁群算法和粒子群算法寻找最短路径。实验结果表明,此算法可以在小规模数据下快速找到精确解,同时,在较大规模数据量下,可以得到比最大最小蚁群算法和遗传算法更好的结果。The problem of multi-point path planning is a NP-hard problem,which is equivalent to finding the shortest path of a starting point and some specific node.Aiming at the problem of multi-point path planning,a retrospective ant colony-particle swarm optimization algorithm was proposed.This algorithm used Floyd-Warshall to transform the graph and combined ant colony algorithm and particle swarm algorithm to find the shortest path.The experimental results show that this algorithm can find the precise solution under small data,at the same time,under a large amount of data,can be better than the maximum minimum ant colony algorithm and genetic algorithm.

关 键 词：NP-HARD问题 最大最小蚁群系统 弗洛伊德算法 粒子群算法 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]