THE DYNAMICS OF A GENETIC ALGORITHM FOR A SIMPLE LEARNING-PROBLEM

A formalism for describing the dynamics of genetic algorithms (GAs) us ing methods from statistical mechanics is applied to the problem of ge neralization in a perceptron with binary weights. The dynamics are sol ved for the case where a new batch of training patterns is presented t o each population member each generation, which considerably simplifie s the calculation. The theory is shown to agree closely to simulations of a real GA averaged over many runs, accurately predicting the mean best solution found. For weak selection and large problem size the dif ference equations describing the dynamics can be expressed analyticall y and we find that the effects of noise due to the finite size of each training batch can be removed by increasing the population size appro priately. If this population resizing is used, one can deduce the most computationally efficient size of training batch each generation. For independent patterns this choice also gives the minimum total number of training patterns used. Although using independent patterns is a ve ry inefficient use of training patterns in general, this work may also prove useful for determining the optimum batch size in the case where patterns are recycled.