Dynastic Potential Crossover Operator

• URL: http://arxiv.org/abs/2402.03918v1
• Date: Tue, 6 Feb 2024 11:38:23 GMT
• Title: Dynastic Potential Crossover Operator
• Authors: Francisco Chicano, Gabriela Ochoa, Darrell Whitley, Renato Tin\'os
• Abstract summary: An optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. We present a recombination operator, called Dynastic Potential Crossover (DPX), that runs in partition time and behaves like an optimal recombination operator for low-epistasis problems.
• Score: 2.908482270923597
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An optimal recombination operator for two parent solutions provides the best solution among those that take the value for each variable from one of the parents (gene transmission property). If the solutions are bit strings, the offspring of an optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. Exploring this hyperplane is computationally costly, in general, requiring exponential time in the worst case. However, when the variable interaction graph of the objective function is sparse, exploration can be done in polynomial time. In this paper, we present a recombination operator, called Dynastic Potential Crossover (DPX), that runs in polynomial time and behaves like an optimal recombination operator for low-epistasis combinatorial problems. We compare this operator, both theoretically and experimentally, with traditional crossover operators, like uniform crossover and network crossover, and with two recently defined efficient recombination operators: partition crossover and articulation points partition crossover. The empirical comparison uses NKQ Landscapes and MAX-SAT instances. DPX outperforms the other crossover operators in terms of quality of the offspring and provides better results included in a trajectory and a population-based metaheuristic, but it requires more time and memory to compute the offspring.

Related papers

• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  Optimal transport theory provides a principled framework for constructing such mappings. We propose a novel optimal transport solver based on Wasserstein-1. Our experiments demonstrate that the proposed solver can mimic the $W$ OT solvers in finding a unique and monotonic" map on 2D datasets.
  arXiv  Detail & Related papers  (2024-11-01T14:23:19Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective [21.6146047576295]
  The top-k operator returns a sparse vector, where the non-zero values correspond to the k largest values of the input. We view the top-k operator as a linear program over the permutahedron, the convex hull of permutations. Our framework is significantly more general than the existing one and allows for example to express top-k operators that select values in magnitude.
  arXiv  Detail & Related papers  (2023-02-02T21:32:13Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• 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)
• Analyzing and Mitigating Interference in Neural Architecture Search [96.60805562853153]
  We investigate the interference issue by sampling different child models and calculating the gradient similarity of shared operators. Inspired by these two observations, we propose two approaches to mitigate the interference. Our searched architecture outperforms RoBERTa$_rm base$ by 1.1 and 0.6 scores and ELECTRA$_rm base$ by 1.6 and 1.1 scores on the dev and test set of GLUE benchmark.
  arXiv  Detail & Related papers  (2021-08-29T11:07:46Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
  We introduce Coop-FTPL, a cooperative version of the well-known Follow The Perturbed Leader algorithm. We show that the expected regret of our algorithm after T time steps is of order QT log(k)(k$alpha$ 1 /Q + m), where Q is the total activation probability mass.
  arXiv  Detail & Related papers  (2020-10-05T07:08:26Z)
• 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)
• Perfect Edge-Transmitting Recombination of Permutations [0.0]
  We derive an algorithm for crossover of permutations that achieves perfect transmission of edges. We also describe a modification of the algorithm that generates the mathematically optimal offspring for the asymmetric travelling salesman problem.
  arXiv  Detail & Related papers  (2020-05-03T15:15:49Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  The SOFT top-k operator approximates the output of the top-k operation as the solution of an Entropic Optimal Transport (EOT) problem. We apply the proposed operator to the k-nearest neighbors and beam search algorithms, and demonstrate improved performance.
  arXiv  Detail & Related papers  (2020-02-16T04:57:52Z)

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.