Binary Mother Tree Optimization Algorithm for 0/1 Knapsack Problem

The knapsack problem is a well-known strongly NP-complete problem where the profits of collection of items in knapsack is maximized under a certain weight capacity constraint. In this paper, a novel Binary Mother Tree Optimization Algorithm (BMTO) and Knapsack Problem Framework (KPF) are proposed to find an efficient solution for 0/1 knapsack problem in a short time. The proposed BMTO method is built on the original MTO and a binary module to solve an optimization problem in a discrete space. The binary module converts a set of real numbers equal to the dimension of the knapsack problem to a binary number using a threshold and the sigmoid function. In fact, the KPF makes the implementation of a metaheuristic algorithm to solve the knapsack problem much simpler. In order to assess the performance of the proposed solutions, extensive experiments are conducted. In this regard, several statistical analyses on the resulting solution are evaluated when solved for two sets of knapsack instances (small and large scale). The results demonstrate that BMTO can produce an efficient solution for knapsack instances of different sizes in a short time, and it outperforms two other algorithms Binary Particle Swarm Optimization (BPSO) and Binary Bacterial Foraging (BBF) algorithms in terms of best solution and time. In addition, the results of BPSO and BBF show the effectiveness of KPF compared to the results in the literature.