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

Jun He, Boris Mitavskiy, Yuren Zhou

Allbwn ymchwil: Cyfraniad at gynhadleddAralladolygiad gan gymheiriaid

15 Dyfyniadau(SciVal)

Crynodeb

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.
Iaith wreiddiolSaesneg
Tudalennau141-148
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - Gorff 2014
Digwyddiad2014 IEEE Congress on Evolutionary Computation (CEC) - Beijing, China, Teyrnas Unedig Prydain Fawr a Gogledd Iwerddon
Hyd: 06 Gorff 201411 Gorff 2014

Cynhadledd

Cynhadledd2014 IEEE Congress on Evolutionary Computation (CEC)
Gwlad/TiriogaethTeyrnas Unedig Prydain Fawr a Gogledd Iwerddon
Cyfnod06 Gorff 201411 Gorff 2014

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn