A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem

Jun He, Boris Mitavskiy, Yuren Zhou

Research output: Contribution to conferenceOtherpeer-review

15 Citations (SciVal)

Abstract

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.
Original languageEnglish
Pages141-148
DOIs
Publication statusPublished - Jul 2014
Event2014 IEEE Congress on Evolutionary Computation (CEC) - Beijing, China, United Kingdom of Great Britain and Northern Ireland
Duration: 06 Jul 201411 Jul 2014

Conference

Conference2014 IEEE Congress on Evolutionary Computation (CEC)
Country/TerritoryUnited Kingdom of Great Britain and Northern Ireland
Period06 Jul 201411 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.

Cite this