Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/128130
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms |
Author: | Neumann, A. Neumann, F. |
Citation: | Lecture Notes in Artificial Intelligence, 2020 / Bäck, T., Preuss, M., Deutz, A.H., Wang, H., Doerr, C., Emmerich, M.T.M., Trautmann, H. (ed./s), vol.12269, pp.404-417 |
Publisher: | Springer |
Publisher Place: | Cham, Switzerland |
Issue Date: | 2020 |
Series/Report no.: | Lecture Notes in Computer Science; 12269 |
ISBN: | 9783030581114 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Parallel Problem Solving from Nature (PPSN) (5 Sep 2020 - 9 Sep 2020 : Leiden, The Netherlands) |
Editor: | Bäck, T. Preuss, M. Deutz, A.H. Wang, H. Doerr, C. Emmerich, M.T.M. Trautmann, H. |
Statement of Responsibility: | Aneta Neumann and Frank Neumann |
Abstract: | Many real-world optimisation problems can be stated in terms of submodular functions. A lot of evolutionary multi-objective algorithms have recently been analyzed and applied to submodular problems with different types of constraints. We present a first runtime analysis of evolutionary multi-objective algorithms for chance-constrained submodular functions. Here, the constraint involves stochastic components and the constraint can only be violated with a small probability of α. We show that the GSEMO algorithm obtains the same worst case performance guarantees as recently analyzed greedy algorithms. Furthermore, we investigate the behavior of evolutionary multi-objective algorithms such as GSEMO and NSGA-II on different submodular chance constrained network problems. Our experimental results show that this leads to significant performance improvements compared to the greedy algorithm. |
Rights: | © Springer Nature Switzerland AG 2020 |
DOI: | 10.1007/978-3-030-58112-1_28 |
Grant ID: | http://purl.org/au-research/grants/arc/DP160102401 |
Published version: | https://link.springer.com/book/10.1007/978-3-030-58112-1 |
Appears in Collections: | Aurora harvest 4 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.