- author = "Jessica Megane and Eric Medvet and Nuno Lourenco and Penousal Machado",
- editor = "Mario Giacobini and Bing Xue and Luca Manzoni",
- title = "Grammar-Based Evolution of Polyominoes",
- booktitle = "EuroGP 2024: Proceedings of the 27th European Conference on Genetic Programming",
- year = "2024",
- volume = "14631",
- series = "LNCS",
- pages = "56--72",
- publisher = "Springer",
- address = "Aberystwyth",
- month = "3-5 " # apr,
- organisation = "EvoStar, Species",
- keywords = "genetic algorithms, genetic programming",
- isbn13 = "978-3-031-56957-9",
-
URL = "
https://jessicamegane.pt/publication/2024-01-18-polyominoes",
-
DOI = "
doi:10.1007/978-3-031-56957-9_4",
- abstract = "Languages that describe two-dimensional (2-D) structures have emerged as powerful tools in various fields, encompassing pattern recognition and image processing, as well as modeling physical and chemical phenomena. One kind of two-dimensional structures is given by labeled polyominoes, i.e., geometric shapes composed of connected unit squares represented in a 2-D grid. In this paper, we present (a) a novel approach, based on grammars, for describing sets of labeled polyominoes that meet some predefined requirements and (b) an algorithm to develop labeled polyominoes using the grammar. We show that the two components can be used for solving optimization problems in the space of labeled polyominoes, similarly to what happens for strings in grammatical evolution (and its later variants). We characterise our algorithm for developing polyominoes in terms of representation-related metrics (namely, validity, redundancy, and locality), also by comparing different representations. We experimentally validate our proposal using a simple evolutionary algorithm on a few case studies where the goal is to obtain a target polyomino: we show that it is possible to enforce hard constraints in the search space of polyominoes, using a grammar, while performing the evolutionary search.",
-
notes = "Nominated for best paper
Part of \cite{Giacobini:2024:GP} EuroGP'2024 held in conjunction with EvoCOP2024, EvoMusArt2024 and EvoApplications2024",
