EuroGP2005

8th European Conference on Genetic Programming

The conference proceedings is available on-line from Springer

The annual EuroGP series are the premier conferences in Europe devoted entirely to genetic programming. The standard is high with about 40% of submissions accepted for oral presentation, and reviewing is double blind. The conference is a mixture of oral presentations and poster sessions. ALL accepted papers are published as papers in a volume of the Springer Lecture Notes in Computer Science, oral presentations get 12 pages and posters get 10 pages.

EuroGP conferences are always enjoyable and offer good opportunities for informal contact with fellow researchers in a friendly and relaxed setting. EuroGP2005 will be held at the University of Lausanne, Switzerland, in conjunction with EvoCOP2005 and EvoWorkshops2005.

High quality papers are sought on topics strongly related to genetic programming, ranging from theoretical work to innovative applications.

Web address: http://www.evonet.info/eurogp2005

Topics include

Organising Committee

Program Chairs
Maarten Keijzer
eurogp AT xs4all DOT nl
KiQ Ltd. Amsterdam & WL | Delft Hydraulics, Delft, The Netherlands
 
Andrea Tettamanzi
tettaman AT genetica-soft DOT com
Genetica S.r.l. & University of Milan, Italy
 
Publication Chair
Pierre Collet
Pierre.Collet AT univ-littoral DOT fr
Laboratoire d'Informatique du Littoral, France
 
Local Chair
Marco Tomassini
Marco.Tomassini AT hec DOT unil DOT ch
University of Lausanne, Switzerland
 
Publicity Chair
Jano van Hemert
jvhemert AT cwi DOT nl
Napier University, Edinburgh, UK

Note: the e-mail addresses are masked for spam protection.


EuroGP Programme

Wednesday, 30 March 2005

Session 1: Data Mining (1120-1250)

Chair: Bill Langdon

Evolving Rules for Document Classification
Laurence Hirsch
Masoud Saeedi
Robin Hirsch

Using Genetic Programming for Multiclass Classification by Simultaneously Solving Component Binary Classification Problems
William Smart
Mengjie Zhang

Assessing the Effectiveness of Incorporating Knowledge in an Evolutionary Concept Learner
Federico Divina

Session 2: GP in Games (1415-1545)

Chair: Moshe Sipper

GP-Gammon: Using Genetic Programming to Evolve Backgammon Players
Yaniv Azaria
Moshe Sipper

GP-Robocode: Using Genetic Programming to Evolve Robocode Players
Yehonatan Shichel
Eran Ziserman
Moshe Sipper

GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players
Ami Hauptman
Moshe Sipper

Session 3: Miscellaneous Applications (1600-1730)

Chair: Marc Schoenauer

Evolution of Robot Controller Using Cartesian Genetic Programming
Simon Harding
Julian Miller

Evolving L-Systems to Capture Protein Structure Native Conformations
(Best Paper Award Candidate)
Gabi Escuela
Gabriela Ochoa
Natalio Krasnogor

[Cancelled] Automated Re-Invention of a Previously Patented Optical Lens System using Genetic Programming
John Koza
Lee Jones
Sameer Al-Sakran

Session 4: Posters (1730-2000)

Thursday, 31 March 2005

Session 5: Representations and Operators (0930-1100)

Chair: Riccardo Poli

Genetic Transposition in Tree-adjoining Grammar Guided Genetic Programming: The Duplication Operator
Nguyen Xuan Hoai
Robert Ian Bob McKay
Daryl Essam
Hoang Tuan Hao

Operator-Based Distance for Genetic Programming: Subtree Crossover Distance
(Best Paper Award Candidate)
Steven Gustafson
Leonardo Vanneschi

Repeated Patterns in Tree Genetic Programming
Bill Langdon
Wolfgang Banzhaf

Session 6: Alternative Paradigms (1120-1250)

Chair: Conor Ryan

MLP : A Combinational Logic Circuit Evaluation Engine for Genetic Parallel Programming
Wai Shing LAU
Gang LI
Sin Man CHEANG
Kin Hong LEE
Kwong Sak LEUNG

An Algorithmic Chemistry for Genetic Programming
(Best Paper Award Candidate)
Christian W.G. Lasarczyk
Wolfgang Banzhaf

Genetic Programming on Wireless Sensor Networks
Derek Michael Johnson
Ankur Teredesai
Robert Thomas Saltarelli

Session 7: Evolutionary Dynamics and Bloat Control (1415-1545)

Chair: James Foster

The Tree-String Problem: An Artificial Domain for Structure and Content Search
Steven Gustafson
Edmund Burke
Natalio Krasnogor

Tarpeian Bloat Control and Generalization Accuracy
Sébastien Mahler
Denis Robilliard
Cyril Fonlupt

Dynamic Size Populations in Distributed Genetic Programming
Denis Rochat
Marco Tomassini
Leonardo Vanneschi

Session 8: Debate (1600-1730)

Topic: Applied GP, successes and failures.

Friday, 1 April 2005

Session 9: Probabilistic Grammar Evolution (0930-1030)

Chair: Michael O'Neill

Bayesian Automatic Programming
Evandro Nunes Regolin
Aurora Trindad Ramirez Pozo

Incorporating Learning Probabilistic Context-sensitive Grammar in Genetic Programming for Efficient Evolution and Adaptation of Snakebot
(Best Paper Award Candidate)
Ivan Tanev


Accepted papers for presentation: titles and abstracts

Evolving Rules for Document Classification
Laurence Hirsch, Masoud Saeedi, Robin Hirsch

We describe a novel method for using Genetic Programming to create compact classification rules based on combinations of N-Grams (character strings). Genetic programs acquire fitness by producing rules that are effective classifiers in terms of precision and recall when evaluated against a set of training documents. We describe a set of functions and terminals and provide results from a classification task using the Reuters 21578 dataset. We also suggest that because the induced rules are meaningful to a human analyst they may have a number of other uses beyond classification and provide a basis for text mining applications


Assessing the Effectiveness of Incorporating Knowledge in an Evolutionary Concept Learner
Federico Divina

Classical methods for Inductive Concept Learning (ICL) rely mostly on using speci �c search strategies, as hill climbing and inverse resolution. These strategies have a great exploitation power, but run the risk of being incapable of escaping from local optima. An alternative approach to ICL is represented by Evolutionary Algorithms (EAs). EAs have a great exploration power, thus they have the capability of escaping from local optima, but their exploitation power is rather poor. These observations suggest that the two approaches are applicable to partly complementary classes of learning problems. More important, they indicate that a system incorporating features from both approaches could benefit from the complementary qualities of the approaches. In this paper we experimentally validate this statement. To this end, we incorporate different search strategies in a framework based on EAs for ICL. Results of experiments show that incorporating standard search strategies helps the EAs in achieving better results.


Dynamic Size Populations in Distributed Genetic Programming
Denis Rochat, Marco Tomassini, Leonardo Vanneschi

This paper proposes the association of two approaches of GP which improve efficiency and reduce bloat. The first approach is to use a multi-population version of GP and the second one is to employ populations that can change size dynamically and adaptively. The latter approach consists in deleting or adding individuals in the population as a function of the current fitness and two other parameters. We test this approach on three well-known problems in GP, artificial ant, even parity 5 and one instance of the symbolic regression. We find that the combination of these two methods improves the quality of the individuals in the populations while keeping their size as small as possible and decreases the amount of resources required.


Genetic Programming on Wireless Sensor Networks
Derek Michael Johnson, Ankur Teredesai, Robert Thomas Saltarelli

Paintable computing or Amorphous Computing paradigms are .... Wireless sensor networks (WSNs) are becoming increasingly important as they attain greater deployment. New techniques for evolutionary computing (EC) are needed to address these new computing models. This paper describes a novel effort to develop a series of variations to evolutionary computing paradims such as Genetic Programming to enable their operation within the wireless sensor network. The ability to compute evolutionary algorithms within the WSN has innumerable advantages including, intelligent-sensing, resource optimized communication strategies, intelligent-routing protocol design, novelty detection, etc to name a few. In this paper we first discuss an evolutionary computing algorithm that operates within a distributed wireless sensor network. Such algorithms include continuous evolutionary computing. Continuous evolutionary computing extends the concept of an asynchronous evolutionary cycle where each individual resides and communicates with its immediate neighbors in an asynchronous time-step and exchanges genetic material. We then describe the adaptations required to develop practicable implementations of evolutionary computing algorithms to effectively work in resource constrained environments such as WSNs. Several adaptations including a novel representation scheme, an approximate fitness computation method and a sufficient statistics based data reduction technique lead to the developmet of a GP implementation that is usable on the low-power, small footprint architectures typical to wireless sensor motes. We demonstrate the utility of our formulations and validate the proposed ideas using a variety of problem sets and describe the results.


Evolution of Robot Controller Using Cartesian Genetic Programming
Simon Harding, Julian Miller

Cartesian Genetic Programming is a graph based representation that has many benefits over traditional tree based methods, including bloat free evolution and faster evolution through neutral search. Here, an integer based version of the representation is applied to a traditional problem in the field : evolving an obstacle avoiding robot controller. The technique is used to rapidly evolve controllers that work in a complex environment and with a challenging robot design. The generalisation of the robot controllers in different environments is also demonstrated. A novel fitness function based on chemical gradients is presented as a means of improving evolvability in such tasks.


GP-Gammon: Using Genetic Programming to Evolve Backgammon Players
Yaniv Azaria and Moshe Sipper

We apply genetic programming to the evolution of strategies for playing the game of backgammon. Pitted in a 1000-game tournament against a standard benchmark player---Pubeval---our best evolved program wins 58% of the games, the highest verifiable result to date. Moreover, several other evolved programs attain win percentages not far behind the champion, evidencing the repeatability of our approach.


GP-Robocode: Using Genetic Programming to Evolve Robocode Players
Yehonatan Shichel, Eran Ziserman, and Moshe Sipper

This paper describes the first attempt to introduce evolutionarily designed players into the international Robocode league, a simulation-based game wherein robotic tanks fight to destruction in a closed arena. Using genetic programming to evolve tank strategies for this highly active forum, we were able to rank third out of twenty-seven players in the category of HaikuBots. Our GPBot was the only entry not written by a human.


GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players
Ami Hauptman and Moshe Sipper

We apply genetic programming to the evolution of strategies for playing chess endgames. Our evolved programs are able to draw or win against an expert human-based strategy, and draw against CRAFTY---a world-class chess program, which finished second in the 2004 Computer Chess Championship.


GENETIC TRANSPOSITION IN TREE-ADJOINING GRAMMAR GUIDED GENETIC PROGRAMMING: THE DUPLICATION OPERATOR
Nguyen Xuan Hoai, Robert Ian Bob McKay, Daryl Essam, and Hoang Tuan Hao

We empirically investigate the use of dual duplication/truncation operators both as mutation operators and as generic local search operators, in combination with genetic search in a tree adjoining grammar guided genetic programming system (TAG3P). The results show that, on the problems tried, duplication/truncation works well as a mutation operator but not reliably when the complexity of the problem was scaled up. When using these dual operators as a generic local search operator, however, it helped TAG3P not only to solve the problems reliably but also cope well with scalability in problem complexity. Moreover, it managed to solve problems with very small population sizes.


MLP : A Combinational Logic Circuit Evaluation Engine for Genetic Parallel Programming
Wai Shing LAU, Gang LI, Sin Man CHEANG, Kin Hong LEE, Kwong Sak LEUNG

Genetic Parallel Programming (GPP) is a novel Genetic Programming paradigm. GPP Logic Circuit Synthesizer (GPPLCS), is a combinational logic circuit learning system based on GPP. The GPPLCS comprises a Multi-Logic-Unit Processor (MLP which is a hardware processor built on a Field Programmable Gate Array (FPGA). The MLP is designed to speed up the evaluation of genetic parallel programs that represent combinational logic circuits. Four combinational logic circuit problems are presented to show the performance of the hardware-assisted GPPLCS. Experimental results show that the hardware MLP speeds up evolutions over 10 times. For difficult problems such as the 6-bit priority selector and the 6-bit comparator, the speedup ratio can be up to 22.


Using Genetic Programming for Multiclass Classification by Simultaneously Solving Component Binary Classification Problems
William Smart and Mengjie Zhang

In this paper a method is presented to solve a series of multiple-class object classification problems using Genetic Programming (GP). All component two-class subproblems of the multiple-class problem are solved in a single run, using a multi-objective fitness function. Probabilistic methods are used, with each evolved program required to solve only one subproblem. Programs gain a fitness related to their rank at the subproblem that they solve best. The new method is compared by experiment to two other GP based methods on four multiple-class classification problems of varying difficulty. The new method outperforms the other methods significantly in almost all experiments. The new method often takes a longer running time, but usually reaches a peak in accuracy very early.


Operator-Based Distance for Genetic Programming: Subtree Crossover Distance
(Best Paper Award Candidate)
Steven Gustafson, Leonardo Vanneschi

This paper explores distance measures based on genetic operators for genetic programming using tree structures. The consistency between genetic operators and distance measures is a crucial point for analytical measures of problem difficulty, such as fitness distance correlation, and for measures of population diversity, such as entropy or variance. The contribution of this paper is the exploration of possible definitions and approximations of operator-based edit distance measures. In particular, we focus on the subtree crossover operator. An empirical study is presented to illustrate the features of an operator-based distance. This paper makes progress toward improved algorithmic analysis by using appropriate measures of distance and similarity.


The Tree-String Problem: An Artificial Domain for Structure and Content Search
Steven Gustafson, Edmund Burke, Natalio Krasnogor

This paper introduces the Tree-String problem for genetic programming and related search and optimisation methods. To improve the understanding of optimisation and search methods, we aim to capture the complex dynamic created by the interdependencies of solution structure and content. Thus, we created an artificial domain that is amenable for analysis, yet representative of a wide-range of real-world applications. The Tree-String problem provides several benefits, including: the direct control of both structure and content objectives, the production of a rich and representative search space, the ability to create tunably difficult and random instances and the flexibility for specialisation.


Bayesian Automatic Programming
Evandro Nunes Regolin, Aurora Trindad Ramirez Pozo

In this work a new approach, named Bayesian Automatic Programming (BAP), to inducing programs is presented. BAP integrates the power of grammar evolution and probabilistic models to evolve programs. We explore the use of BAP in two domains: a regression problem and the artificial ant problem. Its results are compared with traditional Genetic Programming (GP). The experimental results found encourage further investigation, especially to explore BAP in other domains and to improve the proposed approach incorporating new mechanisms.


Evolving L-Systems to Capture Protein Structure Native Conformations
(Best Paper Award Candidate)
Gabi Escuela, Gabriela Ochoa, Natalio Krasnogor

A protein is a linear chain of amino acids, that under certain physical conditions, folds into a unique functional structure, called its native state or tertiary structure. In this state, proteins show repeated substructures like alpha helices and beta sheets. This observation suggests that native structures may be captured by the formalism known as Lindenmayer systems (L-systems). In this paper an evolutionary algorithm is used as the inference procedure for folded structures under the HP model in 2D lattices. The EA searches in the space of possible L-systems which are then executed to obtain the phenotype, thus our approach is close to that of Grammatical Evolution. The problem is to find a set of rewriting rules that represents a target native structure on the selected lattice model. The proposed approach has produced promising results for short sequences under the 2D square lattice. Thus the foundations are set for a novel encoding based on L-systems for evolutionary approaches to both the Protein Structure Prediction and Inverse Folding Problems.


Tarpeian Bloat Control and Generalization Accuracy
Sébastien Mahler, Denis Robilliard, Cyril Fonlupt

In this paper we will focus on machine-learning issues solved with Genetic Programming (GP). Excessive code growth or bloat often happens in GP , greatly slowing down the evolution process. Poli proposed the Tarpeian Control method to reduce bloat, but possible side-effects of this method on the generalization accuracy of GP hypotheses remained to be tested. In particular, since Tarpeian Control puts a brake on code growth, it could behave as a kind of Occam's razor, promoting shorter hypotheses more able to extend their knowledge to cases apart from any learning steps. To answer this question, we experiment Tarpeian Control with symbolic regression. The results are contrasted, showing that it can either increase or reduce the generalization power of GP hypotheses, depending on the problem at hand. This suggest that a blind use of TC is not safe, but also that a careful parameter setup may be profitable in some cases.


Repeated Patterns in Tree Genetic Programming
Bill Langdon, Wolfgang Banzhaf

Large repeated patterns are found in large trees automatically programmed by genetic programming (GP). Size fair crossover limits bloat. Evolved trees are incrementally constructed from high fitness subtrees but they are not classic GP building blocks. Diffuse introns ensure most code is robust to change.


Incorporating Learning Probabilistic Context-sensitive Grammar in Genetic Programming for Efficient Evolution and Adaptation of Snakebot
(Best Paper Award Candidate)
Ivan Tanev

In this work we propose an approach of incorporating probabilistic learning context-sensitive grammar (PLCSG) in genetic programming (GP) employed for evolu-tion and adaptation of locomotion gaits of simulated snake-like robot (Snakebot). In our approach PLCSG is derived from the originally defined context-free grammar, which usually expresses the syntax of genetic programs in canonical GP. During the es-pecially introduced ?steered? mutation the probabilities of applying each of particular production rules with multiple right-hand side alternatives in PLCSG depend on the context, and these probabilities are ?learned? from the aggregated reward values ob-tained from the evolved best-of-generation Snakebots. Empirically obtained results ver-ify that employing PLCSG contributes to the improvement of computational effort of both (i) the evolution of the fastest possible locomotion gaits for various fitness condi-tions and (ii) adaptation of these locomotion gaits to challenging environment and de-graded mechanical abilities of Snakebot. In all of the cases considered in this study, the locomotion gaits, evolved and adapted employing GP with PLCSG feature higher ve-locity and are obtained faster than with canonical GP.


Automated Re-Invention of a Previously Patented Optical Lens System using Genetic Programming
John Koza, Lee Jones, Sameer Al-Sakran

The three dozen or so known instances of human-competitive designs produced by genetic programming for antennas, mechanical systems, circuits, and controllers raise the question of whether the genetic programming can be extended to the design of complex structures from other fields. This paper discusses efforts to apply genetic programming to the automated design of optical lens systems. The paper can be read from two different perspectives. First, broadly, it chronicles the step-by-step process by which the authors approached the problem of applying genetic programming to a domain that was new to them. Second, more narrowly, it describes the use of genetic programming to re-create the complete design for the previously patented Tackaberry-Muller optical lens system. Genetic programming accomplished this ?from scratch??without starting from a pre-specified number of lens and a pre-specified layout and without starting from a pre-existing good design. The genetically evolved design for the Tackaberry-Muller lens system is an example, in the field of optical design, of a human-competitive result produced by genetic programming.


An Algorithmic Chemistry for Genetic Programming
(Best Paper Award Candidate)
Christian W.G. Lasarczyk, Wolfgang Banzhaf

Genetic Programming has been slow at realizing other programming paradigms than conventional, deterministic, sequential von- Neumann type algorithms. In this contribution we discuss a new method of execution of programs introduced recently: Algorithmic Chemistries. Therein, register machine instructions are executed in a non-deterministic order, following a probability distribution. Program behavior is thus highly dependent on frequency of instructions and connectivity between registers. Here we demonstrate the performance of GP on evolving solutions to a parity problem in a system of this type.


Accepted papers for poster presentation: titles and abstracts

Evolve Schemata Directly Using Instruction Matrix Based Genetic Programming

Gang LI, Kin Hong LEE, Kwong Sak LEUNG

This paper proposes a new architecture for tree-based genetic programming to evolve schemata directly. It uses fixed length hs-expressions to represent program trees in any shape, keeps schemata information in an instruction matrix, and extracts individuals from it. In order to manipulate the instruction matrix and the hs-expression, new genetic operators and a new fitness evaluation function are developed. The experimental results verify that its results are much better than those of the canonical genetic programming on the problems tested in this paper.


Evolving Defence Strategies by Genetic Programming

David Jackson

Computer games and simulations are commonly used as a basis for analysing and developing battlefield strategies. Such strategies are usually programmed explicitly, but it is also possible to generate them automatically via the use of evolutionary programming techniques. We focus in particular on the use of genetic programming to evolve strategies for a single defender facing multiple simultaneous attacks. By expressing the problem domain in the form of a ?Space Invaders? game, we show that it is possible to evolve winning strategies for an increasingly complex sequence of scenarios


Evolution of Vertex and Pixel Shaders

Marc Ebner, Markus Reinhardt and Jürgen Albert

In real-time rendering, objects are represented using polygons or triangles. Triangles are easy to render and graphics hardware is highly optimized for rendering of triangles. Initially, the shading computations were carried out by dedicated hardwired algorithms for each vertex and then interpolated by the rasterizer. Todays graphics hardware contains vertex and pixel shaders which can be reprogrammed by the user. Vertex and pixel shaders allow almost arbitrary computations per vertex respectively per pixel. We have developed a system to evolve such programs. The system runs on a variety of graphics hardware due to the use of NVIDIA's high level Cg shader language. Fitness of the shaders is determined by user interaction. Both fixed length and variable length genomes are supported. The system is highly customizable. Each individual consists of a series of meta commands. The resulting Cg program is translated into the low level commands which are required for the particular graphics hardware.


Context-based Repeated Sequences in Linear Genetic Programming

Garnett Carl Wilson and Malcolm Iain Heywood

Repeating code sequences are found in both artificial and natural genomes as an emergent phenomenon. These patterns are of interest in researching both how evolution reuses code segments to create superior individuals and whether building blocks are used in the formation of repeated sequences. In this paper we describe a GP representation using a special type of crossover that is more conducive to the formation of repeated sequences than traditional GP. We then establish that the repeated sequence phenomenon in the implementation displays traits of building blocks by establishing associated regularity of genotype and phenotype elements. As additional merits, the pattern-rich im-plementation boasts succinct solutions with less bloat and accomplishes the code regularity without a loss in performance with respect to fitness.


Evolution of a Strategy for Ship Guidance Using Two Implementations of Genetic Programming

Eva Alfaro-Cid, Euan William McGookin, David James Murray-Smith

In this paper the implementation of Genetic Programming (GP) to optimise a controller structure for a supply ship is assessed. GP is used to evolve control strategies that, given the current and desired state of the propulsion and heading dynamics of a supply ship as inputs, generate the commanded forces required to manoeuvre the ship. The optimised controllers are evaluated through computer simulations and real manoeuvrability tests in a water basin laboratory. In order to deal with the issue of the generation of numerical constants, two kinds of GP algorithms are implemented. The first one chooses the constants necessary to create the controller structure by random generation . The second algorithm includes a Genetic Algorithms (GAs) technique for the optimisation of such constants. The results obtained illustrate the benefits of using GP to optimise propulsion and navigation controllers for ships.


Understanding Evolved Genetic Programs for a Real World Object Detection Problem

Victor Ciesielski, Andrew Innes, Sabu John, John Mamutil

We describe an approach to understanding evolved programs for a real world object detection problem, that of finding orthodontic landmarks in cranio-facial X-Rays. The approach involves modifying the fitness function to encourage the evolution of small programs, limiting the function set to a minimal number of operators and limiting the number of terminals (features). When this was done for two landmarks, an easy one and a difficult one, the evolved programs implemented a linear function of the features. Analysis of these linear functions revealed that underlying regularities were being captured and that successful evolutionary runs usually terminated with the best programs implementing one of a small number of underlying algorithms. Analysis of these algorithms revealed that they are a realistic solution to the object detection problem, given the features and operators available.


mGGA: The meta-Grammar Genetic Algorithm

Michael O'Neill and Anthony Brabazon

A novel Grammatical Genetic Algorithm, the meta-Grammar Genetic Algorithm (mGGA) is presented. The mGGA borrows a grammatical representation and the ideas of modularity and reuse from Genetic Programming, and in particular an evolvable grammar representation from Grammatical Evolution by Grammatical Evolution. We demonstrate its application to a number of benchmark problems where significant performance gains are achieved when compared to static grammars.


On Prediction of Epileptic Seizures by Computing Multiple Genetic Programming Artificial Features

Hiram Firpi, Erik Goodman, Javier Echauz

In this paper, we present a general-purpose, systematic algorithm, consisting of a genetic programming module and a k-nearest neighbor classifier, to automatically create multiple artificial features (i.e., features that are computer-crafted and may not have a known physical meaning) directly from EEG signals that reveal patterns predictive of epileptic seizures. The algorithm was evaluated in three different patients, with prediction defined over a horizon that varies between 1 and 5 minutes before unequivocal electrographic onset. For one patient, a perfect classification was achieved. For the other two patients, a high classification accuracy was reached, predicting three seizures out of four for one, and eleven seizures out of fifteen for the other. For the latter, also, only one normal (non-seizure) signal was misclassified.


Extending Particle Swarm Optimisation via Genetic Programming

Riccardo Poli, W. B. Langdon, O. Holland

Genetic programming is used to evolve Particle Swarm Optimisers (PSOs). PSOs include a small number of interacting particles, which fly over the fitness landscape in search for high fitness points. The particles are typically controlled by forces which encourage each particle to fly back towards the best point on the landscape sampled by it (personal best) while at the same time trying to imitate the best particle in the swarm with a drive towards the swarm?s best. The standard PSO is well known for its effectiveness on a variety of optimisation problems. We explore the possibility of evolving the force generating equations to control the particles in a PSO. Our aim is to verify the feasibility of this approach and to start exploring what types of PSOs are most appropriate for different classes of landscapes.


Teams of Genetic Predictors for Inverse Problem Solving

Defoin Platel Michael, Chami Malik, Clergue Manuel, Collard Philippe

Genetic Programming (GP) has been shown to be a good method of predicting functions that solve inverse problems. In this context, a solution given by GP generally consists of a sole predictor. In contrast, Stack-based GP systems manipulate structures containing several predictors, which can be considered as teams of predictors. Work in Machine Learning reports that combining predictors gives good results in terms of both quality and robustness. In this paper, we use Stack-based GP to study different cooperations between predictors. First, preliminary tests and parameter tuning are performed on two GP benchmarks. Then, the system is applied to a real-world inverse problem. A comparative study with standard methods has shown limits and advantages of teams prediction, leading to encourage the use of combinations taking into account the response quality of each team member.


Inducing Diverse Decision Forests with Genetic Programing

Jan Suchý, Jirí Kubalík

This paper presents an algorithm for induction of ensembles of decision trees, also referred to as decision forests. In order to achieve high expressiveness the trees induced are multivariate, with various, possibly user-defined tests in their internal nodes. Strongly typed genetic programming is utilized to evolve structure of the tests. Special attention is given to the problem of diversity of the forest constructed. An approach is proposed, which explicitly encourages the induction algorithm to produce a different tree each run, which represents an alternative description of the data. It is shown that forests constructed with this approach have significantly reduced classification error even for small forest size, compared to other ensemble methods. Classification accuracy of the algorithm is also compared to other recent methods on several real-world datasets.


Relative Fitness and Absolute Fitness for Co-evolutionary Systems

Nanlin Jin, Edward Tsang

The commonly adopted fitness which evaluates the performance of individuals in co-evolutionary systems is relative fitness. Relative fitness is a dynamic assessment subject to the other co-evolving population(s). Researchers apparently pay less attention to the use of absolute fitness functions in studying co-evolutionary algorithms than the use of relative fitness functions. One of our aims in this work is to formalize both relative fitness and absolute fitness for co-evolving systems. Another aim is to demonstrate the usage of absolute and relative fitness through a case study. We develop a co-evolutionary system by means of Genetic Programming to discover co-adapted strategies for a Basic Alternating-Offers Bargaining Problem. In this case, the relative fitness essentially drives co-evolution to converge to game-theoretic equilibrium. Whereas the relative fitness alone can not discover the whole view of co-evolutionary progress. The absolute fitness, on the other hand helps us to monitor the development of co-adaptive learning. Having analyzed the micro-behavior of the players' strategies, based on their absolute fitness, we can explain how the co-evolving populations converge to the perfect equilibria.


Zero is not a four letter word : Studies in the evolution of language.

Chris Stephens, Conor Ryan, Miguel Nicolau

We examine a model genetic system that has features of both genetic programming and genetic regulatory networks, to show how various forms of degeneracy in the genotype-phenotype map can induce complex and subtle behaviour in the dynamics that lead to enhanced evolutionary robustness and can be fruitfully described in terms of an elementary algorithmic ``language''.


Undirected training of Run Transferable Libraries

Conor Ryan, Maarten Keijzer, Mike Cattolico, Gearoid Murphy

This paper investigates the robustness of Run Transferable Libraries(RTLs) on scaled problems. RTLs are provide GP with a library of functions which replace the usual primitive functions provided when approaching a problem. The RTL evolves from run to run using feedback based on function usage, and has been shown to outperform GP by an order of magnitude on a variety of scalable problems. RTLs can, however, also be applied across a {em domain} of related problems, as well as across a range of scaled instances of a single problem. To this successfully, it will need to balance a range of functions. We introduce a problem that can deceive the system into converging to a sub-optimal set of functions, and demonstrate that this is a consequence of the greediness of the library update algorithm. We demonstrate that a much simpler, truly evolutionary, update strategy doesn't suffer from this problem, and exhibits far better optimization properties than the original strategy