A novel discrete differential evolution algorithm combining transfer function with modulo operation for solving the multiple knapsack problem

In this paper, an efficient method for solving multiple knapsack problem (MKP) using discrete differential evolution is proposed. Firstly, an integer programming model of MKP suitable for discrete evolutionary algorithm is established. Secondly, a new method for discretizing continuous evolutionary algorithm is proposed based on the combination of transfer function and modulo operation. Therefrom, a new discrete differential evolution algorithm (named TMDDE) is proposed. Thirdly, the algorithm GROA is proposed to eliminate infeasible solutions of MKP. On this basis, a new method for solving MKP using TMDDE is proposed. Finally, the performance of TMDDE using S-shaped, U-shaped, V-shaped, and Taper-shaped transfer functions combined with modulo operation is compared, respectively. It is pointed out that T3-TMDDE which used Taper-shaped transfer function T3 is the best. The comparison results of solving 30 MKP instances show that the performance of T3-TMDDE is better than five advanced evolutionary algorithms. It not only indicates that TMDDE is more competitive for solving MKP, but also demonstrates that the proposed discretization method is an effective method.