Diversity-Preserving Exploitation of Crossover
Johannes Lengler, Tom Offermann · 2025
Read Diversity-Preserving Exploitation of Crossover by Johannes Lengler, Tom Offermann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01524.txt.
Introduction
Johannes Lengler and Tom Offermann introduce a way to use crossover in evolution without draining variety, in a 2025 paper. Crossover mixes two parent solutions to make new ones. It works best when the pool is varied. Yet using it tends to shrink that variety. This self defeating loop limits many genetic methods. Their paradigm keeps variety high. It still exploits the gains of mixing.
The resulting method was proven to solve a standard benchmark, LeadingOnes, in notably fewer scoring runs than classic genetic methods need. Only artificial, hand tailored methods had broken that barrier before. Simulations confirmed the theory. Tests on other benchmarks showed the method stays competitive beyond its home example. The authors argue the paradigm deserves systematic study.
Catalog record
| CREATOR | Johannes Lengler, Tom Offermann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-01524
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Diversity-Preserving Exploitation of Crossover Johannes Lengler, Tom Offermann Abstract Crossover is a powerful mechanism for generating new solutions from a given population of solutions. Crossover comes with a discrepancy in itself: on the one hand, crossover usually works best if there is enough diversity in the population; on the other hand, exploiting the benefits of crossover reduces diversity. This antagonism often makes crossover reduce its own effectiveness. We introduce a new paradigm for utilizing crossover that reduces this antagonism, which we call diversity-preserving exploitation of crossover (DiPEC) . The resulting Diversity Exploitation Genetic Algorithm ( DEGA ) is able to still exploit the benefits of crossover, but preserves a much higher diversity than conventional approaches. We demonstrate the benefits by proving that the ( 2 + 1 ) -DEGA (2+1)\textsc{-DEGA} finds the optimum of LeadingOnes with O ( n 5 / 3 log 2 / 3 n ) O(n^{5/3}\log^{2/3}n) fitness evaluations. This is remarkable since standard genetic algorithms need Θ ( n 2 ) \Theta(n^{2}) evaluations, and among genetic algorithms only some artificial and specifically tailored algorithms were known to break this runtime barrier. We confirm the theoretical results by simulations. Finally, we show that the approach is not overfitted to LeadingOnes by testing it empirically on other benchmarks and showing that it is also competitive in other settings. We believe that our findings justify further systematic investigations of the DiPEC paradigm. Keywords: Genetic Algorithm, Runtime Analysis, Diversity, Crossover, Mutation Mask 1 Introduction Crossover, the idea of recombining two or more solutions into a new one, is a key ingredient of genetic algorithms vcrepinvsek2013exploration ; whitley2019next . Crossover often works best when there is enough diversity in the population dang2017escaping ; sudholt2017crossover ; opris2024tight ; doerr2024runtime ; cerf2024population , see also the survey in sudholt2020benefits . In this case, crossover may serve as an exploitation mechanism which is able to find solutions that are fitter than the current population vcrepinvsek2013exploration . However, as usual for exploitation mechanism this comes at a cost for population diversity. In this paper we suggest the following new paradigm for utilizing crossover, which maintains some of the benefits of crossover without destroying so much diversity. The new paradigm: diversity-preserving exploitation of crossover (DiPEC). For illustration, consider optimization of pseudo-Boolean functions f:\{0,1\}^{n}\to\mathbb{R} with uniform crossover. For two parents x^{1} and x^{2} , uniform crossover creates an offspring y by selecting each bit randomly from either x^{1} or x^{2} . Consider the case that y replaces x^{1} or x^{2} in the population. Then the Hamming distance of the new pair \{x^{1},y\} or \{x^{2},y\} is in expectation only half as large as the Hamming distance of the previous pair \{x^{1},x^{2}\} . Hence, diversity of this pair, measured by its Hamming distance, is roughly cut in half, which constitutes a massive loss of diversity. In this paper we will focus on population size 2 , where this is the normal case, and the diversity of the whole population is cut in half. However, the same principle also applies to larger population sizes. In order to explain the new DiPEC paradigm, let us consider the example above and rephrase it. For concreteness, assume that the result of crossover y is fitter than x^{1} , and let m:=x^{1}\oplus y be the bit-wise xor of x^{1} and y . A way to interpret the situation is that m is a fitness-improving mask for x^{1} : if we start from x^{1} and apply the mask m , i.e., flip all bits in x^{1} where the mask has a one-bit, then this yields the search point x^{1}\oplus m=y of higher fitness. So a re-interpretation of the situation is that we have found a fitness-improving mask for x^{1} , where the one-bits in the mask encode bit flips to x^{1} . The problem of this mask is that applying it destroys diversity by decreasing the Hamming distance from x^{1} to x^{2} , roughly by a factor of 2 . The key idea is that in such a situation, the mask m can often be replaced by a smaller mask, meaning a mask that has fewer one-bits. This is based on the assumption that not all bit flips in m are equally important. Often, a small number of critical bit flips in m is responsible for all or most of the fitness improvement, while many other bit flips may contribute little. The key insight is that in such a case, it may be possible to find those critical bit flips efficiently by subsampling the mask m . I.e., we randomly compute another mask m^{\prime} where we independently keep each one-bit with some probability 1/\lambda , while everything else is a zero-bit. Then we apply the mask m^{\prime} to x^{1} , yielding an offspring y^{\prime}:=x^{1}\oplus m^{\prime} . Equivalently, y^{\prime} can be obtained as a biased crossover 1 1 1 This is not related to the concept of unbiased operators introduced by Lehre and Witt lehre2012black . The biased crossover used here is still an unbiased operator in their sense. between x^{1} and y , where we take each bit from y with probability 1/\lambda , and from x^{1} with probability 1-1/\lambda . Then y^{\prime} has a decent chance of 1/\lambda to contain at least the most critical bit flip from the mask m . By repeating the biased crossover \lambda times, we have a good (constant) chance of generating at least one biased crossover that contains the most critical bit flip from the mask m , and hopefully the resulting offspring y^{\prime} is still strictly fitter than x^{1} . Crucially, the Hamming distance H(x^{1},y^{\prime}) is much smaller than the Hamming distance H(x^{1},y) . Hence, if we replace x^{1} by y^{\prime} then we destroy much less diversity than if we replace x^{1} by y . Quantitatively, while we lose in expectation a factor 1/2 with y , i.e., \mathbb{E}[H(x^{2},y)]=\tfrac{1}{2}H(x^{1},x^{2}) , we only lose a factor of 1-\tfrac{1}{2\lambda} with y^{\prime} , i.e., \mathbb{E}[H(x^{2},y^{\prime})]=(1-\tfrac{1}{2\lambda})H(x^{1},x^{2}) . This is a massive difference for preserving diversity, and we will show in this paper that it is often a worthwhile trade-off. Hence we suggest not to consider y for inclusion into the population, but the fittest biased crossover offspring y^{\prime} out of \lambda trials instead. The trade-off in a good (and hopefully typical) situation looks as follows. • The fitness of y^{\prime} is almost as large as the fitness of y . • Including y^{\prime} destroys very little diversity, whereas including y would massively reduce diversity. • This comes at the cost of 1+\lambda function evaluations (of y and of \lambda candidates for y^{\prime} ) instead of just 1 . The cost can be reduced further, as we will discuss later. As we will discuss later, the idea of using biased crossover to extract the most beneficial bit has been used before in the ( 1+(\lambda,\lambda)) -GA doerr2015black , but in a very different situation and with different aim. Our contribution. Apart from introducing the DiPEC paradigm, in this paper we make some first steps of exploring it. Even though the DiPEC paradigm can be applied to arbitrary population sizes, and to arbitrary pairs of search points of different fitness, we focus here on population size \mu=2 and on