Int. J. of Bio-Inspired Computation   »   2017 Vol.10, No.4



Title: Discrete differential evolutions for the discounted {0-1} knapsack problem


Authors: Hong Zhu; Yichao He; Xizhao Wang; Eric C.C. Tsang


Faculty of Information Technology, Macau University of Science and Technology, Macau, China
College of Information and Engineering, Hebei GEO University, 050031, Shijiazhuang, China
College of Computer Science and Software Engineering, Shenzhen University, 518060, Shenzhen, China
Faculty of Information Technology, Macao University of Science and Technology, Macau, China


Abstract: This paper first proposes a discrete differential evolution algorithm for discounted {0-1} knapsack problems (D{0-1}KP) based on feasible solutions represented by the 0-1 vector. Subsequently, based on two encoding mechanisms of transforming a real vector into an integer vector, two new algorithms for solving D{0-1}KP are given through using integer vectors defined on {0, 1, 2, 3}n to represent feasible solutions of the problem. Finally, the paper conducts a comparative study on the performance between our proposed three discrete differential evolution algorithms and those developed by common genetic algorithms for solving several types of large scale D{0-1}KP problems. The paper confirms the feasibility and effectiveness of designing discrete differential evolution algorithms for D{0-1}KP by encoding conversion approaches.


Keywords: discounted {0-1} knapsack problem; differential evolution; encoding conversion method; repairing and optimisation.


DOI: 10.1504/IJBIC.2017.10008802


Int. J. of Bio-Inspired Computation, 2017 Vol.10, No.4, pp.219 - 238


Submission date: 23 Apr 2017
Date of acceptance: 14 Jun 2017
Available online: 08 Nov 2017



Editors Full text accessPurchase this articleComment on this article