Evolving Digital Circuits for the Knapsack Problem

• URL: http://arxiv.org/abs/2109.13107v1
• Date: Sat, 21 Aug 2021 15:48:50 GMT
• Title: Evolving Digital Circuits for the Knapsack Problem
• Authors: Mihai Oltean, Crina Gro\c{s}an and Mihaela Oltean
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi Expression Programming (MEP) is a Genetic Programming variant that uses linear chromosomes for solution encoding. A unique feature of MEP is its ability of encoding multiple solutions of a problem in a single chromosome. In this paper we use Multi Expression Programming for evolving digital circuits for a well-known NP-Complete problem: the knapsack (subset sum) problem. Numerical experiments show that Multi Expression Programming performs well on the considered test problems.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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)
• NAPG: Non-Autoregressive Program Generation for Hybrid Tabular-Textual Question Answering [52.10214317661547]
  Current numerical reasoning methods autoregressively decode program sequences. The accuracy of program generation drops sharply as the decoding steps unfold due to error propagation. In this paper, we propose a non-autoregressive program generation framework.
  arXiv  Detail & Related papers  (2022-11-07T11:25:21Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• 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)
• Mixed-Integer Programming Using a Bosonic Quantum Computer [0.0]
  We propose a scheme for solving mixed-integer programming problems in which the optimization problem is translated to a ground-state preparation problem on a bosonic quantum field modes (qumodes) We show numerical demonstrations by a circuit-based optical quantum computer with each individual qumode prepared.
  arXiv  Detail & Related papers  (2021-12-27T22:01:05Z)
• Improving the Search by Encoding Multiple Solutions in a Chromosome [0.0]
  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.
  arXiv  Detail & Related papers  (2021-10-13T09:38:50Z)
• 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 Evolutionary Algorithms using Multi Expression Programming [0.0]
  Instead of evolving only the parameters of the algorithm we will evolve an entire EA capable of solving a particular problem. An nongenerational EA for function optimization is evolved in this paper. Numerical experiments show the effectiveness of this approach.
  arXiv  Detail & Related papers  (2021-08-22T09:30:57Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• 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)

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.