Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions
Date
2022
Authors
Neumann, F.
Witt, C.
Editors
Rudolph, G.
Kononova, A.V.
Aguirre, H.
Kerschke, P.
Ochoa, G.
Tusar, T.
Kononova, A.V.
Aguirre, H.
Kerschke, P.
Ochoa, G.
Tusar, T.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Lecture Notes in Artificial Intelligence, 2022 / Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tusar, T. (ed./s), vol.13399, pp.542-554
Statement of Responsibility
Frank Neumann and Carsten Witt
Conference Name
International Conference on Parallel Problem Solving from Nature (PPSN) (10 Sep 2022 - 14 Sep 2022 : Dortmund, Germany)
Abstract
Linear functions play a key role in the runtime analysis of evolutionary algorithms and studies have provided a wide range of new insights and techniques for analyzing evolutionary computation methods. Motivated by studies on separable functions and the optimization behaviour of evolutionary algorithms as well as objective functions from the area of chance constrained optimization, we study the class of objective functions that are weighted sums of two transformed linear functions. Our results show that the (1+1) EA, with a mutation rate depending on the number of overlapping bits of the functions, obtains an optimal solution for these functions in expected time O(n log n), thereby generalizing a well-known result for linear functions to a much wider range of problems.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG