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

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

Addresses: 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.087924

International Journal of Bio-Inspired Computation, 2017 Vol.10 No.4, pp.219 - 238

Received: 26 Apr 2017
Accepted: 14 Jun 2017

Published online: 10 Nov 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article