research-article

Open access

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

Authors:

Tobias Friedrich,

Aishwarya RadhakrishnanAuthors Info & Claims

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1584 - 1592

https://doi.org/10.1145/3583131.3590453

Published: 12 July 2023 Publication History

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 Θ(n(n - B) log(B) + n²) 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 experimental studies on how the (μ+1) EA is able to deal with these constraints in a sampling-based setting.

Supplementary Material

PDF File (p1584-friedrich-suppl.pdf)

Supplemental material.

Download
859.18 KB

References

[1]

Hans-Georg Beyer and Bernhard Sendhoff. 2007. Robust optimization-a comprehensive survey. Computer methods in applied mechanics and engineering 196, 33--34 (2007), 3190--3218.

[2]

Abraham Charnes and William W Cooper. 1959. Chance-constrained programming. Management science 6, 1 (1959), 73--79.

[3]

Benjamin Doerr and Timo Kötzing. 2021. Lower Bounds from Fitness Levels Made Easy. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2021). Association for Computing Machinery, New York, NY, USA, 1142--1150.

Digital Library

[4]

Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Springer.

[5]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 1--2 (2002), 51--81.

Digital Library

[6]

A. E. Eiben and James E. Smith. 2015. Introduction to Evolutionary Computing, Second Edition. Springer.

[7]

Tobias Friedrich, Timo Kötzing, J. A. Gregor Lagodzinski, Frank Neumann, and Martin Schirneck. 2020. Analysis of the (1+1) EA on subclasses of linear functions under uniform and linear constraints. Theor. Comput. Sci. 832 (2020), 3--19.

[8]

Tobias Friedrich, Timo Kötzing, J. A. Gregor Lagodzinski, Frank Neumann, and Martin Schirneck. 2017. Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. In Foundations of Genetic Algorithms (FOGA). ACM Press, 45--54.

[9]

Grani A Hanasusanto, Vladimir Roitch, Daniel Kuhn, and Wolfram Wiesemann. 2015. A distributionally robust perspective on uncertainty quantification and chance constrained programming. Mathematical Programming 151 (2015), 35--62.

Digital Library

[10]

Jun He and Xin Yao. 2004. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3 (2004), 21--35.

Digital Library

[11]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.

[12]

Pu Li, Harvey Arellano-Garcia, and Günter Wozny. 2008. Chance constrained programming approach to process optimization under uncertainty. Computers & chemical engineering 32, 1--2 (2008), 25--45.

[13]

Bruce L Miller and Harvey M Wagner. 1965. Chance constrained programming with joint constraints. Operations Research 13, 6 (1965), 930--945.

Digital Library

[14]

Rahul Nair and Elise Miller-Hooks. 2011. Fleet management for vehicle sharing operations. Transportation Science 45, 4 (2011), 524--540.

Digital Library

[15]

Aneta Neumann and Frank Neumann. 2020. Optimising Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-objective Algorithms. In PPSN (1) (Lecture Notes in Computer Science, Vol. 12269). Springer, 404--417.

[16]

Aneta Neumann, Yue Xie, and Frank Neumann. 2022. Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits. In Parallel Problem Solving from Nature - PPSN XVII - 17th International Conference, PPSN 2022, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 13398). Springer, 294--307.

Digital Library

[17]

Frank Neumann, Mojgan Pourhassan, and Carsten Witt. 2021. Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint. Algorithmica 83, 10 (2021), 3209--3237.

Digital Library

[18]

Frank Neumann and Andrew M. Sutton. 2019. Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019. ACM, 147--153.

Digital Library

[19]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization. Springer.

[20]

Chao Qian, Jing-Cheng Shi, Yang Yu, and Ke Tang. 2017. On Subset Selection with General Cost Constraints. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017. ijcai.org, 2613--2619.

[21]

Chao Qian, Yang Yu, and Zhi-Hua Zhou. 2015. Subset Selection by Pareto Optimization. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015. 1774--1782.

[22]

Vahid Roostapour, Aneta Neumann, and Frank Neumann. 2022. Single- and multiobjective evolutionary algorithms for the knapsack problem with dynamically changing constraints. Theor. Comput. Sci. 924 (2022), 129--147.

Digital Library

[23]

Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. 2022. Pareto optimization for subset selection with dynamic cost constraints. Artif. Intell. 302 (2022), 103597.

Digital Library

[24]

Feng Shi, Xiankun Yan, and Frank Neumann. 2022. Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling Problem. In PPSN (2) (Lecture Notes in Computer Science, Vol. 13399). Springer, 526--541.

[25]

Yue Xie, Oscar Harper, Hirad Assimi, Aneta Neumann, and Frank Neumann. 2019. Evolutionary algorithms for the chance-constrained knapsack problem. In Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2019). ACM, 338--346.

Digital Library

[26]

Yue Xie, Aneta Neumann, and Frank Neumann. 2020. Specific single- and multiobjective evolutionary algorithms for the chance-constrained knapsack problem. In Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2020). ACM, 271--279.

Digital Library

[27]

Yue Xie, Aneta Neumann, Frank Neumann, and Andrew M. Sutton. 2021. Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights. In Proceedings of the Genetic and Evolutionary Computation Conference, (GECCO 2021). ACM, 1187--1194.

Digital Library

[28]

Hui Zhang and Pu Li. 2011. Chance constrained programming for optimal power flow under uncertainty. IEEE Transactions on Power Systems 26, 4 (2011), 2417--2424.

Cited By

Doerr BKnowles JNeumann ANeumann FLi XHandl J(2024)A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654169(493-501)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654169

Recommendations

The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on ...
The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
The $$(1+1)$$(1+1) Elitist Black-Box Complexity of LeadingOnes

One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

July 2023

1667 pages

ISBN:9798400701191

DOI:10.1145/3583131

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 Owner/Author(s).

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2023

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '23

Sponsor:

SIGEVO

GECCO '23: Genetic and Evolutionary Computation Conference

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
99
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)20

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BKnowles JNeumann ANeumann FLi XHandl J(2024)A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical AnalysisProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654169(493-501)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654169

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents