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
2023
A Genetic Programming Approach to Engineering MRI Reporter Genes, 2023
Iterative Genetic Improvement: Scaling Stochastic Program Synthesis, 2023
Spatial Genetic Programming, 2023
Phenotype Search Trajectory Networks for Linear Genetic Programming, 2023
MAP-Elites with Cosine-Similarity for Evolutionary Ensemble Learning, 2023
MOAZ: A Multi-Objective AutoML-Zero Framework, 2023
Active Learning Informs Symbolic Regression Model Development in Genetic Programming, 2023
Relieving Coefficient Learning in Genetic Programming for Symbolic Regression via Correlation and Linear Scaling, 2023
A Double Lexicase Selection Operator for Bloat Control in Evolutionary Feature Construction for Regression, 2023
Correlation versus RMSE Loss Functions in Symbolic Regression Tasks, 2023
Genetic Programming Theory and Practice XIX (edited volume), 2023
Relieving Coefficient Learning in Genetic Programming for Symbolic Regression via Correlation and Linear Scaling, 2023
A Double Lexicase Selection Operator for Bloat Control in Evolutionary Feature Construction for Regression, 2023
Active Learning Informs Symbolic Regression Model Development in Genetic Programming, 2023
MOAZ: A Multi-Objective AutoML-Zero Framework, 2023
MAP-Elites with Cosine-Similarity for Evolutionary Ensemble Learning, 2023
Phenotype Search Trajectory Networks for Linear Genetic Programming, 2023
Spatial Genetic Programming, 2023
<
2022
Active Learning Improves Performance on Symbolic Regression Tasks in StackGP, 2022
Optimizing LLVM Pass Sequences with Shackleton: A Linear Genetic Programming Framework, 2022
Using Genetic Programming to Predict and Optimize Protein Function, 2022
Long-Term Evolution Experiment with Genetic Programming, 2022
Optimizing LLVM Pass Sequences with Shackleton: A Linear Genetic Programming Framework, 2022
Active Learning Improves Performance on Symbolic Regression Tasks in StackGP, 2022
Genetic Programming Theory and Practice XVIII (edited volume), 2022
2021
2020
-
Towards Better Evolutionary Software Repair, 2020
-
Time and Individual Duration in Genetic Programming, 2020
-
A Network Perspective on Genotype-Phenotype Mapping in Genetic Programming, 2020
-
ARJA: Automated Repair in Java Programs via Multi-Objective Genetic Programming, 2020
-
Modelling Genetic Programming as a Simple Sampling Algorithm, 2020
-
It is time for new perspectives on how to fight bloat in GP, 2020
-
An Evolutionary System for Better Automatic Software Repair, 2020
-
Temporal Memory Sharing in Visual Reinforcement Learning, 2020
-
Making Better Use of Repair Templates in Automated Software Repair, 2020
-
A Modular Memory Framework for Time Series Prediction, 2020
-
Genetic Programming Theory and Practice XVII (edited volume), 2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
-
Robustness, Evolvability, and Accessibility in Linear Genetic Programming, 2011
-
Stock Trading using LGP with Multiple Time Frames, 2011
-
Rethinking Multilevel Selection in Genetic Programming, 2011
-
SMCGP2: Self Modifying Cartesian Genetic Programming
in Two Dimensions, 2011
-
Self Modifying Cartesian Genetic Programming, 2011
-
Image Processing and Cartesian Genetic Programming, 2011
-
Hardware Acceleration for CGP: Graphics Processing Units, 2011
-
A Survey of Self-Modifying Cartesian Genetic Programming, 2011
2010
-
Interday and Intraday Stock Trading using Probabilistic Adaptive Mapping Developmental Genetic Programming and Linear Genetic Programming, 2010
-
Algorithmic Trading with Developmental and Linear Genetic Programming, 2010
-
Evolving Genes to Balance a Pole, 2010
-
Interday Foreign Exchange Trading using Linear Genetic Programming, 2010
-
Self Modifying Cartesian Genetic Programming: Finding Algorithms that Calculate pi and e to Arbitrary Precision, 2010
-
Fast and Effective Predictability Filters for Stock Price Series using
Linear Genetic Programming, 2010
-
Open Issues in Genetic Programming, 2010
-
Developments in Cartesian Genetic Programming: Self-Modifying CGP, 2010
-
Variable population size and evolution acceleration: a case study with a parallel evolutionary algorithm, 2010
-
Deployment of parallel linear genetic programming using GPUs on PC and video game console platforms, 2010
-
Evolvability and Speed of Evolutionary Algorithms in Light of Recent Developments in Biology, 2010
-
The use of Computational Intelligence in Intrusion Detection Systems: A Review, 2010
2009
-
Evolution, Development and Learning Using Self-Modifying Cartesian Genetic Programming, 2009
-
Soft Memory for Stock Market Analysis using Linear and Developmental Genetic Programming, 2009
-
Neutrality and Variability: Two sides of Evolvability in Linear Genetic Programming, 2009
-
Prediction of Interday Stock Prices using Developmental and Linear Genetic Programming, 2009
-
Self Modifying Cartesian Genetic Programming: Fibonacci, Squares, Regression and Summing, 2009
-
The Role of Population Size in Rate of Evolution in Genetic Programming, 2009
-
A study of heuristic combinations for hyper-hyeuristic
systems for the uncapacitated examination timetabling problem, 2009
-
Evolving Novel Image Features using Genetic Programming-based Image Transforms, 2009
-
Self Modifying Cartesian Genetic Programming: Parity, 2009
2008
-
Genetic Programming on GPUs for Image Processing, 2008 (extended version of Workshop Contribution)
-
Accelerating Genetic Programming on Graphics Processing Units, 2008
-
Genetic Programming on GPUs for Image Processing, 2008
-
Repeated Patterns in Genetic Programming, 2008
-
A Developmental Approach to the Uncapacitated Examination Timetabling Problem, 2008
-
Nonsynonymous to Synonymous Substitution Ratio ka/ks: Measurement for Rate of Evolution in Evolutionary Computation, 2008
-
Combatting Financial Fraud: A Coevolutionary Anomaly Detection Approach, 2008
-
Linear genetic programming GPGPU on Microsoft Xbox 360, 2008
-
An eigen analysis of the GP community, 2008
-
Evolving Blackbox Quantum Algorithms using Genetic Programming, 2008
-
Artificial Development, 2008
-
A Comparison of Cartesian Genetic Programming and Linear Genetic Programming, 2008
-
A SIMD Interpreter for Genetic Programming on GPU Graphics Cards, 2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
-
Evolving real-time behavioral modules
for a robot with GP, 1996
-
Benchmarking the Generalization Capabilities of a
Compiling Genetic programming System using Sparse Data Sets, 1996
-
Programmatic Compression of Images and Sound, 1996
-
Explicitly Defined Introns and Destructive
Crossover in Genetic Programming (Book chapter), 1996
-
The Effect of Extensive Use of the Mutation Operator
on Generalization in Genetic Programming using Sparse Data Sets, 1996
-
Genetic Reasoning --- Evolving Proofs
with Genetic Search, 1996
-
Genetic Programming using Mutation,
Reproduction and Genotype-Phenotype Mapping from linear binary Genomes
into linear LALR(1) Phenotypes, 1996
1995
-
Real Time Evolution of Behavior and a World Model
for a Miniature Robot using GP, 1995
-
A GP System Learning Obstacle Avoiding Behavior
and Controlling a Miniature Robot in Real Time, 1995
-
Genetic Programming Controlling a Miniature
Robot, 1995
-
Explicitly Defined Introns and Destructive Crossover
in Genetic Programming, 1995
-
Evolving Turing-complete programs for a register
machine with self-modifying code, 1995
-
Complexity Compression and Evolution, 1995
1994
1993
-
Genetic Programming for Pedestrians, 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
TITLE: Efficient Evolution of Machine Code for CISC Architectures using
Blocks and Homologous Crossover
AUTHORS: P. Nordin, W. Banzhaf and F. Francone
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.
TITLE: CAD Surface Reconstruction from Digitized 3D Point Data with Genetic
Programming
AUTHORS: R. Keller, W. Banzhaf, J. Mehnen, and K. Weinert
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.
TITLE: Speech Sound Discrimination With Genetic Programming
AUTHORS: Markus Conrads, Peter Nordin and Wolfgang Banzhaf
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
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.
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.
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.
TITLE: Introns in Nature and in Simulated Structure Evolution
AUTHORS: Peter Nordin, Wolfgang Banzhaf and Frank D. Francone
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.
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.
TITLE: Generating Adaptive Behavior for a Real Robot using Function Regression
within Genetic Programming
AUTHORS:Wolfgang Banzhaf, Peter Nordin, Markus Olmer
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.
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.
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.
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.
TITLE: Programmatic Compression of Images and Sound
AUTHORS Peter Nordin, Wolfgang Banzhaf
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Wolfgang Banzhaf
Last updated: Aug 10, 2023