Semantically-Oriented Mutation Operator in Cartesian Genetic Programming for Evolutionary Circuit Design

• URL: http://arxiv.org/abs/2004.11018v1
• Date: Thu, 23 Apr 2020 08:15:48 GMT
• Title: Semantically-Oriented Mutation Operator in Cartesian Genetic Programming for Evolutionary Circuit Design
• Authors: David Hodan, Vojtech Mrazek, Zdenek Vasicek
• Abstract summary: We propose a semantically-oriented mutation operator (SOMO) suitable for the evolutionary design of combinational circuits. Compared to the common CGP and its variants, the proposed method converges on common Boolean benchmarks substantially faster. The most complex circuits were evolved in less than one hour with a single-thread implementation running on a common CPU.
• Score: 0.5414308305392761
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite many successful applications, Cartesian Genetic Programming (CGP) suffers from limited scalability, especially when used for evolutionary circuit design. Considering the multiplier design problem, for example, the 5x5-bit multiplier represents the most complex circuit evolved from a randomly generated initial population. The efficiency of CGP highly depends on the performance of the point mutation operator, however, this operator is purely stochastic. This contrasts with the recent developments in Genetic Programming (GP), where advanced informed approaches such as semantic-aware operators are incorporated to improve the search space exploration capability of GP. In this paper, we propose a semantically-oriented mutation operator (SOMO) suitable for the evolutionary design of combinational circuits. SOMO uses semantics to determine the best value for each mutated gene. Compared to the common CGP and its variants as well as the recent versions of Semantic GP, the proposed method converges on common Boolean benchmarks substantially faster while keeping the phenotype size relatively small. The successfully evolved instances presented in this paper include 10-bit parity, 10+10-bit adder and 5x5-bit multiplier. The most complex circuits were evolved in less than one hour with a single-thread implementation running on a common CPU.

Related papers

• Analysing the Influence of Reorder Strategies for Cartesian Genetic Programming [0.0]
  We introduce three novel operators which reorder the genotype of a graph defined by CGP. We show that the number of iterations until a solution is found and/or the fitness value improves by using CGP with a reorder method. However, there is no consistently best performing reorder operator.
  arXiv  Detail & Related papers  (2024-10-01T08:59:01Z)
• A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design [92.63517027087933]
  A key task in Logic Synthesis (LS) is to transform circuits into simplified circuits with equivalent functionalities. To tackle this task, many LS operators apply transformations to subgraphs -- rooted at each node on an input DAG -- sequentially. We propose a novel data-driven LS operator paradigm, namely PruneX, to reduce ineffective transformations.
  arXiv  Detail & Related papers  (2023-08-22T16:18:48Z)
• Coefficient Mutation in the Gene-pool Optimal Mixing Evolutionary Algorithm for Symbolic Regression [0.0]
  GP-GOMEA is a top-performing algorithm for symbolic regression. We show how simple approaches for optimizing coefficients can be integrated into GP-GOMEA. We find that coefficient mutation can help re-discover the underlying equation by a substantial amount.
  arXiv  Detail & Related papers  (2022-04-26T08:58:47Z)
• Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings) [27.185579156106694]
  This paper characterizes the inherent power of evolutionary algorithms. It shows that expressive encodings can be a key to understanding and realizing the full power of evolution.
  arXiv  Detail & Related papers  (2022-02-19T20:54:37Z)
• Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times [119.41129787351092]
  We show that sequential black-box optimization based on GPs can be made efficient by sticking to a candidate solution for multiple evaluation steps. We modify two well-established GP-Opt algorithms, GP-UCB and GP-EI to adapt rules from batched GP-Opt.
  arXiv  Detail & Related papers  (2022-01-30T20:42:14Z)
• Non-Gaussian Gaussian Processes for Few-Shot Regression [71.33730039795921]
  We propose an invertible ODE-based mapping that operates on each component of the random variable vectors and shares the parameters across all of them. NGGPs outperform the competing state-of-the-art approaches on a diversified set of benchmarks and applications.
  arXiv  Detail & Related papers  (2021-10-26T10:45:25Z)
• Frame Averaging for Invariant and Equivariant Network Design [50.87023773850824]
  We introduce Frame Averaging (FA), a framework for adapting known (backbone) architectures to become invariant or equivariant to new symmetry types. We show that FA-based models have maximal expressive power in a broad setting. We propose a new class of universal Graph Neural Networks (GNNs), universal Euclidean motion invariant point cloud networks, and Euclidean motion invariant Message Passing (MP) GNNs.
  arXiv  Detail & Related papers  (2021-10-07T11:05:23Z)
• Top-N: Equivariant set and graph generation without exchangeability [61.24699600833916]
  We consider one-shot probabilistic decoders that map a vector-shaped prior to a distribution over sets or graphs. These functions can be integrated into variational autoencoders (VAE), generative adversarial networks (GAN) or normalizing flows. Top-n is a deterministic, non-exchangeable set creation mechanism which learns to select the most relevant points from a trainable reference set.
  arXiv  Detail & Related papers  (2021-10-05T14:51:19Z)
• X-volution: On the unification of convolution and self-attention [52.80459687846842]
  We propose a multi-branch elementary module composed of both convolution and self-attention operation. The proposed X-volution achieves highly competitive visual understanding improvements.
  arXiv  Detail & Related papers  (2021-06-04T04:32:02Z)
• Zoetrope Genetic Programming for Regression [2.642406403099596]
  The Zoetrope Genetic Programming (ZGP) algorithm is based on an original representation for mathematical expressions. ZGP is validated using a large number of public domain regression datasets.
  arXiv  Detail & Related papers  (2021-02-26T10:47:10Z)
• Genetic Programming is Naturally Suited to Evolve Bagging Ensembles [0.0]
  We show that minor changes to fitness evaluation and selection are sufficient to make a simple and otherwise-traditional GP algorithm evolve efficiently. Our algorithm fares very well against state-of-the-art ensemble and non-ensemble GP algorithms.
  arXiv  Detail & Related papers  (2020-09-13T16:28:11Z)

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.