On the Difficulty of Evolving Permutation Codes

• URL: http://arxiv.org/abs/2111.13252v1
• Date: Thu, 25 Nov 2021 21:08:16 GMT
• Title: On the Difficulty of Evolving Permutation Codes
• Authors: Luca Mariot, Stjepan Picek, Domagoj Jakobovic, Marko Djurasevic, Alberto Leporati
• Abstract summary: 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.
• Score: 7.673465837624365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial designs provide an interesting source of optimization problems. Among them, permutation codes are particularly interesting given their applications in powerline communications, flash memories, and block ciphers. 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 by using a permutation-based EA. We investigate our approach against four different fitness functions targeting the minimum distance requirement at different levels of detail and with two different policies concerning code expansion and pruning. 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.

Related papers

• Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
  We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs. We show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model.
  arXiv  Detail & Related papers  (2024-07-12T19:27:13Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• 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)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
  optimisation algorithms designed to work on quantum computers have been of research interest in recent years. Many of these solver can only optimise problems that are in binary and quadratic form. There are many optimisation problems that are naturally represented as permutations. We propose new static methods of calculating penalty weights which lead to more promising results.
  arXiv  Detail & Related papers  (2022-06-20T22:00:38Z)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47: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)
• Generating Correct Answers for Progressive Matrices Intelligence Tests [88.78821060331582]
  Raven's Progressive Matrices are multiple-choice intelligence tests, where one tries to complete the missing location in a $3times 3$ grid of abstract images. Previous attempts to address this test have focused solely on selecting the right answer out of the multiple choices. In this work, we focus, instead, on generating a correct answer given the grid, without seeing the choices, which is a harder task, by definition.
  arXiv  Detail & Related papers  (2020-11-01T13:21:07Z)

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.