Analysis of the (1+1) EA on LeadingOnes with Constraints
Files
(Published version)
Date
2025
Authors
Friedrich, T.
Kötzing, T.
Neumann, A.
Neumann, F.
Radhakrishnan, A.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Algorithmica, 2025; 87(5):661-689
Statement of Responsibility
Tobias Friedrich, Timo Kötzing, Aneta Neumann, Frank Neumann, Aishwarya Radhakrishnan
Conference Name
Abstract
Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EAon the LeadingOnes problem with a deterministic cardinality constraint, giving Θ(n(n−B) log(B)+nB) as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using theoretical and experimental studies on how the (μ+1) EA is able to deal with these constraints in a sampling-based setting.
School/Discipline
Dissertation Note
Provenance
Description
Published online: 19 February 2025.
Part of a collection: GECCO 2023
Access Status
Rights
© The Author(s) 2025. OpenAccess This article is licensed under a CreativeCommonsAttribution 4.0 InternationalLicense,which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.