Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights
Author: Neumann, F.
Sutton, A.
Citation: Parallel Problem Solving from Nature - PPSN XV: 15th International Conference, Coimbra, Portugal, September 8-12, 2018, Proceedings, Part II, 2018 / Auger, A., Fonseca, C., Lourenco, N., Machado, P., Paquete, L., Whitley, D. (ed./s), vol.11102 LNCS, pp.141-152
Publisher: Springer
Publisher Place: Cham
Issue Date: 2018
Series/Report no.: Lecture Notes in Computer Science; 11102
ISBN: 9783319992587
ISSN: 0302-9743
Conference Name: International Conference on Parallel Problem Solving from Nature (PPSN) (08 Sep 2018 - 12 Sep 2018 : Coimbra, Portugal)
Statement of
Frank Neumann and Andrew M. Sutton
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 O(n2(logn+logpmax)), where pmax 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 O(n3).
Rights: © Springer Nature Switzerland AG 2018
RMID: 0030096918
DOI: 10.1007/978-3-319-99259-4_12
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
hdl_120108.pdfAccepted version463.45 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.