Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights

Frank Neumann, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We rigorously analyze the runtime of evolutionary algorithms for the classical knapsack problem where the weights are favorably correlated with the profits. Our result for the (1+1) EA generalizes the one obtained in [1] for uniform constraints and shows that an optimal solution in the single-objective setting is obtained in expected time (formula presented), where (formula presented) is the largest profit of the given input. Considering the multi-objective formulation where the goal is to maximize the profit and minimize the weight of the chosen item set at the same time, we show that the Pareto front has size n+1 whereas there are sets of solutions of exponential size where all solutions are incomparable to each other. Analyzing a variant of GSEMO with a size-based parent selection mechanism motivated by these insights, we show that the whole Pareto front is computed in expected time (formula presented).

Original languageEnglish (US)
Title of host publicationParallel Problem Solving from Nature – PPSN XV - 15th International Conference, 2018, Proceedings
EditorsCarlos M. Fonseca, Nuno Lourenco, Penousal Machado, Luis Paquete, Anne Auger, Darrell Whitley
PublisherSpringer Verlag
Pages141-152
Number of pages12
ISBN (Print)9783319992587
DOIs
StatePublished - 2018
Event15th International Conference on Parallel Problem Solving from Nature, PPSN 2018 - Coimbra, Portugal
Duration: Sep 8 2018Sep 12 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11102 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Parallel Problem Solving from Nature, PPSN 2018
CountryPortugal
CityCoimbra
Period9/8/189/12/18

Fingerprint Dive into the research topics of 'Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights'. Together they form a unique fingerprint.

Cite this