Brameier / Banzhaf Linear Genetic Programming

1. Auflage 2007
ISBN: 978-0-387-31030-5
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 316 Seiten

Reihe: Genetic and Evolutionary Computation

Linear Genetic Programming presents a variant of Genetic Programming that evolves imperative computer programs as linear sequences of instructions, in contrast to the more traditional functional expressions or syntax trees. Typical GP phenomena, such as non-effective code, neutral variations, and code growth are investigated from the perspective of linear GP. This book serves as a reference for researchers; it includes sufficient introductory material for students and newcomers to the field.

Markus Brameier received a PhD degree in Computer Science from the Department of Computer Science at University of Dortmund, Germany,in 2004.  From 2003 to 2004 he was a postdoctoral fellow at the Stockholm Bioinformatics Center (SBC), a collaboration between Stockholm University, the Royal Institute of Technology, and Karolinska Institute, in Sweden.  Currently he is Assistant Professor at the Bioinformatics Research Center (BiRC) of the University of Aarhus in Denmark.  His primary research interests are in bioinformatics and genetic programming. Wolfgang Banzhaf is a professor of Computer Science at the Department of Computer Science of Memorial University of Newfoundland, Canada, and head of the department since 2003. Prior to that, he served for 10 years as Associate Professor for Applied Computer Science in the Department of Computer Science at University of Dortmund, Germany. From 1989 to 1993 he was a researcher with Mitsubishi Electric Corp., first in MELCO's Central Research Lab in Japan, then in the United States at Mitsubishi Electric Research Labs Inc., Cambridge, MA. Between 1985 and 1989 he was a postdoc in the Department of Physics, University of Stuttgart, Germany. He holds a PhD in Physics from the University of Karlruhe in Germany. His research interests are in the field of artificial evolution and self-organization studies. He has recently become more involved with bioinformatics.

Autoren/Hrsg.

Brameier, Markus F.

Banzhaf, Wolfgang

Inhaltsverzeichnis

1;Contents;8
2;Preface;12
3;About the Authors;15
4;INTRODUCTION;16
4.1;1.1 Evolutionary Algorithms;16
4.2;1.2 Genetic Programming;18
4.3;1.3 Linear Genetic Programming;21
4.4;1.4 Motivation;23
5;PART I FUNDAMENTAL ANALYSIS;26
5.1;BASIC CONCEPTS OF LINEAR GENETIC PROGRAMMING;28
5.1.1;2.1 Representation of Programs;28
5.1.2;2.1.1 Coding of Instructions;30
5.1.3;2.1.2 Instruction Set;31
5.1.4;2.1.3 Branching Concepts;33
5.1.5;2.1.4 Advanced Branching Concepts;35
5.1.6;2.1.5 Iteration Concepts;37
5.1.7;2.1.6 Modularization Concepts;38
5.1.8;2.2 Execution of Programs;40
5.1.9;2.2.1 Runtime Comparison;41
5.1.10;2.2.2 Translation;43
5.1.11;2.3 Evolution of Programs;44
5.1.12;2.3.1 Initialization;46
5.1.13;2.3.2 Selection;47
5.1.14;2.3.3 Reproduction;48
5.1.15;2.3.4 Variation;48
5.2;CHARACTERISTICS OF THE LINEAR REPRESENTATION;50
5.2.1;3.1 E.ective Code and None.ective Code;50
5.2.2;3.2 Structural Introns and Semantic Introns;52
5.2.3;3.2.1 Detecting and Removing Structural Introns;53
5.2.4;3.2.2 Avoiding Semantic Introns;55
5.2.5;3.2.3 Detecting Semantic Introns;59
5.2.6;3.2.4 Symbolic Simpli.cation;61
5.2.7;3.3 Graph Interpretation;62
5.2.8;3.3.1 Variation E.ects;66
5.2.9;3.3.2 Interpretation of Branches;67
5.2.10;3.3.3 Evaluation Order;69
5.2.11;3.3.4 Tree Interpretation;70
5.2.12;3.4 Analysis of Program Structure;71
5.2.13;3.5 Graph Evolution;75
5.2.14;3.6 Summary and Conclusion;76
5.3;A COMPARISON WITH NEURAL NETWORKS;78
5.3.1;4.1 Medical Data Mining;78
5.3.2;4.2 Benchmark Data sets;79
5.3.3;4.3 Experimental Setup 4.3.1 Genetic Programming;80
5.3.4;4.3.2 Population Structure;82
5.3.5;4.3.3 Neural Networks;83
5.3.6;4.4 Experiments and Comparison 4.4.1 Generalization Performance;84
5.3.7;4.4.2 E.ective Training Time;86
5.3.8;4.4.3 Acceleration of Absolute Runtime;86
5.3.9;4.4.4 Acceleration of E.ective Training Time;87
5.3.10;4.4.5 Further Comparison;89
5.3.11;4.5 Summary and Conclusion;89
6;PART II METHOD DESIGN;90
6.1;LINEAR GENETIC OPERATORS I – SEGMENT VARIATIONS;92
6.1.1;5.1 Variation E.ects;93
6.1.2;5.1.1 Semantic Variation E.ects;93
6.1.3;5.1.2 Structural Variation E.ects;94
6.1.4;5.2 E.ective Variation and Evaluation;94
6.1.5;5.3 Variation Step Size;95
6.1.6;5.4 Causality;97
6.1.7;5.4.1 Self-Adaptation;100
6.1.8;5.5 Selection of Variation Points;101
6.1.9;5.6 Characteristics of Variation Operators;102
6.1.10;5.7 Segment Variation Operators;104
6.1.11;5.7.1 Linear Crossover;104
6.1.12;5.7.2 One-Point Crossover;107
6.1.13;5.7.3 One-Segment Recombination;107
6.1.14;5.7.4 E.ective Recombination;109
6.1.15;5.7.5 Segment Mutations;110
6.1.16;5.7.6 Explicit Introns;111
6.1.17;5.7.7 Building Block or Macro Mutation?;112
6.1.18;5.8 Experimental Setup 5.8.1 Benchmark Problems;114
6.1.19;5.8.2 Parameter Settings;115
6.1.20;5.9 Experiments;117
6.1.21;5.9.1 Comparison of Recombination Operators;117
6.1.22;5.9.2 Comparison with Segment Mutations;121
6.1.23;5.9.3 Crossover Rate;123
6.1.24;5.9.4 Analysis of Crossover Parameters;125
6.1.25;5.9.5 Explicit Introns;129
6.1.26;5.10 Summary and Conclusion;133
6.2;LINEAR GENETIC OPERATORS II – INSTRUCTION MUTATIONS;134
6.2.1;6.1 Minimum Mutation Step Size;134
6.2.2;6.2 Instruction Mutation Operators;136
6.2.3;6.2.1 Macro Mutations;137
6.2.4;6.2.2 Micro Mutations;138
6.2.5;6.2.3 E.ective Mutations;139
6.2.6;6.2.4 Minimum E.ective Mutations;141
6.2.7;6.2.5 Free Mutations;142
6.2.8;6.2.6 Explicit Induction of Neutral Mutations;142
6.2.9;6.3 Experimental Setup 6.3.1 Benchmark Problems;144
6.2.10;6.3.2 Parameter Settings;145
6.2.11;6.4 Experiments;146
6.2.12;6.4.1 Comparison of Instruction Mutations;146
6.2.13;6.4.2 Comparison with Segment Variations;153
6.2.14;6.4.3 Explicit Growth Bias;154
6.2.15;6.4.4 Number of Mutation Points;156
6.2.16;6.4.5 Self-Adaptation;159
6.2.17;6.4.6 Distribution of Mutation Points;160
6.2.18;6.5 Summary and Conclusion;163
6.3;ANALYSIS OF CONTROL PARAMETERS;164
6.3.1;7.1 Number of Registers;164
6.3.2;7.1.1 Initialization of Registers;168
6.3.3;7.1.2 Constant Registers;171
6.3.4;7.2 Number of Output Registers;171
6.3.5;7.3 Rate of Constants;172
6.3.6;7.4 Population Size;174
6.3.7;7.5 Maximum Program Length;177
6.3.8;7.6 Initialization of Linear Programs;179
6.3.9;7.7 Constant Program Length;184
6.3.10;7.8 Summary and Conclusion;185
6.4;A COMPARISON WITH TREE-BASED GENETIC PROGRAMMING;188
6.4.1;8.1 Tree-Based Genetic Programming;188
6.4.2;8.1.1 Tree Genetic Operators;189
6.4.3;8.1.2 Initialization of Tree Programs;191
6.4.4;8.2 Benchmark Problems;192
6.4.5;8.2.1 GP Benchmarks (;192
6.4.6;8.2.2 Bioinformatics Problems (;193
6.4.7;8.2.3 Generalization Data;195
6.4.8;8.3 Experimental Setup;196
6.4.9;8.3.1 A Multi-Representation GP System;196
6.4.10;8.3.2 Complexity of Programs;197
6.4.11;8.3.3 Parameter Settings;198
6.4.12;8.4 Experiments and Comparison 8.4.1 Prediction Quality and Complexity;200
6.4.13;8.4.2 Generalization Ability;203
6.4.14;8.5 Discussion;205
6.4.15;8.6 Summary and Conclusion;206
7;PART III ADVANCED TECHNIQUES AND PHENOMENA;209
7.1;CONTROL OF DIVERSITY AND VARIATION STEP SIZE;210
7.1.1;9.1 Introduction;210
7.1.2;9.2 Structural Program Distance 9.2.1 E . ective Edit Distance;212
7.1.3;9.2.2 Alternative Distance Metrics;214
7.1.4;9.3 Semantic Program Distance;215
7.1.5;9.4 Control of Diversity;216
7.1.6;9.5 Control of Variation Step Size;218
7.1.7;9.6 Experimental Setup;220
7.1.8;9.7 Experiments 9.7.1 Distance Distribution and Correlation;221
7.1.9;9.7.2 Development of E.ective Step Size;225
7.1.10;9.7.3 Structural Diversity Selection;229
7.1.11;9.7.4 Development of E.ective Diversity;230
7.1.12;9.7.5 Semantic Diversity Selection;232
7.1.13;9.7.6 Diversity and Fitness Progress;233
7.1.14;9.7.7 Control of E.ective Mutation Step Size;235
7.1.15;9.8 Alternative Selection Criteria;237
7.1.16;9.9 Summary and Conclusion;238
7.2;CODE GROWTH AND NEUTRAL VARIATIONS;240
7.2.1;10.1 Code Growth in GP;241
7.2.2;10.2 Proposed Causes of Code Growth;242
7.2.3;10.2.1 Protection Theory;242
7.2.4;10.2.2 Drift Theory;243
7.2.5;10.2.3 Bias Theory;243
7.2.6;10.3 In.uence of Variation Step Size;244
7.2.7;10.4 Neutral Variations;245
7.2.8;10.5 Conditional Reproduction and Variation;247
7.2.9;10.6 Experimental Setup;248
7.2.10;10.7 Experiments 10.7.1 Conditional Instruction Mutations;248
7.2.11;10.7.2 E.ective Reproduction;252
7.2.12;10.7.3 Conditional Segment Variations;253
7.2.13;10.7.4 Semantic Diversity;255
7.2.14;10.7.5 Neutral Drift;257
7.2.15;10.7.6 Crossover Step Size;259
7.2.16;10.7.7 Implicit Bias: Linear Crossover;260
7.2.17;10.7.8 Implicit Bias: E.ective Instruction Mutation;263
7.2.18;10.8 Control of Code Growth;264
7.2.19;10.8.1 Variation-Based Control;264
7.2.20;10.8.2 Why Mutations Cause Less Bloat;268
7.2.21;10.8.3 Selection-Based Control;270
7.2.22;10.8.4 E.ective Complexity Selection;271
7.2.23;10.9 Summary and Conclusion;274
7.3;EVOLUTION OF PROGRAM TEAMS;276
7.3.1;11.1 Introduction;276
7.3.2;11.2 Team Evolution;277
7.3.3;11.2.1 Team Representation;278
7.3.4;11.2.2 Team Operators;279
7.3.5;11.3 Combination of Multiple Predictors;280
7.3.6;11.3.1 Making Multiple Decisions Di.er;281
7.3.7;11.3.2 Combination Methods;282
7.3.8;11.3.3 Averaging (AV);284
7.3.9;11.3.4 Weighting by Error (ERR);284
7.3.10;11.3.5 Coevolution of Weights (EVOL);285
7.3.11;11.3.6 Majority Voting (MV);285
7.3.12;11.3.7 Weighted Voting (WV);286
7.3.13;11.3.8 Winner-Takes-All (WTA);286
7.3.14;11.3.9 Weight Optimization (OPT);287
7.3.15;11.4 Experimental Setup 11.4.1 Benchmark Problems;288
7.3.16;11.4.2 Team and Member Fitness;290
7.3.17;11.4.3 Parameter Settings;290
7.3.18;11.5 Experiments;291
7.3.19;11.5.1 Prediction Accuracy;291
7.3.20;11.5.2 Code Size;295
7.3.21;11.5.3 Number of Team Members;297
7.3.22;11.5.4 Number of Varied Members;299
7.3.23;11.5.5 Interpositional Recombination;300
7.3.24;11.5.6 Member Fitness;300
7.3.25;11.6 Combination of Multiple Program Outputs;301
7.3.26;11.7 Summary and Conclusion;302
8;Epilogue;304
9;References;306
10;Index;318

Leseproben

2.1.5 Iteration Concepts (p.22)
Iteration of code by loops plays a rather unimportant role in genetic programming. Most GP applications that require loops involve control problems with the combination of primitive actions of an agent being the object of evolution. Data flow is usually not necessary in such programs.

Instead, each instruction performs actions with side effects on the problem environment and .tness is derived from a reinforcement signal. For the problem classes we focus on here, supervised classiffcation and approximation, iteration is of minor importance. That is not to say that a reuse of code by iterations could not result in more compact and elegant solutions.

In functional programming the concept of loops is unknown. The implicit iteration concept in functional programs denotes recursions which are, however, hard to control in tree-based genetic programming [142]. Otherwise, iterated evaluations of a subtree can have an effect only if functions produce side effects. In linear GP, assignments represent an implicit side effect on memory locations as part of the imperative representation. Nevertheless, the iteration of an instruction segment may only be effective if it includes at least one effective instruction and if at least one register acts as both destination register and source register in the same or a combination of (effective) instructions, e.g., r0 := r0 + 1.

In the following, possible iteration concepts for linear GP will be presented. These comprise conditional loops and loops with a limited number of iterations. One form of iteration in linear programs is a conditional backward jump corresponding to a while loop in C. The problem with this concept is that infinite loops can be easily formed by conditions that are always fulfilled.

In general, it is not possible to detect all in.nite loops in programs, due to the halting problem [36]. A solution to remedy this situation is to terminate a genetic program after a maximal number of instructions. The result of the program would then, however, depend on the execution time allowed.

The more recommended option is a loop concept that limits the number of iterations in each loop. This requires an additional control flow parameter which may either be constant or be varied within loop instructions. Such a construct is usually expressed by a for loop in C. Because only overlapping loops (not nested loops) need to be avoided, an appropriate choice to limit the size of loop blocks may be the coevolution of endfor instructions.

Analogous to the interpretation of branches in Section 2.1.4, a for instruction and a succeeding endfor de.ne a loop block provided that only closed loops lie in between. All other loop instructions are not interpreted.

2.1.6 Modularization Concepts

For certain problems modularization may be advantageous in GP. By using subroutines repeatedly within programs, solutions may become more compact and the same limited program space can be used more efficiently. A problem may also be decomposed into simpler subproblems that can be solved more efficiently in local submodules. In this case, a combination of subsolutions may result in a simpler and better overall solution.