2019，55（20）
1 引言
最短路径问题是图论中的一个经典问题，Dijk stra
算法、Floyd 算法等精确算法均能在多项式时间内求得
一个拓扑图中任意两点间的最短路径。在一些实际场
景中，诸如车载导航、网络路由、物流配送等不仅要求从
源节点到目的节点的最短路径，还要求这两点间的次
求解必经点 k 条最优路径问题的粒子群优化算法
马 炫
1，2
，刘 栋
1
，胡家鑫
1
1. 西安理工大学 自动化与信息工程学院，西安 710048
2. 陕西省复杂系统控制与智能信息处理重点实验室，西安 710048
摘 要：提出了一种解决指定必经点
k
条最优路径问题的粒子群优化算法。算法以
k
条最优路径集合作为优化目
标，将粒子种群划分为
k
个子种群，通过各子种群的局部搜索和子种群间的相互协作，使种群在搜索过程中易于找
到
k
条最优路径。为了提高含有多必经节点的初始生成路径的多样性，设计了基于弹性拉伸原理的种群初始化方
法。在随机生成的 26 个节点 65 条边，50 个节点 262 条边和 80 个节点 41 0 条边的拓扑图中，分别选取不同的源节点
和目的节点，以及必经节点对算法进行了测试。数值实验结果表明，提出的算法在求解网络规模比较大、必经点数
比较多的无环
k
条最优路径问题中具有比较好的性能。
关键词：k 条最优路径 ；必经点；粒子群优化算法
文献标志码：A 中图分类号：TP301 doi：10.3778/j.issn. 100 2-8331.1806-0331
马炫，刘栋，胡家鑫 . 求解必经点
k
条最优路径问题的粒子群优化算法 . 计算机工程与应用，2019，55（20）：89-94.
MA Xuan, LIU Dong, HU Jiaxin. Particle swarm optimization for solving problem of
k
-shortest paths via desig nated
poi nts. Computer En gineering and Applic atio ns, 2019, 55（20）：89-94.
Particle Swar m Op timization for Solving Problem of
k
-Shortest Paths via Designated Poin ts
MA Xuan
1，2
, LIU Dong
1
, H U Jiaxin
1
1.School of Automation and Information En gineering, Xi’an University of Technology, Xi’an 710 048 , China
2.Key Laboratory of Shaanxi Province for Complex System Control and Intelligent Information P rocessing, Xi’an
710048, Chin a
Ab stract：A particle sw arm optimization algorithm is proposed to solve the problem of the k -shortest paths via designated
poi nts. The k -s hortest path set is taken a s the optimizatio n objective. The p article population is divided into k subpopula-
tions, and thr oug h the local search of each su bpo pulation and the coll aboration among subpopulations, it is easy for t he
population to find
k
-shortest paths in the search process. In order to enhance the diversity of the initial path with designated
poi nts, a population initialization method based on elastic stretching principl e is d esigned. In the topological graph of ran-
domly generated 26 nodes with 65 edges, 50 nodes with 262 edges and 80 nodes with 410 edges, different source node
and destina tion node and designated points are selected for testing. The experimental results show that the proposed algo-
rithm has better performance i n solving the problem of the ring-free
k
-shortest p aths with larger network size and mor e
designated points.
Key words：
k
-shortest paths; desig nated points; particle swa rm opti miz atio n
⦾模式识别与人工智能⦾
作者简介：马炫（1962—），男，工学博士，教授，研究领域为智能计算和模式识别，E-mail：maxuan@xaut.edu.cn；刘栋（1 992—），女，
硕士研究生，研究领域为进化计算；胡家鑫（1989—），男，硕士研究生，研究领域为进化计算。
收稿日期：2018-0 6-27 修回日期：2018-11-05 文章编号：100 2-8331（2019）20-0089-06
CN KI 网络出版：201 8-11-26, http://kns.cnki. net/kcm s/detail/11.2127.tp.20181123.1048.008.html
Computer Engineering and Applications 计算机工程与应用
89
评论1