Grammar-Based Evolution of Polyominoes

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