Projects per year
Evolutionary algorithms are well suited for solving the knapsack problem. Some empirical studies claim that evolutionary algorithms can produce good solutions to the 0-1 knapsack problem. Nonetheless, few rigorous investigations address the quality of solutions that evolutionary algorithms may produce for the knapsack problem. This paper focuses on a theoretical investigation of three types of (N+1) evolutionary algorithms that exploit bitwise mutation, truncation selection, plus different repair methods for the 0-1 knapsack problem. It assesses the solution quality in terms of the approximation ratio. Our work indicates that the solution produced by both pure strategy and mixed strategy evolutionary algorithms is arbitrarily bad. Nevertheless, an evolutionary algorithm using helper objectives may produce 1/2-approximation solutions to the 0-1 knapsack problem.
|Publication status||Published - Jul 2014|
|Event||2014 IEEE Congress on Evolutionary Computation (CEC) - Beijing, China, United Kingdom of Great Britain and Northern Ireland|
Duration: 06 Jul 2014 → 11 Jul 2014
|Conference||2014 IEEE Congress on Evolutionary Computation (CEC)|
|Country/Territory||United Kingdom of Great Britain and Northern Ireland|
|Period||06 Jul 2014 → 11 Jul 2014|
FingerprintDive into the research topics of 'A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem'. Together they form a unique fingerprint.
- 1 Finished
Evolutionary Approximation Algorithms for Optimization: Algorithm design and Complexity Analysis
Engineering and Physical Sciences Research Council
01 May 2011 → 31 Oct 2015
Project: Externally funded research