A Novel Binary Artificial Jellyfish Search Algorithm for Solving 0-1 Knapsack Problems

Abstract

The knapsack problem is an NP-hard combinatorial optimization problem for which it is difficult to find a polynomial-time solution. Many researchers have used metaheuristic algorithms that find a near-optimal solution in a reasonable amount of time to solve this problem. Discreteness is required in order to use metaheuristic algorithms in solving binary problems. The Artificial Jellyfish Search (AJS) algorithm is a recently proposed metaheuristic algorithm. The algorithm was created by modeling the foraging behavior of jellyfish in the ocean. AJS has been used mostly for the solution of continuous optimization problems in the literature, and studies on its performance on binary problems are limited. While this study aims to contribute to the literature by proposing a binary version of AJS (Bin_AJS) for the solution of knapsack problems, the effects of eight different transfer functions and five different mutation ratios were examined, and the ideal mutation ratio and transfer function were determined for each dataset. It was found that Bin_AJS, which was examined for two different datasets consisting of a total of forty knapsack problems, reached the optimal value in 97.5% of the problems. According to the Friedman test results, Bin_AJS ranked first in Dataset 1 and second in Dataset 2 when compared to other algorithms in the literature. All the comparisons and statistical tests showed that the algorithm is a successful, competitive, and preferable binary algorithm for knapsack problems.