A Differential Evolution Algorithm with Variable Neighborhood Search for Multidimensional Knapsack Problem

Abstract

This paper presents a differential evolution algorithm with a variable neighborhood search to solve the multidimensional knapsack problem. Unlike the studies employing check and repair operators we employ some sophisticated constraint handling methods to enrich the population diversity by taking advantages of infeasible solution within a predetermined threshold. We propose to a variable neighborhood search employing different mutation strategies to generate the trial population. The proposed algorithm in fact works on a continuous domain but these real-values are converted to 0-1 binary values by using the sigmoid function. In order to enhance the solution quality the differential evolution algorithm with a variable neighborhood search is combined with a binary swap local search algorithm. To the best of our knowledge this is the first reported application of the differential evolution algorithm to solve the multidimensional knapsack problem in the literature. The proposed algorithm is tested on a benchmark instances from the OR-Library. Computational results show its efficiency in solving benchmark instances and its superiority to the best performing algorithms from the literature.