Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/120108
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Neumann, F. | - |
dc.contributor.author | Sutton, A. | - |
dc.contributor.editor | Auger, A. | - |
dc.contributor.editor | Fonseca, C. | - |
dc.contributor.editor | Lourenco, N. | - |
dc.contributor.editor | Machado, P. | - |
dc.contributor.editor | Paquete, L. | - |
dc.contributor.editor | Whitley, D. | - |
dc.date.issued | 2018 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 9783319992587 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/2440/120108 | - |
dc.description.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). | - |
dc.description.statementofresponsibility | Frank Neumann and Andrew M. Sutton | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science; 11102 | - |
dc.rights | © Springer Nature Switzerland AG 2018 | - |
dc.source.uri | https://doi.org/10.1007/978-3-319-99259-4 | - |
dc.title | Runtime analysis of evolutionary algorithms for the knapsack problem with favorably correlated weights | - |
dc.type | Conference paper | - |
dc.contributor.conference | International Conference on Parallel Problem Solving from Nature (PPSN) (8 Sep 2018 - 12 Sep 2018 : Coimbra, Portugal) | - |
dc.identifier.doi | 10.1007/978-3-319-99259-4_12 | - |
dc.publisher.place | Cham | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Neumann, F. [0000-0002-2721-3618] | - |
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.