The dynamics of a genetic algorithm for a simple learning problem

A formalism for describing the dynamics of Genetic Algorithms (GAs) using method s from statistical mechanics is applied to the problem of generalization in a perceptron with binary weights. The dynamics are solved for the case where a new batch of training patterns is presented to each population member each generation, which considerably simplifies 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 difference equations describing the dynamics can be expressed analytically 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 appropriately. 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 very 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.

Modelling the dynamics of genetic algorithms using statistical mechanics

A formalism for modelling the dynamics of Genetic Algorithms (GAs) using methods from statistical mechanics, originally due to Prugel-Bennett and Shapiro, is reviewed, generalized and improved upon. This formalism can be used to predict the averaged trajectory of macroscopic statistics describing the GA's population. These macroscopics are chosen to average well between runs, so that fluctuations from mean behaviour can often be neglected. Where necessary, non-trivial terms are determined by assuming maximum entropy with constraints on known macroscopics. Problems of realistic size are described in compact form and finite population effects are included, often proving to be of fundamental importance. The macroscopics used here are cumulants of an appropriate quantity within the population and the mean correlation (Hamming distance) within the population. Including the correlation as an explicit macroscopic provides a significant improvement over the original formulation. The formalism is applied to a number of simple optimization problems in order to determine its predictive power and to gain insight into GA dynamics. Problems which are most amenable to analysis come from the class where alleles within the genotype contribute additively to the phenotype. This class can be treated with some generality, including problems with inhomogeneous contributions from each site, non-linear or noisy fitness measures, simple diploid representations and temporally varying fitness. The results can also be applied to a simple learning problem, generalization in a binary perceptron, and a limit is identified for which the optimal training batch size can be determined for this problem. The theory is compared to averaged results from a real GA in each case, showing excellent agreement if the maximum entropy principle holds. Some situations where this approximation brakes down are identified. In order to fully test the formalism, an attempt is made on the strong sc np-hard problem of storing random patterns in a binary perceptron. Here, the relationship between the genotype and phenotype (training error) is strongly non-linear. Mutation is modelled under the assumption that perceptron configurations are typical of perceptrons with a given training error. Unfortunately, this assumption does not provide a good approximation in general. It is conjectured that perceptron configurations would have to be constrained by other statistics in order to accurately model mutation for this problem. Issues arising from this study are discussed in conclusion and some possible areas of further research are outlined.

Representation and parameterisation issues in genetic algorithms

A multi-chromosome GA (Multi-GA) was developed, based upon concepts from the natural world, allowing improved flexibility in a number of areas including representation, genetic operators, their parameter rates and real world multi-dimensional applications. A series of experiments were conducted, comparing the performance of the Multi-GA to a traditional GA on a number of recognised and increasingly complex test optimisation surfaces, with promising results. Further experiments demonstrated the Multi-GA's flexibility through the use of non-binary chromosome representations and its applicability to dynamic parameterisation. A number of alternative and new methods of dynamic parameterisation were investigated, in addition to a new non-binary 'Quotient crossover' mechanism. Finally, the Multi-GA was applied to two real world problems, demonstrating its ability to handle mixed type chromosomes within an individual, the limited use of a chromosome level fitness function, the introduction of new genetic operators for structural self-adaptation and its viability as a serious real world analysis tool. The first problem involved optimum placement of computers within a building, allowing the Multi-GA to use multiple chromosomes with different type representations and different operators in a single individual. The second problem, commonly associated with Geographical Information Systems (GIS), required a spatial analysis location of the optimum number and distribution of retail sites over two different population grids. In applying the Multi-GA, two new genetic operators (addition and deletion) were developed and explored, resulting in the definition of a mechanism for self-modification of genetic material within the Multi-GA structure and a study of this behaviour.

Human intervertebral disc cells promote nerve growth over substrata of human intervertebral disc aggrecan

Study Design. Coculture assays of the migration and interaction of human intervertebral disc cells and chick sensory nerves on alternate substrata of collagen and aggrecan. Objective. To examine the effects of aggrecan on disc cell migration, how disc cells and sensory nerves interact, and whether disc cells affect previously reported inhibitory effects of aggrecan on sensory nerve growth. Summary of Background Data. Human intervertebral disc aggrecan is inhibitory to sensory nerve growth in vitro, suggesting that a loss of aggrecan from the disc may have a role in the increased innervation seen in disc degeneration. Endothelial cells that appear to co-migrate with nerves into degenerated intervertebral disc express neurotrophic factors, but the effects of disc cells on nerve growth are not known. Methods. Human disc cells were seeded onto tissue culture plates that had been coated with type I collagen and human intervertebral disc aggrecan. Explants of chick dorsal root ganglions (DRGs) were subsequently added to the plates and sensory neurite outgrowth stimulated by the addition of nerve growth factor. Time-lapse video and fluorescence microscopy were used to examine the migration and interaction of the disc cells and sensory neurites, in the context of the different matrix substrata. The effects of disc cell conditioned medium on nerve growth were also examined. Results. Disc cells spread and migrated on collagen until they encountered the aggrecan substrata, where some cells, but not all, were repelled. In coculture, DRG neurites extended onto the collagen/disc cells until they encountered the aggrecan, where, like the disc cells, many were repelled. However, in the presence of disc cells, some neurites were able to cross onto this normally inhibitory substratum. The number of neurite crossings onto aggrecan correlated significantly with the number of disc cells present on the aggrecan. In control experiments using DRG alone, all extending neurites were repelled at the collagen/aggrecan border. Conditioned medium from disc cell cultures stimulated DRG neurite outgrowth on collagen but did not increase neurite crossing onto aggrecan substrata. Conclusions. Human disc cells migrate across aggrecan substrata that are repellent to sensory DRG neurites. Disc cells synthesize neurotrophic factors in vitro that promote neurite outgrowth. Furthermore, the presence of disc cells in coculture with DRG partially abrogates the inhibitory effects of aggrecan on nerve growth. These findings have important implications for the regulation of nerve growth into the intervertebral disc, but whether disc cells promote nerve growth in vivo remains to be determined.