Form invariance and implicit parallelism

Covariant genetic dynamics

We present a covariant form for the dynamics of a canonical GA of arbitrary cardinality, showing how each genetic operator can be uniquely represented by a mathematical object - a tensor - that transforms simply under a general linear coordinate transformation. For mutation and recombination these tensors can be written as tensor products of the analogous tensors for one-bit strings thus giving a greatly simplified formulation of the dynamics. We analyze the three most well known coordinate systems -- string, Walsh and Building Block - discussing their relative advantages and disadvantages with respect to the different operators, showing how one may transform from one to the other, and that the associated coordinate transformation matrices can be written as a tensor product of the corresponding one-bit matrices. We also show that in the Building Block basis the dynamical equations for all Building Blocks can be generated from the equation for the most fine-grained block (string) by a certain projection ("zapping").

Crossover invariant subsets of the search space for evolutionary algorithms

This paper addresses the relationship between schemata and crossover operators. In Appendix A a general mathematical framework is developed which reveals an interesting correspondence between the families of reproduction transformations and the corresponding collections of invariant subsets of the search space. On the basis of this mathematical apparatus it is proved that the family of masked crossovers is, for all practical purposes, the largest family of transformations whose corresponding collection of invariant subsets is the family of Antonisse's schemata. In the process, a number of other interesting facts are shown. It is proved that the full dynastic span of a given subset of the search space under either one of the traditional families of crossover transformations (one-point crossovers or masked crossovers) is obtained after [log2n] iterations where n is the dimension of the search space. The generalized notion of invariance introduced in the current paper unifies Radcliffe's notions of "respect" and "gene transmission". Besides providing basic tools for the theoretical analysis carried out in the current paper, the general facts established in Appendix A provide a way to extend Radcliffe's notion of "genetic representation function" to compare various evolutionary computation techniques via their representation.

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.

Quantitative structure-activity relationships by evolved neural networks for the inhibition of dihydrofolate reductase by pyrimidines

Evolutionary computation provides a useful method for training neural networks in the face of multiple local optima. This paper begins with a description of methods for quantitative structure activity relationships (QSAR). An overview of artificial neural networks for pattern recognition problems such as QSAR is presented and extended with the description of how evolutionary computation can be used to evolve neural networks. Experiments are conducted to examine QSAR for the inhibition of dihydrofolate reductase by pyrimidines using evolved neural networks. Results indicate the utility of evolutionary algorithms and neural networks for the predictive task at hand. Furthermore, results that are comparable or perhaps better than those published previously were obtained using only a small fraction of the previously required degrees of freedom.