1820 April 2001 Lake Como (Milan), Italy 


EuroGP2001 abstractsOral presentationsHeuristic Learning based on Genetic ProgrammingNicole Drechsler  Frank Schmiedle  Daniel Grosse  Rolf DrechslerAbstract:In this paper we present an approach to learning heuristics based on Genetic Programming (GP). Instead of directly solving the problem by application of GP, GP is used to develop a heuristic that is applied to the problem instance. By this, the typical large runtimes of evolutionary methods have to be invested only once in the learning phase. The resulting heuristic is very fast. The technique is applied to a field from the area of VLSI CAD, i.e. minimization of Binary Decision Diagrams (BDDs). We chose this topic due to its high practical relevance and since it matches the criteria where our algorithm works best, i.e. large problem instances where standard evolutionary techniques cannot be applied due to their large runtimes. Our experiments show that we obtain high quality results that outperform previous methods, while keeping the advantage of low runtimes. Keywords:Heuristic Learning, VLSI CAD, BDD, Binary Decision Diagrams 10 pages Evolving Color Constancy for an Artificial RetinaMarc EbnerAbstract:Objects retain their color in spite of changes in the wavelength and energy composition of the light they reflect. This phenomenon is called color constancy and plays an important role in computer vision research. We have used genetic programming to automatically search the space of programs to solve the problem of color constancy for an artificial retina. This retina consists of a two dimensional array of elements each capable of exchanging information with its adjacent neighbors. The task of the program is to compute the intensities of the light illuminating the scene. These intensities are then used to calculate the reflectances of the object. Randomly generated color Mondrians were used as fitness cases. The evolved program was tested on artificial Mondrians and natural images. Keywords:Color Constancy, Artificial Retina, Image Processing 12 pages Adaptive Genetic Programming Applied to New and Existing Simple Regression ProblemsJeroen Eggermont  Jano I. van HemertAbstract:In this paper we continue our study on adaptive genetic programming. We use Stepwise Adaptation of Weights (SAW) to boost performance of a genetic programming algorithm on simple symbolic regression problems. We measure the performance of a standard GP and two variants of SAW extensions on two different symbolic regression problems from literature. Also, we propose a model for randomly generating polynomials which we then use to further test all three GP variants. Keywords:Adaptation, Symbolic Regression, Problem Generator, Program Trees 13 pages An Evolutionary Approach to Automatic Generation of VHDL Code for LowPower Digital FiltersMassimiliano Erba  Roberto Rossi  Valentino Liberali  Andrea TettamanziAbstract:An evolutionary algorithm is used to design a finite impulse response digital filter with reduced power consumption. The proposed design approach combines genetic optimization and simulation methodology, to evaluate a multiobjective fitness function which includes both the suitability of the filter transfer function and the transition activity of digital blocks. The proper choice of fitness function and selection criteria allows the genetic algorithm to perform a better search within the design space, thus exploring possible solutions which are not considered in the conventional structured design methodology. Although the evolutionary process is not guaranteed to generate a filter fully compliant to specifications in every run, experimental evidence shows that, when specifications are met, evolved filters are much better than classical designs both in terms of power consumption and in terms of area, while maintaining the same performance. Keywords:Evolvable Hardware, Evolutionary Algorithms, Electronic Design, Digital Filters, VHDL 15 pages Studying the Influence of Communication Topology and Migration on Distributed Genetic ProgrammingF. Fernandez  L. Vanneschi  M. TomassiniAbstract:In this paper we present a systematic experimental study of some of the parameters influencing parallel and distributed genetic programming (PADGP) by using three benchmark problems. We first present results on the system's communication topology and then we study the parameters governing individual migration between subpopulations: the number of individuals sent and the frequency of exchange. Our results suggest that fitness evolution is more sensitive to the migration factor than the communication topology. Keywords:Distributed Genetic Programming, Parallelism, Multipopulation structures, Parallel evolutionary algorithms 13 pages CAGE: A Tool for Parallel Genetic Programming ApplicationsGianluigi Folino  Clara Pizzuti  Giandomenico SpezzanoAbstract:A new parallel implementation of genetic programming based on the cellular model is presented and compared with the island model approach. Although the widespread belief that cellular model is not suitable for parallel genetic programming implementations, experimental results show a better convergence with respect to the island approach, a good scaleup behaviour and a nearly linear speedup. Keywords:Parallel programming, Cellular model 11 pages Ripple Crossover in Genetic ProgrammingMaarten Keijzer  Conor Ryan  Michael O'Neill  Mike Cattolico  Vladin BabovicAbstract:This paper isolates and identifies the effects of the crossover operator used in Grammatical Evolution. This crossover operator has already been shown to be adept at combining useful building blocks and to outperform engineered crossover operators such as Homologous Crossover. This crossover operator, Ripple Crossover is described in terms of Genetic Programming and applied to two benchmark problems. Its performance is compared with that of traditional subtree crossover on populations employing the standard functions and terminal set, but also against populations of individuals that encode Context Free Grammars. Ripple crossover is more effective in exploring the search space of possible programs than subtree crossover. This is shown by examining the rate of premature convergence during the run. Ripple crossover produces populations whose fitness increases gradually over time, slower than, but to an eventual higher level than that of subtree crossover. Keywords:Grammatical evolution, Context Free Grammars, Crossover, Intrinsic Polymorphism 14 pages Evolving Receiver Operating Characteristics for Data FusionW. B. Langdon  B. F. BuxtonAbstract:It has been suggested that the ``Maximum Realisable Receiver Operating Characteristics'' for a combination of classifiers is the convex hull of their individual ROCs [Scott et al., 1998]. As expected in at least some cases better ROCs can be produced. We show genetic programming (GP) can automatically produce a combination of classifiers whose ROC is better than the convex hull of the supplied classifier's ROCs. Keywords:Data Fusion, Data Mining, Knowledge Discovery, Receiver Operating Characteristics, ROC, Combining Classifiers 10 pages An Adaptive Mapping for Developmental Genetic ProgrammingSteve Margetts  Antonia J. JonesAbstract:In this article we introduce a general framework for constructing an adaptive genotypetophenotype mapping, and apply it to developmental genetic programming. In this preliminary investigation, we run a series of comparative experiments on a simple test problem. Our results show that the adaptive algorithm is able to outperform its nonadaptive counterpart. Keywords:Developmental Genetic Programming, Adaptive Genotype to Phenotype Mappings, MAX Problem 11 pages A schema theory analysis of the evolution of size in genetic programming with linear representationsNicholas Freitag McPhee  Riccardo PoliAbstract:In this paper we use the schema theory presented elsewhere in this volume to better understand the changes in size distribution when using GP with standard crossover and linear structures. Applications of the theory to problems both with and without fitness suggest that standard crossover induces specific biases in the distributions of sizes, with a strong tendency to over sample small structures, and indicate the existence of strong redistribution effects that may be a major force in the early stages of a GP run. We also present two important theoretical results: An exact theory of bloat, and a general theory of how average size changes on flat landscapes with glitches. The latter implies the surprising result that a single program glitch in an otherwise flat fitness landscape is sufficient to drive the average program size of an infinite population, which may have important implications for the control of code growth. Keywords:Schema theory, Linear representations, Bloat, Length distributions, Fitness landscape glitches, Onethenzeros problem 18 pages Exact Schema Theorems for GP with OnePoint and Standard Crossover Operating on Linear Structures and their Application to the Study of the Evolution of SizeRiccardo Poli  Nicholas Freitag McPheeAbstract:In this paper, firstly we specialise the exact GP schema theorem for onepoint crossover to the case of linear structures of variable length, for example binary strings or programs with arity1 primitives only. Secondly, we extend this to an exact schema theorem for GP with standard crossover applicable to the case of linear structures. Then we study, both mathematically and numerically, the schema equations and their fixed points for infinite populations for both a constant and a lengthrelated fitness function. This allows us to characterise the bias induced by standard crossover. This is very peculiar. In the case of a constant fitness function, at the fixedpoint, structures of any length are present with nonzero probability. However, shorter structures are sampled exponentially much more frequently than longer ones. Keywords:Schema theory, Crossover, Crossover bias, Standard Crossover, Fixed points, Variablelength Genetic Algorithms, 16 pages General Schema Theory for Genetic Programming with SubtreeSwapping CrossoverRiccardo PoliAbstract:In this paper a new, general and exact schema theory for genetic programming is presented. The theory includes a microscopic schema theorem applicable to crossover operators which replace a subtree in one parent with a subtree from the other parent to produce the offspring. A more macroscopic schema theorem is also provided which is valid for crossover operators in which the probability of selecting any two crossover points in the parents depends only on their size and shape. The theory is based on the notions of Cartesian node reference systems and variablearity hyperschemata both introduced here for the first time. In the paper we provide examples which show how the theory can be specialised to specific crossover operators and how it can be used to derive an exact definition of effective fitness and a sizeevolution equation for GP. Keywords:Schema theory, Crossover, Subtreeswapping Crossover, Standard Crossover, Evolution of size, Bloat, Variablelength Genetic Algorithms 16 pages Evolving modules in Genetic Programming by subtree encapsulationSimon C. Roberts  Daniel Howard  John R. KozaAbstract:In treebased genetic programming (GP), the most frequent subtrees on later generations are likely to constitute useful partial solutions. This paper investigates the effect of encapsulating such subtrees by representing them as atoms in the terminal set, so that the subtree evaluations can be exploited as terminal data. The encapsulation scheme is compared against a second scheme which depends on random subtree selection. Empirical results show that both schemes improve upon standard GP. Keywords:Modularisation, Code Reuse, Subtree Encapsulation, Image Processing, 16 pages Evolution of Affine Transformations and Iterated Function Systems using Hierarchical Evolution StrategyAnargyros SarafopoulosAbstract:Often optimization problems involve the discovery of many scalar coefficients. Although genetic programming (GP) has been applied to the optimization and discovery of functions with an arbitrary number of scalar coefficients, recent results indicate that a method for finetuning GP scalar terminals can assist the discovery of solutions. In this paper we demonstrate an approach where genetic programming and evolution strategies (ES) are seamlessly combined. We apply our GP/ES hybrid, which we name Hierarchical Evolution Strategy, to the problem of evolving affine transformations and iterated function systems (IFS). We compare the results of our approach with GP and notice an improvement in performance in terms of discovering better solutions and speed. Keywords:Strongly Typed GP, STGP, Evolution Strategies, Iterated Function Systems 16 pages Evolving Turing machines for Biosequences Recognition and AnalysisEdgar E. Vallejo  Fernando RamosAbstract:This article presents a genetic programming system for biosequence recognition and analysis. In our model, a population of Turing machines evolves the capability of biosequence recognition using genetic algorithms. We use HIV sequences as the working example. Experimental results indicate that evolved Turing machines are capable of recognizing HIV sequences in a collection of training sets. In addition, we demonstrate that the evolved Turing machines can be used to approximate the multiple sequence alignment problem. Keywords:Bioinformatics, DNA, Turing machines, Multiple Sequence aligment 12 pages Neutrality and the Evolvability of Boolean Function LandscapeTina Yu  Julian MillerAbstract:This work is a study of neutrality in the context of Evolutionary Computation systems. In particular, we introduce the use of explicit neutrality with an integer string coding scheme to allow neutrality to be measured during evolution. We tested this method on a Boolean benchmark problem. The experimental results indicate that there is a positive relationship between neutrality and evolvability: neutrality improves evolvability. We also identify four characteristics of adaptive/neutral mutations that are associated with high evolvability. They may be the ingredients in designing effective Evolutionary Computation systems for the Boolean class problem. Keywords:Neutrality, Evolvability, Boolean function landscape, Neutral mutation, Exploration vs. Exploitation, Graphbased Genetic Programming 14 pages Polymorphism and Genetic ProgrammingTina YuAbstract:Types have been introduced to Genetic Programming (GP) by researchers with different motivation. We present the concept of types in GP and introduce a typed GP system, PolyGP, that supports polymorphism through the use of three different kinds of type variable. We demonstrate the usefulness of this kind of polymorphism in GP by evolving two polymorphic programs (nth and map) using the system. Based on the analysis of a series of experimental results, we conclude that this implementation of polymorphism is effective in assisting GP evolutionary search to generate these two programs. PolyGP may enhance the applicability of GP to a new class of problems that are difficult for other polymorphic GP systems to solve. Keywords:Polymorphism, Strongly Typed GP, STGP, Multiobjective optimisation, Typed GP, Constraint handling, PolyGP 16 pages PostersProgrammable Smart Membranes: Using Genetic Programming to Evolve Scalable Distributed Controllers for a Novel SelfReconfigurable Modular Robotic ApplicationForrest H Bennett III  Brad Dolin  Eleanor G. RieffelAbstract:Selfreconfigurable modular robotics represents a new approach to robotic hardware, in which the "robot" is composed of many simple, identical interacting modules. We propose a novel application of modular robotics: the programmable smart membrane, a device capable of actively filtering objects based on numerous measurable attributes. Creating control software for modular robotic tasks like the smart membrane is one of the central challenges to realizing their potential advantages. We use genetic programming to evolve distributed control software for a 2dimensional smart membrane capable of distinguishing objects based on color. The evolved controllers exhibit scalability to a large number of modules and robustness to the initial configurations of the robotic filter and the particles. Keywords:modular robot, distributed control, smart membrane, selfreconfigurable, scalable, robust 12 pages A GP Artificial Ant for image processing: preliminary experiments with EASEAEnzo Bolis  Christian Zerbi  Pierre Collet  Jean Louchet  Evelyne LuttonAbstract:This paper describes how animatbased "food foraging" techniques may be applied to the design of lowlevel image processing algorithms. First, we show how we implemented the food foraging application using the EASEA software package. We then use this technique to evolve an animat and learn how to move inside images and detect highgradient lines with a minimum exploration time. The resulting animats do not use standard "scanning + filtering" techniques but develop other image exploration strategies close to contour tracking. Experimental results on grey level images are presented. Keywords:Image processing, Contour detection, EASEA, Animat 10 pages Feature Extraction for the kNearest Neighbour Classifier with Genetic ProgrammingMartijn C.J. BotAbstract:In pattern recognition the curse of dimensionality can be handled either by reducing the number of features, e.g. with decision trees or by extraction of new features. We propose a genetic programming (GP) framework for automatic extraction of features with the express aim of dimension reduction and the additional aim of improving accuracy of the knearest neighbour (kNN) classifier. We will show that our system is capable of reducing most datasets to one or two features while kNN accuracy improves or stays the same. Such a small number of features has the great advantage of allowing visual inspection of the dataset in a twodimensional plot. Since kNN is a nonlinear classification algorithm, we compare several linear fitness measures. We will show the a very simple one, the accuracy of the minimal distance to means (mdm) classifier outperforms all other fitness measures. We introduce a stopping criterion gleaned from numeric mathematics. New features are only added if the relative increase in training accuracy is more than a constant d, for the mdm classifier estimated to be 3.3 Keywords:Feature Extraction, Machine Learning 12 pages An Indirect BlockOriented Representation for Genetic ProgrammingEva Brucherseifer  Peter Bechtel  Stephan Freyer  Peter MarenbachAbstract:When Genetic Programming (GP) is applied to system identification or controller design different codings can be used for internal representation of the individuals. One common approach is a blockoriented representation where nodes of the tree structure directly correspond to blocks in a block diagram. In this paper we present an indirect blockoriented representation, which adopts some aspects of the way humans perform the modelling in order to increase the GP system's performance. A causality measure based on an edit distance is examined to compare the direct an the indirect representation. Finally, results from a real world application of the indirect blockoriented representation are presented. Keywords:Blockoriented representation, Biotechnology, Process modelling, Controller design, Causality 12 pages Raising the Dead; Extending Evolutionary Algorithms with a Casebased MemoryJeroen Eggermont  Tom Lenaerts  Sanna Poyhonen  Alexandre TermierAbstract:In dynamically changing environments, the performance of a standard evolutionary algorithm deteriorates. This is due to the fact that the population, which is considered to contain the history of the evolutionary process, does not contain enough information to allow the algorithm to react adequately to changes in the fitness landscape. Therefore, we added a simple, global casebased memory to the process to keep track of interesting historical events. Through the introduction of this memory and a storing and replacement scheme we were able to improve the reaction capabilities of an evolutionary algorithm with a periodically changing fitness function. Keywords:Dynamic Fitness, Global Memory 11 pages Layered Learning in Genetic Programming for a Cooperative Robot Soccer ProblemSteven M. Gustafson  William H. HsuAbstract:We present an alternative to standard genetic programming (GP) that applies layered learning techniques to decompose a problem. GP is applied to subproblems sequentially, where the population in the last generation of a subproblem is used as the initial population of the next subproblem. This method is applied to evolve agents to play keepaway soccer, a subproblem of robotic soccer that requires cooperation among multiple agents in a dynnamic environment. The layered learning paradigm allows GP to evolve better solutions faster than standard GP. Results show that the layered learning GP outperforms standard GP by evolving a lower fitness faster and an overall better fitness. Results indicate a wide area of future research with layered learning in GP. Keywords:Layered Learning, Hierarchical abstractions, Robot soccer, Robots, Multiagent systems 11 pages LinearTree GP and its comparison with other GP structuresWolfgang Kantschik  Wolfgang BanzhafAbstract:In recent years different genetic programming (GP) structures have emerged. Today, the basic forms of representation for genetic programs are tree, linear and graph structures. In this contribution we introduce a new kind of GP structure which we call lineartree. We describe the lineartreestructure, as well as crossover and mutation for this new GP structure in detail. We compare lineartree programs with linear and tree programs by analyzing their structure and results on different test problems. Keywords:Linear tree structure, GP representation, Crossover 11 pages Evolving HandEye Coordination for a Humanoid Robot with Machine Code Genetic ProgrammingW. B. Langdon  Peter NordinAbstract:We evolve, using AIMGP machine code genetic programming, Discipulus, an approximation of the inverse kinematics of a real robotics arm with many degrees of freedom. Elvis is a bipedal robot with humanlike geometry and motion capabilities  a humanoid, primarily controlled by evolutionary adaptive methods. The GP system produces a useful inverse kinematic mapping, from target 3D points (via pairs of stereo video images) to a vector of arm controller actuator set points. Keywords:Humanoid Robotics, Genetic Reasoning, Brain Building, Robotic Arm, Robots, Inverse Kinematics, Stereo Vision, Discipulus 12 pages Adaption of Operator Probabilities in Genetic ProgrammingJens Niehaus  Wolfgang BanzhafAbstract:In this work we tried to reduce the number of free parameters within Genetic Programming without reducing the quality of the results. We developed three new methods to adapt the probabilities, different genetic operators are applied with. Using two problems from the areas of symbolic regression and classification we showed that the results in these cases were better than randomly chosen parameter sets and could compete with parameter sets chosen with empirical knowledge. Keywords:Adaptation, Adaption, Structure Optimisation 12 pages Crossover in Grammatical Evolution: The Search ContinuesMichael O'Neill  Conor Ryan  Maarten Keijzer  Mike CattolicoAbstract:Grammatical Evolution is an evolutionary automatic programming algorithm that can produce code in any language, requiring as inputs a BNF grammar definition describing the output language, and the fitness function. The utility of crossover in GP systems has been hotly debated for some time, and this debate has also arisen with respect to Grammatical Evolution. This paper serves to continue an analysis of the crossover operator in Grammatical Evolution by looking at the result of turning off crossover, and by exchanging randomly generated blocks in a headless chickenlike crossover. Results show that crossover in Grammatical Evolution is essential on the problem domains examined. The mechanism of onepoint crossover in Grammatical Evolution is discussed, resulting in the discovery of some interesting properties that could yield an insight into the operator's success. Keywords:Grammatical Evolution, Crossover, GenotypePhenotype Mapping, Linear Genome, Grammar 12 pages Computational Complexity, Genetic Programming, and ImplicationsBart Rylander  Terry Soule  James FosteryAbstract:Recent theory work has shown that a Genetic Program (GP) used to produce programs may have output that is bounded above by the GP itself [l]. This paper presents proofs that show that 1) a program that is the output of a GP or any inductive process has complexity that can be bounded by the Kolmogorov complexity of the originating program; 2) this result does not hold if the random number generator used in the evolution is a true random source; and 3) an optimization problem being solved with a GP will have a complexity that can be bounded below by the growth rate of the minimum length problem representation used for the implementation. These results are then used to provide guidance for GP implementation. Keywords:Computational Complexity, Quantum Computing 13 pages Genetic Programming for Financial Time Series PredictionMassimo Santini  Andrea TettamanziAbstract:This paper describes an application of genetic programming to forecasting financial markets that allowed the authors to rank first in a competition organized within the CEC2000 on "Dow Jones Prediction". The approach is substantially driven by the rules of that competition, and is characterized by individuals being made up of multiple GP expressions and specific genetic operators. Keywords:Time Series prediction, Financial markets, Multiexpression individuals, Genetic operators, Crossover 10 pages Active Handwritten Character Recognition using Genetic ProgrammingA. Teredesai  J. Park  V. GovindarajuAbstract:This paper is intended to demonstrate the effective use of genetic programming in handwritten character recognition. When the resources utilized by the classifier increase incrementally and depend on the complexity of classification task, we term such a classifier as active. The design and implementation of active classifiers based on genetic programming principles becomes very simple and efficient. Genetic Programming has helped optimize handwritten character recognition problem in terms of feature set selection. We propose an implementation with dynamism in preprocessing and classification of handwritten digit images. This paradigm will supplement existing methods by providing better performance in terms of accuracy and processing time per image for classification. Different levels of informative detail can be present in image data and our proposed paradigm helps highlight these information rich zones. We compare our performance with passive and active handwritten digit classification schemes that are based on other pattern recognition techniques. Keywords:Pattern Recognition, Active Character Recognition, Digit Recognition, Handwritten digit classification 9 pages 

Web site designed and maintained by Chris Osborne at EvoNet. 