Evolutionary algorithms for designing reversible cellular automata

Luca Mariot, Stjepan Picek, Domagoj Jakobovic, Alberto Leporati

Research output: Contribution to journalArticleScientificpeer-review

6 Downloads (Pure)

Abstract

Reversible Cellular Automata (RCA) are a particular kind of shift-invariant transformations characterized by 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. In the single-objective approach, we observe that GP can already find an optimal solution in the initial population. This indicates that evolutionary algorithms are not needed when evolving only the reversibility of such CA, and a more efficient method is to generate at random syntactic trees that define the local update rule. On the other hand, GA and GP proved to be quite effective in the multi-objective and lexicographic approach to (1) discover a trade-off between the reversibility and the Hamming weight of conserved landscape rules, and (2) observe that conserved landscape CA cannot be used in symmetric cryptography because their Hamming weight (and thus their nonlinearity) is too low.

Original languageEnglish
Pages (from-to)429-461
Number of pages33
JournalGENETIC PROGRAMMING AND EVOLVABLE MACHINES
Volume22
Issue number4
DOIs
Publication statusPublished - 2021

Keywords

  • Cellular automata
  • Genetic algorithms
  • Genetic programming
  • Reversibility
  • Shift-invariant transformations

Fingerprint

Dive into the research topics of 'Evolutionary algorithms for designing reversible cellular automata'. Together they form a unique fingerprint.

Cite this