A Binary Hiking Optimization Algorithm for 0/1 Knapsack Problem

Abstract

 The 0/1 knapsack problem is one of the prominent NP-hard binary optimization problems. Solving such problems using exact methods can be computationally expensive. Therefore, metaheuristic methods which offer optimal or near optimal solutions in a reasonable time, are commonly utilized for such tasks. The Hiking Optimization Algorithm (HOA) is a recently proposed metaheuristic optimization algorithm that is inspired by the similarity between the hikers’ navigation of steep terrain and the search process within the optimization problem’s search space. However, the basic algorithm is initially proposed for continuous optimization problems. To apply the algorithm to binary optimization tasks, certain adaptations are required. One of the commonly used binarization techniques involves using a transfer function to convert continuous decision variables into binary counterparts. In this study, HOA is binarized using four different variants for each of the following transfer function types: S-shaped, U-shaped, Z-shaped, and T-shaped. Furthermore, a repair function is adopted to tackle the infeasible solutions produced by the algorithm. The performance of the proposed binary HOA (binHOA) algorithm is assessed on two standard benchmark datasets. The results are compared with the binary versions of the well-known optimization algorithms. The experimental results indicate that the proposed binary version of HOA is a competitive alternative for the 0/1 knapsack problem.