Evolutionary Algorithms for Designing Reversible Cellular Automata
- URL: http://arxiv.org/abs/2105.12039v1
- Date: Tue, 25 May 2021 16:19:58 GMT
- Title: Evolutionary Algorithms for Designing Reversible Cellular Automata
- Authors: Luca Mariot, Stjepan Picek, Domagoj Jakobovic, Alberto Leporati
- Abstract summary: Reversible Cellular Automata (RCA) are shift-invariant transformations characterized by a dynamics composed only of disjoint cycles.
We formulate the search of a specific class of RCA as an optimization problem to be tackled with Genetic Algorithms (GA) and Genetic Programming (GP)
Results shed new light on 1) the difficulty of the associated optimization problem for GA and GP, 2) the relevance of conserved landscape CA in the domain of cryptography and reversible computing, and 3) the relationship between the reversibility property and the Hamming weight.
- Score: 8.382710169577447
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reversible Cellular Automata (RCA) are a particular kind of shift-invariant
transformations characterized by a dynamics composed only of disjoint cycles.
They have many applications in the simulation of physical systems, cryptography
and reversible computing. In this work, we formulate the search of a specific
class of RCA -- namely, those whose local update rules are defined by conserved
landscapes -- as an optimization problem to be tackled with Genetic Algorithms
(GA) and Genetic Programming (GP). In particular, our experimental
investigation revolves around three different research questions, which we
address through a single-objective, a multi-objective, and a lexicographic
approach. The results obtained from our experiments corroborate the previous
findings and shed new light on 1) the difficulty of the associated optimization
problem for GA and GP, 2) the relevance of conserved landscape CA in the domain
of cryptography and reversible computing, and 3) the relationship between the
reversibility property and the Hamming weight.
Related papers
- Multi-objective Memetic Algorithm with Adaptive Weights for Inverse Antenna Design [0.0]
modification of a single-objective algorithm into its multi-objective counterpart.
Result is a considerable increase in speed in the order of tens to hundreds.
arXiv Detail & Related papers (2024-08-07T08:43:38Z) - Analyzing and Overcoming Local Optima in Complex Multi-Objective Optimization by Decomposition-Based Evolutionary Algorithms [5.153202024713228]
Multi-objective Evolutionary Algorithms (MOEADs) often converge to local optima, limiting solution diversity.
We introduce an innovative RP selection strategy, the Vector-Guided Weight-Hybrid method, designed to overcome the local optima issue.
Our research comprises two main experimental components: an ablation involving 14 algorithms within the MOEADs framework from 2014 to 2022 to validate our theoretical framework, and a series empirical tests to evaluate the effectiveness of our proposed method against both traditional and cutting-edge alternatives.
arXiv Detail & Related papers (2024-04-12T14:29:45Z) - Continuous Cartesian Genetic Programming based representation for
Multi-Objective Neural Architecture Search [12.545742558041583]
We propose a novel approach for designing less complex yet highly effective convolutional neural networks (CNNs)
Our approach combines real-based and block-chained CNNs representations based on cartesian genetic programming (CGP) for neural architecture search (NAS)
Two variants are introduced that differ in the granularity of the search space they consider.
arXiv Detail & Related papers (2023-06-05T07:32:47Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA)
We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$.
When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
arXiv Detail & Related papers (2021-10-18T14:00:22Z) - Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian
Modeling [68.69431580852535]
We introduce a novel GP regression to incorporate the subgroup feedback.
Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches.
We execute our algorithm on two disparate social problems.
arXiv Detail & Related papers (2021-07-07T03:57:22Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure.
We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
arXiv Detail & Related papers (2021-06-09T08:05:36Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm.
We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights.
We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
arXiv Detail & Related papers (2020-10-13T08:02:38Z) - Activation Relaxation: A Local Dynamical Approximation to
Backpropagation in the Brain [62.997667081978825]
Activation Relaxation (AR) is motivated by constructing the backpropagation gradient as the equilibrium point of a dynamical system.
Our algorithm converges rapidly and robustly to the correct backpropagation gradients, requires only a single type of computational unit, and can operate on arbitrary computation graphs.
arXiv Detail & Related papers (2020-09-11T11:56:34Z) - Single- and Multi-Objective Evolutionary Algorithms for the Knapsack
Problem with Dynamically Changing Constraints [13.896724650508087]
We investigate single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem.
Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios.
arXiv Detail & Related papers (2020-04-27T03:50:24Z) - Total Deep Variation for Linear Inverse Problems [71.90933869570914]
We propose a novel learnable general-purpose regularizer exploiting recent architectural design patterns from deep learning.
We show state-of-the-art performance for classical image restoration and medical image reconstruction problems.
arXiv Detail & Related papers (2020-01-14T19:01:50Z)
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.