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, 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) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
Two current popular bilevelimats AID-BiO and ITD-BiO naturally involve solving one or two sub-problems.
We first establish unified convergence analysis for both AID-BiO and ITD-BiO that are applicable to all implementation choices of loops.
arXiv Detail & Related papers (2022-05-27T20:28:52Z) - 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.