An efficient binary differential evolution algorithm for the multidimensional knapsack problem

摘要

This paper proposes a novel approach for the multidimensional knapsack problem (MDKP) using differential evolution. Firstly, the principle and the pseudo-code of binary differential evolution with hybrid encoding (HBDE) are presented. On the basis of the existing repair operator 2 (RO2), an improved repair operator 3 (RO3) for handling the infeasible solutions of MDKP is developed. Then, combine HBDE with RO3, an efficient algorithm (HBDE-RO3) for MDKP is proposed. Finally, the experiment results of the 138 well-known MDKP benchmarks show that RO3 is advantageous to deal with the infeasible solutions than RO2, and the proposed algorithm HBDE-RO3 has superior performance for solving MDKP than the state-of-the-art algorithms.