Specializing Context-Free Grammars with a (1 + 1)-EA

Luca Manzoni, Alberto Bartoli, Mauro Castelli, Ivo Goncalves, Eric Medvet

Research output: Contribution to journalArticle

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.

Original languageEnglish
Article number9047973
Pages (from-to)960-973
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume24
Issue number5
DOIs
Publication statusPublished - Oct 2020

Keywords

  • Grammar design
  • grammatical evolution
  • run time analysis

Fingerprint Dive into the research topics of 'Specializing Context-Free Grammars with a (1 + 1)-EA'. Together they form a unique fingerprint.

Cite this