Genetic Programming: 4th European Conference, EuroGP 2001 Lake Como, Italy, April 18–20, 2001 Proceedings (Lecture Notes in Computer Science (2038))

In This Volume Are The Proceedings Of The Fourth European Conference On - Netic Programming (eurogp 2001) Which Took Place At Lake Como In Italy On April, 18{20 2001. Eurogp Has Become R Mly Established As The Premier - Ropean Event Devoted To Genetic Programming. Eurogp Began Life In 1998 As An International Workshop And Was Held In Paris (14{15 April, Lncs 1391). - Ter That It Was Held In Got ¨ Eborg, Sweden (26{27 May 1999, Lncs 1598). Its R St Appearance As A Conference Was Last Year In Edinburgh In Scotland (15{ 16 April, Lncs 1802). Each Year Eurogp Has Been Co-located With A Series Of Specialist Workshops (lncs 1468, 1596, 1803). This Year Was No Exception And Evoworkshops 2001 Were Also Held At Lake Como (18-19 April, Lncs 2037). Genetic Programming (gp) Refers To A Branch Of Evolutionary Compu- Tion In Which Computer Programs Are Automatically Generated Over A Period Of Time Using A Process That Mimics Darwinian Evolution. The 30 Papers In These Proceedings More Than Amply Demonstrate The Wide And Varied Applicability Of Gp. There Are Papers That Apply Gp To Robotics, Artic Ial Retina, Character Recognition, Nancialprediction, Digitall Terandelectronic Circuitdesign,image Processing, Data Fusion, And Biosequencing. In Addition There Are Many Papers That Address Foundational And Theoretical Issues. Arigorousdouble-blindrefereeing Systemwasappliedtothe42submitted- Pers. This Resulted In 17 Plenary Talks(40% Of Those Submitted) And 13 Research Posters. Heuristic Learning Based On Genetic Programming / Nicole Drechsler [and Others] -- Evolving Color Constancy For An Artificial Retina / Marc Ebner -- Adaptive Genetic Programming Applied To Nee And Existing Simple Regression Problems / Jeroen Eggermont, Jano I. Van Hemert -- Evolutionary Approach To Automatic Generation Of Vhdl Code For Low-power Digital Filters / Massimiliano Erba [and Others] -- Studying The Influence Of Communication Topology And Migration On Distributed Genetic Programming / Francisco Fernández, Marco Tomassini, Leonardo Vanneschi -- Cage: A Tool For Parallel Genetic Programming Applications / Gianluigi Folino, Clara Pizzuti, Giandomenico Spezzano -- Ripple Crossover In Genetic Programming / Maarten Keijzer [and Others] -- Evolving Receiver Operating Characteristics For Data Fusion / William B. Langdon, Bernard F. Buxton -- Adaptive Mapping For Developmental Genetic Programming / Steve Margetts, Antonia J. Jones -- Schema Theory Analysis Of The Evolution Of Size In Genetic Programming With Linear Representations / Nicholas Freitag Mcphee, Riccardo Poli -- Exact Schema Theorems For Gp With One-point And Standard Crossover Operating On Linear Structures And Their Application To The Study Of The Evolution Of Size / Riccardo Poli, Nicholas Freitag Mcphee -- General Schema Theory For Genetic Programming With Subtree-swapping Crossover / Riccardo Poli -- Evolving Modules In Genetic Programming By Subtree Encapsulation / Simon C. Roberts, Daniel Howard, John R. Koza -- Evolution Of Affine Transformations And Interated Function Systems Using Hierarchical Evolution Strategy / Anargyros Sarafopulos -- Evolving Turning Machines For Biosequence Recognition And Analysis / Edgar E. Vallejo, Fernando Ramos -- Neutrality And The Evolvability Of Boolean Function Landscape / Tina Yu, Julian Miller -- Polymorphism And Genetic Programming / Tina Yu -- Programmable Smart Membranes: Using Genetic Programming To Evolve Scalable Distributed Controllers For A Novel Self-reconfigurable Modular Robotic Application / Forrest H. Bennett Iii, Brad Dolin, Eleanor G. Rieffel -- Gp Artificial Ant For Image Processing: Preliminary Experiments With Easea / Enzo Bolis [and Others] -- Feature Extraction For The K-nearest Neighbour Classifier With Genetic Programming / Martijn C.j. Bot -- Indirect Block-oriented Representation For Genetic Programming / Eva Brucherseiger [and Others] -- Raising The Dead: Extending Evolutionary Algorithms With A Case-based Memory / Jeroen Eggermont [and Others] -- Layered Learning In Genetic Programming For A Cooperative Robot Soccer Problem / Steven M. Gustafson, William H. Hsu -- Linear-tree Gp And Its Comparison With Other Gp Structures / Wolfgang Kantschik, Wolfgang Banzhaf -- Evolving Hand-eye Coordination For A Humanoid Robot With Machine Code Genetic Programming / William B. Langdon, Peter Nordin -- Adaption Of Operator Probabilities In Genetic Programming / Jens Niehaus, Wolfgang Banzhaf -- Crossover In Grammatical Evolution: The Search Continues / Michael O'neill [and Others] -- Computational Complexity, Genetic Programming, And Implications / Bart Rylander, Terry Soule, James Foster -- Genetic Programming For Financial Time Series Prediction / Massimo Santini, Andrea Tettamanzi -- Active Handwritten Character Recognition Using Genetic Programming / Ankur Teredesai, J. Park, Venugopal Govindaraju. Julian Miller ... [et Al.]. Includes Bibliographical References And Index. Genetic Programming Preface Organisation Table of Contents Heuristic Learning Based on Genetic Programming Introduction Problem Description BOMs GP Solution Representation Operators Algorithm and Parameter Setting Size Reduction Experimental Results Conclusions References Evolving Color Constancy for an Artificial Retina Introduction An Artificial Retina Experiments Results Conclusion References Adaptive Genetic Programming Applied to New and Existing Simple Regression Problems Introduction Symbolic Regression with Genetic Programming Stepwise Adaptation of Weights Problem Generator Experiments and Results Koza Functions Randomly Generated Polynomials Conclusions Future Research References An Evolutionary Approach to Automatic Generation of VHDL Code for Low-Power Digital Filters Introduction Motivation and Problem Statement Genetic Representation of FIR Filters The Evolutionary Algorithm Experiments and Results Low-Pass Filter with Normalized Pass Band (0, 0.25) Low-Pass Filter with Normalized Pass Band (0, 0.35) Conclusion References Studying the Influence of Communication Topology and Migration on Distributed Genetic Programming Introduction Parallel and Distributed Genetic Programming (PADGP) Implementation and Software Tools Methodology and Problems Description Effort of Computation Even Parity 5 Problem The Artificial Ant Problem on the Santa Fe Trail The Field Programmable Gate Array (FPGA) Problem Comparing Topologies Studying Migration Parameters Conclusions References CAGE: A Tool for Parallel Genetic Programming Applications Introduction Parallel Genetic Programming Parallel Implementation of CAGE Experimental Results Conclusions and Future Work References Ripple Crossover in Genetic Programming Introduction Context Free Grammars and Grammatical Evolution Closed vs. Context Free Grammars Ripple Crossover in GE and GP Experiments Results Discussion Conclusions References Evolving Receiver Operating Characteristics for Data Fusion Introduction ``Maximum Realisable'' ROC An Example Evolving a Combined Classifier Function and Terminal Sets Fitness Function Results Discussion Conclusions Future Work References An Adaptive Mapping for Developmental Genetic Programming Introduction Stack-Based Genetic Programming An Adaptive Genotype to Phenotype Mapping Using a Huffman-Decoding Mapping A Coevolutionary Model for Adaptive Mappings Experimental Setup Results Conclusions Future Work References A Schema Theory Analysis of the Evolution of Size in Genetic Programming with Linear Representations Introduction Schema Theory for GP on Linear Structures Three Theories of Bloat Why Theory Matters Schema Theory Definitions The Schema Theorem An Exact Theory of Bloat Flat Fitness Landscapes The One-then-Zeros Problem One-then-Zeros Problem Definition Calculating alpha_xo ((=)^N , t) and alpha_xo(1(0)^alpha ,t) One-then-Zeros Results Landscape Levels and Program Size Computing the Mean Size Conclusions and Future Work References Exact Schema Theorems for GP with One-Point and Standard Crossover Operating on Linear Structures and Their Application to the Study of the Evolution of Size Introduction Exact Schema Theory for Linear Structures Evolution of Size in Linear Systems Experimental Results Fixed-Point Size Distribution for Standard Crossover on a Flat Landscape Search Space Sampling under Standard Crossover Conclusions References General Schema Theory for Genetic Programming with Subtree-Swapping Crossover Introduction Background Node Reference Systems Functions over Node Reference Systems Modelling Subtree-Swapping Crossovers Microscopic Exact GP Schema Theorem for Subtree-Swapping Crossovers Macroscopic Exact GP Schema Theorem Applications and Specialisations Macroscopic Exact Schema Theorem for GP with Standard Crossover Size-Evolution Equation for GP with Subtree-Swapping Crossover Effective Fitness for GP with Subtree-Swapping Crossovers Conclusions References Evolving Modules in Genetic Programming by Subtree Encapsulation Introduction Subtree Encapsulation Scheme Selecting Subtrees for Modularisation Subtree Database Encapsulation Procedure Subtree Encapsulation for Target Detection Training Data GP Specifications Target Detection Performance Varying the Number of Encapsulated Subtrees Computation Time Interpretation of Subtree Operation Conclusions References Evolution of Affine Transformations and Iterated Function Systems Using Hierarchical Evolution Strategy Introduction Hierarchical Evolution Strategy Strongly Typed Genetic Programming Evolution of Affine Transformations STGP Architecture Architecture Using the Hierarchical Evolution Strategy Mutation for ES Individuals, Fitness Function, and Control Parameters Results for the Inverse Problem for Affine Transformations Evolution of Iterated Function Systems Architecture Using the Hierarchical Evolution Strategy Architecture Using STGP Fitness Function Control Parameters Results for the Inverse Problem for IFS Conclusions References Evolving Turing Machines for Biosequence Recognition and Analysis Introduction Turing Machines as the Model of Computation of GP Experiments Experiment 1: Turing Machines Experiment 2: Two-Way Deterministic Finite Automata Experiment 3: Multiple Sequence Alignment Conclusions and Future Work References Neutrality and the Evolvability of Boolean Function Landscape Introduction Neutrality: Implicit Versus Explicit Neutral Versus Adaptive Mutation Cartesian Genetic Programming Experiments Even-3-Parity Problem Evolutionary Algorithm Neutrality Measured with Hamming Distance Results Analysis and Discussion Related Work Conclusion and Future Work Referernces Programmable Smart Membranes: Using Genetic Programming to Evolve Scalable Distributed Controllers for a Novel Self-Reconfigurable Modular Robotic Application Introduction Related Work Modular Robot Simulator Movement Sensors The Smart Membrane Problem Function Set Terminal Set Fitness Parallelization Results Generalization Conclusions and Future Work References A GP Artificial Ant for Image Processing: Preliminary Experiments with EASEA Introduction EASEA and genetic programming The artificial ant problem, animats and low-level image processing Implementing a food foraging process using EASEA Animat functions Initialising trees Crossover Mutation Fitness evaluation Results Contour detection Grey level images and contour detection Basic animat functions Genetic operators Results Comments on implementation Conclusion and future work References Feature Extraction for the k-Nearest Neighbour Classifier with Genetic Programming Introduction Related Work A Framework for Feature Extraction Overview Features Course of Evolution Fitness Measure Stopping Criterion Comparison Algorithms Experiments Results Evolved Features Timing Conclusion References An Indirect Block-Oriented Representation for Genetic Programming Introduction GP Codings for Models or Controller Direct Block-Oriented Representation Indirect Block-Oriented Representation Comparison of Both Representations Real World Application of the Indirect Representation Conclusion References Raising the Dead: Extending Evolutionary Algorithms with a Case-Based Memory Introduction Context Periodically Changing Problems Incorporating a Case-Based Memory Experiments Conclusion and Future Work References Layered Learning in Genetic Programming for a Cooperative Robot Soccer Problem Introduction Keep-Away Soccer Layered Learning Experiments Results Conclusions References Linear-Tree GP and Its Comparison with Other GP Structures Introduction of Linear-Tree GP Recombination of Linear-Tree Programs Mutation Test Problems Symbolic Regression Non-regression Problems Experimental Results Difference between the Representations Analysis of the Linear-Tree-Structure The Analysis of the Crossover-Operator Summary and Outlook References Evolving Hand-Eye Coordination for a Humanoid Robot with Machine Code Genetic Programming Introduction Background The Elvis Humanoid Software Architecture Experiments Inverse Kinematics Experiment Cameras and Image Processing Collection of Training Data Use of Discipulus Demonstration Results Discussion Future Work Summary and Conclusions References Adaption of Operator Probabilities in Genetic Programming Introduction GGP and Genetic Operators Graph Representation Genetic Operators The Evolutionary Algorithm Different Methods of Adaption Population-Level Dynamic Probabilities (PDP) Fitness Based Dynamic Probabilities (FBDP) Individual-Level Dynamic Probabilities (IDP) Experiments and Results Symbolic Regression Classification Discussion Conclusion References Crossover in Grammatical Evolution: The Search Continues Introduction Grammatical Evolution The GE Crossover Operator Experimental Approach Results Discussion Conclusions and Future Work References Symbolic Regression Grammar Santa Fe Trail Grammar Computational Complexity, Genetic Programming, and Implications Introduction Kolmogorov Complexity GP Complexity GPs for Programs GPs for Function Optimization Implications to GP Design Large vs. Small Populations Increasing Complexity Quantum GPs Universal Genetic Program Conclusions References Genetic Programming for Financial Time Series Prediction Introduction The Problem The Algorithm The Initial Structures Fitness Operations for Modifying Structures Experiments Test Problem: Parabola Predicting the Dow Jones Conclusion References Active Handwritten Character Recognition Using Genetic Programming Introduction Related Work GeneARM- Genetic Active Recognition Methods Apparatus Setup Fitness Testing Phase Experiments Results and Discussion Conclusion References Author Index Subject Index 3540453555_17_OnlinePDF.pdf.pdf 1 Introduction 2 Types in Genetic Programming 3 Dynamically Typed GP 4 Strongly Typed GP 5 Experiments 6 Discussion 7 Conclusions Bibliography Genetic Programming: 4th European Conference, EuroGP 2001 Lake Como, Italy, April 18–20, 2001 Proceedings Author: Julian Miller, Marco Tomassini, Pier Luca Lanzi, Conor Ryan, Andrea G. B. Tettamanzi, William B. Langdon Published by Springer Berlin Heidelberg ISBN: 978-3-540-41899-3 DOI: 10.1007/3-540-45355-5 Table of Contents: Heuristic Learning Based on Genetic Programming Evolving Color Constancy for an Artificial Retina Adaptive Genetic Programming Applied to New and Existing Simple Regression Problems An Evolutionary Approach to Automatic Generation of VHDL Code for Low-Power Digital Filters Studying the Influence of Communication Topology and Migration on Distributed Genetic Programming CAGE: A Tool for Parallel Genetic Programming Applications Ripple Crossover in Genetic Programming Evolving Receiver Operating Characteristics for Data Fusion An Adaptive Mapping for Developmental Genetic Programming A Schema Theory Analysis of the Evolution of Size in Genetic Programming with Linear Representations Exact Schema Theorems for GP with One-Point and Standard Crossover Operating on Linear Structures and Their Application to the Study of the Evolution of Size General Schema Theory for Genetic Programming with Subtree-Swapping Crossover Evolving Modules in Genetic Programming by Subtree Encapsulation Evolution of Affine Transformations and Iterated Function Systems Using Hierarchical Evolution Strategy Evolving Turing Machines for Biosequence Recognition and Analysis Neutrality and the Evolvability of Boolean Function Landscape Polymorphism and Genetic Programming Programmable Smart Membranes: Using Genetic Programming to Evolve Scalable Distributed Controllers for a Novel Self-Reconfigurable Modular Robotic Application A GP Artificial Ant for image processing: preliminary experiments with EASEA. Feature Extraction for the k-Nearest Neighbour Classifier with Genetic Programming These are the the refereed proceedings of the 4th European Conference on Genetic Programming. They range theoretical and foundational issues to applications such as robotics, artificial retina, character recognition, financial prediction, digital filter and electronic circuit design. Genetic programming (GP) is a fast developing field which aims at evolving a population of computer codes towards a program that solves a given problem [Koz92].