求解必经点k条最优路径问题的粒子群优化算法

来源：计算机工程与应用杂志2019年第20期北京时间：

作者：马炫，刘栋，胡家鑫

单位：1.西安理工大学 自动化与信息工程学院，西安 710048；2.陕西省复杂系统控制与智能信息处理重点实验室，西安 710048

摘要：提出了一种解决指定必经点[k]条最优路径问题的粒子群优化算法。算法以[k]条最优路径集合作为优化目标，将粒子种群划分为[k]个子种群，通过各子种群的局部搜索和子种群间的相互协作，使种群在搜索过程中易于找到[k]条最优路径。为了提高含有多必经节点的初始生成路径的多样性，设计了基于弹性拉伸原理的种群初始化方法。在随机生成的26个节点65条边，50个节点262条边和80个节点410条边的拓扑图中，分别选取不同的源节点和目的节点，以及必经节点对算法进行了测试。数值实验结果表明，提出的算法在求解网络规模比较大、必经点数比较多的无环[k]条最优路径问题中具有比较好的性能。

关键词：[k]条最优路径,必经点,粒子群优化算法