Understanding the internal functioning of evolutionary algorithms is an essential requirement for improving their performance and reliability. Increased computational resources available in current mainstream computers make it possible for new previously infeasible research directions to be explored. Therefore, a comprehensive theoretical analysis of their mechanisms and dynamics using modern tools becomes possible. Recent algorithmic achievements like offspring selection in combination with linear scaling have enabled genetic programming (GP) to achieve high quality results in system identification in less than 50 generations using populations of only several hundred individuals. Therefore, the active gene pool of evolutionary search remains manageable and may be subjected to new theoretical investigations closely related to genetic programming schema theories, building block hypotheses and bloat theories.
Genetic algorithms emulate emergent systems in which complex patterns are formed from an initially simple and random pool of elementary structures. In GP, complexity emerges under the influence of stabilizing selection which preserves the useful genetic variation created by recombination and mutation. The mapping between the structures used for solution representation and the ones used for the evaluation of fitness has a major influence on algorithm behavior. Population-wide effects concerning building blocks, genetic diversity and bloat can be conceptually seen as results of the complex interaction between phenotypic operators (selection) and genotypic operators (mutation and recombination). This coupling known as the “variation-selection loop” is the main engine for GP emergent behavior and constitutes the main topic of this research. This thesis aims to provide a unified theoretical framework which can explain GP evolution. To this end, it explores the way in which the genotype-phenotype map, in relation with the evolutionary operators (selection, recombination, mutation) determines algorithmic behaviour. As the title suggests, the main contribution consists of a novel “tracing” framework that makes it possible to determine the exact patterns of building block and gene propagation through the generations and the way smaller elements are gradually assembled into more complex structures by the evolutionary algorithm.
Zusammenfassung
Um die Leistung und Zuverlässigkeit von evolutionären Algorithmen zu verbessern, ist es notwendig deren interne Funktionsweise zu verstehen. Die hohe Rechenleistung aktueller Mainstream-Computer erlaubt neue Forschungsrichtungen zu erkunden, welche früher, aufgrund fehlender Rechenleistung, nicht möglich waren. Für evolutionäre Algorithmen wird es dadurch möglich, deren interne Mechaniken und Dynamiken umfangreich zu analysieren. Aktuelle algorithmische Fortschritte, wie Nachkommensselektion (Offspring Selection) in Kombination mit linearer Skalierung, ermöglicht Genetischer Programmierung (GP) hochqualitative Ergebnisse in der Systemidentifikation zu erreichen, in weniger als 50 Generationen bei einer Populationsgröße von nur wenigen hunderten Individuen. Der dadurch überschaubare aktive Genpool der evolutionären Suche ermöglicht neue theoretische Untersuchungen zum GP Schema Theorem, zur Baustein Hypothese und zu Bloat-Theorien.
Genetische Algorithmen emulieren emergente Systeme in denen komplexe Muster geformt werden, basierend auf einer initialen, zufällig generiertem Menge an elementaren Strukturen. In GP entsteht die Komplexität durch den Einfluss der stabilisierenden Selektion, welche nützliche genetische Variation erhält die von Rekombination und Mutation erzeugt werden. Die Zuordnung zwischen Strukturen zur Lösungsrepräsentation (Genotyp) und Fitnessevaluierung (Phänotyp) beeinflusst das algorithmische Verhalten stark. Populationsweite Auswirkungen betreffend Bausteine, genetischer Diversität und Bloat entstehen durch das komplexe Zusammenwirken phänotypischen Operatoren (Selektion) und genotypischen Operatoren (Rekombination und Mutation). Dieser Mechanismus, bekannt als „Variation-Selektion Schleife”, ist die treibende Kraft des emergente Verhalten von GP und bildet das Hauptforschungsthema dieser Arbeit. Diese Arbeit zielt darauf ab, einen einheitlichen, theoretischen Rauem zu schaffen welcher Evolution in GP erklären kann. Dafür wird der Einfluss von auf das algorithmische Verhalten untersucht, basierend auf die Zuordnung von Genotyp und Phänotyp, unter Berücksichtigung der evolutionärer Operatoren (Selektion, Rekombination, Mutation). Wie der Titel der Arbeit bereits andeutet, besteht der wichtigste Beitrag aus einem neuartigen System zur Überwachung und Rückverfolgung von Genen über mehrere Generationen hinweg. Dies ermöglicht es das Verhalten von Bausteinen zu erforschen, sowie zu erkunden wie bei evolutionären Algorithmen aus kleinen Elementen nach und nach komplexere Strukturen gebildet werden.
