Speeding up the 0–1 knapsack problem using Flying Fox Optimization Algorithm
Discover Applied Sciences · 06.06.2026 · 8 (9)
DOI: 10.1007/s42452-026-08831-7 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discover Applied Sciences, online erschienen am 06.06.2026. Verfasst von Farnaz Hoseini und 1 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
The 0–1 Knapsack Problem is a classical NP-hard combinatorial optimization problem widely used as a benchmark for evaluating optimization algorithms. In this study, the Flying Fox Optimization Algorithm (FFOA), a nature-inspired metaheuristic based on the collective foraging behavior of flying foxes, is applied to solve the 0–1 knapsack problem and accelerated through parallel computing. The algorithm was implemented in both sequential and parallel modes using MATLAB with CUDA-enabled GPU support in order to evaluate the computational benefits of parallel execution. In the proposed parallel framework, the population of flying foxes (candidate solutions) is divided into computational blocks, and the evaluation of the objective function and population updates are executed concurrently on GPU cores. The performance of the proposed approach was evaluated on 20 standard benchmark instances from the KPI dataset with problem sizes ranging from 50 to 500 items. Each instance was solved in 10 independent runs, and several performance metrics including best solution value, average value, standard deviation, execution time, and error rate were recorded. The results show that the proposed Parallel FFOA consistently achieves near-optimal solutions with error rates below 0.5% and low standard deviation values (2.17–12.91), indicating high robustness and stability. In terms of computational efficiency, the average execution time ranged from 0.35 to 1.72 s depending on the problem size. Moreover, the parallel implementation significantly improves performance for large populations; when the number of flying foxes reached 4000–5000, the algorithm achieved a maximum speedup of 1.92 compared with the sequential CPU implementation. These results demonstrate that the proposed parallel FFOA provides an efficient and scalable approach for solving large-scale 0–1 knapsack problems by effectively exploiting GPU-based parallel computing. GPU-accelerated Parallel FFOA achieves up to 92% reduction in execution time for large-scale knapsack problems. Nature-inspired flying-fox foraging behavior provides a powerful metaheuristic for resource optimization. Parallel FFOA delivers near-optimal solutions with error rates below 0.5% across 20 KPI benchmark instances. Robust and stable performance validated by low standard deviation across repeated runs. Scalable and efficient solution with execution times between 0.35 and 1.72 s for 50–500 item problems.
Zitieren
APA
Hoseini, F., & Mirzaei, A. (2026). Speeding up the 0–1 knapsack problem using Flying Fox Optimization Algorithm. Discover Applied Sciences, 8(9). https://doi.org/10.1007/s42452-026-08831-7
Vancouver
Hoseini F, Mirzaei A. Speeding up the 0–1 knapsack problem using Flying Fox Optimization Algorithm. Discover Applied Sciences. 2026;8(9). doi:10.1007/s42452-026-08831-7
BibTeX
@article{Hoseini2026,
author = {Hoseini, Farnaz and Mirzaei, Abbas},
title = {Speeding up the 0–1 knapsack problem using Flying Fox Optimization Algorithm},
journal = {Discover Applied Sciences},
year = {2026},
volume = {8},
number = {9},
doi = {10.1007/s42452-026-08831-7}
}
EUVIMED