Analysis of the (1+1) EA on LeadingOnes with Constraints

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) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving Θ(𝑛(𝑛-𝐵) log(𝐵) + 𝑛²) as the tight bound. Our results show that the be- haviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the prob- lem in the context of stochastic constraints and provide insights tudies on how the (𝜇+1) EA is able to deal with se constraints in a sampling-based setting.