Attribute Grammar Based Genetic Programming

Genetische Programmierung basierend auf attributierten Grammatiken

,

• Publisher: Cuvillier Verlag
• Year: 2010
• Print ISBN: 9783869552293
• eBook ISBN: 9783736932296
• Edition: 1

Genetic programming is a well-known evolutionary optimization methodologycomplex structures (trees) using to solve various optimization problems. Theoptimal solutions are looked for by altering randomly the tree individuals. Theserandom changes can improve the quality of the represented solutions, but theycan also result in invalid individuals. These individuals must be detected andeither corrected or eliminated.In this thesis, we present how attribute grammars can be applied toattain these goals. Firstly, we employ the derivation trees of the grammaras individuals. Each derivation tree is enhanced with attributes that areevaluated simultaneously to the tree construction. Secondly, we introduce asmart random tree generator. A unique property of this random tree generator isthat it considers constraints—specified via special attributes—while generatingrandomly derivation trees. The trees created this way are valid with respect toboth the given constraints and the grammar rules. Thirdly, by combining therandom tree generator with tree operators, we ensure that no invalid individualsare created at all during the evolutionary search. In addition, we demonstratevarious ways how attributes can be used to bias beneficially the evolutionarysearch.Finally, we outline how this approach can be adapted to optimize filter descriptionsof finite impulse response filters. Concerning the enormous search spaceof this problem and the complexity of the solutions, it is highly advantageousthat by means of attributes we can ensure that only valid filter compositionsare accounted during the search. A further restriction of the generated filterdescriptions 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.