Improving the Search by Encoding Multiple Solutions in a Chromosome

• URL: http://arxiv.org/abs/2110.11239v1
• Date: Wed, 13 Oct 2021 09:38:50 GMT
• Title: Improving the Search by Encoding Multiple Solutions in a Chromosome
• Authors: Mihai Oltean
• Abstract summary: We investigate the possibility of encoding multiple solutions of a problem in a single chromosome. In order to obtain some benefits the chromosome decoding process must have the same complexity as in the case of a single solution in a chromosome. Numerical experiments show that encoding multiple solutions in a chromosome greatly improves the search process.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the possibility of encoding multiple solutions of a problem in a single chromosome. The best solution encoded in an individual will represent (will provide the fitness of) that individual. In order to obtain some benefits the chromosome decoding process must have the same complexity as in the case of a single solution in a chromosome. Three Genetic Programming techniques are analyzed for this purpose: Multi Expression Programming, Linear Genetic Programming, and Infix Form Genetic Programming. Numerical experiments show that encoding multiple solutions in a chromosome greatly improves the search process.

Related papers

• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• GEC-DePenD: Non-Autoregressive Grammatical Error Correction with Decoupled Permutation and Decoding [52.14832976759585]
  Grammatical error correction (GEC) is an important NLP task that is usually solved with autoregressive sequence-to-sequence models. We propose a novel non-autoregressive approach to GEC that decouples the architecture into a permutation network. We show that the resulting network improves over previously known non-autoregressive methods for GEC.
  arXiv  Detail & Related papers  (2023-11-14T14:24:36Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut.
  arXiv  Detail & Related papers  (2022-04-15T03:32:40Z)
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems [0.0]
  We present an intuitive method for synthesizing and analyzing discrete (i.e., integer-based) optimization problems. This method is expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. Second, we perform numerical studies comparing several runtime encodings. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables.
  arXiv  Detail & Related papers  (2022-03-28T01:01:12Z)
• Multi Expression Programming for solving classification problems [0.0]
  Multi Expression Programming (MEP) is a Genetic Programming variant which encodes multiple solutions in a single chromosome. This paper introduces and deeply describes several strategies for solving binary and multi-class classification problems within the textitmulti solutions per chromosome paradigm of MEP.
  arXiv  Detail & Related papers  (2022-03-16T13:11:50Z)
• Deriving Smaller Orthogonal Arrays from Bigger Ones with Genetic Algorithm [1.370633147306388]
  We consider the problem of constructing a binary array starting from a bigger one, by removing a specified amount of lines. We develop a genetic algorithm where the underlying chromosomes are constant-weight binary strings that specify the lines to be cancelled from the starting OA. We perform a preliminary experimental validation of the proposed genetic algorithm by crafting the initial OA as a random permutation of several blocks of the basic parity-check array.
  arXiv  Detail & Related papers  (2021-11-25T12:06:24Z)
• Multi Expression Programming -- an in-depth description [0.0]
  MEP individuals are strings of genes encoding complex computer programs. A unique MEP feature is the ability to store multiple solutions of a problem in a single chromosome.
  arXiv  Detail & Related papers  (2021-09-29T01:57:18Z)
• Evolving Digital Circuits for the Knapsack Problem [0.0]
  Multi Expression Programming (MEP) is a Genetic Programming variant that uses linear chromosomes for solution encoding. In this paper we use Multi Expression Programming for evolving digital circuits for a well-known NP-Complete problem: the knapsack (subset sum) problem.
  arXiv  Detail & Related papers  (2021-08-21T15:48:50Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• 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)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

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.