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.