Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/120108
Citations | ||
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: | Lecture Notes in Artificial Intelligence, 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 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (PPSN) (8 Sep 2018 - 12 Sep 2018 : Coimbra, Portugal) |
Editor: | Auger, A. Fonseca, C. Lourenco, N. Machado, P. Paquete, L. Whitley, D. |
Statement of Responsibility: | 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 |
DOI: | 10.1007/978-3-319-99259-4_12 |
Published version: | https://doi.org/10.1007/978-3-319-99259-4 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hdl_120108.pdf | Accepted version | 463.45 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.