Genetic Programming: 6th European Conference, EuroGP 2003, Essex, UK, April 14-16, 2003. Proceedings (Lecture Notes in Computer Science, 2610)

In this volume we present the accepted contributions to the Sixth European Conference on Genetic Programming (EuroGP 2003) which took place at the University of Essex, UK on 14-16 April 2003. EuroGP is now a well-established conference and, without any doubt, the most important international event - voted to Genetic Programming occurring in Europe. The proceedings have all been published by Springer-Verlag in the LNCS series. EuroGP began as an - ternational workshop in Paris, France in 1998 (14–15 April, LNCS 1391). Sub- quently the workshop was held in G ̈ oteborg, Sweden in 1999 (26–27 May, LNCS 1598) and then EuroGP became an annual conference: in 2000 in Edinburgh, UK (15–16 April, LNCS 1802), in 2001 in Lake Como, Italy (18–19 April, LNCS 2038) and in 2002 in Kinsale, Ireland (3–5 April, LNCS 2278). From the outset, there have always been specialized workshops, co-located with EuroGP, focusing on applications of evolutionary algorithms (LNCS 1468, 1596, 1803, 2037, and 2279). This year was no exception and EvoWorkshops 2003, incorporating Evo- BIO, EvoCOP, EvoIASP, EvoMUSART, EvoSTIM and EvoROB, took place at the University of Essex (LNCS 2611). Genetic Programming (GP) is that part of Evolutionary Computation which solves particular complex problems or tasks by evolving and adapting popu- tions of computer programs, using Darwinian evolution and Mendelian genetics as a source of inspiration. Lecture Notes in Computer Science 2610 Preface Organization Table of Contents Evolving Cellular Automata to Grow Microstructures 1 Introduction 2 Background 2.1 Introduction to Microstructures 2.2 Cellular Automata 2.3 Effector Automata 3 Using GAs to Grow Microstructures with Effector Automata 3.1 Effector Automata Rules 3.2 Genetic Algorithm 3.3 Fitness Function 4 Experiments 5 Results 5.1 Results for Experiment 1 5.2 Results for Experiment 2 6 Analysis 7 Conclusion References An Innovative Application of a Constrained-Syntax Genetic Programming System to the Problem of Predicting Survival of Patients 1 Introduction 2 A Constrained-Syntax GP for Discovering Classification Rules 2.1 Syntactic Constraints on the Individual Representation 2.2 Genetic Operators 2.3 Fitness Function 2.4 Classification of New Instances 3 Computational Results 4 Conclusions and Future Research References New Factorial Design Theoretic Crossover Operator for Parametrical Problem 1 Introduction 2 Orthogonal Arrays and Factorial Design Methods (Preliminary) 3 Crossover Operators with Factorial Design Methods 4 Crossover Operation with Interaction Effect Analysis 5 Numerical Experiments and Results 6 Conclusion References Overfitting or Poor Learning: A Critique of Current Financial Applications of GP 1 Motivation and Introduction 2 Signal Ratio and Overfitting 3 Experimental Designs 3.1 Data 3.2 Genetic Programming 4 Results 5 Two Further Tests 6 Conclusion: Implications for Financial Applications References Evolutionary Design of Objects Using Scene Graphs 1 Motivation 2 Scene Graph 3 Evolving Scene Graphs 4 Evolving the Blades of a Wind Turbine 5 Experiments 6 Conclusion References Ensemble Techniques for Parallel Genetic Programming Based Classifiers 1 Introduction 2 Ensemble Techniques 3 Data Classification Using Cellular Genetic Programming 4 Ensemble of Classifiers in CGP 5 Experimental Results 6 Conclusions and Future Work References Improving Symbolic Regression with Interval Arithmetic and Linear Scaling 1 Introduction 2 Why Protected Operators Do Not Help 3 Static Analysis through Interval Arithmetic 4 Minimization of Error Can Deceive Genetic Programming 5 Linear Scaling 6 Demonstration 7 Conclusion References Evolving Hierarchical and Recursive Teleo-reactive Programs through Genetic Programming 1 Introduction 2 Teleo-reactive Programs 3 Methods 3.1 Functions and Terminals 3.2 Evaluation of Fitness 3.3 Parameters 3.4 Human-Designed Solution 4 Results and Discussion 5 Conclusions 6 Further Work References Interactive GP for Data Retrieval in Medical Databases* 1 Introduction 2 ELISE: An Evolutionary Learning Interactive Search Engine 3 Genome and Structure 3.1 Rewriting Language 3.2 Language Structure 3.3 Instruction Set 3.4 Derived Rewriting Rules 4 Evolving a User Profile: GP Genetic Operators 4.1 Fitness Function and User Interaction 4.2 Initialisation and Parameters 5 Experiments and Analysis 6 Conclusion and Future Works References Parallel Programs Are More Evolvable than Sequential Programs 1 Introduction 2 Genetic Parallel Programming (GPP) 2.1 The Multi-ALU Processor (MAP) 2.2 The Evolution Engine (EE) 3 The GPP Accelerating Phenomenon 4 Experimental Settings 4.1 Computational Effort Measurement 5 Results and Evaluations 6 Conclusions and Further Work References Genetic Programming with Meta-search: Searching for a Successful Population within the Classification Domain 1 Introduction 2 Meta-search: A Pyramid Strategy 3 Meta-search: Population Beam Search 4 A Combined Approach: A Pyramid Search and Population Beam Search 5 Experimental Configuration 6 Results 6.1 Training Times 6.2 Future Directions for Meta-search Methods 6.3 Conclusions References Evolving Finite State Transducers: Some Initial Explorations 1 Introduction 1.1 Relevance to Genetic Programming 2 Motivation 3 Finite State Transducers 3.1 Example FST 4 Evolutionary Algorithm 5 Fitness Functions 6 Fitness Distance Correlation Analysis 7 Results 8 Discussion and Conclusions References Reducing Population Size while Maintaining Diversity 1 Introduction 2 Existing Techniques to Measure and Maintain Diversity 3 Minimal Directed Acyclic Graph Representation 4 Measuring the Added Diversity of an Individual 5 Experimental Results 5.1 Symbolic Regression 5.2 AI Planning 5.3 Robocup 6 Conclusions References How Functional Dependency Adapts to Salience Hierarchy in the GAuGE System 1 Introduction 2 Grammatical Evolution 3 Genetic Algorithms Using Grammatical Evolution 3.1 Example GAuGE Mapping 3.2 Previous Results 4 Problems 4.1 BinInt 4.2 InvBinInt 4.3 Onemax 5 Experiments 5.1 Experimental Setup 5.2 Results 5.3 Analysis 6 Conclusions 7 Future Work References More on Computational Effort Statistics for Genetic Programming 1 Introduction 2 Measurement and Calculation of the Computational Effort 3 Computational Effort for Steady-State Algorithms 4 Experimental Framework 5 Influence of $P_{textit {fail}}$ on the Computational Effort 6 Influence of $sd$ on the Computational Effort 7 Summary References Analysis of a Digit Concatenation Approach to Constant Creation 1 Introduction 1.1 Background 1.2 Structure of Paper 2 Grammatical Evolution 3 Problem Domain and Experimental Approach 3.1 Finding a Static Real Constant 3.2 Finding Dynamic Real Constants 3.3 The Logistic Equation 3.4 Constant Creation Grammars 4 Results 4.1 Finding a Static Real Constant 4.2 Finding Dynamic Real Constants 4.3 The Logistic Equation 5 Conclusions and Future Work References Genetic Programming with Boosting for Ambiguities in Regression Problems 1 Introduction 2 Genetic Programming and Boosting 2.1 Principles 2.2 The GPboost Algorithm 2.3 Getting Several Solutions 3 Dealing with Several Solutions 3.1 Dendrograms for Dealing with Ambiguities 4 A Scheme to Overcome Ambiguities 4.1 Setting up a Cluster Value 4.2 Description of the Algorithm 5 Experiments, Error and Results 6 Conclusion and Future Works References A How to Build a Dendrogram B Computing the Cutoff Value Maximum Homologous Crossover for Linear Genetic Programming 1 Introduction 2 Maximum Homologous Crossover 2.1 Edit Distance 2.2 Best Alignment and Recombination 2.3 Features of Maximum Homologous Crossover 3 Royal Road Landscapes for LGP 4 Experimental Results 4.1 Setup 4.2 Homology Driven Fitness Problem 4.3 Royal Road Landscape 5 Conclusion and Perspectives References A Simple but Theoretically-Motivated Method to Control Bloat in Genetic Programming 1 Introduction 2 Background 3 The Tarpeian Method to Control Bloat 4 Experimental Result 5 Conclusions and Future Work References Divide and Conquer: Genetic Programming Based on Multiple Branches Encoding 1 Introduction 2 Multiple Branches Encoding: Divide and Conquer 2.1 MB Individual Evaluation 2.2 Genetic Operators 3 MBGP in Modelling 3.1 Symbolic Regression 3.2 Modelling and Prediction 4 Logic Circuits Design 5 Conclusions References Feature Construction and Selection Using Genetic Programming and a Genetic Algorithm 1 Introduction 2 The GAP Algorithm 2.1 Feature Creation 2.2 Feature Selection 3 Experimentation 3.1 Results 3.2 Analysis 3.3 A Rough Comparison to Other Algorithms 4 Conclusion References Genetic Programming Applied to Compiler Heuristic Optimization 1 Introduction 2 Related Work 3 Compilation, Heuristics and Priority Functions 4 Predication 4.1 Predication Primitives 5 Priority-Based Coloring Register Allocation 5.1 Register Allocation Primitives 6 Experimental Parameters 6.1 Infrastructure 6.2 GP Run Parameters 6.3 Evaluation 7 Results 7.1 Predication: Specialized Priority Functions 7.2 Predication: Finding General Purpose Priority Functions 7.3 Register Allocation: Specialized Priority Functions 7.4 Register Allocation: General Purpose Priority Functions 8 Conclusions 9 Future Work References Modularity in Genetic Programming 1 Introduction 2 Modularity 3 Related Work 4 Definitions and Proofs 5 Implications for Learning 6 Discussion 7 Conclusion References Decreasing the Number of Evaluations in Evolutionary Algorithms by Using a Meta-model of the Fitness Function 1 Introduction 2 Tournament Selection by Classification 3 Confidence Level 4 Influence on the Performance of the EA 5 Evolving a Classifier with Genetic Programming 6 Application 7 Discussion References Assembling Strategies in Extrinsic Evolvable Hardware with Bidirectional Incremental Evolution 1 Introduction 2 Bidirectional Incremental Evolution 2.1 Direct Incremental Evolution (DIE) 2.2 Reverse Incremental Evolution (RIE) 3 Assembling Processes 3.1 Assembling Strategies at RIE Level 3.2 Circuit Linkage at the Decomposition Level 3.3 Assembling Strategies at the Chromosome Level 4 Experimental Results 5 Conclusions and Future Work References Neutral Variations Cause Bloat in Linear GP 1 Introduction 2 Basics on Linear GP 2.1 Variation Effects 3 Code Growth in GP 4 Conditional Variation 5 Benchmark Problems 6 Experimental Setup 7 Experimental Results 8 Conclusion References Experimental Design Based Multi-parent Crossover Operator 1 Introduction 2 Experimental Design Methods (Preliminary) 3 Multi-parent Diagonal Crossover 4 Multi-parent Crossover with Orthogonal Latin Square Design 5 Algorithm Comparison 6 Conclusion References An Enhanced Framework for Microprocessor Test-Program Generation 1 Introduction 2 Related Work 3 Proposed Approach 3.1 Sub-DAG 3.2 Frames 3.3 Instruction Library and Nodes 3.4 Evolution 3.5 Auto Adaptation 4 Experimental Evaluation 5 Conclusions References The Effect of Plagues in Genetic Programming: A Study of Variable-Size Populations 1 Introduction 2 Computational Effort 3 A Model of Plagues 4 Experimental Results 4.1 Fitness vs. Effort 4.2 Effort Relationships 4.3 Diversity 5 Conclusions and Future Work References Multi Niche Parallel GP with a Junk-Code Migration Model 1 Introduction. Background 1.1 Junk Code 1.2 Multi Niche Genetic Programming 2 Multi Niche Parallel GP 2.1 Parallelisation Strategy 2.2 Experimental Setup 2.3 Results 3 Conclusions References Tree Adjoining Grammars, Language Bias, and Genetic Programming 1 Introduction 2 Tree Adjoining Grammars 3 Tree Adjoining Grammar Guided Genetic Programming 4 An Example of TAG3P+ with Language Bias 5 Conclusions and Future Work References Artificial Immune System Programming for Symbolic Regression 1 Introduction 2 Artificial Immune Systems 3 A Clonal Selection Algorithm 4 Applying the Algorithm to Symbolic Regression 5 Future Work References Grammatical Evolution with Bidirectional Representation 1 Introduction 2 Grammatical Evolution 3 Information Loss during Crossover in GE 4 Bidirectional Representation 5 Setup of the Experiments 6 Results 7 Conclusions References Introducing a Perl Genetic Programming System – and Can Meta-evolution Solve the Bloat Problem? 1 Introduction 2 Implementation 2.1 Object-Oriented Design 2.2 Tree-as-Hash-Table Genotype Representation 2.3 Grammar Specification 2.4 Random Initialisation of Programs 2.5 Persistence of GP Individuals 2.6 Code/Fitness Evaluation 3 Genetic Algorithm Design 3.1 The Genetic Algorithm 3.2 "Homologous'' Crossover 3.3 Mutation Operators 4 Benchmarking 4.1 Speed Comparison with lilgp 4.2 Mutation and Crossover Strategies 5 Conclusion References Evolutionary Optimized Mold Temperature Control Strategies Using a Multi-polyline Approach 1 Introduction 2 Encoding 2.1 Mold Temperature Control Circuits 2.2 The Mold 3 Fitness 4 The Evolutionary Algorithm 5 Results 5.1 Basic Analyzes 5.2 Practical Application 5.3 Experimental Setup 6 Conclusions and Outlook References Genetic Programming for Attribute Construction in Data Mining 1 Introduction 2 A Review of Attribute Construction 3 A New GP for Attribute Construction 3.1 Individual Representation 3.2 Selection Method and Genetic Operators 3.3 Fitness Function 4 Computational Results 5 Conclusions and Future Research References Sensible Initialisation in Chorus 1 Introduction 2 Chorus 2.1 Chorus Initialisation 3 Initialisation 3.1 Initialisation in Genetic Programming 3.2 Sensible Initialisation in Chorus 4 Experimental Setup 4.1 Results 4.2 Discussion 5 Conclusions References An Analysis of Diversity of Constants of Genetic Programming 1 Introduction 2 Constants in Genetic Programming 2.1 Implementation and Optimization of Constants 2.2 Sorted Table Method 3 The Eve Phenomenon 4 Experimental Setup 4.1 Results 4.2 Application to Real Symbolic Regression Problems 4.3 Results 5 Temporal Properties of Mutation 5.1 Lineage of Constants 5.2 Distinct Constants 5.3 Successful Mutations 6 Conclusions References Research of a Cellular Automaton Simulating Logic Gates by Evolutionary Algorithms 1 Introduction 2 Simulation of a Logic Gate 3 Framework 3.1 Cellular Automata 3.2 Evolutionary Algorithms 4 A New Rule 4.1 Starting Rules 4.2 Crossover and Mutation 4.3 Fitness Function 4.4 Evolutionary Algorithm 4.5 Result 5 Rule R 5.1 The Glider of R 5.2 The Glider Gun of R 5.3 Collisions 6 Eater 6.1 Population 6.2 Offspring 6.3 Fitness Function 6.4 Evolutionary Algorithm 7 Related Works 8 Synthesis and Perspectives References From Implementations to a General Concept of Evolvable Machines 1 Introduction 2 Evolutionary Computational Machines Design 2.1 A Software Viewpoint 2.2 A Hardware Viewpoint 2.3 A Formal Viewpoint 2.4 Relation of the Approaches 3 Evolvable Machines 3.1 Formal Approach 3.2 Computational Power 4 Summary 5 Conclusions References Cooperative Evolution on the Intertwined Spirals Problem* 1 Introduction 2 Background 3 Cooperative Mechanisms 4 The Genetic Program 5 Results -- Fitness 6 Results -- Cooperation 7 Results -- Size 8 Conclusions and Future Work References The Root Causes of Code Growth in Genetic Programming 1 Introduction 1.1 Terminology and Background 1.2 Existing Theories of Code Growth 1.3 Problems and Methodology 2 Components of Code Growth 3 Resilience in GP Trees 3.1 Our Measurement of Resilience 3.2 The Resilience of Randomly Generated Trees 3.3 Resilience in Actual GP Runs 3.4 What Makes Trees Resilient 4 A Selection Scheme that Eliminates Bloat 4.1 The Possibility of MBC as a Probabilistic Size Penalty 5 Effects on Scalability 6 Conclusions References Fitness Distance Correlation in Structural Mutation Genetic Programming 1 Introduction 2 Distance Measure for Genetic Programs 3 Structural Mutation Operators 4 Experimental Results 4.1 Fitness Distance Correlation 4.2 Trap Functions 4.3 Royal Trees 4.4 MAX Problem 5 Conclusions and Future Work 1 Proof of the Distance/Operator Consistency Property References Disease Modeling Using Evolved Discriminate Function 1 Introduction 2 Genetic Programming 3 Diagnosis of Severe Diseases Using Discriminate Function 4 Experimental Results 5 Summary and Conclusion References No Free Lunch, Program Induction and Combinatorial Problems 1 Introduction 2 Search Algorithm Framework 3 Discussion of NFL 4 Program Induction and NFL 5 Combinatorial Problems and Terminating Search Algorithms 6 Extending the Framework for Terminating Search Algorithms 7 Comments and Discussion 8 Summary References Author Index

This book constitutes the refereed proceedings of the 6th European Conference on Genetic Programming, EuroGP 2003, held in Essex, UK in April 2003.

The 45 revised papers presented were carefully reviewed and selected from 61 submissions. All current aspects of genetic programming and genetic algorithms are addressed, ranging from foundational, theoretical, and methodological issues to advanced applications in various fields.

Classification is an important problem extensively studied in several research areas, such as statistical pattern recognition, machine learning and data mining [Hand 1997].