[Next] [Previous] [Top] [Contents]

Meta-Genetic Programming: Co-evolving the Operators of Variation - Bruce Edmonds

1. Introduction

Evolutionary algorithms are relatively robust over many problem domains. It is for this reason that they are often chosen for use where there is little domain knowledge. However for particular problem domains their performance can often be improved by tuning the parameters of the algorithm. The most studied example of this is the ideal mix of crossover and mutation in genetic algorithms. One possible compromise in this regard is to let such parameters be adjusted (or even evolve) along with the population of solutions so that the general performance can be improved without losing the generality of the algorithm*1. The most frequently quoted is [4], which investigates the incremental tuning of parameters depending on the success of the operators in initially converged populations.

Such techniques have also been applied in genetic programming (GP)*2. This usually involved the storing of extra information to guide the algorithm, for example in [2] extra genetic material is introduced to record a weight effecting where the tree-crossover operator will act. As [1] says, "There is not reason to believe that having only one level of adaption in an evolutionary computation is optimal" (page 161).

In genetic programming the genetic operators are usually fixed by the programmer. Typically these are a variety of crossover and propagation, but can also include others, for example mutation. A variety of alternative operators have been invented and investigated (e.g. [2]). It is usually found that, at least for some problems these preform better than the `classic' mix*3 of mostly tree-crossover and some propagation (e.g. [3]).

Meta-Genetic Programming (MGP) encodes these operators as trees. These "act" on other tree structures to produce the next generation. This representation allows the simultaneous evolution of the operators along with the population of solutions. In this technique what is co-evolved along with the base population is not a fixed set of parameters or extra genetic material associated with each gene, by operators who are themselves encoded as variable length representations - so their form as well as their preponderance can be evolved..

This technique introduces extra computational cost, which must be weighed against any advantage gained. Also the technique turns out to be very sensitive to biases in the syntax from which the operators are generated, it is thus much less robust.

Iterating this technique can involve populations of operators acting on populations of operators acting on populations etc., and even populations acting on themselves. This allows a range of techniques to be considered within a common framework - even allowing the introduction of deductive operators such as Modus Ponens to be included.

In section 2., I describe the basic technique in more detail. In section 5., I describe the use of possible elaborations of MGP to provide a coherent framework for the analysis of a wide range of such structures. I test a few configurations of MGP on the parity problem at different levels of difficulty in section 4., followed by a general discussion (section 7.). I finish with a small sample of the further work that needs to be done about this technique in section 8..

Meta-Genetic Programming: Co-evolving the Operators of Variation - Bruce Edmonds - 28 JAN 98
[Next] [Previous] [Top] [Contents]

Generated with CERN WebMaker