Genetic algorithms and fitness variance with an application to the automated design of artificial neural networks
William Michael Rudnick · 1992
Existing genetic algorithm (GA) theory addresses how schema fitness serves as a measure of the expected increase or decrease of schema representation within the population. The work presented here considers how schema fitness variance affects schema representation through GA decision-making. It has long been known that the more significant bits of binary coded parameters converge before bits of lesser significance. This phenomenon, called domino convergence, is explored using the identity problem, f(x) = x. Sometimes convergence stops prematurely (a phenomenon called convergence stall), depending upon the relative magnitude of the mutation rate and the length of the encoding string. Analyses and models are presented exploring various aspects of these phenomena. GA convergence occurs in competition partitions. Each partition has an associated signal (measure of the force tending towards correct decision-making within that partition) and noise (measure of the force hindering correct decision-making). Which has the upper hand within a particular partition determines if the GA chooses correctly between competing schemata, which in turn determines convergence in the partition. Signal, noise, and the signal-to-noise ratio (SNR) are each defined in terms of fitness variance, with the SNR reconciling the conflicting effects of signal and noise. Formulas for the flat-population schema fitness variance, signal, noise, and SNR are derived using the Walsh basis. Both domino convergence and convergence stall are examined from the signal versus noise perspective. Designing an artificial neural network (ANN) for a specified problem can be difficult. Since the design of biological neural networks is a result of evolution, evolutionary search techniques may be well suited to network design. Back-propagation is known to generalize well on the contiguity problem (counting the number of clumps of 1s in a binary input field) when hidden layer receptive fields are narrow, but with high performance variance (noise) due to local minima. Evolutionary network design is used as a case study in applying GAs to a difficult, noisy problem. A program called GAND, genetic algorithms for network design, is described and tested on the contiguity problem. A number of techniques are presented that allow GAND, starting with randomly generated network interconnections, to evolve architectures rivaling the best produced by hand.