EFFECTIVE DEGREES OF FREEDOM IN GENETIC ALGORITHMS

An evolution equation for a population of strings evolving under the g enetic operators, selection, mutation, and crossover, is derived. The corresponding equation describing the evolution of schemata is found b y performing an exact coarse graining of this equation. In particular, exact expressions for schema reconstruction are derived that allow fo r a critical appraisal of the ''building-block hypothesis'' of genetic algorithms. A further coarse graining is made by considering the cont ribution of all length-l schemata to the evolution of population obser vables such as fitness growth. As a test function for investigating th e emergence of structure in the evolution, the increase per generation of the in-schemata fitness averaged over all schemata of length l, De lta(l), is introduced. In finding solutions to the evolution equations we concentrate more on the effects of crossover; in particular, we co nsider crossover in the context of Kauffman Nk models with k=0,2. For k=0, with a random initial population, in the first step of evolution the contribution from schema reconstruction is equal to that of schema destruction leading to a scale invariant situation where the contribu tion to fitness of schemata of size l is independent of l. This balanc e is broken in the next step of evolution, leading to a. situation whe re schemata that are either much larger or much smaller than half the string size dominate those with l approximate to N/2. The balance betw een block destruction and reconstruction is also broken in a k>0 lands cape. It is conjectured that the effective degrees of freedom for such landscapes are landscape connective trees that break down into effect ively fit smaller blocks, and not the blocks themselves. Numerical sim ulations confirm this ''connective tree hypothesis'' by showing that c orrelations drop off with connective distance and not with intrachromo somal distance.