Neidio i’r brif dudalen lywio Neidio i chwilio Neidio i’r prif gynnwys

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

  • Jun He
  • , Boris Mitavskiy
  • , Yuren Zhou
  • South China University of Technology

Allbwn ymchwil: Cyfraniad at gynhadledd › Arall › adolygiad gan gymheiriaid

16 Dyfyniadau (Scopus)

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 2014 → 11 Gorff 2014

Cynhadledd

Cynhadledd2014 IEEE Congress on Evolutionary Computation (CEC)
Gwlad/TiriogaethTeyrnas Unedig Prydain Fawr a Gogledd Iwerddon
Cyfnod06 Gorff 2014 → 11 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