General schema theory for genetic programming with subtree-swapping crossover: Part II

This paper is the second part of a two-part paper which introduces a general schema theory for genetic programming (GP) with subtree-swapping crossover (Part I (Poli and McPhee, 2003)). Like other recent GP schema theory results, the theory gives an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. The theory is based on a Cartesian node reference system, introduced in Part I, and on the notion of a variable-arity hyperschema, introduced here, which generalises previous definitions of a schema. The theory includes two main theorems describing the propagation of GP schemata: a microscopic and a macroscopic schema theorem. The microscopic version is applicable to crossover operators which replace a subtree in one parent with a subtree from the other parent to produce the offspring. Therefore, this theorem is applicable to Koza's GP crossover with and without uniform selection of the crossover points, as well as one-point crossover, size-fair crossover, strongly-typed GP crossover, context-preserving crossover and many others. The macroscopic version is applicable to crossover operators in which the probability of selecting any two crossover points in the parents depends only on the parents' size and shape. In the paper we provide examples, we show how the theory can be specialised to specific crossover operators and we illustrate how it can be used to derive other general results. These include an exact definition of effective fitness and a size-evolution equation for GP with subtree-swapping crossover.     

Exact Schema Theory and Markov Chain Models for Genetic Programming and Variable-length Genetic Algorithms with Homologous Crossover

Genetic Programming (GP) homologous crossovers are a group of operators, including GP one-point crossover and GP uniform crossover, where the offspring are created preserving the position of the genetic material taken from the parents. In this paper we present an exact schema theory for GP and variable-length Genetic Algorithms (GAs) which is applicable to this class of operators. The theory is based on the concepts of GP crossover masks and GP recombination distributions that are generalisations of the corresponding notions used in GA theory and in population genetics, as well as the notions of hyperschema and node reference systems, which are specifically required when dealing with variable size representations.In this paper we also present a Markov chain model for GP and variable-length GAs with homologous crossover. We obtain this result by using the core of Vose's model for GAs in conjunction with the GP schema theory just described. The model is then specialised for the case of GP operating on 0/1 trees: a tree-like generalisation of the concept of binary string. For these, symmetries exist that can be exploited to obtain further simplifications.In the absence of mutation, the Markov chain model presented here generalises Vose's GA model to GP and variable-length GAs. Likewise, our schema theory generalises and refines a variety of previous results in GP and GA theory.     

Schema theory for genetic programming with one-point crossover and point mutation

We review the main results obtained in the theory of schemata in genetic programming (GP), emphasizing their strengths and weaknesses. Then we propose a new, simpler definition of the concept of schema for GP, which is closer to the original concept of schema in genetic algorithms (GAs). Along with a new form of crossover, one-point crossover, and point mutation, this concept of schema has been used to derive an improved schema theorem for GP that describes the propagation of schemata from one generation to the next. We discuss this result and show that our schema theorem is the natural counterpart for GP of the schema theorem for GAs, to which it asymptotically converges.     

一种线性表示的遗传程序设计方法研究

遗传程序设计领域中的一个重要研究内容是如何有效地表示进化的个体（计算机程序），对采用树的线性后缀形式的个体进行位置信息编码以实现多种形式的遗传操作，并给出形式化定义，设计并实现了一个基于栈的遗传程序设计算法，通过模拟实验比较了各操作的性能，这种编码方式可以扩展到程序的线性结构中，以实现特定的遗传操作，显示出线性表示具有适于解决不同问题的可行性和灵活性，还给出了基于串的一点交叉的线性遗传程序设计的模式理论，它可以把标准遗传算法的模式生成机制统一到该理论框架中。     

Understanding the biases of generalised recombination: part I

This is the first part of a two-part paper where we propose, model theoretically and study a general notion of recombination for fixed-length strings, where homologous recombination, inversion, gene duplication, gene deletion, diploidy and more are just special cases. The analysis of the model reveals that the notion of schema emerges naturally from the model's equations. In Part I, after describing and characterising the notion of generalised recombination, we derive both microscopic and coarse-grained evolution equations for strings and schemata and illustrate their features with simple examples. Also, we explain the hierarchical nature of the schema evolution equations and show how the theory presented here generalises past work in evolutionary computation. In Part II, the study provides a variety of fixed points for evolution in the case where recombination is used alone, which generalise Geiringer's theorem. In addition, we numerically integrate the infinite-population schema equations for some interesting problems, where selection and recombination are used together to illustrate how these operators interact. Finally, to assess by how much genetic drift can make a system deviate from the infinite-population-model predictions we discuss the results of real GA runs for the same model problems with generalised recombination, selection and finite populations of different sizes.     

Exact Schema Theory for Genetic Programming and Variable-Length Genetic Algorithms with One-Point Crossover

A few schema theorems for genetic programming (GP) have been proposed in the literature in the last few years. Since they consider schema survival and disruption only, they can only provide a lower bound for the expected value of the number of instances of a given schema at the next generation rather than an exact value. This paper presents theoretical results for GP with one-point crossover which overcome this problem. First, we give an exact formulation for the expected number of instances of a schema at the next generation in terms of microscopic quantities. Due to this formulation we are then able to provide an improved version of an earlier GP schema theorem in which some (but not all) schema creation events are accounted for. Then, we extend this result to obtain an exact formulation in terms of macroscopic quantities which makes all the mechanisms of schema creation explicit. This theorem allows the exact formulation of the notion of effective fitness in GP and opens the way to future work on GP convergence, population sizing, operator biases, and bloat, to mention only some of the possibilities.     

Semantic schema modeling for genetic programming using clustering of building blocks

Semantic schema theory is a theoretical model used to describe the behavior of evolutionary algorithms. It partitions the search space to schemata, defined in semantic level, and studies their distribution during the evolution. Semantic schema theory has definite advantages over popular syntactic schema theories, for which the reliability and usefulness are criticized. Integrating semantic awareness in genetic programming (GP) in recent years sheds new light also on schema theory investigations. This paper extends the recent work in semantic schema theory of GP by utilizing information based clustering. To this end, we first define the notion of semantics for a tree based on the mutual information between its output vector and the target and introduce semantic building blocks to facilitate the modeling of semantic schema. Then, we propose information based clustering to cluster the building blocks. Trees are then represented in terms of the active occurrence of building block clusters and schema instances are characterized by an instantiation function over this representation. Finally, the expected number of schema samples is predicted by the suggested theory. In order to evaluate the suggested schema, several experiments were conducted and the generalization, diversity preserving capability and efficiency of the schema were investigated. The results are encouraging and remarkably promising compared with the existing semantic schema.     

Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control

Genetic programming (GP) is one of the most widely used paradigms of evolutionary computation due to its ability to automatically synthesize computer programs and mathematical expressions. However, because GP uses a variable length representation, the individuals within the evolving population tend to grow rapidly without a corresponding return in fitness improvement, a phenomenon known as bloat. In this paper, we present a simple bloat control strategy for standard tree-based GP that achieves a one order of magnitude reduction in bloat when compared with standard GP on benchmark tests, and practically eliminates bloat on two real-world problems. Our proposal is to substitute standard subtree crossover with the one-point crossover (OPX) developed by Poli and Langdon (Second online world conference on soft computing in engineering design and manufacturing, Springer, Berlin (1997)), while maintaining all other GP aspects standard, particularly subtree mutation. OPX was proposed for theoretical purposes related to GP schema theorems, however since it curtails exploration during the search it has never achieved widespread use. In our results, on the other hand, we are able to show that OPX can indeed perform an effective search if it is coupled with subtree mutation, thus combining the bloat control capabilities of OPX with the exploration provided by standard mutation.     

Conjugate schema and basis representation of crossover and mutation operators

In genetic search algorithms and optimization routines, the representation of the mutation and crossover operators are typically defaulted to the canonical basis. We show that this can be influential in the usefulness of the search algorithm. We then pose the question of how to find a basis for which the search algorithm is most useful. The conjugate schema is introduced as a general mathematical construct and is shown to separate a function into smaller dimensional functions whose sum is the original function. It is shown that conjugate schema, when used on a test suite of functions, improves the performance of the search algorithm on 10 out of 12 of these functions. Finally, a rigorous but abbreviated mathematical derivation is given in the appendices.     

Semantic schema theory for genetic programming

Schema theory is the most well-known model of evolutionary algorithms. Imitating from genetic algorithms (GA), nearly all schemata defined for genetic programming (GP) refer to a set of points in the search space that share some syntactic characteristics. In GP, syntactically similar individuals do not necessarily have similar semantics. The instances of a syntactic schema do not behave similarly, hence the corresponding schema theory becomes unreliable. Therefore, these theories have been rarely used to improve the performance of GP. The main objective of this study is to propose a schema theory which could be a more realistic model for GP and could be potentially employed for improving GP in practice. To achieve this aim, the concept of semantic schema is introduced. This schema partitions the search space according to semantics of trees, regardless of their syntactic variety. We interpret the semantics of a tree in terms of the mutual information between its output and the target. The semantic schema is characterized by a set of semantic building blocks and their joint probability distribution. After introducing the semantic building blocks, an algorithm for finding them in a given population is presented. An extraction method that looks for the most significant schema of the population is provided. Moreover, an exact microscopic schema theorem is suggested that predicts the expected number of schema samples in the next generation. Experimental results demonstrate the capability of the proposed schema definition in representing the semantics of the schema instances. It is also revealed that the semantic schema theorem estimation is more realistic than previously defined schemata.     

Theoretical results in genetic programming: the next ten years?

We consider the theoretical results in GP so far and prospective areas for the future. We begin by reviewing the state of the art in genetic programming (GP) theory including: schema theories, Markov chain models, the distribution of functionality in program search spaces, the problem of bloat, the applicability of the no-free-lunch theory to GP, and how we can estimate the difficulty of problems before actually running the system. We then look at how each of these areas might develop in the next decade, considering also new possible avenues for theory, the challenges ahead and the open issues.     

Understanding the biases of generalised recombination: part II

This is the second part of a two-part paper where we propose, model theoretically and study a general notion of recombination for fixed-length strings where homologous recombination, inversion, gene duplication, gene deletion, diploidy and more are just special cases. In Part I, we derived both microscopic and coarse-grained evolution equations for strings and schemata for a selecto-recombinative GA using generalised recombination, and we explained the hierarchical nature of the schema evolution equations. In this part, we provide a variety of fixed points for evolution in the case where recombination is used alone, thereby generalising Geiringer's theorem. In addition, we numerically integrate the infinite-population schema equations for some interesting problems, where selection and recombination are used together to illustrate how these operators interact. Finally, to assess by how much genetic drift can make a system deviate from the infinite-population-model predictions we discuss the results of real GA runs for the same model problems with generalised recombination, selection and finite populations of different sizes.     

进化算法中的模式定理及建筑块

探讨了进化算法中的模式定理及建筑块理论．通过引入模式进化、模式进化能力、适度模式等概念，以标准遗传算法为例，证明了在变异算子独立的条件下，进化算法中模式的构成与多点交叉和变异的顺序无关，然后证明了具有强进化能力的模式，将以指数阶增长．该文的模式理论有别于Holland等人提出的模式理论，特别是在交叉算子上采用了多点交叉算子，给出了相应的公式；并从这一推导过程论证了建筑块假设的合理性，可以称之为建筑块理论．     

Depth-control strategies for crossover in tree-based genetic programming

The standard subtree crossover operator in the tree-based genetic programming (GP) has been considered as problematic. In order to improve the standard subtree crossover, controlling depth of crossover points becomes a research topic. However, the existence of many different and inconsistent crossover depth-control schemes and the possibility of many other depth-control schemes make the identification of good depth-control schemes a challenging problem. This paper aims to investigate general heuristics for making good depth-control schemes for crossover in tree-based GP. It analyses the patterns of depth of crossover points in good predecessor programs of five GP systems that use the standard subtree crossover and four approximations of the optimal crossover operator on three problems in different domains. The analysis results show that an effective depth-control scheme is problem-dependent and evolutionary stage-dependent, and that good crossover events have a strong preference for roots and (less strongly) bottoms of parent program trees. The results also show that some ranges of depths between the roots and the bottoms are also preferred, suggesting that unequal-depth-selection-probability strategies are better than equal-depth-selection-probability strategies.     

Revising Z: Part II – logical development

This is the second of two related papers. In “Revising Z: Part I - logic and semantics” (this journal) we introduced a simple specification logic Z _C comprising a logic and a semantics (in ZF set theory). We then provided an interpretation for (a rational reconstruction of) the specification language Z within Z _C . As a result we obtained a sound logic for Z, including the basic schema calculus. In this paper we extend the basic framework with more sophisticated features (including schema operations) and we mount a critique of a number of concepts used in Z. We further demonstrate that the complications and confusions which these concepts introduce can be avoided without compromising expressibility. Received March 1998 / Accepted in revised form April 1999     

An extension of Geiringer's theorem for a wide class of evolutionary search algorithms

The frequency with which various elements of the search space of a given evolutionary algorithm are sampled is affected by the family of recombination (reproduction) operators. The original Geiringer theorem tells us the limiting frequency of occurrence of a given individual under repeated application of crossover alone for the classical genetic algorithm. Recently, Geiringer's theorem has been generalized to include the case of linear GP with homologous crossover (which can also be thought of as a variable length GA). In the current paper we prove a general theorem which tells us that under rather mild conditions on a given evolutionary algorithm, call it A, the stationary distribution of a certain Markov chain of populations in the absence of selection is unique and uniform. This theorem not only implies the already existing versions of Geiringer's theorem, but also provides a recipe of how to obtain similar facts for a rather wide class of evolutionary algorithms. The techniques which are used to prove this theorem involve a classical fact about random walks on a group and may allow us to compute and/or estimate the eigenvalues of the corresponding Markov transition matrix which is directly related to the rate of convergence towards the unique limiting distribution.     

A mosaic of Chu spaces and Channel Theory I: Category-theoretic concepts and tools

Chu Spaces and Channel Theory are well-established areas of investigation in the general context of category theory when applied to semantically-based information flow. In this Part I of a two-part work, we review a range of related concepts and examples showing how these methods can be applied to logic and computer science, including Formal Concept Analysis, distributed systems and ontology development. We also discuss spatial coarse-graining in relationship to information, and in this direction we establish some basic simplicial and categorical techniques which will supplement the other methods of this Part I when they are applied to characterise visual object identification and the inference of mereological (i.e. part-whole) complexity in Part II.     

A new crossover operator in genetic programming for object classification.

The crossover operator has been considered "the centre of the storm" in genetic programming (GP). However, many existing GP approaches to object recognition suggest that the standard GP crossover is not sufficiently powerful in producing good child programs due to the totally random choice of the crossover points. To deal with this problem, this paper introduces an approach with a new crossover operator in GP for object recognition, particularly object classification. In this approach, a local hill-climbing search is used in constructing good building blocks, a weight called looseness is introduced to identify the good building blocks in individual programs, and the looseness values are used as heuristics in choosing appropriate crossover points to preserve good building blocks. This approach is examined and compared with the standard crossover operator and the headless chicken crossover (HCC) method on a sequence of object classification problems. The results suggest that this approach outperforms the HCC, the standard crossover, and the standard crossover operator with hill climbing on all of these problems in terms of the classification accuracy. Although this approach spends a bit longer time than the standard crossover operator, it significantly improves the system efficiency over the HCC method.     

A data model and a query languagefor multimedia documents databases

A multimedia application involves information that may be in a form of video, images, audio, text and graphics, need to be stored, retrieved and manipulated in large databases. In this paper, we propose an object-oriented database schema that supports multimedia documents and their temporal, spatial and logical structures. We present a document example and show how the schema can adress all the structures described. We also present a multimedia query specification language that can be used to describe a multimedia content portion to be retrieved from the database. The language provides means by which the user can specify the information on the media as well as the temoral and spatial relationships among these media.     

Structural search spaces and genetic operators

In a previous paper (Rowe et al., 2002), aspects of the theory of genetic algorithms were generalised to the case where the search space, omega, had an arbitrary group action defined on it. Conditions under which genetic operators respect certain subsets of omega were identified, leading to a generalisation of the term schema. In this paper, search space groups with more detailed structure are examined. We define the class of structural crossover operators that respect certain schemata in these groups, which leads to a generalised schema theorem. Recent results concerning the Fourier (or Walsh) transform are generalised. In particular, it is shown that the matrix group representing omega can be simultaneously diagonalised if and only if omega is Abelian. Some results concerning structural crossover and mutation are given for this case.