tutorial

Drift analysis

Author:

Per Kristian LehreAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Pages 1239 - 1258

https://doi.org/10.1145/2330784.2330939

Published: 07 July 2012 Publication History

Get Access

References

[1]

Benjamin Doerr and Leslie Ann Goldberg. Drift analysis with tail bounds. In Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, PPSN'10, pages 174--183, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

Google Scholar

[2]

Benjamin Doerr, Daniel Johannsen, and Carola Winzen. Multiplicative drift analysis. In GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation, pages 1449--1456, New York, NY, USA, 2010. ACM.

Digital Library

Google Scholar

[3]

Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1

Google Scholar

[4]

1) Evolutionary Algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

Google Scholar

[5]

Simon Fischer, Lars Olbrich, and Berthold Vöcking. Approximating wardrop equilibria with finitely many agents. Distributed Computing, 21(2):129--139, 2008.

Digital Library

Google Scholar

[6]

Oliver Giel and Ingo Wegener. Evolutionary algorithms and the maximum matching problem. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), pages 415--426, 2003.

Digital Library

Google Scholar

[7]

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

Crossref

Google Scholar

[8]

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

Digital Library

Google Scholar

[9]

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

Digital Library

Google Scholar

[10]

Jens Jagersküpper. Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoretical Computer Science, 379(3):329--347, 2007.

Digital Library

Google Scholar

[11]

Jens Jagersküpper. A Blend of Markov-Chain and Drift Analysis. In Proceedings of the 10th International Conference on Parallel Problem Solving from Nature (PPSN 2008), 2008.

Google Scholar

[12]

Daniel Johannsen. Random combinatorial structures and randomized search heuristics. PhD thesis, Universitat des Saarlandes, 2010.

Google Scholar

[13]

Per Kristian Lehre. Negative drift in populations. In Proceedings of Parallel Problem Solving from Nature - (PPSN XI), volume 6238 of LNCS, pages 244--253. Springer Berlin / Heidelberg, 2011.

Digital Library

Google Scholar

[14]

Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation. Algorithmica, pages 1--20, 2012.

Digital Library

Google Scholar

[15]

Sean P. Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, 1993.

Google Scholar

[16]

B. Mitavskiy, J. E. Rowe, and C. Cannings. Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. International Journal of Intelligent Computing and Cybernetics, 2(2):243--284, 2009.

Crossref

Google Scholar

[17]

Frank Neumann, Dirk Sudholt, and Carsten Witt. Analysis of different mmas aco algorithms on unimodal functions and plateaus. Swarm Intelligence, 3(1):35--68, 2009.

Crossref

Google Scholar

[18]

Pietro Oliveto and Carsten Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, pages 1--18, 2010. 10.1007/s00453-010--9387-z.

Digital Library

Google Scholar

[19]

Pietro S. Oliveto and Carsten Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Technical Report Reihe CI, No. CI-247/08, SFB 531, Technische Universitat Dortmund, Germany, 2008.

Google Scholar

[20]

Galen H. Sasaki and Bruce Hajek. The time complexity of maximum matching by simulated annealing. Journal of the ACM, 35(2):387--403, 1988.

Digital Library

Google Scholar

[21]

Dirk Sudholt. General lower bounds for the running time of evolutionary algorithms. In Proceedings of Parallel Problem Solving from Nature - (PPSN XI), volume 6238 of LNCS, pages 124--133. Springer Berlin / Heidelberg, 2010.

Digital Library

Google Scholar

[22]

David Williams. Probability with Martingales. Cambridge University Press, 1991.

Crossref

Google Scholar

[23]

Carsten Witt. Optimizing linear functions with randomized search heuristics - the robustness of mutation. In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pages 420--431, Dagstuhl, Germany, 2012. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.

Google Scholar

Cited By

View all

Hwang HWitt CFriedrich TDoerr CArnold D(2019)Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial toolsProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340302(1-12)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340302
Akimoto YAuger AGlasmachers TTakadama K(2018)Drift theory in continuous search spacesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205606(801-808)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205606
Dang DLehre P(2016)Runtime Analysis of Non-elitist PopulationsAlgorithmica10.1007/s00453-015-0103-x75:3(428-461)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-0103-x
Show More Cited By

Index Terms

Drift analysis
1. Mathematics of computing
  1. Probability and statistics
    1. Stochastic processes
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

Drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (EAs). Various previous works apply a drift theorem going back to Hajek in order to show exponential lower bounds on the optimization time of EAs. However, ...
Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
Special Issue: Theory of Evolutionary Computation

Drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (EAs). Various previous works apply a drift theorem going back to Hajek in order to show exponential lower bounds on the optimization time of EAs. However, ...
Drift analysis of mutation operations for biogeography-based optimization

As an essential factor of evolutionary algorithms (EAs), mutation operator plays an important role in exploring the search space, maintaining the diversity of individuals and breaking away local optimums. In most standard evolutionary algorithms, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

July 2012

1586 pages

ISBN:9781450311786

DOI:10.1145/2330784

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
122
Total Downloads

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

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hwang HWitt CFriedrich TDoerr CArnold D(2019)Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial toolsProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340302(1-12)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340302
Akimoto YAuger AGlasmachers TTakadama K(2018)Drift theory in continuous search spacesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205606(801-808)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205606
Dang DLehre P(2016)Runtime Analysis of Non-elitist PopulationsAlgorithmica10.1007/s00453-015-0103-x75:3(428-461)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-0103-x
Dang DLehre PArnold D(2014)Evolution under partial informationProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598375(1359-1366)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598375
Lehre PWitt C(2014)Concentrated Hitting Times of Randomized Search Heuristics with Variable DriftAlgorithms and Computation10.1007/978-3-319-13075-0_54(686-697)Online publication date: 8-Nov-2014
https://doi.org/10.1007/978-3-319-13075-0_54
Doerr BJansen TWitt CZarges CAlba E(2013)A method to derive fixed budget results from expected optimisation timesProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463565(1581-1588)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463565

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.

PDF

eReader

View online with eReader.

eReader

References

Cited By

Index Terms

Recommendations

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

Drift analysis of mutation operations for biogeography-based optimization

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations