Attribute Grammar Based Genetic Programming (PDF)

Genetic programming is a well-known evolutionary optimization methodology
complex structures (trees) using to solve various optimization problems. The
optimal solutions are looked for by altering randomly the tree individuals. These
random changes can improve the quality of the represented solutions, but they
can also result in invalid individuals. These individuals must be detected and
either corrected or eliminated.
In this thesis, we present how attribute grammars can be applied to
attain these goals. Firstly, we employ the derivation trees of the grammar
as individuals. Each derivation tree is enhanced with attributes that are
evaluated simultaneously to the tree construction. Secondly, we introduce a
smart random tree generator. A unique property of this random tree generator is
that it considers constraints—specified via special attributes—while generating
randomly derivation trees. The trees created this way are valid with respect to
both the given constraints and the grammar rules. Thirdly, by combining the
random tree generator with tree operators, we ensure that no invalid individuals
are created at all during the evolutionary search. In addition, we demonstrate
various ways how attributes can be used to bias beneficially the evolutionary
search.
Finally, we outline how this approach can be adapted to optimize filter descriptions
of finite impulse response filters. Concerning the enormous search space
of this problem and the complexity of the solutions, it is highly advantageous
that by means of attributes we can ensure that only valid filter compositions
are accounted during the search. A further restriction of the generated filter
descriptions is realized by a unique design of the derivation trees. As a result,
solely redundancy-free filter descriptions are considered during the optimization,
making redundancy-reducing post-processings superfluous.