一种求解K最短路径问题的新算法

来源：计算机技术与发展杂志2015年第11期北京时间：

作者：赵礼峰;于汶雨

摘要：种群分割是混合蛙跳算法的重要组成部分,不同的种群分割方法对混合蛙跳算法的收敛速度的影响不同.文中首先在原始混合蛙跳算法基础上,提出一种新的种群分割方法,使得每个族群中的个体适应度趋近均衡.然后结合Yen算法的偏离路径思想提出一种新的学习策略,对算法迭代方法进行改进.改进后的混合蛙跳算法适用于求解K最短路径问题.最后对改进后的算法进行仿真实验.首先选取单调递归的Dijkstra算法对改进算法可行性进行验证,结果表明改进后的算法是可行的;再选取遗传算法与改进算法进行对比,结果表明改进后的算法在寻优精确度、时间效率和稳定性方面均优于遗传算法.

关键词：混合蛙跳算法;种群分割;学习策略;K最短路径