An Evolutionary View on Reversible Shift-Invariant Transformations

Luca Mariot, Stjepan Picek, Domagoj Jakobovic, Alberto Leporati

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

We consider the problem of evolving a particular kind of shift-invariant transformation – namely, Reversible Cellular Automata (RCA) defined by conserved landscape rules – using GA and GP. To this end, we employ three different optimization strategies: a single-objective approach carried out with GA and GP where only the reversibility constraint of marker CA is considered, a multi-objective approach based on GP where both reversibility and the Hamming weight are taken into account, and a lexicographic approach where GP first optimizes only the reversibility property until a conserved landscape rule is obtained, and then maximizes the Hamming weight while retaining reversibility. The results are discussed in the context of three different research questions stemming from exhaustive search experiments on conserved landscape CA, which concern (1) the difficulty of the associated optimization problem for GA and GP, (2) the utility of conserved landscape CA in the domain of cryptography and reversible computing, and (3) the relationship between the reversibility property and the Hamming weight.

Original languageEnglish
Title of host publicationGenetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings
EditorsTing Hu, Nuno Lourenço, Eric Medvet, Federico Divina
PublisherSpringer Open
Pages118-134
Number of pages17
ISBN (Print)9783030440930
DOIs
Publication statusPublished - 2020
Event23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020 - Seville, Spain
Duration: 15 Apr 202017 Apr 2020
Conference number: 23

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12101 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020
CountrySpain
CitySeville
Period15/04/2017/04/20
OtherVirtual/online event due to COVID-19

Keywords

  • Cellular automata
  • Genetic Algorithms
  • Genetic Programming
  • Reversibility
  • Shift-invariant transformations

Fingerprint Dive into the research topics of 'An Evolutionary View on Reversible Shift-Invariant Transformations'. Together they form a unique fingerprint.

  • Cite this

    Mariot, L., Picek, S., Jakobovic, D., & Leporati, A. (2020). An Evolutionary View on Reversible Shift-Invariant Transformations. In T. Hu, N. Lourenço, E. Medvet, & F. Divina (Eds.), Genetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings (pp. 118-134). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12101 LNCS). Springer Open. https://doi.org/10.1007/978-3-030-44094-7_8