Friedrich, T.Kötzing, T.Neumann, A.Neumann, F.Radhakrishnan, A.2025-10-282025-10-282025Algorithmica, 2025; 87(5):661-6890178-46171432-0541https://hdl.handle.net/2440/148028Published online: 19 February 2025. Part of a collection: GECCO 2023Understanding 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.en© 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/.Evolutionary algorithms; Chance constraint optimization; Run time analysis; TheoryJournal article10.1007/s00453-025-01298-9690933Neumann, A. [0000-0002-0036-4782]Neumann, F. [0000-0002-2721-3618]