Victoria University

Empirical Analysis of Schemata in Genetic Programming

ResearchArchive/Manakin Repository

Show simple item record

dc.contributor.advisor Zhang, Mengjie
dc.contributor.advisor Andreae, Peter Smart, Will 2011-09-20T01:33:11Z 2011-09-20T01:33:11Z 2011 2011
dc.description.abstract Schemata and buiding blocks have been used in Genetic Programming (GP) in several contexts including subroutines, theoretical analysis and for empirical analysis. Of these three the least explored is empirical analysis. This thesis presents a powerful GP empirical analysis technique for analysis of all schemata of a given form occurring in any program of a given population at scales not previously possible for the kinds of global analysis performed. There are many competing GP forms of schema and, rather than choosing one for analysis, the thesis defines the match-tree meta-form of schema as a general language expressing forms of schema for use by the analysis system. This language can express most forms of schema previously used in tree-based GP. The new method can perform wide-ranging analyses on the prohibitively large set of all schemata in the programs by introducing the concepts of maximal schema, maximal program subset, representative set of schemata, and representative program subset. These structures are used to optimize the analysis, shrinking its complexity to a manageable size without sacrificing the result. Characterization experiments analyze GP populations of up to 501 60- node programs, using 11 forms of schema including rooted-hyperschemata and non-rooted fragments. The new method has close to quadratic complexity on population size, and quartic complexity on program size. Efficacy experiments present example analyses using the new method. The experiments offer interesting insights into the dynamics of GP runs including fine-grained analysis of convergence and the visualization of schemata during a GP evolution. Future work will apply the many possible extensions of this new method to understanding how GP operates, including studies of convergence, building blocks and schema fitness. This method provides a much finer-resolution microscope into the inner workings of GP and will be used to provide accessable visualizations of the evolutionary process. en_NZ
dc.language.iso en_NZ
dc.publisher Victoria University of Wellington en_NZ
dc.subject Empirical analysis en_NZ
dc.subject Schemata en_NZ
dc.subject Genetic programming en_NZ
dc.title Empirical Analysis of Schemata in Genetic Programming en_NZ
dc.type Text en_NZ
vuwschema.contributor.unit School of Engineering and Computer Science en_NZ
vuwschema.subject.marsden 280212 Neural Networks, Genetic Algorithms and Fuzzy Logic en_NZ
vuwschema.subject.marsden 280401 Analysis of Algorithms and Complexity en_NZ
vuwschema.type.vuw Awarded Doctoral Thesis en_NZ Computer Science en_NZ Victoria University of Wellington en_NZ Doctoral en_NZ Doctor of Philosophy en_NZ
vuwschema.subject.anzsrcfor 089999 Information and Computing Sciences not elsewhere classified en_NZ

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ResearchArchive

Advanced Search


My Account