poster

Experimental Analyses of Crossover and Diversity on Jump

Authors:

Xiaoyue Li,

Timo KötzingAuthors Info & Claims

GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

Pages 823 - 826

https://doi.org/10.1145/3583133.3590657

Published: 24 July 2023 Publication History

Get Access

Abstract

While it is mathematically proven that the (μ + 1) GA optimizes Jump_k efficiently for low crossover probabilities, theory research still struggles with the analysis of crossover-based optimization for high crossover probabilities on this key test function. Research in this area has improved our understanding of crossover in general, in particular regarding the emergence of diversity, the crucial ingredient for successful optimization with genetic algorithms.

In this paper we study the optimizing process after the (μ + 1) GAhas reached the plateau of Jump_k. We are interested in (a) the stationary distribution of the algorithm on the plateau (when ignoring the optimum) and (b) the dynamics of the stationary distribution. We experimentally show that the (μ+1) GA achieves 10% complementary pairs if μ = 10 · k, unless n is very small. Regarding the dynamics, we show samples of how bit positions gain and lose individuals with a 0 at that position.

References

[1]

Duc-Cuong Dang, Tobias Friedrich, Martin S. Krejca, Timo Kötzing, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew Michael Sutton. 2016. Escaping Local Optima with Diversity Mechanisms and Crossover. In Proc. of GECCO'16. ACM Press, 645--652.

Google Scholar

[2]

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping Local Optima Using Crossover With Emergent Diversity. IEEE Transactions on Evolutionary Computation 22, 3 (2018), 484--497.

Crossref

Google Scholar

[3]

Grasiele R. Duarte and Beatriz S. L. P. de Lima. 2021. An Operation to Promote Diversity in Evolutionary Algorithms in a Dynamic Hybrid Island Model. In Proc. of GECCO'21 Companion. ACM Press, 1779--1787.

Google Scholar

[4]

Thomas Gabor, Lenz Belzner, and Claudia Linnhoff-Popien. 2018. Inheritance-Based Diversity Measures for Explicit Convergence Control in Evolutionary Algorithms. In Proc. of GECCO'18. ACM Press, 841--848.

Digital Library

Google Scholar

[5]

Thomas Jansen and Ingo Wegener. 2002. The Analysis of Evolutionary Algorithms - A Proof That Crossover Really Can Help. Algorithmica 34 (2002), 47--66.

Digital Library

Google Scholar

[6]

Valentín Osuna-Enciso, Erik Cuevas, and Bernardo Morales Castañeda. 2022. A diversity metric for population-based metaheuristic algorithms. Information Sciences 586 (2022), 192--208.

Digital Library

Google Scholar

[7]

Adam Prügel-Bennett. 2010. Benefits of a Population: Five Mechanisms That Advantage Population-Based Algorithms. IEEE TEvC 14 (2010), 500--517.

Google Scholar

[8]

Giovanni Squillero and Alberto Tonda. 2016. Divergence of character and premature convergence: A survey of methodologies for promoting diversity in evolutionary optimization. Information Sciences 329 (2016), 782--799.

Digital Library

Google Scholar

[9]

Dirk Sudholt. 2020. The Benefits of Population Diversity in Evolutionary Algorithms: A Survey of Rigorous Runtime Analyses. Springer, 359--404.

Google Scholar

Cited By

View all

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

Index Terms

Experimental Analyses of Crossover and Diversity on Jump
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 helps in pseudo-boolean optimization
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

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 ...
Crossover Consideration in Genetic Algorithm
ICMLSC '24: Proceedings of the 2024 8th International Conference on Machine Learning and Soft Computing

Crossover is an important process in genetic algorithms. This process will swap genes between the chromosomes of the parents. The results from the crossover process may not be better than those of the parents, which affect the result of the genetic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

July 2023

2519 pages

ISBN:9798400701207

DOI:10.1145/3583133

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the owner/author(s).

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2023

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO '23 Companion

Sponsor:

SIGEVO

GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
31
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

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

View Options

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

Escaping Local Optima with Diversity Mechanisms and Crossover

How crossover helps in pseudo-boolean optimization

Crossover Consideration in Genetic Algorithm