- author = "Luca Manzoni and Alberto Bartoli and Mauro Castelli and Ivo Goncalves and Eric Medvet",
- title = "Specializing Context-Free Grammars With a (1 + 1)-{EA}",
- journal = "IEEE Transactions on Evolutionary Computation",
- year = "2020",
- volume = "24",
- number = "5",
- pages = "960--973",
- month = oct,
- keywords = "genetic algorithms, genetic programming, grammatical evolution,Grammar design, runtime analysis",
- ISSN = "1089-778X",
-
DOI = "
doi:10.1109/TEVC.2020.2983664",
- size = "14 pages",
- abstract = "Context-free grammars are useful tools for modeling the solution space of problems that can be solved by optimization algorithms. For a given solution space, there exists an infinite number of grammars defining that space, and there are clues that changing the grammar may impact the effectiveness of the optimization. In this article, we investigate theoretically and experimentally the possibility of specializing a grammar in a problem, that is, of systematically improving the quality of the grammar for the given problem. To this end, we define the quality of a grammar for a problem in terms of the average fitness of the candidate solutions generated using that grammar. Theoretically, we demonstrate the following findings: 1) that a simple mutation operator employed in a (1 + 1)-EA setting can be used to specialize a grammar in a problem without changing the solution space defined by the grammar and 2) that three grammars of equal quality for a grammar-based version of the ONEMAX problem greatly vary in how they can be specialized with that (1 + 1)-EA, as the expected time required to obtain the same improvement in quality can vary exponentially among grammars. Then, experimentally, we validate the theoretical findings and extend them to other problems, grammars, and a more general version of the mutation operator.",
-
notes = "Dipartimento di Matematica e Geoscienze, University of
Trieste, 34127 Trieste, Italy.
INSPEC Accession Number: 19992322
Also known as \cite{9047973}",
