Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/136892
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits |
Author: | Neumann, A. Xie, Y. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2022 / Rudolph, G., Kononova, A.V., Aguirre, H.E., Kerschke, P., Ochoa, G., Tusar, T. (ed./s), vol.13398, pp.294-307 |
Publisher: | Springer |
Publisher Place: | Online |
Issue Date: | 2022 |
Series/Report no.: | Lecture Notes in Computer Science; 13398 |
ISBN: | 9783031147135 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (PPSN) (10 Sep 2022 - 14 Sep 2022 : Dortmund, Germany) |
Editor: | Rudolph, G. Kononova, A.V. Aguirre, H.E. Kerschke, P. Ochoa, G. Tusar, T. |
Statement of Responsibility: | Aneta Neumann, Yue Xie, Frank Neumann |
Abstract: | Evolutionary algorithms have been widely used for a range of stochastic optimization problems in order to address complex real-world optimization problems. We consider the knapsack problem where the profits involve uncertainties. Such a stochastic setting reflects important real-world scenarios where the profit that can be realized is uncertain. We introduce different ways of dealing with stochastic profits based on tail inequalities such as Chebyshev’s inequality and Hoeffding bounds that allow to limit the impact of uncertainties. We examine simple evolutionary algorithms and the use of heavy tail mutation and a problem-specific crossover operator for optimizing uncertain profits. Our experimental investigations on different benchmarks instances show the results of different approaches based on tail inequalities as well as improvements achievable through heavy tail mutation and the problem specific crossover operator. |
Keywords: | Stochastic knapsack problem; Chance-constrained optimization; Evolutionary algorithms |
Rights: | © 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG |
DOI: | 10.1007/978-3-031-14714-2_21 |
Grant ID: | http://purl.org/au-research/grants/arc/FT200100536 |
Published version: | https://link.springer.com/book/10.1007/978-3-031-14714-2 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.