Analysis of the Effective Degrees of Freedom in Genetic Algorithms

Details Analysis of the Effective Degrees of Freedom in Genetic Algorithms Analysis of the Effective Degrees of Freedom in Genetic Algorithms

1996-11-13

arxiv.org/abs/adap-org/9611005v1

Physics

Condensed Matter

31 pages, TeX source, please email the authors for a hard copy including figures

Scientific paper

An evolution equation for a population of strings evolving under the genetic operators: selection, mutation and crossover is derived. The corresponding equation describing the evolution of schematas is found by performing an exact coarse graining of this equation. In particular exact expressions for schemata reconstruction are derived which allows for a critical appraisal of the ``building-block hypothesis'' of genetic algorithms. A further coarse-graining is made by considering the contribution of all length-l schematas to the evolution of population observables such as fitness growth. As a test function for investigating the emergence of structure in the evolution the increase per generation of the in-schemata fitness averaged over all schematas of length l, $\Delta_l$, is introduced. In finding solutions of the evolution equations we concentrate more on the effects of crossover, in particular we consider 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 schemata reconstruction is equal to that of schemata destruction leading to a scale invariant situation where the contribution to fitness of schematas of size l is independent of l. This balance is broken in the next step of evolution leading to a situation where schematas that are either much larger or much smaller than half the string size dominate over those with $l \approx N/2$. The balance between block destruction and reconstruction is also broken in a k>0 landscape. It is conjectured that the effective degrees of freedom for such landscapes are landscape connective trees that break down into effectively fit smaller blocks, and not the blocks themselves. Numerical simulations confirm this ``connective tree hypothesis'' by showing that correlations drop off with connective distance and not with intrachromosomal distance.

Affiliated with

Also associated with

No associations

Rating

Analysis of the Effective Degrees of Freedom in Genetic Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of the Effective Degrees of Freedom in Genetic Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of the Effective Degrees of Freedom in Genetic Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-598946