Shuffled frog leaping algorithm and its application to 0/1 knapsack problem

• Here, a modified discrete shuffled frog leaping algorithm (MDSFL) is proposed to solve 01 knapsack problems.
• Different types of knapsack problem instances are generated to test the convergence property of MDSFLA.
• The result shows that it is very effective in solving small to medium sized knapsack problems.
• Computational experiments with a set of large-scale instances show that the MDSFL can be an efficient alternative for solving tightly constrained 01 knapsack problems.

This paper proposes a modified discrete shuffled frog leaping algorithm (MDSFL) to solve 01 knapsack problems. The proposed algorithm includes two important operations: the local search of the ‘particle swarm optimization’ technique; and the competitiveness mixing of information of the ‘shuffled complex evolution’ technique. Different types of knapsack problem instances are generated to test the convergence property of MDSFLA and the result shows that it is very effective in solving small to medium sized knapsack problems. Further, computational experiments with a set of large-scale instances show that MDSFL can be an efficient alternative for solving tightly constrained 01 knapsack problems.