Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms

Simple item page
dc.contributor.authorNeumann, A.
dc.contributor.authorNeumann, F.
dc.contributor.conferenceInternational Conference on Parallel Problem Solving from Nature (PPSN) (5 Sep 2020 - 9 Sep 2020 : Leiden, The Netherlands)
dc.contributor.editorBäck, T.
dc.contributor.editorPreuss, M.
dc.contributor.editorDeutz, A.H.
dc.contributor.editorWang, H.
dc.contributor.editorDoerr, C.
dc.contributor.editorEmmerich, M.T.M.
dc.contributor.editorTrautmann, H.
dc.date.issued2020
dc.description.abstractMany 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.
dc.description.statementofresponsibilityAneta Neumann and Frank Neumann
dc.identifier.citationLecture 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
dc.identifier.doi10.1007/978-3-030-58112-1_28
dc.identifier.isbn9783030581114
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.orcidNeumann, A. [0000-0002-0036-4782]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/128130
dc.language.isoen
dc.publisherSpringer
dc.publisher.placeCham, Switzerland
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401
dc.relation.ispartofseriesLecture Notes in Computer Science; 12269
dc.rights© Springer Nature Switzerland AG 2020
dc.source.urihttps://link.springer.com/book/10.1007/978-3-030-58112-1
dc.titleOptimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Computer Science publications