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

research-article

Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering

Authors:

Christine ZargesAuthors Info & Claims

FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

Pages 1 - 14

https://doi.org/10.1145/1967654.1967656

Published: 05 January 2011 Publication History

Abstract

Analyzing the computational complexity of evolutionary algorithms has become an accepted and important branch in evolutionary computation theory. This is usually done by analyzing the (expected) optimization time measured by means of the number of function evaluations and describing its growth as a function of a measure for the size of the search space. Most often asymptotic results describing only the order of growth are derived. This corresponds to classical analysis of (randomized) algorithms in algorithmics. Recently, the emerging field of algorithm engineering has demonstrated that for practical purposes this analysis can be too coarse and more details of the algorithm and its implementation have to be taken into account in order to obtain results that are valid in practice. Using a very recent analysis of a simple evolutionary algorithm as starting point it is shown that the same holds for evolutionary algorithms. Considering this example it is demonstrated that counting function evaluations more precisely can lead to results contradicting actual run times. Motivated by these limitations of computational complexity analysis an algorithm engineering-like approach is presented.

References

[1]

A. Auger and B. Doerr. Theory of Randomized Search Heuristics. World Scientific Review, 2011. To appear.

Digital Library

[2]

T. Bartz-Beielstein. Experimental Research in Evolutionary Computation - The New Experimentalism. Springer, 2006.

Digital Library

[3]

S. Böttcher, B. Doerr, and F. Neumann. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In R. Schaefer, C. Cotta, J. Kołodziej, and G. Rudolph, editors, Proceedings of the 11th International Conference on Parallel Problem Solving From Nature (PPSN XI), volume 6238 of LNCS, pages 1--10. Springer, 2010.

Digital Library

[4]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001. 2nd edition.

Digital Library

[5]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

[6]

T. Jansen and D. Sudholt. Analysis of an asymmetric mutation operator. Evolutionary Computation, 18(1):1--26, 2010.

Digital Library

[7]

T. Jansen and I. Wegener. On the choice of the mutation probability for the (1 + 1) EA. In M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo, and H.-P. Schwefel, editors, Proceedings of the 6th International Conference on Parallel Problem Solving From Nature (PPSN VI), volume 1917 of LNCS, pages 89--98. Springer, 2000.

Digital Library

[8]

T. Jansen and I. Wegener. On the analysis of a dynamic evolutionary algorithm. Journal of Discrete Algorithms, 4(1):181--199, 2005.

[9]

D. Knuth. The Art of Computer Programming. Volume II. Addison-Wesley, 1969.

[10]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Natural Computing Series. Springer, 2010.

Digital Library

[11]

P. S. Oliveto, J. He, and X. Yao. Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3):281--293, 2007.

[12]

G. Rudolph. Convergence Properties of Evolutionary Algorithms. Kovac, 1997.

[13]

G. Rudolph and J. Ziegenhirt. Computation time of evolutionary operators. In T. Bäck, D. B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, pages E2.2:1--4. CRC Press, 1997.

[14]

P. Sanders. Algorithm engineering - an attempt at a definition. In S. Albers, H. Alt, and S. Näher, editors, Efficient Algorithms - Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, volume 5760 of LNCS, pages 321--340. Springer, 2009.

Digital Library

[15]

I. Wegener. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In R. Sarker, X. Yao, and M. Mohammadian, editors, Evolutionary Optimization, pages 349--369. Kluwer, 2002.

Cited By

Dang DOpris ASudholt D(2024)On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them EfficientlyParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_15(230-245)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_15
Jansen TZarges C(2024)Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable OrderingsEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-57712-3_12(177-192)Online publication date: 2024
https://doi.org/10.1007/978-3-031-57712-3_12
Buzdalov MSilva SPaquete L(2023)Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of PatchesProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596388(1873-1881)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596388
Show More Cited By

Index Terms

Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A large population size can be unhelpful in evolutionary algorithms

The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on ...
A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We investigate the MAX-2-SAT problem and study evolutionary algorithms by parameterized runtime analysis. The parameterized runtime analysis of evolutionary algorithms has been initiated recently and reveals new insights into which type of instances of ...
The impact of parametrization in memetic evolutionary algorithms

Memetic (evolutionary) algorithms integrate local search into the search process of evolutionary algorithms. As computational resources have to be spread adequately among local and evolutionary search, one has to care about when to apply local search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

January 2011

262 pages

ISBN:9781450306331

DOI:10.1145/1967654

Program Chairs:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
W. B. Langdon
University College London, UK

Copyright © 2011 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 ACM 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: 05 January 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '11

Sponsor:

SIGEVO

FOGA '11: Foundations of Genetic Algorithms XI

January 5 - 9, 2011

Schwarzenberg, Austria

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
532
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dang DOpris ASudholt D(2024)On the Equivalence Between Stochastic Tournament and Power-Law Ranking Selection and How to Implement Them EfficientlyParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_15(230-245)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_15
Jansen TZarges C(2024)Experimental and Theoretical Analysis of Local Search Optimising OBDD Variable OrderingsEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-57712-3_12(177-192)Online publication date: 2024
https://doi.org/10.1007/978-3-031-57712-3_12
Buzdalov MSilva SPaquete L(2023)Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of PatchesProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596388(1873-1881)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596388
Lehre PSutton ASilva SPaquete L(2023)Runtime Analysis with Variable CostProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590432(1611-1618)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590432
Bernardes W(2023)Optimizing TOC and IOC units of directional overcurrent relays in mutually coupled circuits using evolutionary PSOEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106389125:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106389
Heidari HZeng B(2023)An optimized grey transition Verhulst methodEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.105870120:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.105870
Khaldi MDraa A(2023)Surrogate-assisted evolutionary optimisation: a novel blueprint and a state of the art surveyEvolutionary Intelligence10.1007/s12065-023-00882-817:4(2213-2243)Online publication date: 3-Oct-2023
https://doi.org/10.1007/s12065-023-00882-8
Doerr BGhannane YIbn Brahim M(2023)Runtime Analysis for Permutation-based Evolutionary AlgorithmsAlgorithmica10.1007/s00453-023-01146-886:1(90-129)Online publication date: 26-Jul-2023
https://doi.org/10.1007/s00453-023-01146-8
Kneissl CSudholt D(2023)The Cost of Randomness in Evolutionary Algorithms: Crossover can Save Random BitsEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-30035-6_12(179-194)Online publication date: 31-Mar-2023
https://doi.org/10.1007/978-3-031-30035-6_12
Lissovoi AOliveto PWarwicker J(2020)Simple Hyper-Heuristics Control the Neighbourhood Size of Randomised Local Search Optimally for LeadingOnesEvolutionary Computation10.1162/evco_a_0025828:3(437-461)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1162/evco_a_00258
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