Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization

Abstract

A memetic meta-heuristic called the shuffled frog-leaping algorithm (SFLA) has been developed for solving combinatorial optimization problems. The SFLA is a population-based cooperative search metaphor inspired by natural memetics. The algorithm contains elements of local search and global information exchange. The SFLA consists of a set of interacting virtual population of frogs partitioned into different memeplexes. The virtual frogs act as hosts or carriers of memes where a meme is a unit of cultural evolution. The algorithm performs simultaneously an independent local search in each memeplex. The local search is completed using a particle swarm optimization-like method adapted for discrete problems but emphasizing a local search. To ensure global exploration, the virtual frogs are periodically shuffled and reorganized into new memplexes in a technique similar to that used in the shuffled complex evolution algorithm. In addition, to provide the opportunity for random generation of improved information, random virtual frogs are generated and substituted in the population.The algorithm has been tested on several test functions that present difficulties common to many global optimization problems. The effectiveness and suitability of this algorithm have also been demonstrated by applying it to a groundwater model calibration problem and a water distribution system design problem. Compared with a genetic algorithm, the experimental results in terms of the likelihood of convergence to a global optimal solution and the solution speed suggest that the SFLA can be an effective tool for solving combinatorial optimization problems.