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
- Genetic Instruct: Scaling up Synthetic Generation of Coding Instructions for Large Language Models [54.51932175059004]
We introduce a scalable method for generating synthetic instructions to enhance the code generation capability of Large Language Models.
The proposed algorithm, Genetic-Instruct, mimics evolutionary processes, utilizing self-instruction to create numerous synthetic samples from a limited number of seeds.
arXiv Detail & Related papers (2024-07-29T20:42:59Z) - 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)
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.