Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization
Date
2024
Authors
Neumann, F.
Rudolph, G.
Editors
Affenzeller, M.
Winkler, S.M.
Kononova, A.V.
Trautmann, H.
Tusar, T.
Machado, P.
Back, T.
Winkler, S.M.
Kononova, A.V.
Trautmann, H.
Tusar, T.
Machado, P.
Back, T.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Lecture Notes in Artificial Intelligence, 2024 / Affenzeller, M., Winkler, S.M., Kononova, A.V., Trautmann, H., Tusar, T., Machado, P., Back, T. (ed./s), vol.15150, pp.166-180
Statement of Responsibility
Frank Neumann and Günter Rudolph
Conference Name
International Conference on Parallel Problem Solving from Nature (PPSN) (14 Sep 2024 - 18 Sep 2024 : Hagenberg, Austria)
Abstract
Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the (1 + 1)-EA due to the presence of local optima. We introduce for the first time single-objective algorithms that are provably successful for different classes of constrained submodular maximization problems. Our algorithms are variants of the (1 + λ)-EA and (1+1)-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024