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

  • سال انتشار: 1402
  • محل انتشار: مجله پیشرفت در تحقیقات کامپیوتری، دوره: 14، شماره: 2
  • کد COI اختصاصی: JR_JACR-14-2_002
  • زبان مقاله: انگلیسی
  • تعداد مشاهده: 158
دانلود فایل این مقاله

نویسندگان

Farnaz Hoseini

Department of Computer Engineering, Technical and Vocational University (TVU), Tehran, Iran

چکیده

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.

کلیدواژه ها

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

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.