Diversity-Preserving Exploitation of Crossover

• URL: http://arxiv.org/abs/2507.01524v1
• Date: Wed, 02 Jul 2025 09:28:06 GMT
• Title: Diversity-Preserving Exploitation of Crossover
• Authors: Johannes Lengler, Tom Offermann,
• Abstract summary: We introduce a new paradigm for utilizing crossover that reduces this antagonism, which we call diversity-preserving exploitation of crossover (DiPEC)<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 finds the optimum of LeadingOnes with $O(n^{5/3}\log^{2/3} n)$ fitness evaluations. This is remarkable since standard genetic algorithms need $\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.

Related papers

• Analysing Equilibrium States for Population Diversity [0.0]
  Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover. We study how population diversity of $(mu+1)$ algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment.
  arXiv  Detail & Related papers  (2023-04-19T14:30:20Z)
• Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation [4.212663349859165]
  We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II. We show that immune-inspired hypermutations cannot avoid exponential optimisation times.
  arXiv  Detail & Related papers  (2023-01-31T15:03:34Z)
• Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search [20.948038514886377]
  Population-based search has emerged as a possible alternative to Reinforcement Learning (RL) for black-box neural architecture search (NAS) This paper presents the first theoretical analysis of the behaviors of mutation, crossover and RL in black-box NAS. It proposes a new crossover operator based on the shortest edit path (SEP) in graph space.
  arXiv  Detail & Related papers  (2022-10-25T13:39:55Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• A Large-scale Multiple-objective Method for Black-box Attack against Object Detection [70.00150794625053]
  We propose to minimize the true positive rate and maximize the false positive rate, which can encourage more false positive objects to block the generation of new true positive bounding boxes. We extend the standard Genetic Algorithm with Random Subset selection and Divide-and-Conquer, called GARSDC, which significantly improves the efficiency. Compared with the state-of-art attack methods, GARSDC decreases by an average 12.0 in the mAP and queries by about 1000 times in extensive experiments.
  arXiv  Detail & Related papers  (2022-09-16T08:36:42Z)
• A New Lagrangian Problem Crossover: A Systematic Review and Meta-Analysis of Crossover Standerds [1.1802674324027231]
  This paper presents an overview of crossover standards classification. The significance of novel standard crossover is proposed depending on Lagrangian Dual Function (LDF) The accuracy and performance of the proposed standard have evaluated by three unimodal test functions.
  arXiv  Detail & Related papers  (2022-04-21T15:50:02Z)
• A Twin Neural Model for Uplift [59.38563723706796]
  Uplift is a particular case of conditional treatment effect modeling. We propose a new loss function defined by leveraging a connection with the Bayesian interpretation of the relative risk. We show our proposed method is competitive with the state-of-the-art in simulation setting and on real data from large scale randomized experiments.
  arXiv  Detail & Related papers  (2021-05-11T16:02:39Z)
• A Crossover That Matches Diverse Parents Together in Evolutionary Algorithms [0.228438857884398]
  The problem of choice is evolutionary decision tree construction. We propose a new method of performing the crossover phase. One variant emerges clearly as the best approach, whereas the remaining ones are below the baseline.
  arXiv  Detail & Related papers  (2021-05-08T11:43:26Z)
• Diverse Knowledge Distillation for End-to-End Person Search [81.4926655119318]
  Person search aims to localize and identify a specific person from a gallery of images. Recent methods can be categorized into two groups, i.e., two-step and end-to-end approaches. We propose a simple yet strong end-to-end network with diverse knowledge distillation to break the bottleneck.
  arXiv  Detail & Related papers  (2020-12-21T09:04:27Z)
• Rethinking conditional GAN training: An approach using geometrically structured latent manifolds [58.07468272236356]
  Conditional GANs (cGAN) suffer from critical drawbacks such as the lack of diversity in generated outputs. We propose a novel training mechanism that increases both the diversity and the visual quality of a vanilla cGAN.
  arXiv  Detail & Related papers  (2020-11-25T22:54:11Z)
• Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability [4.33419118449588]
  We investigate a family of $(mu+lambda)$ Genetic Algorithms (GAs) which creates offspring either from mutation or by recombining two randomly chosen parents. By scaling the crossover probability, we can thus interpolate from a fully mutation-only algorithm towards a fully crossover-based GA.
  arXiv  Detail & Related papers  (2020-06-10T15:22:44Z)
• AvgOut: A Simple Output-Probability Measure to Eliminate Dull Responses [97.50616524350123]
  We build dialogue models that are dynamically aware of what utterances or tokens are dull without any feature-engineering. The first model, MinAvgOut, directly maximizes the diversity score through the output distributions of each batch. The second model, Label Fine-Tuning (LFT), prepends to the source sequence a label continuously scaled by the diversity score to control the diversity level. The third model, RL, adopts Reinforcement Learning and treats the diversity score as a reward signal.
  arXiv  Detail & Related papers  (2020-01-15T18:32:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.