Scholarlink

<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1298_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="186" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Theta (n (n-B)\log (B) + nB)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mi>B</mi> <mo stretchy="false">)</mo> <mo>log</mo> <mo stretchy="false">(</mo> <mi>B</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>n</mi> <mi>B</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 (<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1298_Article_IEq2.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mu \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>μ</mi> </math></EquationSource> </InlineEquation>+1) EA is able to deal with these constraints in a sampling-based setting.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年2月19日

查看全文
  • Tobias Friedrich,
  • Timo Kötzing,
  • Aneta Neumann,
  • Frank Neumann,
  • Aishwarya Radhakrishnan

摘要

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 \(\Theta (n (n-B)\log (B) + nB)\) Θ ( n ( n - B ) log ( B ) + n B ) 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 ( \(\mu \) μ +1) EA is able to deal with these constraints in a sampling-based setting.