Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms
Date
2020
Authors
Neumann, A.
Neumann, F.
Editors
Bäck, T.
Preuss, M.
Deutz, A.H.
Wang, H.
Doerr, C.
Emmerich, M.T.M.
Trautmann, H.
Preuss, M.
Deutz, A.H.
Wang, H.
Doerr, C.
Emmerich, M.T.M.
Trautmann, H.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
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
Statement of Responsibility
Aneta Neumann and Frank Neumann
Conference Name
International Conference on Parallel Problem Solving from Nature (PPSN) (5 Sep 2020 - 9 Sep 2020 : Leiden, The Netherlands)
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Springer Nature Switzerland AG 2020