Cycle Mutation: Evolving Permutations via Cycle Induction

• URL: http://arxiv.org/abs/2205.14125v2
• Date: Tue, 31 May 2022 16:06:40 GMT
• Title: Cycle Mutation: Evolving Permutations via Cycle Induction
• Authors: Vincent A. Cicirello
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Evolutionary algorithms solve problems by simulating the evolution of a population of candidate solutions. We focus on evolving permutations for ordering problems like the traveling salesperson problem (TSP), as well as assignment problems like the quadratic assignment problem (QAP) and largest common subgraph (LCS). We propose cycle mutation, a new mutation operator whose inspiration is the well known cycle crossover operator, and the concept of a permutation cycle. We use fitness landscape analysis to explore the problem characteristics for which cycle mutation works best. As a prerequisite, we develop new permutation distance measures: cycle distance, $k$-cycle distance, and cycle edit distance. The fitness landscape analysis predicts that cycle mutation is better suited for assignment and mapping problems than it is for ordering problems. We experimentally validate these findings showing cycle mutation's strengths on problems like QAP and LCS, and its limitations on problems like the TSP, while also showing that it is less prone to local optima than commonly used alternatives. We integrate cycle mutation into the open-source Chips-n-Salsa library, and the new distance metrics into the open-source JavaPermutationTools library.

Related papers

• A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
  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.
  arXiv  Detail & Related papers  (2023-11-24T16:32:44Z)
• 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)
• Runtime Analysis for Permutation-based Evolutionary Algorithms [9.044970217182117]
  We show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order $mTheta(m)$ on jump functions with jump size $m$. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference.
  arXiv  Detail & Related papers  (2022-07-05T15:49:29Z)
• 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)
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow [73.1896399783641]
  In membership/subscriber acquisition and retention, we sometimes need to recommend marketing content for multiple pages in sequence. We propose to formulate the problem as an MDP with Bandits where Bandits are employed to model the transition probability matrix. We observe the proposed MDP with Bandits algorithm outperforms Q-learning with $epsilon$-greedy and decreasing $epsilon$, independent Bandits, and interaction Bandits.
  arXiv  Detail & Related papers  (2021-07-01T03:54:36Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• SPANet: Generalized Permutationless Set Assignment for Particle Physics using Symmetry Preserving Attention [62.43586180025247]
  Collisions at the Large Hadron Collider produce variable-size sets of observed particles. Physical symmetries of decay products complicate assignment of observed particles to decay products. We introduce a novel method for constructing symmetry-preserving attention networks.
  arXiv  Detail & Related papers  (2021-06-07T18:18:20Z)
• Multiview Sensing With Unknown Permutations: An Optimal Transport Approach [42.62524143925126]
  We take a fresh look at the problem of recovering a signal subject to unknown permutations through the lens of optimal transport. We exploit this by introducing a regularization function that promotes the more likely permutations in the solution. We show that, even though the general problem is not convex, an appropriate relaxation of the resulting regularized problem allows us to exploit the well-developed machinery of OT and develop a tractable algorithm.
  arXiv  Detail & Related papers  (2021-03-12T18:48:18Z)
• 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)
• Tell Me How to Ask Again: Question Data Augmentation with Controllable Rewriting in Continuous Space [94.8320535537798]
  Controllable Rewriting based Question Data Augmentation (CRQDA) for machine reading comprehension (MRC), question generation, and question-answering natural language inference tasks. We treat the question data augmentation task as a constrained question rewriting problem to generate context-relevant, high-quality, and diverse question data samples.
  arXiv  Detail & Related papers  (2020-10-04T03:13:46Z)

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.