Speeding up the ۰-۱ Knapsack Problem Using Shuffled Frog Leaping Algorithm
Publish place: Journal of Advances in Computer Research، Vol: 14، Issue: 2
Publish Year: 1402
نوع سند: مقاله ژورنالی
زبان: English
View: 91
This Paper With 13 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JACR-14-2_002
تاریخ نمایه سازی: 3 مهر 1402
Abstract:
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:
Authors
Farnaz Hoseini
Department of Computer Engineering, Technical and Vocational University (TVU), Tehran, Iran