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  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 language||English (US)|
|Title of host publication||Parallel Problem Solving from Nature – PPSN XV - 15th International Conference, 2018, Proceedings|
|Editors||Carlos M. Fonseca, Nuno Lourenco, Penousal Machado, Luis Paquete, Anne Auger, Darrell Whitley|
|Number of pages||12|
|State||Published - 2018|
|Event||15th International Conference on Parallel Problem Solving from Nature, PPSN 2018 - Coimbra, Portugal|
Duration: Sep 8 2018 → Sep 12 2018
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||15th International Conference on Parallel Problem Solving from Nature, PPSN 2018|
|Period||9/8/18 → 9/12/18|
Bibliographical notePublisher Copyright:
© 2018, Springer Nature Switzerland AG.