Zvada S (2010)
Publication Language: English
Publication Type: Thesis
Publication year: 2010
Publisher: Cuvillier
City/Town: Göttingen
ISBN: 978-3-86955-229-3
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.
APA:
Zvada, S. (2010). Attribute Grammar Based Genetic Programming (Dissertation).
MLA:
Zvada, Szilvia. Attribute Grammar Based Genetic Programming. Dissertation, Göttingen: Cuvillier, 2010.
BibTeX: Download