Evolutionary algorithms for the design of orthogonal Latin squares based on cellular automata

Luca Mariot, Stjepan Picek, Domagoj Jakobovic, Alberto Leporati

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

9 Citations (Scopus)

Abstract

We investigate the design of Orthogonal Latin Squares (OLS) by means of Genetic Algorithms (GA) and Genetic Programming (GP). Since we focus on Latin squares generated by Cellular Automata (CA), the problem can be reduced to the search of pairs of Boolean functions that give rise to OLS when used as CA local rules. As it is already known how to design CA-based OLS with linear Boolean functions, we adopt the evolutionary approach to address the nonlinear case, experimenting with different encodings for the candidate solutions. In particular, for GA we consider single bitstring, double bitstring and quaternary string encodings, while for GP we adopt a double tree representation. We test the two metaheuristics on the spaces of local rules pairs with n = 7 and n = 8 variables, using two fitness functions. The results show that GP is always able to generate OLS, even if the optimal solutions found with the first fitness function are mostly linear. On the other hand, GA achieves a remarkably lower success rate than GP in evolving OLS, but the corresponding Boolean functions are always nonlinear.

Original languageEnglish
Title of host publicationGECCO'17 Proceedings of the Genetic and Evolutionary Computation Conference
Place of PublicationNew York, NY
PublisherAssociation for Computing Machinery (ACM)
Pages306-313
Number of pages8
ISBN (Electronic)978-1-4503-4920-8
DOIs
Publication statusPublished - 2017
EventGECCO 2017: Genetic and Evolutionary Computation Conference - Berlin, Germany
Duration: 15 Jul 201719 Jul 2017
http://gecco-2017.sigevo.org/index.html/HomePage

Conference

ConferenceGECCO 2017
CountryGermany
CityBerlin
Period15/07/1719/07/17
OtherA Recombination of the 26th International Conference on Genetic Algorithms (ICGA) and the 22nd Annual Genetic Programming Conference (GP).
Internet address

Keywords

  • Orthogonal Latin Squares
  • Cellular Automata
  • Genetic Algorithms
  • Genetic Programming
  • Boolean Functions
  • Pairwise Balancedness
  • ‹aternary Strings
  • Nonlinearity

Fingerprint

Dive into the research topics of 'Evolutionary algorithms for the design of orthogonal Latin squares based on cellular automata'. Together they form a unique fingerprint.

Cite this