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

 

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.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 accessAccess for SubscribersPurchase this articleComment on this article