A Shuffled Frog Leaping Algorithm for k-Shortest Paths Problem

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.