Projects per year
Abstract
Evolutionary algorithms are well suited for solving the knapsack problem. Some empirical studies claim that evolutionary algorithms can produce good solutions to the 01 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 01 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/2approximation solutions to the 01 knapsack problem.
Original language  English 

Pages  141148 
DOIs  
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
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 
Fingerprint
Dive into the research topics of 'A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem'. Together they form a unique fingerprint.Projects
 1 Finished

Evolutionary Approximation Algorithms for Optimization: Algorithm design and Complexity Analysis
He, J.
Engineering and Physical Sciences Research Council
01 May 2011 → 31 Oct 2015
Project: Externally funded research