research-article

Improved analysis methods for crossover-based algorithms

Authors:

Benjamin Doerr,

Madeleine TheileAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 247 - 254

https://doi.org/10.1145/1569901.1569937

Published: 08 July 2009 Publication History

Get Access

Abstract

We deepen the theoretical analysis of the genetic algorithm for the all-pairs shortest path problem proposed by Doerr, Happ and Klein (GECCO 2008). We show that the growth of the paths through crossover operations can be analyzed without the previously used approach of waiting until all paths of a certain length are present in the population. This allows to prove an improved guarantee for the optimization time of O(n^3.25 log^1/4(n). We also show that this bound is asymptotically tight. Besides the mere run-time result, our analysis is a step towards understanding how crossover works and how it can be analyzed with rigorous methods.

References

[1]

N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, New York, 1992.

Google Scholar

[2]

B. Doerr, E. Happ, and C. Klein. A tight bound for the (1 1)-EA on the single source shortest path problem. In IEEE Congress on Evolutionary Computation 2007, pages 1890--1895, Singapore, 2007. IEEE.

Crossref

Google Scholar

[3]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In C. Ryan and M. Keijzer, editors, Genetic and Evolutionary Computation Conference 2008, pages 539--546, Atlanta, USA, 2008. ACM.

Digital Library

Google Scholar

[4]

W. Feller. An introduction to probability theory and its applications. Vol. I. Third edition. John Wiley&Sons Inc., New York, 1968.

Google Scholar

[5]

J. Scharnow, K. Tinnefeld, and I. Wegener. Fitness landscapes based on sorting and shortest paths problems. In PPSN, volume 2439 of Lecture Notes in Computer Science, pages 54--63. Springer, 2002.

Digital Library

Google Scholar

[6]

J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, pages 349--66, 2004.

Google Scholar

Cited By

View all

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Show More Cited By

Index Terms

Improved analysis methods for crossover-based algorithms
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Empirical Analysis of Crossover-Based Evolutionary Algorithms on Rugged Landscape
GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

The crossover is considered as an essential component of the evolutionary algorithms. There exist different ways of how to use it, and in this paper we compare two approaches commonly used in pseudo-Boolean optimization, the classic approach of (μ + 1)...
Adding Crossover to Extinction-Based Evolutionary Algorithms
ICCEE '09: Proceedings of the 2009 Second International Conference on Computer and Electrical Engineering - Volume 02

Extinction-based Evolutionary Algorithms (EEA) have been recently developed as the solutions for the problem of early convergence in multimodal optimization tasks. The reproduction of EEAs is done only by mutation. Moreover, according to recent studies, ...
Fast mutation in crossover-based algorithms
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was successfully used only in purely mutation-based algorithms. There, it can relieve the algorithm ...

Comments

Information & Contributors

Information

Published In

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
206
Total Downloads

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

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Doerr BKrawiec K(2021)Runtime analysis via symmetry argumentsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3462720(23-24)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3462720
Doerr BKrawiec K(2021)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461406(369-398)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461406
Sutton A(2021)Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String ProblemAlgorithmica10.1007/s00453-021-00809-8Online publication date: 15-Feb-2021
https://doi.org/10.1007/s00453-021-00809-8
Doerr B(2020)Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative DriftEvolutionary Computation10.1162/evco_a_00283(1-25)Online publication date: 16-Nov-2020
https://doi.org/10.1162/evco_a_00283
Doerr BCoello Coello C(2020)A gentle introduction to theory (for non-theoreticians)Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389889(373-403)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389889
Doerr B(2020)Runtime analysis of evolutionary algorithms via symmetry argumentsInformation Processing Letters10.1016/j.ipl.2020.106064(106064)Online publication date: Nov-2020
https://doi.org/10.1016/j.ipl.2020.106064
Sutton AWitt C(2020)Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family GraphsAlgorithmica10.1007/s00453-020-00776-6Online publication date: 4-Nov-2020
https://doi.org/10.1007/s00453-020-00776-6
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Empirical Analysis of Crossover-Based Evolutionary Algorithms on Rugged Landscape

Adding Crossover to Extinction-Based Evolutionary Algorithms

Fast mutation in crossover-based algorithms