A Heuristics-Guided Simplified Discrete Harmony Search Algorithm for Solving 0-1 Knapsack Problem

The harmony search (HS) algorithm is a novel metaheuristic which has been widely used to solve both continuous and discrete optimization problems. In order to improve the performance and simplify the implementation of the HS algorithm for solving the 0-1 knapsack problem (0-1KP), this paper proposes a heuristics-guided simplified discrete harmony search (SDHS) algorithm which does not use random search operator and has only one intrinsic parameter, harmony memory size. The SDHS algorithm uses a memory consideration operator to construct a feasible solution, and then the constructed solution is further enhanced by a solution-level pitch adjustment operator. Two heuristics, the profit–weight ratio of an item and the profit of an item, are used to greedily guide the memory consideration operator and the solution-level pitch adjustment operator, respectively. In the memory consideration operator, items are considered in non-ascending order of profit–weight ratio assigned from the harmony memory. In the solution-level pitch adjustment operator, items not in the knapsack are attempted to be selected in non-ascending order of profit. The SDHS algorithm outperforms several state-of-the-art algorithms, with an average improvement of 0.55% in the quality of solutions on large problem instances.