More Web Proxy on the site http://driver.im/

research-article

(1+1) EA on Generalized Dynamic OneMax

Authors:

Andrei Lissovoi,

Carsten WittAuthors Info & Claims

FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

Pages 40 - 51

https://doi.org/10.1145/2725494.2725502

Published: 17 January 2015 Publication History

Abstract

Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension.

Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.

References

[1]

Auger, Anne and Doerr, Benjamin (2011). Theory of Randomized Search Heuristics -- Foundations and Recent Developments. World Scientific Publishing.

Digital Library

[2]

Doerr, Benjamin, Johannsen, Daniel, and Schmidt, Martin (2011). Runtime analysis of the (1+1) evolutionary algorithm on strings over finite alphabets. In Proc. of FOGA'11, 119--126. ACM Press.

Digital Library

[3]

Doerr, Benjamin and Pohl, Sebastian (2012). Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet. In Proc. of GECCO'12, 1317--1324. ACM Press.

Digital Library

[4]

Droste, Stefan (2002). Analysis of the (1+1) EA for a dynamically changing OneMax-variant. In Proc. of CEC'02, 55--60. IEEE Press.

Digital Library

[5]

Droste, Stefan (2003). Analysis of the (1+1) EA for a dynamically bitwise changing OneMax. In Proc. of GECCO'03, 909--921. Springer.

Digital Library

[6]

Hajek, Bruce (1982). Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 13, 502--525.

[7]

He, Jun and Yao, Xin (2001). Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127, 57--85.

Digital Library

[8]

Jansen, Thomas (2013). Analyzing Evolutionary Algorithms -- The Computer Science Perspective. Natural Computing Series. Springer.

Digital Library

[9]

Jansen, Thomas and Schellbach, Ulf (2005). Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in the lattice. In Proc. of GECCO'05, 841--848. ACM Press.

Digital Library

[10]

Jansen, Thomas and Zarges, Christine (2014). Evolutionary algorithms and artificial immune systems on a bi-stable dynamic optimisation problem. In Proc. of GECCO'14, 975--982. ACM Press.

Digital Library

[11]

Jin, Yaochu and Branke, Jürgen (2005). Evolutionary optimization in uncertain environments--A survey. IEEE Transactions on Evolutionary Computation, 9, 303--317.

Digital Library

[12]

Kötzing, Timo (2014). Concentration of first hitting times under additive drift. In Proc. of GECCO'14, 1391--1398. ACM Press.

Digital Library

[13]

Kötzing, Timo and Molter, Hendrik (2012). ACO beats EA on a dynamic pseudo-boolean function. In Proc. of PPSN'12, 113--122. Springer.

Digital Library

[14]

Lehre, Per Kristian and Witt, Carsten (2014). Concentrated hitting times of randomized search heuristics with variable drift. In Proc. of ISAAC'14, 686--697. Springer. Extended version at http://arxiv.org/abs/1307.2559.

[15]

Lissovoi, Andrei and Witt, Carsten (2015). MMAS versus population-based EA on a family of dynamic fitness functions. Algorithmica. In press, final version online at http://dx.doi.org/10.1007/s00453-015--9975-z.

[16]

Neumann, Frank and Witt, Carsten (2010). Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Natural Computing Series. Springer.

Digital Library

[17]

Oliveto, Pietro Simone and Witt, Carsten (2011). Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59, 369--386.

Digital Library

[18]

Oliveto, Pietro Simone and Witt, Carsten (2012). Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation. Tech. rep., http://arxiv.org/abs/1211.7184.

[19]

Oliveto, Pietro Simone and Zarges, Christine (2013). Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change. In Proc. of GECCO'13, 837--844. ACM Press.

Digital Library

[20]

Rowe, Jonathan E. and Sudholt, Dirk (2014). The choice of the offspring population size in the (1,λ) evolutionary algorithm. Theoretical Computer Science, 545, 20--38.

Digital Library

Cited By

Jedidia FDoerr BKrejca M(2024)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science10.1016/j.tcs.2024.114622(114622)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114622
Fajardo MLehre PLin S(2023)Runtime Analysis of a Co-Evolutionary AlgorithmProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607132(73-83)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607132
Lehre PQin XSilva SPaquete L(2023)Self-adaptation Can Help Evolutionary Algorithms Track Dynamic OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590494(1619-1627)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590494
Show More Cited By

Index Terms

(1+1) EA on Generalized Dynamic OneMax
1. Theory of computation
  1. Design and analysis of algorithms

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 ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and ...
OneMax in Black-Box Models with Several Restrictions
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

As in classical runtime analysis the OneMax problem is the most prominent test problem also in black-box complexity theory. It is known that the unrestricted, the memory-restricted, and the ranking-based black-box complexities of this problem are all of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

January 2015

200 pages

ISBN:9781450334341

DOI:10.1145/2725494

Program Chairs:
Jun He
Aberystwyth University, UK
,
Thomas Jansen
Aberystwyth University, UK
,
Gabriela Ochoa
University of Stirling, UK
,
Christine Zarges
University of Birmingham, UK

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 January 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Natur og Univers, Det Frie Forskningsråd

Conference

FOGA '15

Sponsor:

SIGEVO

FOGA '15: Foundations of Genetic Algorithms XIII

January 17 - 22, 2015

Aberystwyth, United Kingdom

Acceptance Rates

FOGA '15 Paper Acceptance Rate 16 of 26 submissions, 62%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
211
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jedidia FDoerr BKrejca M(2024)Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science10.1016/j.tcs.2024.114622(114622)Online publication date: May-2024
https://doi.org/10.1016/j.tcs.2024.114622
Fajardo MLehre PLin S(2023)Runtime Analysis of a Co-Evolutionary AlgorithmProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607132(73-83)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607132
Lehre PQin XSilva SPaquete L(2023)Self-adaptation Can Help Evolutionary Algorithms Track Dynamic OptimaProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590494(1619-1627)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590494
Werth BBeham AKarder JWagner SAffenzeller M(2022)Fitness Landscape Analysis on Binary Dynamic Optimization ProblemsProcedia Computer Science10.1016/j.procs.2022.01.299200(1004-1013)Online publication date: 2022
https://doi.org/10.1016/j.procs.2022.01.299
Qian CLiu DZhou Z(2022)Result diversification by multi-objective evolutionary algorithms with theoretical guaranteesArtificial Intelligence10.1016/j.artint.2022.103737309(103737)Online publication date: Aug-2022
https://doi.org/10.1016/j.artint.2022.103737
Lengler JRiedi S(2022)Runtime Analysis of the $$(\mu + 1)$$-EA on the Dynamic BinVal FunctionSN Computer Science10.1007/s42979-022-01203-z3:4Online publication date: 10-Jun-2022
https://doi.org/10.1007/s42979-022-01203-z
Lehre PQin X(2022)More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain EnvironmentsAlgorithmica10.1007/s00453-022-01044-586:2(396-441)Online publication date: 2-Oct-2022
https://doi.org/10.1007/s00453-022-01044-5
Doerr BNeumann F(2021)A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/34723041:4(1-43)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1145/3472304
Doerr BKötzing T(2020)Multiplicative Up-DriftAlgorithmica10.1007/s00453-020-00775-7Online publication date: 30-Oct-2020
https://doi.org/10.1007/s00453-020-00775-7
Doerr BWitt CYang J(2020)Runtime Analysis for Self-adaptive Mutation RatesAlgorithmica10.1007/s00453-020-00726-2Online publication date: 12-Jun-2020
https://doi.org/10.1007/s00453-020-00726-2
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents