A Survey and Analysis of Evolutionary Operators for Permutations
- URL: http://arxiv.org/abs/2311.14595v1
- Date: Fri, 24 Nov 2023 16:32:44 GMT
- Title: A Survey and Analysis of Evolutionary Operators for Permutations
- Authors: Vincent A. Cicirello
- Abstract summary: Evolving permutations directly requires specialized evolutionary operators.
In this paper, we survey the breadth of evolutionary operators for permutations.
We implement all of these in Chips-n-Salsa, an open source Java library for evolutionary computation.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There are many combinatorial optimization problems whose solutions are best
represented by permutations. The classic traveling salesperson seeks an optimal
ordering over a set of cities. Scheduling problems often seek optimal orderings
of tasks or activities. Although some evolutionary approaches to such problems
utilize the bit strings of a genetic algorithm, it is more common to directly
represent solutions with permutations. Evolving permutations directly requires
specialized evolutionary operators. Over the years, many crossover and mutation
operators have been developed for solving permutation problems with
evolutionary algorithms. In this paper, we survey the breadth of evolutionary
operators for permutations. We implemented all of these in Chips-n-Salsa, an
open source Java library for evolutionary computation. Finally, we empirically
analyze the crossover operators on artificial fitness landscapes isolating
different permutation features.
Related papers
- Massively Parallel Genetic Optimization through Asynchronous Propagation
of Populations [50.591267188664666]
Propulate is an evolutionary optimization algorithm and software package for global optimization.
We provide an MPI-based implementation of our algorithm, which features variants of selection, mutation, crossover, and migration.
We find that Propulate is up to three orders of magnitude faster without sacrificing solution accuracy.
arXiv Detail & Related papers (2023-01-20T18:17:34Z) - Socio-cognitive Optimization of Time-delay Control Problems using
Evolutionary Metaheuristics [89.24951036534168]
Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches.
In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
arXiv Detail & Related papers (2022-10-23T22:21:10Z) - On Fitness Landscape Analysis of Permutation Problems: From Distance
Metrics to Mutation Operator Selection [0.0]
We explore the theory and expand upon the practice of fitness landscape analysis for optimization problems over the space of permutations.
We begin with a survey of the available distance metrics for permutations, and then use principal component analysis to classify these metrics.
Our implementations of the permutation metrics, permutation mutation operators, and associated evolutionary algorithm, are available in a pair of open source Java libraries.
arXiv Detail & Related papers (2022-08-23T20:46:49Z) - Cycle Mutation: Evolving Permutations via Cycle Induction [0.0]
We propose cycle mutation, a new mutation operator whose inspiration is the well known cycle crossover operator.
We use fitness landscape analysis to explore the problem characteristics for which cycle mutation works best.
arXiv Detail & Related papers (2022-05-27T17:37:22Z) - On the Difficulty of Evolving Permutation Codes [7.673465837624365]
This paper addresses the design of permutation codes by evolutionary algorithms (EA) by developing an iterative approach.
Starting from a single random permutation, new permutations satisfying the minimum distance constraint are incrementally added to the code.
We compare the results achieved by our EA approach to those of a simple random search, remarking that neither method scales well with the problem size.
arXiv Detail & Related papers (2021-11-25T21:08:16Z) - Discovering Non-monotonic Autoregressive Orderings with Variational
Inference [67.27561153666211]
We develop an unsupervised parallelizable learner that discovers high-quality generation orders purely from training data.
We implement the encoder as a Transformer with non-causal attention that outputs permutations in one forward pass.
Empirical results in language modeling tasks demonstrate that our method is context-aware and discovers orderings that are competitive with or even better than fixed orders.
arXiv Detail & Related papers (2021-10-27T16:08:09Z) - Batch Bayesian Optimization on Permutations using Acquisition Weighted
Kernels [86.11176756341114]
We introduce LAW, a new efficient batch acquisition method based on the determinantal point process.
We provide a regret analysis for our method to gain insight in its theoretical properties.
We evaluate the method on several standard problems involving permutations such as quadratic assignment.
arXiv Detail & Related papers (2021-02-26T10:15:57Z) - AdaLead: A simple and robust adaptive greedy search algorithm for
sequence design [55.41644538483948]
We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead)
AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
arXiv Detail & Related papers (2020-10-05T16:40:38Z) - The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
We show that the $(lambda,lambda)$ genetic algorithm finds the optimum in $O(n2)$ fitness queries.
We also present the first analysis of this algorithm on a permutation-based problem called Ham.
arXiv Detail & Related papers (2020-04-18T17:04:57Z) - A Permutation-Equivariant Neural Network Architecture For Auction Design [49.41561446069114]
Design of an incentive compatible auction that maximizes expected revenue is a central problem in Auction Design.
In this work, we consider auction design problems that have permutationequivariant symmetry and construct a neural architecture that is capable of perfectly recovering the permutationequi optimal mechanism.
arXiv Detail & Related papers (2020-03-02T00:37:36Z)
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.