Session:

TUT - Tutorials

Title:

Taxonomy and Coarse Graining in EC

Authors:

Christopher Stephens

Abstract:

The theory of genetic dynamics, in both population biology and evolutionary computation, is difficult. In the latter it is also relatively undeveloped, there existing many different types of evolutionary algorithm, such as genetic algorithms, genetic programming, evolutionary strategies etc. whose theoretical relationships are not very clear. Even for a particular type of algorithm, such as genetic algorithms, the theoretical underpinnings have traditionally consisted of apparently antagonistic elements such as, on one side, Holland's Schema theorem, the associated Building Block Hypothesis, and on the other side, exact, microscopic models such as the Vose model. Besides offering a conceptual, qualitative understanding theory should also make quantitative predictions. In this aspect "engineering-type", approximate models have had more success than their more mathematically rigorous, exact counterparts. However, there are still no known systematic, general approximation schemes for describing the dynamics of an evolutionary algorithm. Theoretical understanding is greatly facilitated by an adequate taxonomy - a practical example being the periodic table in chemistry. In this tutorial I show how recent developments in exact, coarse-grained (schema-based) formulations of genetic dynamics point the way to a more adequate taxonomy of evolutionary algorithms. In particular, I will show how genetic algorithms and genetic programming can be "unified" in this way, leading to exact schema theorems for both, a deeper, more rigorous understanding of Holland's Schema theorem and the Building Block hypothesis, an extension of these to genetic programming, and a reconciliation of them with microscopic formulations such as the Vose model. We will see how the different formulations are simply coordinate transformations of one another in the space of representations. I will also show how tools and concepts from theoretical physics, such as the renormalization group, can further the theoretical understanding of genetic dynamics and also offer potential systematic approximation schemes for describing them.