[1]赵礼峰,于汶雨. 一种求解K最短路径问题的新算法[J].计算机技术与发展,2015,25(11):67-70.
　ZHAO Li-feng,YU Wen-yu. A New Algorithm for Solving K Shortest Path Problem[J].,2015,25(11):67-70.
点击复制

 一种求解K最短路径问题的新算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
25
期数:
2015年11期
页码:
67-70
栏目:
智能、算法、系统工程
出版日期:
2015-11-10

文章信息/Info

Title:
 A New Algorithm for Solving K Shortest Path Problem
文章编号:
1673-629X（2015)11-0067-04
作者:
 赵礼峰; 于汶雨
 南京邮电大学 理学院
Author(s):
 ZHAO Li-feng; YU Wen-yu
关键词:
 ; 混合蛙跳算法; 种群分割; 学习策略; K最短路径
Keywords:
 ; Shuffled Frog Leaping Algorithm (SFLA); segmentation population; learning strategy; K shortest path
分类号:
TP301.6
文献标志码:
A
摘要:
 种群分割是混合蛙跳算法的重要组成部分,不同的种群分割方法对混合蛙跳算法的收敛速度的影响不同.文中首先在原始混合蛙跳算法基础上,提出一种新的种群分割方法,使得每个族群中的个体适应度趋近均衡.然后结合Yen算法的偏离路径思想提出一种新的学习策略,对算法迭代方法进行改进.改进后的混合蛙跳算法适用于求解K最短路径问题.最后对改进后的算法进行仿真实验.首先选取单调递归的Dijkstra算法对改进算法可行性进行验证,结果表明改进后的算法是可行的;再选取遗传算法与改进算法进行对比,结果表明改进后的算法在寻优精确度、时间效率和稳定性方面均优于遗传算法.
Abstract:
 Population segmentation is an important part of shuffled frog leaping algorithm of which convergence rate is affected by differ-ent population segmentation methods. A new segmentation method on the basis of the original SFLA is proposed in this paper so that the individual fitness in each ethnic group approaches equilibrium. Then present a new learning strategy combined with the deviated path idea of the Yen algorithm to improve the algorithm’ s iterative method. The improved shuffled frog leaping algorithm is suitable to solve the K-shortest path problem. Finally,do the simulation for the improved algorithm. Firstly,the monotonous recursive Dijkstra algorithm is se-lected to verify the feasibility of the improved algorithm and the results show that the improved algorithm is feasible. And then the genetic algorithm is selected to compare with the improved algorithm,and the results show that the improved algorithm’ s optimization accuracy, time efficiency and stability is superior to the genetic algorithm.

相似文献/References:

[1]熊伟平 曾碧卿.几种仿生优化算法的比较研究[J].计算机技术与发展,2010,(03):9.
　XIONG Wei-ping,ZENG Bi-qing.Studies on Some Bionic Optimization Algorithms[J].,2010,(11):9.
[2]代永强,王联国.PSO和SFLA混合优化算法[J].计算机技术与发展,2014,24(04):77.
　DAI Yong-qiang,WANG Lian-guo.Hybrid Optimization Algorithm of PSO and SFLA[J].,2014,24(11):77.
[3]张志宏,吴庆波,邵立松,等.基于飞腾平台TOE协议栈的设计与实现[J].计算机技术与发展,2014,24(07):1.
　ZHANG Zhi-hong,WU Qing-bo,SHAO Li-song,et al. Design and Implementation of TCP/IP Offload Engine Protocol Stack Based on FT Platform[J].,2014,24(11):1.
[4]梁文快,李毅. 改进的基因表达算法对航班优化排序问题研究[J].计算机技术与发展,2014,24(07):5.
　LIANG Wen-kuai,LI Yi. Research on Optimization of Flight Scheduling Problem Based on Improved Gene Expression Algorithm[J].,2014,24(11):5.
[5]黄静,王枫,谢志新,等. EAST文档管理系统的设计与实现[J].计算机技术与发展,2014,24(07):13.
　HUANG Jing,WANG Feng,XIE Zhi-xin,et al. Design and Implementation of EAST Document Management System[J].,2014,24(11):13.
[6]侯善江[],张代远[][][]. 基于样条权函数神经网络P2P流量识别方法[J].计算机技术与发展,2014,24(07):21.
　HOU Shan-jiang[],ZHANG Dai-yuan[][][]. P2P Traffic Identification Based on Spline Weight Function Neural Network[J].,2014,24(11):21.
[7]李璨,耿国华,李康,等. 一种基于三维模型的文物碎片线图生成方法[J].计算机技术与发展,2014,24(07):25.
　LI Can,GENG Guo-hua,LI Kang,et al. A Method of Obtaining Cultural Debris’ s Line Chart Based on Three-dimensional Model[J].,2014,24(11):25.
[8]翁鹤,皮德常. 混沌RBF神经网络异常检测算法[J].计算机技术与发展,2014,24(07):29.
　WENG He,PI De-chang. Chaotic RBF Neural Network Anomaly Detection Algorithm[J].,2014,24(11):29.
[9]刘茜[],荆晓远[],李文倩[],等. 基于流形学习的正交稀疏保留投影[J].计算机技术与发展,2014,24(07):34.
　LIU Qian[],JING Xiao-yuan[,LI Wen-qian[],et al. Orthogonal Sparsity Preserving Projections Based on Manifold Learning[J].,2014,24(11):34.
[10]尚福华,李想,巩淼. 基于模糊框架-产生式知识表示及推理研究[J].计算机技术与发展,2014,24(07):38.
　SHANG Fu-hua,LI Xiang,GONG Miao. Research on Knowledge Representation and Inference Based on Fuzzy Framework-production[J].,2014,24(11):38.
[11]刘立群[],韩俊英[],代永强[],等. 果蝇优化算法优化性能对比研究[J].计算机技术与发展,2015,25(08):94.
　LIU Li-qun[],HAN Jun-ying[],DAI Yong-qiang[],et al. Comparative Study on Optimization Performance of Fruit Fly Optimization Algorithm [J].,2015,25(11):94.

更新日期/Last Update: 2016-01-05