Speeding up the ۰-۱ Knapsack Problem Using Shuffled Frog Leaping Algorithm

The knapsack problem is known as a NP-hard problem. The knapsack or rucksack problem consists of determining, given a set of items, each of which has a cost and a value, the number of items included in a collection such that the total cost is less than a given cost and the total value is as large as possible. There is a dynamic programming solution for this problem called the ۰-۱ knapsack. The ۰-۱ knapsack problem restricts the number of individual items to zero or one. The shuffled frog-leaping algorithm (SFLA) has long been considered a meta-heuristic algorithm that derives from how frog groups search for food. SFLA can improve computing performance by letting all frogs participate in memetic evolution and access an excellent ability for global search by adding the self-variation behavior to the frog. This study represents an efficient solution for the ۰-۱ knapsack problem using SFLA. Regarding the parallel nature of most meta-heuristic algorithms, they can be successfully used for speedup. Since it is time-consuming to test all the cases when the problems become larger, Compute Unified Device Architecture (CUDA) is used to implement the solution in parallel. The results of simulating the ۰-۱ knapsack problem using SFLA on the CUDA platform show that the execution time for a parallel solution decreases as the population of frogs increases. For the ۰-۱ Knapsack problem, it is ۲۵۲ times faster than the sequential solution.

Keywords:

Knapsack problem , the ۰-۱ Knapsack Problem , Shuffled Frog Leaping Algorithm , SFLA , CUDA