An Improved Shuffled Frog-Leaping Algorithm to Solving 0–1 Knapsack Problem

Abstract

To address the problems of slow convergence, low search accuracy, and easy fall into local optimum, and generating a large number of infeasible solutions when solving the 0–1 Knapsack Problem, which makes it difficult to obtain the optimal solution scheme, in this paper, we present a greedy induced mutation method for locally optimal solutions, namely, an improved Shuffled Frog Leaping Algorithm (Shuffled Frog Leaping Algorithm based on Greedy Algorithm and Mutation, SFLA-GA-M). First, the proposed algorithm adjusts the population generation of individuals in the SFLA to avoid infeasible solutions, thereby optimizing the local update strategy. Secondly, an induced mutation mechanism that incorporates both greedy algorithms and genetic algorithms is introduced to enhance the search accuracy of the algorithm. Finally, ten classical 0–1 Knapsack Problem cases were selected to prove the feasibility and robustness of the proposed SFLA-GA-M by comparing with other two SFLA variants, which are MDSFLA, DSFLA. Meanwhile, to further verify the performance of the SFLA-GA-M, two classical 0–1 KPs with multi-dimensional test cases were introduced by compared with other five algorithm: DEA, PSO, GA, BMA and IFMA, respectively. The experimental results show that SFLA-GA-M has achieved stronger convergence and stability compared to DEA, PSO, and GA, and it has displayed better search efficiency and a superior global search capability than BMA and IFMA in solving large-sized 0–1 Knapsack Problem.

Keywords

• Shuffled frog leaping algorithm
• genetic algorithm
• mutation
• 0-1 knapsack problem