Lévy Flight Shuffle Frog Leaping Algorithm Based on Differential Perturbation and Quasi-Newton Search

Xinming Zhang, Zihao Fu, Haiyan Chen, Wentao Mao, Shangwang Liu, Guoqi LiuIEEE Access 2019 · DOI

Abstract

The Lévy flight Shuffle Frog Leaping Algorithm (LSFLA) is a variant of the Shuffled Frog Leaping Algorithm (SFLA) that significantly enhances performance. However, it still suffers from defects such as poor convergence and low efficiency. This paper proposes an improved version, the LSFLA based on Differential perturbation and Quasi-Newton search (DQLSFLA). DQLSFLA introduces an all-solution updating method to replace the traditional worst-solution update, reducing computational complexity and omitting redundant sorting steps. Furthermore, it employs a hybrid subgroup strategy combining random differential perturbation and an improved Lévy flight method to balance global exploration and local exploitation. Finally, a quasi-Newton local search is integrated to accelerate convergence in the final stages. Experimental results on the CEC-2014 test suite and real-world applications, including medical image enhancement and the Quadratic Assignment Problem (QAP), demonstrate that DQLSFLA outperforms LSFLA and other state-of-the-art algorithms in both optimization quality and efficiency.

Introduction

Intelligent Optimization Algorithms (IOAs) are essential tools in artificial intelligence, designed to solve complex, non-linear problems by mimicking natural processes. The Shuffled Frog Leaping Algorithm (SFLA) is a prominent example, simulating a group of frogs searching for the best food source. While effective, SFLA and its variants like LSFLA often struggle with low efficiency due to frequent sorting, premature convergence into local optima, and high sensitivity to parameter settings.

The DQLSFLA was developed to address these bottlenecks, creating a more robust optimizer capable of handling high-dimensional challenges in fields ranging from logistics to medical imaging.

Methodology: The DQLSFLA Framework

The DQLSFLA introduces three primary innovations to the standard frog-leaping paradigm to enhance its search capabilities and speed.

1. All-Solution Updating

Traditional SFLA variants typically update only the "worst" frog in a subgroup during each iteration. This requires the algorithm to re-sort the population constantly to identify the worst performer, a computationally expensive process. DQLSFLA replaces this with an all-solution updating mechanism. By updating every frog in a subgroup simultaneously, the algorithm eliminates the sorting step at every sub-iteration, reduces overhead, and facilitates parallel computing architectures.

2. Hybrid Subgroup Strategy

To maintain a balance between "exploration" (searching new areas) and "exploitation" (refining known solutions), DQLSFLA splits each subgroup into two halves:

  • First Half: Utilizes a Random Differential Perturbation approach. This maintains population diversity and prevents the algorithm from getting trapped in local optima.
  • Second Half: Employs an Improved Lévy Flight method. This uses a combination of small steps and occasional long jumps, allowing the frogs to navigate the search space more effectively than standard random walks.
Conceptual framework of the DQLSFLA algorithm

Bio-inspired algorithms are excellent at finding the general vicinity of a global optimum but often lack the precision to find the exact peak. DQLSFLA addresses this by triggering a Quasi-Newton local search during the final 3% of the evaluation budget. This mathematical "finishing move" provides the high-precision refinement necessary for complex engineering problems.

Experimental Evaluation and Results

The algorithm was rigorously tested against three distinct benchmarks to verify its versatility and power.

CEC-2014 Benchmark Performance

On the CEC-2014 test suite, which includes 30 complex mathematical functions, DQLSFLA achieved the best average rank (2.43) among 11 state-of-the-art algorithms. Notably, in 50-dimensional tests, DQLSFLA completed its optimization in 22.1 seconds, a 31% reduction in runtime compared to the 32.2 seconds required by the baseline LSFLA.

Real-World Applications

  • Medical Image Enhancement: When applied to chest bone fluoroscopic and blood vessel images, DQLSFLA produced higher objective evaluation scores ($F(Z)$) than LSFLA, resulting in significantly clearer textures and better contrast.
  • Quadratic Assignment Problem (QAP): In logistics optimization (assigning 20 facilities to 40 locations), DQLSFLA found lower-cost solutions with higher stability and lower standard deviation than competing methods.

Conclusion

DQLSFLA represents a significant step forward in bio-inspired optimization. By streamlining the update process and combining stochastic search with rigorous local refinement, it achieves a superior balance of speed and accuracy. Future research will focus on making the transition to the Quasi-Newton phase more adaptive and applying the algorithm to broader engineering design and resource scheduling challenges.

Summary updated

Abstract

Lévy flight Shuffle Frog Leaping Algorithm (LSFLA) is a SFLA variant and enhances the performance of SFLA largely, however, it still has some defects, such as poor convergence and low efficiency. So an improved LSFLA, namely, LSFLA based on Differential perturbation and Quasi-Newton search (DQLSFLA), is proposed in this paper. Firstly, the way of updating only one solution which is the worst one at every sub-iteration in LSFLA is replaced with an all-solution updating way in the subgroup to improve the probability of obtaining the best solution, to omit one sorting step at every sub-iteration and the sub-iteration number parameter setting, to reduce the computational complexity and to enhance the optimization efficiency. Secondly, a random differential perturbation approach and an improved Lévy flight updating one are created and used in the subgroup updating to form DLSFLA, that is, the first half frogs in the subgroup use the random differential perturbation updating approach to improve the global search ability, and the last half adopt the improved Lévy flight updating method to keep the advantage of the Lévy flight updating method and overcome its defects. Finally, quasi-Newton local search is integrated into DLSFLA near the end of the algorithm to improve the convergence speed. Experimental results on the complex functions from CEC-2014 show that DQLSFLA's convergence quality and optimization efficiency are much better than LSFLA's and that compared with quite a few other state-of-the-art algorithms, DQLSFLA has better performance. The results on medical image enhancement and Quadratic Assignment Problem (QAP) also show that DQLSFLA can solve the real word optimization problems better than LSFLA can.
BibTeX
@inproceedings{zhang2019levy,
  author = {Xinming Zhang and Zihao Fu and Haiyan Chen and Wentao Mao and Shangwang Liu and Guoqi Liu},
  title = {{Lévy Flight Shuffle Frog Leaping Algorithm Based on Differential Perturbation and Quasi-Newton Search}},
  booktitle = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2936254},
}
Figure