A Thermodynamical Selection-Based Discrete Differential Evolution for the 0-1 Knapsack Problem

Many problems in business and engineering can be modeled as 0-1 knapsack problems. However, the 0-1 knapsack problem is one of the classical NP-hard problems. Therefore, it is valuable to develop effective and efficient algorithms for solving 0-1 knapsack problems. Aiming at the drawbacks of the sel...

Full description

Saved in:
Bibliographic Details
Published in:Entropy (Basel, Switzerland) Switzerland), 2014-12, Vol.16 (12), p.6263-6285
Main Authors: Guo, Zhaolu, Yue, Xuezhi, Zhang, Kejun, Wang, Shenwen, Wu, Zhijian
Format: Article
Language:English
Subjects:
0-1 knapsack problem
Algorithms
Balancing
Business
differential evolution
discrete optimization
Entropy
Evolution
Free energy
Gain
Knapsack problem
Operators
thermodynamical selection
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many problems in business and engineering can be modeled as 0-1 knapsack problems. However, the 0-1 knapsack problem is one of the classical NP-hard problems. Therefore, it is valuable to develop effective and efficient algorithms for solving 0-1 knapsack problems. Aiming at the drawbacks of the selection operator in the traditional differential evolution (DE), we present a novel discrete differential evolution (TDDE) for solving 0-1 knapsack problem. In TDDE, an enhanced selection operator inspired by the principle of the minimal free energy in thermodynamics is employed, trying to balance the conflict between the selective pressure and the diversity of population to some degree. An experimental study is conducted on twenty 0-1 knapsack test instances. The comparison results show that TDDE can gain competitive performance on the majority of the test instances.
ISSN:1099-4300
1099-4300
DOI:10.3390/e16126263