Solving 0-1 Bi-Objective Multi-dimensional Knapsack Problems Using Binary Genetic Algorithm

Abstract

The multi-dimensional knapsack problem (MDKP) is a well-known NP-hard problem in combinatorial optimization. As it has various real-life applications the MDKP has been intensively studied in the literature. On the other hand far too little attention has been paid to the multi-objective version of the MDKP. In this chapter we consider the bi-objective multi-dimensional knapsack problem (BOMDKP). We propose a Binary Genetic Algorithm (BGA) with an external archive for the problem. Our proposed BGA algorithm also employs a binary local search. The non-dominated solution sets are obtained for various bi-objective benchmark instances with 100 250 500 and 750 items by employing the proposed BGA. Then the performance of the BGA is compared with other multi-objective algorithms from the literature i.e. MOEA/D and MOFPA. Furthermore it is observed that the Pareto-optimal solution set provided by Zitzler and Laumans for 500 items and 2 knapsacks includes 30 dominated solutions. Also the Pareto-optimal solutions for the scenario with 750 items are not reported in Zitzler and Thiele [43]. Hence the true Pareto-optimal solution sets are found for all benchmark problem instances using Improved Augmented Epsilon Constraint (AUGMECON2) method. The non-dominated solution sets of the BGA MOEA/D and MOFPA are compared with the Pareto-optimal solution sets for all test instances. The computational results indicate that the proposed BGA is more effective to solve the BOMDKP than the best-performing algorithms from the literature. © 2020 Elsevier B.V. All rights reserved.