@inproceedings{cea32b583ca545efad8194611f27858c,
title = "Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights",
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).",
author = "Frank Neumann and Sutton, {Andrew M.}",
note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.; 15th International Conference on Parallel Problem Solving from Nature, PPSN 2018 ; Conference date: 08-09-2018 Through 12-09-2018",
year = "2018",
doi = "10.1007/978-3-319-99259-4_12",
language = "English (US)",
isbn = "9783319992587",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "141--152",
editor = "Fonseca, {Carlos M.} and Nuno Lourenco and Penousal Machado and Luis Paquete and Anne Auger and Darrell Whitley",
booktitle = "Parallel Problem Solving from Nature – PPSN XV - 15th International Conference, 2018, Proceedings",
}