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

research-article

How crossover helps in pseudo-boolean optimization

Authors:

Madeleine TheileAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 989 - 996

https://doi.org/10.1145/2001576.2001711

Published: 12 July 2011 Publication History

Abstract

Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump.

First, we assess the potential speedup by crossover when combined with a fitness-invariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions.

Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity.

References

[1]

J. Culberson. Genetic invariance: A new paradigm for genetic algorithm design. Technical report, 1992.

[2]

M. Dietzfelbinger, B. Naudts, C. Van Hoyweghen, and I. Wegener. The analysis of a recombinative hill-climber on H-IFF. IEEE Transactions on Evolutionary Computation, 7(5):417--423, 2003.

Digital Library

[3]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In Proc. of GECCO '08, pages 539--546. ACM, 2008.

Digital Library

[4]

B. Doerr, D. Johannsen, T. Kötzing, F. Neumann, and M. Theile. More effective crossover operators for the all-pairs shortest path problem. In Proc. of PPSN '10, pages 184--193. Springer, 2010.

Digital Library

[5]

B. Doerr and M. Theile. Improved analysis methods for crossover-based algorithms. In Proc. of GECCO '09, pages 247--254. ACM, 2009.

Digital Library

[6]

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

[7]

S. Droste, T. Jansen, and I. Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems, 39(4):525--544, 2006.

Digital Library

[8]

S. Fischer and I. Wegener. The one-dimensional Ising model: Mutation versus recombination. Theoretical Computer Science, 344(2--3):208--225, 2005.

Digital Library

[9]

T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt. Analysis of diversity-preserving mechanisms for global exploration. Evolutionary Computation, 17(4):455--476, 2009.

Digital Library

[10]

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

Digital Library

[11]

C. Horoba and D. Sudholt. Running time analysis of ACO systems for shortest path problems. In Proc. of SLS '09, pages 76--91. Springer, 2009.

Digital Library

[12]

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

Digital Library

[13]

T. Jansen and I. Wegener. Real royal road functions--where crossover provably is essential. Discrete Applied Mathematics, 149:111--125, 2005.

Digital Library

[14]

P. K. Lehre and C. Witt. Black box search by unbiased variation. In Proc. of GECCO '10, pages 1441--1448, 2010.

Digital Library

[15]

A. Moraglio. Convex evolutionary search. In Proc. of FOGA '11, pages 151--162. ACM, 2011.

Digital Library

[16]

F. Neumann and M. Theile. How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem. In Proc. of PPSN '10, pages 667--676. Springer, 2010.

Digital Library

[17]

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

Digital Library

[18]

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

[19]

J. N. Richter, A. Wright, and J. Paxton. Ignoble trails - where crossover is provably harmful. In Proc. of PPSN '08, pages 92--101. Springer, 2008.

Digital Library

[20]

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

Digital Library

[21]

D. Sudholt. Crossover is provably essential for the Ising model on trees. In Proc. of GECCO '05, pages 1161--1167. ACM, 2005.

Digital Library

[22]

R. A. Watson and T. Jansen. A building-block royal road where crossover is provably essential. In Proc. of GECCO '07, pages 1452--1459. ACM, 2007.

Digital Library

[23]

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.

[24]

A. H. Wright, M. D. Vose, and J. E. Rowe. Implicit parallelism. In Proc. of GECCO '03, pages 1505--1517. Springer, 2003.

Digital Library

Cited By

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
Opris ALengler JSudholt DLi XHandl J(2024)A Tight O(4/p) Runtime Bound for a (μ+1)GA on Jump for Realistic Crossover ProbabilitiesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654120(1605-1613)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654120
Show More Cited By

Index Terms

How crossover helps in pseudo-boolean optimization
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Escaping Local Optima with Diversity Mechanisms and Crossover
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016
Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jump_k. All ...
How crossover speeds up building block assembly in genetic algorithms

We reinvestigate a fundamental question: How effective is crossover in genetic algorithms in combining building blocks of good solutions? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. ...
Partition Crossover for Pseudo-Boolean Optimization
FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

A partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

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: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
318
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Opris ALengler JSudholt DLi XHandl J(2024)A Tight O(4/p) Runtime Bound for a (μ+1)GA on Jump for Realistic Crossover ProbabilitiesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654120(1605-1613)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654120
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
Lengler JOpris ASudholt D(2024)Analysing Equilibrium States for Population DiversityAlgorithmica10.1007/s00453-024-01226-386:7(2317-2351)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-024-01226-3
Cerf SLengler J(2024)How Population Diversity Influences the Efficiency of CrossoverParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_7(102-116)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_7
Aladdin ARashid T(2023)A New Lagrangian Problem Crossover—A Systematic Review and Meta-Analysis of Crossover StandardsSystems10.3390/systems1103014411:3(144)Online publication date: 9-Mar-2023
https://doi.org/10.3390/systems11030144
Friedrich TKötzing TRadhakrishnan ASchiller LSchirneck MTennigkeit GWietheger S(2023)Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization10.1145/36036293:2(1-32)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3603629
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
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