An Evolutionary View on Reversible Shift-Invariant Transformations

Luca Mariot; Stjepan Picek; Domagoj Jakobovic; Alberto Leporati

doi:10.1007/978-3-030-44094-7_8

An Evolutionary View on Reversible Shift-Invariant Transformations

Luca Mariot^*, Stjepan Picek, Domagoj Jakobovic, Alberto Leporati

^*Corresponding author for this work

Cyber Security

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

4 Citations (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 language	English
Title of host publication	Genetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings
Editors	Ting Hu, Nuno Lourenço, Eric Medvet, Federico Divina
Publisher	SpringerOpen
Pages	118-134
Number of pages	17
ISBN (Print)	9783030440930
DOIs	https://doi.org/10.1007/978-3-030-44094-7_8
Publication status	Published - 2020
Event	23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020 - Seville, Spain Duration: 15 Apr 2020 → 17 Apr 2020 Conference number: 23

Publication series

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

Conference

Conference	23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020
Country/Territory	Spain
City	Seville
Period	15/04/20 → 17/04/20
Other	Virtual/online event due to COVID-19

Bibliographical note

Virtual/online event due to COVID-19

Keywords

Cellular automata
Genetic Algorithms
Genetic Programming
Reversibility
Shift-invariant transformations

Access to Document

10.1007/978-3-030-44094-7_8

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). SpringerOpen. https://doi.org/10.1007/978-3-030-44094-7_8

Mariot, Luca ; Picek, Stjepan ; Jakobovic, Domagoj et al. / An Evolutionary View on Reversible Shift-Invariant Transformations. Genetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings. editor / Ting Hu ; Nuno Lourenço ; Eric Medvet ; Federico Divina. SpringerOpen, 2020. pp. 118-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9cf17b1efee44cd0ac726872084e8889,

title = "An Evolutionary View on Reversible Shift-Invariant Transformations",

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.",

keywords = "Cellular automata, Genetic Algorithms, Genetic Programming, Reversibility, Shift-invariant transformations",

author = "Luca Mariot and Stjepan Picek and Domagoj Jakobovic and Alberto Leporati",

note = "Virtual/online event due to COVID-19 ; 23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020 ; Conference date: 15-04-2020 Through 17-04-2020",

year = "2020",

doi = "10.1007/978-3-030-44094-7_8",

language = "English",

isbn = "9783030440930",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "SpringerOpen",

pages = "118--134",

editor = "Ting Hu and Nuno Louren{\c c}o and Eric Medvet and Federico Divina",

booktitle = "Genetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12101 LNCS, SpringerOpen, pp. 118-134, 23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020, Seville, Spain, 15/04/20. https://doi.org/10.1007/978-3-030-44094-7_8

An Evolutionary View on Reversible Shift-Invariant Transformations. / Mariot, Luca ; Picek, Stjepan; Jakobovic, Domagoj et al.
Genetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings. ed. / Ting Hu; Nuno Lourenço; Eric Medvet; Federico Divina. SpringerOpen, 2020. p. 118-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12101 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - An Evolutionary View on Reversible Shift-Invariant Transformations

AU - Mariot, Luca

AU - Picek, Stjepan

AU - Jakobovic, Domagoj

AU - Leporati, Alberto

N1 - Conference code: 23

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Cellular automata

KW - Genetic Algorithms

KW - Genetic Programming

KW - Reversibility

KW - Shift-invariant transformations

UR - http://www.scopus.com/inward/record.url?scp=85084758364&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-44094-7_8

DO - 10.1007/978-3-030-44094-7_8

M3 - Conference contribution

AN - SCOPUS:85084758364

SN - 9783030440930

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 118

EP - 134

BT - Genetic Programming - 23rd European Conference, EuroGP 2020, Held as Part of EvoStar 2020, Proceedings

A2 - Hu, Ting

A2 - Lourenço, Nuno

A2 - Medvet, Eric

A2 - Divina, Federico

PB - SpringerOpen

T2 - 23rd European Conference on Genetic Programming, EuroGP 2020, held as part of EvoStar 2020

Y2 - 15 April 2020 through 17 April 2020

ER -

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

An Evolutionary View on Reversible Shift-Invariant Transformations

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this