List of Publication Titles in Genetic Programming and Computational Development

Wolfgang Banzhaf


Older papers (from 1993 back) are represented by abstracts only and are available upon email request
We give titles and links. If you click the underlined words in a title you will see an abstract and source information of the paper. If you click the corresponding filename you will retrieve a copy.
Back to Publications Overview


2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

1995

1994

1993


List of Abstracts and Sources

TITLE: Evolution on Neutral Networks in Genetic Programming

AUTHORS: W. Banzhaf and A. Leier

SOURCE: Genetic Programming - Theory and Applications III
T. Yu, R. Riolo and B. Worzel (Eds.), Kluwer Academic, Boston, MA, 2006, 207 - 221

ABSTRACT: We examine the behavior of an evolutionary search on neutral networks in a simple linear GP system of a Boolean function space problem. To this end we draw parallels between notions in RNA-folding problems and in Genetic Programming, observe parameters of neutral networks and discuss the population dynamics via the occupation probability of network nodes in runs on their way to the optimal solution.

FILENAME: GPTP3.pdf (526 kB)




TITLE: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005)

EDITORS: Beyer, H.-G.; O'Reilly, U.-M.; Arnold, D.; Banzhaf, W.; Blum, C.; Bonabeau, E.; Cantu-Paz, E.; Dasgupta, D.; Deb, K.; Foster, J.; deJong, E.; Lipson, H.; Llora, S.; Mancoridis, M.; Pelikan, M.; Raidl, G.; Soule, T.; Tyrrell, A.; Watson, J.-P.; Zitzler, E.

SOURCE: ACM Press, New York, 2005, Volume 1: 1112 pages and Volume 2: 1132 pages

ABSTRACT: These two volumes contain the Proceedings of GECCO 2005.


TITLE: Comparison of Selection Strategies for Evolutionary Quantum Circuit Design

AUTHORS: Andre Leier and Wolfgang Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference (GECCO-04), Seattle, USA, 26-30 June 2004, K. Deb, R. Poli, W. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. Foster, M. Harman, O. Holland, P.L. Lanzi, L. Spector, A. Tettamanzi, D. Thierens, A. Tyrrell (Eds.), 2004, pp. 557 --- 568

ABSTRACT: Evolution of quantum circuits faces two major: Complex and huge search spaces and the high costs of simulating quantum circuits on conventional computers.In this paper we analyze different selection strategies, which are applied to the Deutsch-Josza problem and the 1-SAT problem using our GP system. Furthermore, we show the effects of adding randomnes to the selection mechanism of a (1,10) selection strategy. In can be demonstrated that this boosts the evolution of quantum algorithms on particular problems.

FILENAME: lb04_final.pdf (200 kB)




TITLE: Dynamic Subset Selection Based on a Fitness Case Topology

AUTHORS: Christian Lasarczyk, Peter Dittrich and Wolfgang Banzhaf

SOURCE: Evolutionary Computation, 12 (2004) pp. 223 - 242

ABSTRACT: A large training set of fitness cases can critically slow down genetic programming, if no appropriate subset selection method is applied. Such a method allows to evaluate an individual on a smaller subset of fitness cases. In this paper we suggest a new subset selection method that takes the problem structure into account, while being problem independent at the same time. In order to achieve this, information about the problem structure is acquired during evolutionary search by creating a topology (relationship) on the set of fitness cases. The topology is induced by individuals of the evolving population, through increasing the strength of the relation between two fitness cases, if an individual of the population is able to solve both of them. Our new topology-based subset selection method chooses a subset, such that fitness cases in this subset are as little as possible related with respect to the induced topology. We compare topology-based selection of fitness cases with dynamic subset selection and stochastic subset sampling on four different problems. On average, runs with topology-based selection show faster progress than the others.

FILENAME: topology.pdf (2047 kB)




TITLE: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004)

EDITORS: Deb, K.; Poli, R.; Banzhaf, W.; Beyer, H.-G.; Burke, E.; Darwen, P.; Dasgupta, D.; Floreano, D.; Foster, J.; Harman, M.; Holland, O.; Lanzi, P.L.; Spector, L.; Tettamanzi, A.; Thierens, D.; Tyrrell, A.

SOURCE: Springer, Berlin, 2004, LNCS Volume 3102 and Volume 3103




ABSTRACT: These volumes contain the Proceedings of GECCO 2004, held in Seattle, WA, USA June 26-30, 2004.


TITLE: The Challenge of Complexity

AUTHORS: Wolfgang Banzhaf and Julian Miller

SOURCE: Frontiers in Evolutionary Computation
A. Menon (Ed.), Kluwer Academic, Boston, MA 2004, pp. 243 - 260

ABSTRACT: In this chapter we discuss the challenge provided by the problem of evolving large amounts of computer code via Genetic Programming. We argue that the problem is analogous to what Nature had to face when moving to multi-cellular life. We propose to look at developmental processes and there mechanisms to come up with solutions for this ''challenge of complexity'' in Genetic Programming.

FILENAME: challenge_rev.pdf (235 kB)




TITLE: Artificial Regulatory Networks and Genetic Programming

AUTHORS: Wolfgang Banzhaf

SOURCE: Genetic Programming - Theory and Applications
R. Riolo, B. Worzel (Eds.), Kluwer Academic, Boston, MA, 2003, 43 - 61

ABSTRACT: An artificial regulatory network able to reproduce a number of phenomena found in natural genetic regulatory networks (such as heterochrony, evolution, stability and variety of network behavior) is proposed. The connection to a new genetic representation for Genetic Programming is outlined.

FILENAME: toy_world3.pdf (1,542 kB)




TITLE: Evolving the Program for a Cell: From French Flags to Boolean Circuits

AUTHORS: Julian Miller and Wolfgang Banzhaf

SOURCE: On Growth, Form and Computers, P. Bentley und S. Kumar (Eds.), Academic Press, New York, 2003, 278 - 302

FROM THE INTRODUCION ...:
The development of an entire organism from a single cell is one of the most profound and awe inspiring phenomena in the whole of the natural world. The complexity of living systems itself dwarfs anything that man has produced. This is all the more the case for the processes that lead to these intricate systems. In each phase of the development of a multi-cellular being, this living system has to survive, whether stand-alone or supported by various structures and processes provided by other living systems. Organisms construct themselves, out of humble single-celled beginnings, riding waves of interaction between the information residing in their genomes - inherited from the evolutionary past of their species via their progenitors - and the resources of their environment.

FILENAME: chapter_finalrevision.pdf (1,652 kB)




TITLE: You can judge a book by its cover - Evolution of gait controllers based on program code analysis

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proceedings of the Sixth International Conference on Climbing and Walking Robots, CLAWAR-2003, G. Muscato, D. Longo (Eds.), Professional Engineering Publ., Bury St. Edmunds, U.K., 2003, 205 - 212

ABSTRACT: This paper introduces a Genetic Programming (GP) approach to automatically evolve control programs for walking robots. In contrast to earlier work, in which the evolution of gait control programs depended on the direct measurement of the quality of movements of simulated robots, in this paper a new method is presented that circumvents time consuming evaluations of control programs through the probabilistic evolutionary process.

FILENAME: ZieglerBanzhaf.pdf (234 kB)




TITLE: Evolving Hogg's Quantum Algorithm Using Linear-Tree GP

AUTHORS: Andre Leier and Wolfgang Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference (GECCO-03), Chicago, USA, 12-16 Juli 2003
E. Cantu-Paz, J. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harmann, J. Wegener, D. Dasgupta, M.A. Potter, A.C. Schultz, K. Dowsland, N. Jonoska, J.F. Miller (Eds.), Springer, LNCS 2723, Berlin, 2003, pp. 390 - 400

ABSTRACT: Intermediate measurements in quantum circuits compare to conditional branchings in programming languages. Due to this, quantum circuits have a natural linear-tree structure. In this paper a Genetic Programming system based on linear-tree genome structures developed for the purpose of automatic quantum circuit design is introduced. It was applied to instances of the 1-SAT problem, resulting in evidently and ``visibly'' scalable quantum algorithms, which correspond to Hogg's quantum algorithm.

FILENAME: hogg.pdf (222 kB)




TITLE: Decreasing the Number of Evaluations in Evolutionary Algorithms by using a Meta-Model of the Fitness Function

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proc. 6th Europ. Conference on Genetic Programming, Exeter, England, April 2003
C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa (Eds.) Springer, LNCS 2610, Berlin, 2003, pp. 264 - 275

ABSTRACT: In this paper a method is presented that decreases the necessary number of evaluations in Evolutionary Algorithms. A classifier with confidence information is evolved to replace time consuming evaluations during tournament selection. Experimental analysis of a mathematical example and the application of the method to the problem of evolving walking patterns for quadruped robots show the potential of the presented approach.

FILENAME: lncs_decrease.pdf (642 kB)




TITLE: More on Computational Effort Statistics for Genetic Programming

AUTHORS: Jens Niehaus and Wolfgang Banzhaf

SOURCE: Proc. 6th Europ. Conference on Genetic Programming, Exeter, England, April 2003
C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa (Eds.) Springer, LNCS 2610, Berlin, pp. 164 - 172

ABSTRACT: In this contribution we take a look at the computational effort statistics as described by Koza. We transfer the notion from generational genetic programming to tournament-selection (steady-state) GP and show why, in both cases, the measured value of the effort often differs from its theoretical counterpart. It is discussed how systematic estimation errors are introduced by a low number of experiments. Two reasons examined are the number of unsuccessful experiments and the variation in the number of fitness evaluations necessary to find a solution among the successful experiments.

FILENAME: lncs_ce.pdf (168 kB)




TITLE: Neutral Variations Cause Bloat in Linear GP

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: Proc. 6th Europ. Conference on Genetic Programming, Exeter, England, April 2003
C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa (Eds.)\\ Springer, LNCS 2610, Berlin, pp. 286 - 296

ABSTRACT: In this contribution we investigate the influence of different variation effects on the growth of code. A mutation-based variant of linear GP is applied that operates with minimum structural step sizes. % on the imperative program structure. Results show that neutral variations are a direct cause for (and not only a result of) the emergence and the growth of intron code. The influence of non-neutral variations % on code growth has been found to be considerably smaller. Neutral variations turned out to be beneficial by solving two classification problems more successfully.

FILENAME: lncs_neutral.pdf (184 kB)




TITLE: Genetic Programming and its application in Machining Technology

AUTHORS: Wolfgang Banzhaf, Markus Brameier, Martin Stautner and Klaus Weinert

SOURCE: in: H.-P. Schwefel, I. Wegener und K. Weinert (Eds.)
Advances in Computational Intelligence, Springer, Berlin, 2002, pp. 194 - 241

ABSTRACT: Geetic Programming (GP) dontes a varioant of evolutionary algorithms that breeds solutions to problems in the form of computer programs. In recent years, GP has become incresingly important for real-world applications, including engineering tasks in particular. This contribution integrates both further development of the GP paradigm and its applications to challenging problems in machining technology. Different variants of program representations are investigated.

FILENAME: CI-book-chapter.pdf (4004 kB)




TITLE: On the Scalability of Social Order

AUTHORS: Peter Dittrich, Thomas Kron and Wolfgang Banzhaf

SOURCE: (Electronic) Journal of Artificial Societies and Social Simulation, Vol. 6 (2003) issue 1

ABSTRACT: We investigate an algorithmic model based first of all on Luhmann's description of how social order may originate [N. Luhmann, Soziale Systeme, Frankfurt/Main, Suhrkamp, 1984, pp. 148-179]. In a basic 'dyadic' setting, two agents build up expectations during their interaction process. First, we include only two factors into the decision process of an agent, namely, its expectation about the future and its expectation about the other agent's expectation (called 'expectation-expectation' by Luhmann). Simulation experiments of the model reveal that 'social' order appears in the dyadic situation for a wide range of parameter settings, in accordance with Luhmann. If we move from the dyadic situation of two agents to a population of many interacting agents, we observe that the order usually disappears. In our simulation experiments, scalable order appears only for very specific cases, namely, if agents generate expectation- expectations based on the activity of other agents and if there is a mechanism of 'information proliferation', in our case created by observation of others. In a final demonstration we show that our model allows the transition from a more actor oriented perspective of social interaction to a systems-level perspective. This is achieved by deriving an 'activity system' from the microscopic interactions of the agents. Activity systems allow to describe situations (states) on a macroscopic level independent from the underlying population of agents. They also allow to draw conclusions on the scalability of social order.

FILENAME: http://jasss.soc.surrey.ac.uk/6/1/3.html




TITLE: Automatic evolution of control programs for a small humanoid walking robot

AUTHORS: Jens Ziegler, Jan Barnholt, Jens Busch and Wolfgang Banzhaf

SOURCE: Proceedings of the Fifth International Conference on Climbing and Walking Robots, CLAWAR-2002
P. Bidaud and F. Ben Amar, (Eds.), Professional Engineering Publishing, 2002, pp. 109 - 116

ABSTRACT:

FILENAME: (n kB)




TITLE: Evolving chess playing programs

AUTHORS: Roderich Gross, Keno Albrecht, Wolfgang Kantschik and Wolfgang Banzhaf

SOURCE: Proc. of the Genetic and Evolutionary Computation Conference (GECCO-02), New York, USA, 9-13 Juli 2002
W.B. Langdon E. Cantu-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M.A. Potter, A.C. Schultz, J.F. Miller, E. Burke, N. Jonoska (Eds.), Morgan Kaufmann, San Francisco, CA, 2002, 740 - 747

ABSTRACT: This contribution introduces a hybrid GP/ES system for the evolution of chess playing computer programs. We discuss the basic system and examine its performance in comparison to pre-existing algorithms of the type alpha-beta and its improved variants. We can show that evolution is able to outperform these algorithms both in terms of efficiency and strength.

FILENAME: evochess_final.pdf (185 kB)




TITLE: Some considerations on the reason for bloat

AUTHORS: Wolfgang Banzhaf and William B. Langdon

SOURCE: Genetic Programming and Evolvable Machines, Vol. 3 (2002) pp. 81-91

ABSTRACT: A representation-less model for genetic programming is presented. The model is intended to examine the mechanisms that lead to bloat in genetic programming (GP). We discuss two hypotheses (fitness causes bloat and neutral code is protective) and perform simulations to examine the predictions deduced from these hypotheses. Our observation is that predictions from both hypotheses are realized in the simulated model.

FILENAME: genp_bloat.pdf (177 kB)




TITLE: Explicit Control of Diversity and Effective Variation Distance in Linear Genetic Programming

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: Proceedings of the 4th European Conference on Genetic Programming, EuroGP 2002, Kinsale, Ireland, E. Lutton, J. Foster, J. Miller, C. Ryan and A. Tettamanzi (Eds.), Springer LNCS 2278, Berlin, 2002, pp. 38-50

ABSTRACT: We have investigated structural distance metrics for linear genetic programs. Causal connections between changes of the genotype and changes of the phenotype form a necessary condition for analyzing structural differences between genetic programs and for the two objectives of this paper: (i) The distance information between individuals is used to control structural diversity of population individuals actively by a two-level tournament selection. (ii) Variation distance of effective code is controlled for different genetic operators - including a mutation operator that works closely with the applied distance measure. Numerous experiments have been performed for three benchmark problems.

FILENAME: eurogp02_dist.pdf (190 kB)




TITLE: Linear-Graph GP -- A new GP Structure

AUTHORS: Wolfgang Kantschik and Wolfgang Banzhaf

SOURCE: Proceedings of the 4th European Conference on Genetic Programming, EuroGP 2002, Kinsale, Ireland, E. Lutton, J. Foster, J. Miller, C. Ryan and A. Tettamanzi (Eds.), Springer LNCS 2278, Berlin, 2002, pp. 83-92

ABSTRACT: 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 linear-graph, it is a further development of the linear-Tree structure. We describe the linear-graph structure, as well as crossover and mutation for this new GP structure in detail. We compare linear-graph programs with linear and tree programs by analyzing their structure and results on different test problems.

FILENAME: eurogp02_lingraph.pdf (256 kB)




TITLE: Automatic Generation of Control Programs for Walking Robots Using Genetic Programming

AUTHORS: J. Busch, J. Ziegler, W. Banzhaf, A. Ross, D. Sawitzki and C. Aue

SOURCE: Proceedings of the 4th European Conference on Genetic Programming, EuroGP 2002, Kinsale, Ireland, E. Lutton, J. Foster, J. Miller, C. Ryan and A. Tettamanzi (Eds.), Springer LNCS 2278, Berlin, 2002, pp. 259-268

ABSTRACT: We present the system SIGEL that combines the simulation and visualization of robots with a Genetic Programming system for the automated evolution of walking. It is designed to automatically generate control programs for arbitrary robots without depending on detailed analytical information of the robots' kinematic structure. Different fitness functions as well as a variety of parameters allow the easy and interactive configuration and adaptation of the evolution process and the simulations.

FILENAME: eurogp02_sigel.pdf (205 kB)




TITLE: Evolving Teams of Predictors with Linear Genetic Programming

AUTHORS: Markus Brameier and Wolfgang Banzhaf

SOURCE: Genetic Programming and Evolvable Machines, Vol. 2 (2001) pp. 381-407

ABSTRACT: This paper applies the evolution of GP teams to different classification and regression problems and compares different methods for combining the outputs of the team programs. These include hybrid approaches where (1) a neural network is used to optimize the weights of programs in a team for a common decision and (2) a real-numbered vector (the representation of evolution strategies) of weights is evolved with each team in parallel. The cooperative team approach results in an improved training and generalization performance compared to the standard GP method. The higher computational overhead of team evolution is counteracted by using a fast variant of linear GP.

FILENAME: teams.pdf (203 kB)




TITLE: Evolution of Robot Leg Movements in a Physical Simulation

AUTHORS: Jens Ziegler and Wolfgang Banzhaf

SOURCE: Proceedings of the Fourth International Conference on Climbing and Walking Robots, CLAWAR , 2001, K. Berns and R. Dillmann, (Eds.), Professional Engineering Publishing

ABSTRACT: This paper introduces a Genetic Programming approach to creating patterns of movements for legs of walking robots. It uses a physics-based simulation system to evaluate the fitness of movement patterns, which are emerging from the interpret ation of the individuals of the population. Different methods are shown that increase the speed of the evolution by several orders of magnitude.

FILENAME: ZBCLAWAR01.pdf (283 kB)




TITLE: Constructing a Small Humanoid Walking Robot as a Platform for the Genetic Evolution of Walking

AUTHORS: Jens Ziegler, Krister Wolff, Peter Nordin and Wolfgang Banzhaf

SOURCE: Autonomous Minirobots for Research and Edutainment, AMiRE2001, Proceedings of the 5th International Heinz Nixdorf Symposium , 2001, U. Rückert (Ed.),HNI-Verlagsschriftenreihe, Vol. 97, ISBN 3-935433-06-9, Paderborn, 2001

ABSTRACT: Walking robots from the next challenge in the field of autonomous robots. This paper describes the construction of a fully autonomous humanoid walking robot as a platform for machine learning algorithms like, e.g., Genetic Programming. Built from off-the-shelf components, the described humanoids are cheap, robust and easy to program, which make them an ideal test platform for several experimental approaches in machine learning, sensor fusion or adaptive control. In addition to these research related topics, the walking robots are an ideal tool for educational purposes.

FILENAME: ZWNB_AMIRE2001.pdf (344 kB)




TITLE: AIM-GP and Parallelism

AUTHORS: P. Nordin, M. Brameier, F. Hoffmann, F. Francone, and W. Banzhaf

SOURCE: Proceedings of Congress on Evolutionary Computation, Washington, 1999, IEEE Press, Piscataway, NJ, pp. 1059 -- 1066

EDITORS: NN

ABSTRACT: Many machine learning tasks are just too hard to be solved with a single processor machine, no matter how efficient algorithms we use and how fast our hardware is. Luckily genetic programming is well suited for parallelization compared to standard serial algorithms. This paper describes the first parallel implementation of an AIM-GP system creating the potential for an extremely fast system. The system is tested on three problems and several variants of demes and migration are evaluated. Most of the results are applicable to both linear and tree based systems.

FILENAME: cec_parallel.pdf (131 kB)




TITLE: Linear-Tree GP and its comparison with other GP structures

AUTHORS: W. Kantschik and W. Banzhaf

SOURCE: Proceedings of 4th EuroGP Conference, Como 2001, Springer, LNCS 2038, Berlin, 2001, pp. 302 -- 312

EDITORS: J. Miller, M. Tomassini, P.-L. Lanzi, C. Ryan, A. Tettamanzi and W. B. Langdon

ABSTRACT: 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 linear-tree. We describe the linear-tree-structure, as well as crossover and mutation for this new GP structure in detail. We compare linear-tree programs with linear and tree programs by analyzing their structure and results on different test problems.

FILENAME: eurogp01-1.pdf (222 kB) /H4>


TITLE: Adaption of Operator Probabilities in Genetic Programming

AUTHORS: J. Niehaus und W. Banzhaf

SOURCE: Proceedings of 4th EuroGP Conference, Como 2001, Springer, LNCS 2038, Berlin, 2001, pp. 325 -- 336

EDITORS: J. Miller, M. Tomassini, P.-L. Lanzi, C. Ryan, A. Tettamanzi and W. B. Langdon

ABSTRACT: 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.

FILENAME: eurogp01-2.pdf (240 kB)




TITLE: Genetic Programming Bloat without Semantics

AUTHORS: W. B. Langdon and W. Banzhaf

SOURCE: Proceedings of 6th International Conference on Parallel Problem Solving from Nature - PPSN VI, Paris 2000, Springer, LNCS 1917, Berlin, 2000, pp. 201 -- 210

EDITORS: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo and H.-P. Schwefel

ABSTRACT: To investigate the fundamental causes of bloat, six artificial random binary tree search spaces are presented. Fitness is given by program syntax (the genetic programming genotype). GP populations are evolved on both random problems and problems with ``building blocks''. These are compared to problems with explicit ineffective code (introns, junk code, inviable code). Our results suggest the entropy random walk explanation of bloat remains viable. The hard building block problem might be used in further studies, e.g. of standard subtree crossover.

FILENAME: ppsn00.pdf (242 kB) /H4>


TITLE: Artificial Intelligence: Genetic Programming

AUTHORS: Wolfgang Banzhaf

SOURCE: published as part of the Elsevier Encyclopedia of the Social and Behavioral Sciences, 2001

ABSTRACT: Genetic Programming is a new method to generate computer programs. It was gleaned from the natural model of biological evolution. Programs are ''bred'' through continuous improvement of an initially random population of programs. Improvements are made possible by variation of programs and selection according to prespecified criteria for judging the quality of a solution. In this contribution I shall discuss the origins of Genetic Programming, both in evolutionary thinking and in Artificial Intelligence (Machine Learning in particular). Next is a discussion of the state of the art of Genetic Programming, including the major achievements of the method in recent years. This leads to an overview of the application areas where GP is most frequently used at present. Among these areas is robotics and the control of behavior, both of real and virtual agents. The article will conclude with a section on the use of Genetic Programming for simulation in the social sciences.

FILENAME: ency.pdf (108 kB)




TITLE: The artificial evolution of computer code (essay, published together with other essays on Genetic Programming)

AUTHORS: Wolfgang Banzhaf, John Koza, Conor Ryan, Lee Spector, Christian Jacob, Haym Hirsch

SOURCE: IEEE Intelligent Systems and their Applications, May/June 2000, pp. 74 - 84

ABSTRACT: This is a collection of essays which deal with Genetic Programming. The intended audience is general AI people and engineers.

FILENAME: ieee_intelligentsystems.pdf (138 kB)




TITLE: Genetic Programming --- Proceedings Third European Conference, EuroGP'2000, Edinburgh, April 2000

EDITORS: Riccardo Poli, Wolfgang Banzhaf, Bill Langdon, Julian Miller, Peter Nordin and Terence C. Fogarty

SOURCE: Lecture Notes in Computer Science. Eds.: G. Goos, J. Hartmanis, J. van Leeuwen. Vol. 1802 2000. 232 pp. Softcover ISBN 3-540-67339-5

ABSTRACT: This book constitutes the refereed proceedings of the Third European Conference on Genetic Programming, EuroGP 2000, held in Scotland, UK, in April 2000. The 14 revised full papers presented together with 13 short papers were carefully reviewed and selected from a total of 39 submissions. All relevant aspects of genetic programming are addressed, ranging from theoretical and foundational issues to applications in a variety of fields such as automatic design, pattern recognition, robotic control, music and image processing, and symbolic regression.  

You can buy this book immediately by clicking on the title.




TITLE: A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining

AUTHORS: M. Brameier and W. Banzhaf

SOURCE: IEEE Transactions on Evolutionary Computation 5 (2001), pp. 17 -- 26

ABSTRACT: We apply linear genetic programming to several diagnosis problems in medicine. An efficient algorithm is presented that eliminates intron code in linear genetic programs. This results in a significant speedup which is especially interesting when operating with complex datasets as they are occuring in real-world applications like medicine. We compare our results to those obtained with neural networks and argue that genetic programming is able to show similar performance in classification and generalization even within a relatively small number of generations. 

FILENAME: ieee_taec.pdf (213 kB)




TITLE: The Evolution of Genetic Code in Genetic Programming

AUTHORS: R. Keller and W. Banzhaf

SOURCE: Proceedings of first GECCO conference, Orlando 1999, Morgan Kaufmann, San Francisco, 1999, pp. 1077 -- 1082

EDITORS: W. Banzhaf, J. Daida, A. Eiben, M. Garzon, V. Honavar, M. Jakiela and R. Smith

ABSTRACT: In most Genetic Programming (GP) approaches, the space of genotypes, that is the search space, is identical to the space of phenotypes, that is the solution space. Developmental approaches, like Developmental Genetic Programming (DGP), distinguish between genotypes and phenotypes and use a genotype-phenotype mapping prior to fitness evaluation of a phenotype. To perform this mapping, DGP uses a problem-specific manually designed genetic code, that is a mapping from genotype components to phenotype components. The employed genetic code is critical for the performance of the underlying search process. Here, the evolution of genetic code is introduced as a novel approach for enhancing the search process. It is hypothesized that code evolution improves the performance of developmental approaches by enabling them to beneficially adapt the fitness landscape during search. As the first step of investigation, this article empirically shows the operativeness of code evolution.

FILENAME: t.pdf (88 kB)




TITLE: Efficient Evolution of Machine Code for CISC Architectures using Blocks and Homologous Crossover

AUTHORS: P. Nordin, W. Banzhaf and F. Francone

SOURCE: Advances in Genetic Programming III, MIT Press, Cambridge, MA, 1999, pp. 275 -- 299

EDITORS: L. Spector, W. Langdon, U. O'Reilly and P. Angeline

ABSTRACT: This chapter describes recent advances in genetic programming of machine code. Evolutionary program induction using binary machine code is the fastest known Genetic Programming method. It is, in addition, the most well studied Genetic Programming system that uses a linear genome. Evolutionary program induction using binary machine code was originally referred to as {\em Compiling Genetic Programming System} (CGPS). For clarity, the name was changed in early 1998 to {\em Automatic Induction of Machine Code---Genetic Programming} (AIM-GP). AIM-GP stores evolved programs as linear strings of native binary machine code, which are directly executed by the processor. The absence of an interpreter and complex memory handling increases the speed of AIM-GP by about two orders of magnitude. AIM-GP has so far been applied to processors with a fixed instruction length (RISC) using integer and floating-point arithmetic. We also describe several recent advances in the AIM-GP technology. Such advances include enabling the induction of code for CISC processors such as the INTEL x86 as well as JAVA and many embedded processors. The new techniques also make AIM-GP more portable in general and simplify the adaptation to any processor architecture. Other additions include the use of floating point instructions, control flow instructions, ADFs and new genetic operators e.g. aligned homologous crossover. This chapter also discusses the benefits and drawbacks of register machine GP versus tree-based GP. This chapter is directed towards the practitioner, who wants to extend AIM-GP to new architectures and application domains.

FILENAME: aigp3_v6.pdf (169 kB)




TITLE: CAD Surface Reconstruction from Digitized 3D Point Data with Genetic Programming

AUTHORS: R. Keller, W. Banzhaf, J. Mehnen, and K. Weinert

SOURCE: Advances in Genetic Programming III, MIT Press, Cambridge, MA, 1999, pp. 41 -- 65

EDITORS: L. Spector, W. Langdon, U. O'Reilly and P. Angeline

ABSTRACT: Surface reconstruction is a hard key problem in the industrial core domain of computer-aided design (CAD) applications. A workpiece must be represented in some standard CAD object description format such that its representation can be efficiently used in a CAD process like redesign. To that end, a digitizing process represents the object surface as a weakly-structured discrete and digitized set of 3D points. Surface reconstruction attempts to transform this representation into an efficient CAD representation. Certain classic approaches produce inefficient reconstructions of surface areas that do not correspond to construction logic. Here, a new reconstruction principle along with empiric results is presented which yields logical and efficient representations. This principle is implemented as a Genetic-Programming/Evolution-Strategy-based software system.

FILENAME: Surreal.pdf (248 kB)




TITLE: Speech Sound Discrimination With Genetic Programming

AUTHORS: Markus Conrads, Peter Nordin and Wolfgang Banzhaf

SOURCE: Proc. 1st European Workshop on Genetic Programming, Lecture Notes in Computer Science, LNCS, Vol. 1391, Springer, Berlin, 1998, pp. 113 -- 129

EDITORS: W. Banzhaf, R. Poli, M. Schoenauer and T. Fogarty

ABSTRACT: The question that we investigate in this paper is, whether it is possible for Genetic Programming to extract certain regularities from raw time series data of human speech. We examine whether a genetic programming algorithm can find programs that are able to discriminate certain spoken vowels and consonants. We present evidence that this can indeed be achieved with a surprisingly simple approach that does not need preprocessing. The data we have collected on the system's behavior show that even speaker-independent discrimination is possible with GP. 

FILENAME: evogp.pdf (187 kB)




TITLE: Learning to Move a Robot with Random Morphology

AUTHORS: Peter Dittrich, Andreas Buergel and Wolfgang Banzhaf

SOURCE: Proc. 1st European Workshop on Evolutionary Robotics, Lecture Notes in Computer Science, LNCS, Vol. 1468, Springer, Berlin, 1998, 165 - 178

EDITORS: P. Husbands and J.-A. Meyer

ABSTRACT: Complex robots inspired by biological systems usually consist of many dependent actuators and are difficult to control. If no model is available automatic learning and adaptation methods have to be applied. The aim of this contribution is twofold: (1) To present an easy to maintain and cheap test platform, which fulfils the requirements of a complex control problem. (2) To discuss the application of Genetic Programming for evolution of control programs in real time. An extensive number of experiments with two real robots has been carried out. 

FILENAME: evorobot_final.pdf (285 kB)




TITLE: Genetic Programming --- Proceedings First European Workshop, EuroGP'98, Paris, France, April 1998

EDITORS: Wolfgang Banzhaf, Riccardo Poli, Marc Schoenauer and Terence C. Fogarty

SOURCE: Lecture Notes in Computer Science. Eds.: G. Goos, J. Hartmanis, J. van Leeuwen. Vol. 1391 1998. 232 pp. Softcover ISBN 3-540-64360-5

ABSTRACT: This volume comprises 18 papers from the first workshop on Genetic Programming held in Europe. 

You can buy this book immediately by clicking on the title.

FIND OUT MORE? CLICK HERE!




TITLE: Evolution of a World Model for a Miniature Robot using Genetic Programming

AUTHORS: Peter Nordin, Wolfgang Banzhaf and Markus Brameier

SOURCE: Robotics and Autonomous Systems, 25 (1998) pp. 105 - 116

ABSTRACT: We have used an automatic programming method called Genetic Programming (GP) for control of a miniature robot. Our earlier work on real-time learning suffered from the drawback of the learning time being limited by the response dynamics of the robot's environment. In order to overcome this problem we have devised a new technique which allows learning from past experiences that are stored in memory. The new method shows its advantage when perfect behavior emerges in experiments quickly and reliably. It is tested on two control tasks, obstacle avoiding and wall following behavior, both in simulation and on the real robot platform Khepera. 

FILENAME: robotics_and_autonomous.pdf (916 kB)




TITLE: Introns in Nature and in Simulated Structure Evolution

AUTHORS: Peter Nordin, Wolfgang Banzhaf and Frank D. Francone

SOURCE: Biocomputing and Emergent Computation, Proc. of BCEC97 Skovde, Sweden, September 1-2, 1997 , D. Lundh, B. Olsson and A. Narayanan (Eds.) World Scientific, Singapore, 1997,  22 - 35

ABSTRACT: In this study we measure the compression of information in a simulated evolutionary system. We do the investigation taking introns in the genome into account. We mainly investigate evolution of linear computer code but also present results from evolution of three-structures as well as messy-genetic algorithms. The size of solutions is an important property of any system trying to learn or adapt to its environment. The results show significant compression or constant size of exons during evolution---in contrast to the rapid growth of overall size. Our conclusion is that an inbuild pressure towards low-complexity solutions are measurable in several simulated evolutionary systems which may account for the robust adaption showed by these systems. 

FILENAME: skovde_final.pdf (249 kB)




TITLE: Genetic Programming - An Introduction On the automatic evolution of computer programs and its application

AUTHORS: Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, Frank D. Francone

PUBLISHER: dpunkt, Heidelberg and Morgan Kaufmann, San Francisco

For orders in Germany, Austria, Switzerland: dpunkt.verlag
For orders in Japanese: SciTech Press
For orders everywhere else: Click above.

ABSTRACT: Genetic Programming (GP) has recently emerged as an important paradigm for automatic generation of computer programs. GP combines biological metaphors drawn from evolution with computer science techniques in order to generate algorithms and programs automatically. The authors have been working in this field from the outset. They provide a vivid and detailed introduction to this rapidly growing area of evolutionary computation. History, biological motivation, theoretical and practical foundations, state-of-the-art techniques and real-world applications are presented along with exercises, a glossary and references to up-to-date free GP internet sites and related literature. The book is intended to serve as a textbook for the computer science student and as a reference book for the software engineer (software professional, professional software developer). 





TITLE: Real Time Control of a Khepera Robot using Genetic Programming

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Cybernetics and Control, Vol. 26 (3) 1997 pp. 533 --- 561

ABSTRACT: A computer language is a very general form of representing and specifying an autonomous agent's behavior. The task of planning feasible actions could then simply be reduced to an instance of automatic programming. We have evaluated the use of an evolutionary technique for automatic programming called Genetic Programming (GP) to directly control a miniature robot. To our knowledge, this is the first attempt to control a real robot with a GP based learning method. Two schemes are presented. The objective of the GP system in our first approach is to evolve real-time obstacle avoiding behavior. This technique enables real-time learning with a real robot using genetic programming. It has, however, the drawback that the learning time is limited by the response dynamics of the environment. To overcome this problems we have devised a second method, learning from past experiences which are stored in memory. This new system allows a speed-up of the algorithm by a factor of more than 2000. Obstacle avoiding behavior emerges much faster, approximately 40 times as fast, allowing learning of this task in 1.5 minutes. This learning time is several orders of magnitudes faster then comparable experiments with other control architectures. Furthermore, the GP algorithm is very compact and can be ported to the micro-controller of the autonomous mobile miniature robot. 

FILENAME: robot12.pdf (269 kB)




TITLE: Generating Adaptive Behavior for a Real Robot using Function Regression within Genetic Programming

AUTHORS:Wolfgang Banzhaf, Peter Nordin, Markus Olmer

SOURCE: 2nd International Conference on Genetic Programming, Stanford, 1997, J. Koza, K. Deb, M. Dorigo, D. Fogel. M. Garzon, H. Iba, R. Riolo (Eds), Morgan Kaufmann Publisher, San Francisco, 1997, 35 -- 43

ABSTRACT: We discuss the generation of adaptive behavior for an autonomous robot within the framework of a special kind of function regression used in compiling Genetic Programming (GP). The control strategy for the robot is derived, using an evolutionary algorithm, from a continuous improvement of machine language programs which are varied and selected against each other. We give an overview of our recent work on several fundamental behaviors like obstacle avoidance and object following adapted from programs that were originally random sequences of commands. It is argued that the method is generally applicable where there is a need for quick adaptation within real-time problem domains. 

FILENAME: robot_over.pdf (190 kB)




TITLE: Genetic Reasoning --- Evolving Proofs with Genetic Search

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: 2nd International Conference on Genetic Programming, Stanford, 1997, J. Koza, K. Deb, M. Dorigo, D. Fogel. M. Garzon, H. Iba, R. Riolo (Eds), Morgan Kaufmann Publisher, San Francisco, 1997, 255 -- 260

ABSTRACT: Most automated reasoning systems relies on human knowledge or heuristics to guide the reasoning or search for proofs. We have evaluated the use of a powerful general search algorithm to search in the space of mathematical proofs. In our approach automated reasoning is seen as an instance of automated programming where the proof is seen as a program (of functions corresponding to rules of inference) that transforms a statement into an axiom. Genetic programming is a technique for automated programming that evolves programs with a genetic algorithm. We show that such a system can be used to evolve mathematical proofs in complex domains i.e. arithmetics and program verification. The system is not restricted to evaluations of classical two-valued logic but can be used with for instance Kleene's three valued logic in order to detect paradoxes that can occur in real life reasoning applications. 

FILENAME: gen_reas.pdf (134 kB)




TITLE: An On-Line Method to Evolve Behavior and to Control a Miniature Robot in Real Time with Genetic Programming

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Adaptive Behaviour, 5 (2) , 1997, 107 --- 140

ABSTRACT: We present a novel evolutionary approach to robotic control of a real robot based on genetic programming (GP). Our approach uses genetic programming techniques that manipulate machine code to evolve control programs for robots. This variant of GP has several advantages over a conventional GP system, such as higher speed, lower memory requirements and better real time properties. Previous attempts to apply GP in robotics use simulations to evaluate control programs and have difficulties with learning tasks involving a real robot. We present an on-line control method that is evaluated in two different physical environments and applied to two tasks using the Khepera robot platform: obstacle avoidance and object following. The results show fast learning and good generalization. 

FILENAME: adapt_behav.pdf (344 kB)




TITLE: Evolving real-time behavioral modules for a robot with GP

AUTHORS Markus Olmer, Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. 6th International Symposium on Robotics And Manufacturing (ISRAM-96), Montpellier, France, 1996, in: Robotics and Manufacturing, M. Jamshidi, F. Pin, P. Dauchez (Eds.), Asme Press, New York, 1996, 675 --- 680

ABSTRACT: In this paper we demonstrate an efficient method which divides a control task into smaller sub--tasks. We use a Genetic Programming system that first learns the sub-tasks and then evolves a higher--level action selection strategy for deciding which of the evolved lower--level algorithms should be in control. The Swiss miniature robot Khepera is employed as the experimental platform. Results are presented which show that the robot is indeed able to evolve both the control algorithms for the different lower--level tasks and the strategy for the selection of tasks. The evolved solutions also show robust performance even if the robot is lifted and placed in a completely different environment or if obstacles are moved around. 

FILENAME: isram96.pdf (121 kB)




TITLE: Programmatic Compression of Images and Sound

AUTHORS Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. 1st annual Conf. on Genetic Programming (GP-96), Stanford, 1996, J. Koza, D. Goldberg, D. Fogel, R. Riolo (Eds.), MIT Press, Cambridge, MA, 1996, pp. 72 --- 81

ABSTRACT: The importance of digital data compression in the future media arena cannot be overestimated. A novel approach to data compression is built on Genetic Programming. This technique has been referred to as "programmatic compression". In this paper we apply a variant of programmatic compression to the compression of bitmap images and sampled digital sound. The work presented here constitutes the first successful result of genetic programming applied to compression of real full size images and sound. A compiling genetic programming system is used for efficiency reasons. Different related issues are discussed, such as the handling of very large fitness case sets. 

FILENAME: gp96.pdf (148 kB)




TITLE: Explicitly Defined Introns and Destructive Crossover in Genetic Programming

AUTHORS:Peter Nordin, Frank Francone, Wolfgang Banzhaf

SOURCE: Advances in Genetic Programming II, P. Angeline, K. Kinnear (eds.), MIT Press, Cambridge, MA, 1996, pp. 111 --- 134

ABSTRACT: In Genetic Programming, introns play at least two substantial roles: (1) A structural protection role, allowing the population to preserve highly-fit building blocks; and (2) A global protection role, enabling an individual to protect itself almost entirely against the destructive effect of crossover. We introduce Explicitly Defined Introns into Genetic Programming. Our results suggest that the introduction of Explicitly Defined Introns can improve fitness, generalization, and CPU time. Further, Explicitly Defined Introns partially replace the role of Implicit Introns ( that is, introns that emerge from crossover and mutation without being explicitly defined as such). Finally, Explicitly Defined Introns and Implicit Introns appear, in some situations, to work in tandem to produce better training, fitness and generalization than occurs without Explicitly Defined Introns. 

FILENAME: aigp2.pdf (214 kB)




TITLE: Benchmarking the Generalization Capabilities of a Compiling Genetic programming System using Sparse Data Sets

AUTHORS: Frank D. Francone, Peter Nordin, Wolfgang Banzhaf

SOURCE: Genetic Programming 1996: Proceedings of the first annual conference J.R. Koza, D.E. Goldberg, D.B. Fogel, R.Riolo (Eds.), MIT Press, Cambridge, 1996, 72 --- 80

ABSTRACT: Compiling Genetic Programming Systems (‘CPGS’) are advanced evolutionary algorithms that directly evolve RISC machine code. In this paper we compare the ability of CGPS to generalize with that of other machine learning (‘ML’) paradigms. This study presents our results on three classification problems. Our study involved 720 complete CGPS runs of population 3000 each, over 500 billion fitness evaluations and 480 neural network runs as benchmarks. Our results were as follows: 1. When CGPS was trained on data sets that were not too sparse, CGPS performed very well, equaling the generalization capability of other ML systems quickly and consistently. 2. When CGPS was trained on very sparse data sets, CGPS produced individuals that generalized almost as well other ML systems trained on much larger data sets. 3. As between CGPS and multilayer feedforward neural networks trained on the same sparse data sets, CGPS generalized as well (and often better) than the neural network.

FILENAME: benchmarking.pdf (121 kB)




TITLE: The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming using Sparse Data Sets

AUTHORS: Wolfgang Banzhaf, Frank D. Francone, Peter Nordin

SOURCE: 4th Int. Conf. on Parallel Problem Solving from Nature (PPSN96), W. Ebeling, I. Rechenberg, H.P. Schwefel, H.M. Voigt (Eds.), Springer, Berlin, 1996, 300 --- 309

ABSTRACT: Ordinarily, Genetic Programming uses little or no mutation. Crossover is the predominant operator. This study tests the effect of a very aggressive use of the mutation operator on the generalization performance of our Compiling Genetic Programming System ('CPGS'). We ran our tests on two benchmark classification problems on very sparse training sets. In all, we performed 240 complete runs of population 3000 for each of the problems, varying mutation rate between 5\% and 80\%. We found that increasing the mutation rate can significantly improve the generalization capabilities of GP. The mechanism by which mutation affects the generalization capability of GP is not entirely clear. What is clear is that changing the balance between mutation and crossover effects the course of GP training substantially --- for example, increasing mutation greatly extends the number of generations for which the GP system can train before the population converges. 

FILENAME: ppsn96_mut.pdf (154 kB)




TITLE: Genetic Reasoning --- Evolving Proofs with Genetic Search

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Dept. of CS, University of Dortmund, SysReport 1996

ABSTRACT: Most automated reasoning systems relies on human knowledge or heuristics to guide the reasoning or search for proofs. We have evaluated the use of a powerful general search algorithm to search in the space of mathematical proofs. In our approach automated reasoning is seen as an instance of automated programming where the proof is seen as a program (of functions corresponding to rules of inference) that transforms a statement into an axiom. Genetic programming is a technique for automated programming that evolves programs with a genetic algorithm. We show that such a system can be used to evolve mathematical proofs in complex domains i.e. arithmetics and program verification. The system is not restricted to evaluations of classical two-valued logic but can be used with for instance Kleene's three valued logic in order to detect paradoxes that can occur in real life reasoning applications. 

FILENAME: icml96.pdf (157 kB)




TITLE: Genetic Programming using Mutation, Reproduction and Genotype-Phenotype Mapping from linear binary Genomes into linear LALR(1) Phenotypes

AUTHORS:Robert Keller, Wolfgang Banzhaf

SOURCE: Proc. 1st annual Conf. on Genetic Programming (GP-96), Stanford, 1996, J. Koza, D. Goldberg, D. Fogel, R. Riolo (Eds.), MIT Press, Cambridge, MA, 1996, pp. 116 --- 122

ABSTRACT: In common GP approaches, the space of genotypes (search space) is identical to the space of phenotypes (solution space). Facts and theories from molecular biology suggest the introduction of non-identical genospaces and phenospaces, and a generic genotype-phenotype mapping (GPM) which maps unconstrained genotypes into syntactically correct phenotypes. Neutral variants come into effect due to GPM. They enhance genetic diversity and allow for escaping local optima in phenospace via high-dimensional saddle surfaces in genospace. We propose a concrete GPM which maps linear binary genotypes into linear phenotypes of an arbitrary LALR(1) programming language. Empirical results are presented which show that the GPM improves the performance of GP under mutation and reproduction. 

FILENAME: lalr_gp96.pdf (129 kB)




TITLE: Real Time Evolution of Behavior and a World Model for a Miniature Robot using Genetic Programming

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Dept. of CS, University of Dortmund, SysReport 5/95

ABSTRACT: A very general form of representing and specifying an autonomous agent's behavior is by using a computer language. The task of planning feasible actions could then simply be reduced to an instance of automatic programming. We have evaluated the use of an evolutionary technique for automatic programming called Genetic Programming (GP) to directly control a miniature robot. To our knowledge, this is the first attempt to control a real robot with a GP based learning method. Two schemes are presented. The objective of the GP-system in our first approach is to evolve real-time obstacle avoiding behavior from sensorial data. This technique enables real time learning with a real robot using genetic programming, it has, however, the drawback of the learning time being limited by the response dynamics of the environment. To overcome this problems we have devised a second method, learning from past experiences stored in memory. This new system allows speeds up of the algorithm by a factor of more than 2000. The emergence of the obstacle avoiding behavior is also speeded up by a factor of 40 enabling learning of this task in 1.5 minutes. This learning time is several orders of magnitudes faster then comparable experiments with other control architectures. The used algorithm is furthermore very compact and can be fitted into the micro-controller of the autonomous mobile miniature robot. 

FILENAME: mem_robot.pdf (258 kB)




TITLE: A Genetic Programming System Learning Obstacle Avoiding Behavior and Controlling a Miniature Robot in Real Time

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE:Dept. of CS, University of Dortmund, SysReport 4/95

ABSTRACT: We have evaluated the use of the evolutionary technique Genetic Programming (GP) to directly control a miniature robot. The goal of the GP-system was to evolve real-time obstacle avoiding behavior from sensorial data. The evolved programs are used in a sense-think-act context. We employed a novel technique to enable real time learning with a real robot using genetic programming. The technique uses a probabilistic sampling of the environment where each individual is tested on a new real-time fitness case in a tournament selection procedure. The fitness has a pain and a pleasure part. The negative part of fitness, the pain, is simply the sum of the proximity sensor values. In order to keep the robot from standing still or gyrating, it has a pleasure component to its fitness. It gets pleasure from going straight and fast. The evolved algorithm shows robust performance even if the robot is lifted and placed in a completely different environment or if obstacles are moved around. 

FILENAME: adapt_robot.pdf (244 kB)




TITLE: Genetic Programming Controlling a Miniature Robot

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: AAAI Fall Symposium Series 1995, Symposium on Genetic Programming

ABSTRACT: We have evaluated the use of Genetic Programming to directly control a miniature robot. The goal of the GP-system was to evolve real-time obstacle avoiding behaviour from sensorial data. The evolved programs are used in a sense-think-act context. We employed a novel technique to enable real time learning with a real robot. The technique uses a probabilistic sampling of the environment where each individual is tested on a new real-time fitness case in a tournament selection procedure. The fitness has a pain and a pleasure part. The negative part of fitness, the pain, is simply the sum of the proximity sensor values. In order to keep the robot from standing still or gyrating, it has a pleasure component to fitness. It gets pleasure from going straight and fast. The evolved algorithm shows robust performance even if the robot is lifted and placed in a completely different environment or if obstacles are moved around. 

FILENAME: AAAI-robot.pdf (107 kB)




TITLE: Explicitly Defined Introns and Destructive Crossover in Genetic Programming

AUTHORS:Peter Nordin, Frank Francone, Wolfgang Banzhaf

SOURCE: Workshop on Genetic Programming, Machine Learning, 1995

ABSTRACT: In Genetic Programming, introns play at least two substantial roles: (1) A structural protection role, allowing the population to preserve highly-fit building blocks; and (2) A global protection role, enabling an individual to protect itself almost entirely against the destructive effect of crossover. We introduce Explicitly Defined Introns into Genetic Programming. Our results suggest that the introduction of Explicitly Defined Introns can improve fitness, generalization, and CPU time. Further, Explicitly Defined Introns partially replace the role of Implicit Introns ( that is, introns that emerge from crossover and mutation without being explicitly defined as such). Finally, Explicitly Defined Introns and Implicit Introns appear, in some situations, to work in tandem to produce better training, fitness and generalization than occurs without Explicitly Defined Introns. 

FILENAME: ML95.pdf (305 kB)




TITLE: Evolving Turing-complete programs for a register machine with self-modifying code

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. of Int. Conference on Genetic Algorithms, Pittsburgh, 1995

ABSTRACT: The majority of commercial computers today are register machines of von Neumann type. We have developed a method to evolve Turing-complete programs for a register machine. The described implementation enables the use of most program constructs, such as arithmetic operators, large indexed memory, automatic decomposition into subfunctions and subroutines (ADFs), conditional constructs i.e. if-then-else, jumps, loop structures, recursion, protected functions, string and list functions. Any C-function can be compiled and linked into the function set of the system. The use of register machine language allows us to work at the lowest level of binary machine code without any interpreting steps. In a von Neumann machine, programs and data reside in the same memory and the genetic operators can thus directly manipulate the binary machine code in memory. The genetic operators themselves are written in C-language but they modify individuals in binary representation. The result is an execution speed enhancement of up to 100 times compared to an interpreting C-language implementation, and up to 2000 times compared to a LISP implementation. The use of binary machine code demands a very compact coding of about one byte per node in the individual. The resulting evolved programs are disassembled into C-modules and can be incorporated into a conventional software development environment. The low memory requirements and the significant speed enhancement of this technique could be of use when applying genetic programming to new application areas, platforms and research domains. 

FILENAME: icga95-2.pdf(168 kB)




TITLE: Complexity Compression and Evolution

AUTHORS:Peter Nordin, Wolfgang Banzhaf

SOURCE: Proc. of Int. Conference on Genetic Algorithms, Pittsburgh, 1995

ABSTRACT: Compression of information is an important concept in the theory of learning. We argue for the hypothesis that there is an inherent compression pressure towards short, elegant and general solutions in a genetic programming system and other variable length evolutionary algorithms. This pressure becomes visible if the size or complexity of solutions are measured without non-effective code segments called introns. The built in parsimony pressure effects complex fitness functions, crossover probability, generality, maximum depth or length of solutions, explicit parsimony, granularity of fitness function, initialization depth or length, and modularization. Some of these effects are positive and some are negative. In this work we provide a basis for an analysis of these effects and suggestions to overcome the negative implications in order to obtain the balance needed for successful evolution. An empirical investigation that supports our hypothesis is also presented. 

FILENAME: icga95-1.pdf (205 kB)




TITLE: Explicit maintenance of genetic diversity on genospaces

AUTHORS: Robert Keller, Wolfgang Banzhaf

SOURCE: Unpublished Manuscript, June 1994

ABSTRACT: When evolving genotypes, i.e. structures, with an evolutionary algorithm (EA), e.g. genetic programming (GP), genetic diversity, i.e. structural diversity, of each generation is a necessary condition for the fast detection of a high-fitness individual and for a fast adaptation of the population to a changing environment. Thus, it is an important objective to maintain diversity during runtime of the EA. Concepts and methods are introduced which propose extensions of EAs towards explicit maintenance of diversity by means of formally defined measures. For arbitrary genospaces, which are sets of genotypes, a {\it diversity measure} is proposed that is based on a structural measure which is defined by the minimal number of applications of edit operations needed to transform a genotype into another genotype. The proposed measures, concepts and methods are general, i.e they are independent on the structure type of the actual genotypes. Only the edit operations depend on the actual structure type. For the structure type of node-labeled trees, we propose edit operations, so that the above measures and methods can be used by GP paradigms operating on such structures. Since the proposed measures are purely structure-based, they are orthogonal to fitness as a quality measure on genospaces. 

FILENAME: genDiv.pdf (215 kB)




TITLE: Genotype-Phenotype-Mapping and Neutral Variation --- A case study in Genetic Programming

AUTHORS: Wolfgang Banzhaf

SOURCE: Proceedings PARALLEL PROBLEM SOLVING FROM NATURE III, Y. Davidor, H.-P. Schwefel and R. Männer (Eds.), Springer, Berlin, 1994, pp. 322 --- 332

ABSTRACT: We propose the application of a genotype-phenotype mapping to the solution of constrained optimization problems. The method consists of strictly separating the search space of genotypes from the solution space of phenotypes. A mapping from genotypes into phenotypes provides for the appropriate expression of information represented by the genotypes. The mapping is constructed as to guarantee feasibility of phenotypic solutions for the problem under study. This enforcing of constraints causes multiple genotypes to result in one and the same phenotype. Neutral variants are therefore frequent and play an important role in maintaining genetic diversity. As a specific example, we discuss Binary Genetic Programming (BGP), a variant of Genetic Programming that uses binary strings as genotypes and program trees as phenotypes. 

FILENAME: ppsn94.pdf (137 kB)




TITLE: Genetic Programming for Pedestrians

AUTHORS: Wolfgang Banzhaf

SOURCE: MERL Technical Report, 93-03, Mitsubishi Electric Research Labs, Cambridge, MA, 1993

ABSTRACT: We propose an extension to the Genetic Programming paradigm which allows users of traditional Genetic Algorithms to evolve computer programs. To this end, we have to introduce mechanisms like transscription, editing and repairing into Genetic Programming. We demonstrate the feasibility of the approach by using it to develop programs for the prediction of sequences of integer numbers. 

FILENAME: pedes93.pdf (154 kB)




Wolfgang Banzhaf
Last updated: Jan 25, 2017