摘要
提出了一种求解k条最短路径问题的混合蛙跳算法.采用自然路径的形式对青蛙个体编码,设计了一种能够使模因信息在青蛙个体间传递的蛙跳方法.在各青蛙族群内部,通过较差个体向优秀个体的跳跃进行局部搜索,从而优化模因信息.在族群之间,通过混合与排序使各族群的模因信息得以交流与重组,从而获取新的寻优方向.数值实验表明,本文算法搜索k条最短路径的能力强、收敛速度快、稳定性好,可应用于求解大规模网络中的多条最优路径问题.
A shuffled frog leaping algorithm for solving k-shortest paths problem is proposed.The algorithm uses the form of natural route to encode frog individual.A method of carrying out leaping behavior of frog is designed to transmit meme information among frogs.In each memeplex,the meme information of frog individuals is optimized by the local search realized through the leaping from the worse individuals to the better ones.New searching orientation of each memeplex is made by shuffling all memeplexes together and sorting them,to exchange and recombine meme information with other memeplexes.The simulation results show that the proposed algorithm performs better in searching k-shortest paths with high converging speed and stability.It can be applied to large-scale networks to solve the problem of finding multiple optimal paths.
出处
《信息与控制》
CSCD
北大核心
2011年第5期614-618,共5页
Information and Control
基金
陕西省教育厅专项科研计划资助项目(09JK641)
关键词
混合蛙跳算法
最短路径
局部搜索
shuffled frog leaping algorithm
shortest path
local search
