Enzyme Genetic Programming
Modelling Biological Evolvability in Genetic Programming
Michael Adam Lones
Department of Electronics, University of York, Heslington, York YO10 5DD, UK
PhD Thesis. Submitted September 2003. Defended March 2004.
Abstract
This thesis introduces a new approach to program representation in genetic programming
in which interactions between program components are expressed in terms of a
component's behaviour rather through its relative position within a representation or
through other non-behavioural systems of reference. This approach has the advantage
that a component's behaviour is expressed in a way that is independent of any
particular program it finds itself within; and thereby overcomes the problem when using
conventional program representations whereby program components lose their behavioural
context following recombination. More generally, this implicit context representation
leads to a process of meaningful variation filtering; whereby inappropriate change
induced by variation operators can be wholly or partially ignored. This occurs as a
consequence of program behaviours emerging from the self-organisation of program
components, ignoring those components which do not fit the contexts declared by the
other components within the program. This process results in gradual change within the
behaviour of a program during evolution. This thesis also presents results which show
that implicit context representation leads to better size evolution characteristics
than conventional genetic programming; and that functional redundancy and Lamarckian
reinforcement learning both improve evolutionary search, agreeing with previous
research by other authors.
A PDF version of this thesis is available here (~2Mb).
Contents
About the HTML version
Acknowledgements
Declaration
Hypothesis
1 Introduction
1.1 Genetic Programming
1.2 Biological Modelling
1.3 Evolvability
1.4 Enzyme Genetic Programming
1.5 Contributions
1.6 Thesis Organisation
2 Evolution
2.1 Evolution of Individuals
2.1.1 Evolvability
2.1.2 Evolutionary Spaces and Landscapes
2.1.3 Neutral Evolution
2.2 Evolution of Groups
2.2.1 Co-operative Evolution
2.2.2 Competitive Evolution
2.3 Summary
2.4 Perspectives
3 Biological Representation
3.1 Biological Components
3.1.1 Proteins and Enzymes
3.1.2 Nucleic Acids
3.1.3 Genes
3.1.4 Chromosomes
3.1.5 Cells
3.2 Biological Processes
3.2.1 DNA Replication
3.2.2 Transcription
3.2.3 Cell Division
4 Biochemical Pathways
4.1 Metabolic Networks
4.2 Signalling Networks
4.3 Gene Expression
5 Biological Evolvability
5.1 Compartmentalisation
5.2 Redundancy
5.2.1 Functional redundancy
5.2.2 Structural redundancy
5.2.3 Weak Linkage
5.3 Evolution through Redundancy
5.4 Neutral Evolution
5.5 Other Sources of Evolvability
5.6 Evolution of Evolvability
5.7 Summary
6 Genetic Programming
6.1 Evolutionary Computation
6.1.1 Genetic Algorithms
6.2 Conventional Genetic Programming
6.3 Problems with Recombination
6.4 Solution Size Evolution and Bloat
6.5 Expressiveness
6.5.1 Linguistic Approaches
6.5.2 Representational Approaches
6.6 Summary
7 Evolvability in Evolutionary Computation
7.1 Variation versus Representation
7.2 Adapting Variation
7.3 Introducing Pleiotropy
7.3.1 Modularity
7.3.2 Implicit Reuse
7.4 Evolvability through Redundancy
7.4.1 Structural Redundancy
7.4.2 Coding Redundancy and Neutrality
7.4.3 Functional Redundancy
7.5 Positional Independence
7.5.1 Linkage Learning
7.5.2 Floating Representations
7.5.3 Gene Expression
7.6 Summary
7.7 Perspectives
8 Enzyme Genetic Programming
8.1 Introduction
8.2 Representing Programs in Genetic Programming
8.2.1 Explicit context
8.2.2 Indirect context
8.3 Implicit Context Representation
8.3.1 An Illustrative Example
8.3.2 Representing Programs with Implicit Context
8.4 Implicit Context in Enzyme Genetic Programming
8.4.1 Functionality
8.5 Program Development
8.6 Evolution of Program Representations
8.6.1 Initialisation and Variation
8.7 Summary
9 Experimental Results and Analysis
9.1 Experimental Method
9.1.1 Symbolic Regression
9.2 Comparative Performance
9.3 Functionality
9.4 Recombinative Behaviour
9.4.1 Effect of crossover type
9.4.2 Crossover versus Mutation
9.4.3 Microscopic Behaviours
9.5 Size Evolution
9.6 Redundancy
9.7 Phenotypic Linkage
9.7.1 Phenotypic Linkage Learning
9.7.2 Stability and Replication Fidelity
9.8 Genetic Linkage
9.9 Component Reuse
9.10 Development
9.11 Discussion
10 Summary and Conclusions
10.1 Rationale and Work Done
10.2 Conclusions
10.3 Limitations of This Study
10.4 Further Work
A The Activity Model
Bibliography
List of Tables
7.1 An example redundant code
9.1 Metrics used to measure performance and behaviour of program evolution.
9.2 Behavioural parameters and their default settings.
9.3 Boolean regression test problems.
9.4 Performance of enzyme GP with different operators
A.1 Performance of activity model upon two-bit multiplier problem.
List of Figures
2.1 An evolutionary system
2.2 Evolution of a group of entities
2.3 Co-operative interactions during evolution
3.1 Hierarchical levels of protein structure
3.2 Enzyme activity
3.3 Nucleotides of DNA
3.4 DNA Replication
3.5 Protein synthesis through transcription and translation
3.6 Mitotic cell division
3.7 Meiosis
4.1 Biochemical Pathways
4.2 The citrate cycle
4.3 Initiation of a Signalling Pathway
6.1 One generation of an evolutionary algorithm
6.2 Sub-tree crossover
6.3 Loss of context following sub-tree crossover
6.4 Grammatical evolution
7.1 Koza's branch creation operator
7.2 A GP expression tree containing introns
7.3 Cartesian GP circuit with functional redundancy
7.4 Recombination in Harik's Linkage Learning GA
8.1 Mapping from program representation to program
8.2 Loss of context during cartesian GP recombination
8.3 Evolution of an abstract implicit context system
8.4 Enzyme model
8.5 Example functionality space
8.6 Derivation of functionality
8.7 Format of a program representation
8.8 Top-down development of a simple Boolean expression
8.9 An example of strongest-first development
8.10 Structure of the network genetic algorithm
8.11 A conceptual view of enzyme GP uniform crossover
8.12 Recombination using transfer and remove
9.1 The two-bit multiplier problem
9.2 Comparing functionality shapes and random shapes
9.3 Effect of shape calculation upon performance
9.4 Comparing uniform and TR recombination
9.5 Headless chicken recombination
9.6 Comparing relative abilities of recombination and mutation operators
9.7 A simple example of subsumption
9.8 Behaviours resulting from transfer and remove operations.
9.9 Two-bit multiplier size evolution
9.10 Effect of transfer limit upon size evolution
9.11 Evolution of program size
9.12 Comparing program size growth against forced representation growth
9.13 Effect of removing non-coding components
9.14 Effect of number of binding sites upon performance
9.15 Evolution of phenotypic linkage
9.16 Relationship between phenotypic linkage and representation length
9.17 Performance of phenotypic linkage learning
9.18 Effects of phenotypic linkage learning
9.19 Effect of size of function and input terminal sets
9.20 Evolution of genetic linkage and relationship with representation length
9.21 Functional component reuse
9.22 Behaviour of development strategies
9.23 Scalability of development strategies
10.1 Variation filtering preserves output behaviour
10.2 Implicit structural context
A.1 Visualising the activity model
A.2 Evolution of a full adder with the activity model
[Back to home page]
Translated in part from
TEX
by
TTH,
version 3.59 on 20 Apr 2004, 14:31,
© Michael Lones 2003
This page uses Google Analytics to track visitors. See Privacy Statement.