what is a building block in genetic programming? by examining the smallest subtree possible-a single leaf node. The analysis of these subtrees indicates a considerably more complex portrait of what exactly is meant by a building block in GP than what has traditionally been considered.

On the emergence of the cooperative behaviour for multiple agents by means of Genetic Programming (GP). Our experimental domains are multi-agent test beds, i.e., the robot navigation task and the Tile World. The world consists of a simulated robot agent and a simulated environment which is both dynamic and unpredictable. In our previous paper, we proposed three types of strategies, i.e, homogeneous breeding, heterogeneous breeding, and co-evolutionary breeding, for the purpose of evolving the cooperative behavior. We use the heterogeneous breeding in this paper. The previous Q-learning approach commonly used for the multi-agent task has the difficulty with the combinatorial explosion for many agents. This is because the state space for Q-table is so huge for the practical computer resources. We show how successfully GP-based multi-agent learning is applied to multi-agent tasks and compare the performance with Q-learning by experiments. Thereafter, we conduct experiments with the evolution of the communicating agents. The communication is an essential factor for the emergence of cooperation. This is because a collaborative agent must be able to handle situations in which conflicts arise and must be capable of negotiating with other agents to reach an agreement. The effectiveness of the emergent communication is empirically shown in terms of the robustness of generated GP programs.

Fitness distributions are employed as tools for understanding the effects of variation operators in Genetic Programming. Eleven operators are analysed on four common benchmark problems by estimating generation dependent features of the fitness distributions, e.g. the probability of improvement and the expected average fitness change.

There are three genetic operators: crossover, mutation and reproduction in Genetic Programming (GP). Among these genetic operators, the crossover operator mainly contributes to searching for a solution program. Therefore, we aim at improving the program generation by extending the crossover operator. The normal crossover selects crossover points randomly and destroys building blocks. We think that building blocks can be protected by swapping larger substructures. In our former work, we proposed a depth-dependent crossover. The depth-dependent crossover protected building blocks and constructed larger building blocks easily by swapping shallower nodes. However, there was problem-dependent characteristics on the depth-dependent crossover, because the depth selection probability was fixed for all nodes in a tree. To solve this difficulty, we propose a self-tuning mechanism for the depth selection probability. We call this type of crossover a self-tuning depth-dependent crossover. We compare GP performances of the selftuning depthdependent crossover with performances of the original depth-dependent crossover. Our experimental results clarify the superiority of the self tuning depth dependent crossover.

Surface reconstruction is a hard 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 digitising 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.

The design of an electrical circuit entails creation of the circuit's topology, sizing, placement, and routing. Each of these tasks is either vexatious or computationally intractable. Design engineers typically perform these tasks sequentially - thus forcing the engineer to grapple with one vexatious or intractable problem after another. We describe a holistic approach to the automatic creation of a circuit's topology, sizing, placement, and routing. This approach starts with a high level statement of the requirements for the desired circuit and uses genetic programming to automatically and simultaneously create the circuit's topology, sizing, placement, and routing. The approach is illustrated with the problem of designing an analog lowpass filter circuit. The fitness measure for a candidate circuit considers the area of the fully laid-out circuit as well as whether the circuit passes or suppresses the appropriate frequencies. Genetic programming requires only about 11/2orders of magnitude more computer time to create the circuit's topology, sizing, placement, and routing than to create the topology and sizing for this illustrative problem.

The phenomenon of growth in program size in genetic programming populations has been widely reported. In a variety of experiments and static analysis we test the standard protective code explanation and find it to be incomplete. We suggest bloat is primarily due to distribution of fitness in the space of possible programs and because of this, in the absence of bias, it is in general inherent in any search technique using a variable length representation. We investigate the fitness landscape produced by program tree-based genetic operators when acting upon points in the search space. We show bloat in common operators is primarily due to the exponential shape of the underlying search space. Nevertheless we demonstrate new operators with considerably reduced bloating characteristics. We also describe mechanisms whereby bloat arises and relate these back to the shape of the search space. Finally we show our simple random walk entropy increasing model is able to predict the shape of evolved programs.

I explore several extensions to genetic programming for applications involving the forecasting of real world chaotic time series. We first used Genetic Symbolic Regression (GSR),which is the standard genetic programming technique applied to the forecasting problem in the same way that it is often applied to symbolic regression problems [ Koza 1992, 1994]. We observed that the performance of GSR depends on the characteristics of the time series, and in particular that it worked better for deterministic time series than it did for stochastic or volatile time series. Taking a hint from this observation, an assumption was made in this study that the dynamics of a time series comprise a deterministic and a stochastic part. By subtracting the model built by GSR for the deterministic part from the original time series, the stochastic part would be obtained as a residual time series. This study noted the possibility that GSR could be used recursively to model the residual time series of rather stochastic dynamics, which may still comprise another deterministic and stochastic part. An algorithm called GRR (Genetic Recursive Regression) has been developed to apply GSR recursively to the sequence of residual time series of stochastic dynamics, giving birth to a sequence of sub-models for deterministic dynamics extractable at each recursive application. At each recursive application and after some termination conditions are met, the submodels become the basis functions for a series-expansion type representation of a model. The numerical coefficients of the model are calculated by the least square method with respect to the predetermined region of the time series data set. When the region includes the latest data set, the model reflects the most recent changes in the dynamics of a time series, thus increasing the forecasting performance. This chapter shows how GRR has been successfully applied to many real world chaotic time series. The results are compared with those from other GSR-like methods and various soft-computing technologies such as neural networks. The results show that GRR saves much computational effort while achieving enhanced forecasting performance for several selected problems.

This chapter describes recent advances in genetic programming of machine code. Evolutionary program induction of binary machine code is one of the fastest 1 GP methods and the most well studied linear approach. The technique has previously been known as Compiling Genetic Programming System (CGPS) but to avoid confusion with methods using an actual compiler and to separate the system from the method, the name has been changed to Automatic Induction of Machine Code with Genetic Programming (AIM-GP). AIM-GP stores individuals as a linear string of native binary machine code, which is directly executed by the processor. The absence of an interpreter and complex memory handling allows increased speed of several orders of magnitudes. AIM-GP has so far been applied to processors with a fixed instruction length (RISC) using integer arithmetics. This chapter describes several new advances to the AIM-GP method which are important for the applicability of the technique. Such advances include enabling the induction of code for CISC processors such as the most widespread computer architecture INTEL x86 as well as JAVA and many embedded processors. The new technique also makes AIM-GP more portable in general and simplifies 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. We also discuss the benefits and drawbacks of register machine GP versus tree-based GP. This chapter is meant to be a directed towards the practitioner, who wants to extend AIM-GP to new architectures and application domains.

Introduction Genetic Programming (GP) [Koza, 1992; Koza, 1994; Banzhaf et al., 1998] is usually seen as quite demanding from the computation load and memory use point of view. So, over the years a number of ideas on how to improve GP performance have been proposed in the literature. We recall the main speedup techniques published to date in Section 13.2. Some of these techniques are now used in many GP implementations. Thanks to this and to the fact that the power of our workstations is increasing exponentially (today's CPUs are now more than 10 times faster than those used in early GP work), nowadays we can run 50 generations a typical GP benchmark problem with a population of 500 individuals in perhaps ten seconds on a normal workstation. Nonetheless, the demand for more and more efficient implementations has not stopped. This is because extensive experimental GP studies (like [Langdon and Poli, 1998] or [Luke and Spector, 1998]) and complex applications (like [Poli, 1996]

we present a novel way of addressing the issue of variable complexity of evolved solutions and a revised interpretation of how Genetic Programming (GP) constructs solutions, based on the rooted-tree schema concept. A rooted-tree schema is a simple relation on the space of tree-shaped structures which provides a quantifiable partitioning of the search space. Formal manipulation of rooted-tree schemata allows: (1) The role of the size in the selection and survival of evolved expressions to be made explicit; (2) The interrelationship between parsimony penalty, size, and fitness of evolved expressions to be clarified and better understood; (3) The introduction of alternative approaches to evolving parsimonious solutions by preventing rooted-tree schema from bloating. The rooted-tree schema concept provides a top-down perspective of how program expressions are evolved, contrary to the common belief that small pieces of code, or building blocks, are gradually assembled to create solutions. Analysis shows that GP, while it improves solutions, combines both bottom-up and top-down refinement strategies.

We discuss the application of genetic programming (GP) to the problem of robust language understanding in the context of a large scale multi-lingual speech-to-speech translation system. Efficiently and effectively processing sentences outside of the coverage of a system's linguistic knowledge sources is still an open problem in computational linguistics, a problem that must be faced if natural language interfaces will ever be practical. In this chapter, the GP based ROSE approach to robust language understanding is demonstrated to yield a significantly better time/quality trade-off than previous non-GP approaches. GP is used to search for the optimal way to assemble fragments of a meaning representation. The ROSE approach is the first application of a program induction technique to a problem of this type.

This chapter describes a Genetic Programming system, Paragen, which transforms serial programs into functionally identical parallel programs. Unlike most other GP systems, it is possible to prove that the programs generated by the system are functionally identical. The ability to prove that the output of a GP run is correct has greatly improved the chances of GP being used in a commercial situation.

Quantum computers are computational devices that use the dynamics of atomic-scale objects to store and manipulate information. Only a few, small-scale quantum computers have been built to date, but quantum computers can in principle outperform all possible classical computers in significant ways. Quantum computation is therefore a subject of considerable theoretical interest that may also have practical applications in the future. Genetic programming can automatically discover new algorithms for quantum computers [spector:1998:GPqc]. We describe how to simulate a quantum computer so that the fitness of a quantum algorithm can be determined on classical hardware. We then describe ways in which three different genetic programming approaches can drive the simulator to evolve new quantum algorithms. The approaches are standard tree-based genetic programming, stack-based linear genome genetic programming, and stackless linear genome genetic programming. We demonstrate the techniques on four different problems: the two-bit early promise problem, the scaling majority-on problem, the four-item database search problem, and the two-bit and-or problem. For three of these problems (all but majority-on) the automatically discovered algorithms are more efficient than any possible classical algorithms for the same problems. One of the better-than-classical algorithms (for the two-bit and-or problem) is in fact more efficient than any previously known quantum algorithm for the same problem, suggesting that genetic programming may be a valuable tool in the future study of quantum programming.

Welcome to the third volume of Advances in Genetic Programming series. The Genetic Programming (GP) field has matured considerably since the first two volumes were produced in conjunction with workshops held at the International Conference on Genetic Algorithms (ICGA) [kinnear:book,book:1996:aigp2]. During the 1993 and 1995 ICGA conferences the interest in GP was strong but within this broader community there were only a few presentation and publication slots for GP work. The Advances volumes therefore provided an important outlet for creative new work in GP. Interest in GP continued to grow and there is now a separate annual conference on GP in the USA, as well as a European workshop on GP and several other conferences that regularly feature GP themes (see Section 1.2).

There is a fundamental problem with genetic programming as it is currently practised, the genetic re- combination operators that drive the learning process act at random, without regard to how the internal components of the programs to be recombined behaved during training. This research introduces a method of program transformations that is principled, based on the program's internal behaviour, and significantly more likely than random local sampling to improve the transformed programs' fitness values. The contribution of our research is a detailed approach by which principled credit-blame assignment can be brought to GP and that credit-blame assignment can be focused to improve that same evolutionary process. This principled credit-blame assignment is done through a new program representation called neural programming and applied through a set of principled processes called, collectively, internal reinforcement in neural programming. This internal reinforcement of evolving programs is presented here as a first step toward the desired gradient descent in program space.

We describes the application of a grammatically-based Genetic Programming system to discover rainfall-runoff relationships for two vastly different catchments. A context-free grammar is used to define the search space for the mathematical language used to express the evolving programs. A daily time series of rainfall-runoff is used to train the evolving population. A deterministic lumped parameter model, based on the unit hydrograph, is compared with the results of the evolved models on an independent data set. The favourable results of the Genetic Programming approach show that machine learning techniques are potentially a useful tool for developing hydrological models, especially when the relationship between rainfall and runoff is poor.

Genetic programming provides a useful paradigm for developing multiagent systems in the domains where human programming alone is not sufficient to take into account all the details of possible situations. However, existing GP methods attempt to evolve collective behavior immediately from primitive actions. More realistic tasks require several emergent behaviors and a proper coordination of these is essential for success. We have recently proposed a framework, called fitness switching, to facilitate learning to coordinate composite emergent behaviors using genetic programming. Coevolutionary fitness switching described in this chapter extends our previous work by introducing the concept of coevolution for more effective implementation of fitness switching. Performance of the presented method is evaluated on the table transport problem and a simple version of simulated robot soccer problem. Simulation results show that coevolutionary fitness switching provides an effective mechanism for learning complex collective behaviors which may not be evolved by simple genetic programming.