Article

Crossover is provably essential for the Ising model on trees

Author:

Dirk SudholtAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 1161 - 1167

https://doi.org/10.1145/1068009.1068202

Published: 25 June 2005 Publication History

Get Access

Abstract

Due to experimental evidence it is incontestable that crossover is essential for some fitness functions. However, theoretical results without assumptions are difficult. So-called real royal road functions are known where crossover is proved to be essential, i.e., mutation-based algorithms have an exponential expected runtime while the expected runtime of a genetic algorithm is polynomially bounded. However, these functions are artificial and have been designed in such a way that crossover is essential only at the very end (or at other well-specified points) of the optimization process.Here, a more natural fitness function based on a generalized Ising model is presented where crossover is essential throughout the whole optimization process. Mutation-based algorithms such as (μ+λ) EAs with constant population size are proved to have an exponential expected runtime while the expected runtime of a simple genetic algorithm with population size 2 and fitness sharing is polynomially bounded.

References

[1]

P. Briest, D. Brockhoff, B. Degener, M. Englert, C. Gunia, T. Jansen, O. Heering, M. Leifhelm, K. Plociennik, H. Röglin, A. Schweer, D. Sudholt, S. Tannenbaum, and I. Wegener. The Ising model: simple evolutionary algorithms as adaptation schemes. In Proceedings of the Eighth Conference on Parallel Problem Solving from Nature (PPSN VIII), volume 3242 of Lecture Notes in Computer Science, pages 31--40. Springer-Verlag, 2004.

Crossref

Google Scholar

[2]

S. Fischer. A polynomial upper bound for a mutation-based algorithm on the two-dimensional Ising model. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2004, volume 3102 of Lecture Notes in Computer Science, pages 1100--1112. Springer-Verlag, 2004.

Crossref

Google Scholar

[3]

S. Fischer and I. Wegener. The Ising model on the ring: Mutation versus recombination. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2004, volume 3102 of Lecture Notes in Computer Science, pages 1113--1124. Springer-Verlag, 2004.

Crossref

Google Scholar

[4]

D. E. Goldberg, C. Van Hoyweghen, and B. Naudts. Spin-flip symmetry and synchronization. Evolutionary Computation, 10:317--344, 2002.

Digital Library

Google Scholar

[5]

E. Ising. Beitrag zur Theorie des Ferromagnetismus. Z. Physik, 31:235--288, 1925.

Crossref

Google Scholar

[6]

T. Jansen and I. Wegener. Real royal road functions -- functions where crossover provably is essential. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pages 375--382. Morgan Kaufmann, 2001.

Google Scholar

[7]

T. Jansen and I. Wegener. On the analysis of evolutionary algorithms -- a proof that crossover really can help. Algorithmica, 34(1):47--66, 2002.

Digital Library

Google Scholar

[8]

T. Storch and I. Wegener. Real royal road functions for constant population size. Theoretical Computer Science, 320:123--134, 2004.

Digital Library

Google Scholar

[9]

R. A. Watson and J. B. Pollack. Hierarchically consistent test problems for genetic algorithms. In P. J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, editors, Proceedings of the Congress on Evolutionary Computation, volume 2, pages 1406--1413, Mayflower Hotel, Washington D.C., USA, 6-9 1999. IEEE Press.

Google Scholar

Cited By

View all

Sudholt DSquillero GLi XHandl J(2024)Theory and Practice of Population Diversity in Evolutionary ComputationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648430(1391-1409)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648430
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
Dang DOpris ASudholt D(2024)Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationArtificial Intelligence10.1016/j.artint.2024.104098(104098)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104098
Show More Cited By

Index Terms

Crossover is provably essential for the Ising model on trees
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

The one-dimensional Ising model: mutation versus recombination

The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight into how these algorithms work as adaptation schemes. The one-dimensional Ising model with periodic boundary conditions has been considered as a typical ...
Real royal road functions-where crossover provably is essential
Special issue: Boolean and pseudo-boolean funtions

Mutation and crossover are the main search operators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some explicitly defined fitness functions f"n:{0,1}^n->R ...
Real royal road functions — where crossover provably is essential
GECCO'01: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation

Mutation and crossover are the main search operators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some explicitly defined fitness functions f_n : {0,1}ⁿ → ℝ ...

Comments

Information & Contributors

Information

Published In

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

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: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
409
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sudholt DSquillero GLi XHandl J(2024)Theory and Practice of Population Diversity in Evolutionary ComputationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648430(1391-1409)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648430
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
Dang DOpris ASudholt D(2024)Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationArtificial Intelligence10.1016/j.artint.2024.104098(104098)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104098
Doerr BQu ZWilliams BChen YNeville J(2023)Runtime analysis for the NSGA-IIProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26461(12399-12407)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26461
Dang DOpris ASalehi BSudholt DWilliams BChen YNeville J(2023)A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisationProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26460(12390-12398)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26460
Sankineni PSutton A(2023)Symmetry Breaking for Voting Mechanisms*Evolutionary Computation10.1162/evco_a_0032731:3(309-335)Online publication date: 1-Sep-2023
https://doi.org/10.1162/evco_a_00327
Doerr BQu ZSilva SPaquete L(2023)Hot off the Press: Runtime Analysis for the NSGA-II - Provable Speed-Ups From CrossoverProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595845(19-20)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595845
Sudholt DSquillero GSilva SPaquete L(2023)Theory and Practice of Population Diversity in Evolutionary ComputationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595053(1361-1378)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595053
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
Bossek JSudholt D(2023)Do Additional Target Points Speed Up Evolutionary Algorithms?Theoretical Computer Science10.1016/j.tcs.2023.113757(113757)Online publication date: Feb-2023
https://doi.org/10.1016/j.tcs.2023.113757
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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

The one-dimensional Ising model: mutation versus recombination

Real royal road functions-where crossover provably is essential

Real royal road functions — where crossover provably is essential

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