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.

A genetic algorithm to optimise the component placement process in the PCB assembly

In printed circuit board (PCB) assembly, the efficiency of the component placement process is dependent on two interrelated issues: the sequence of component placement, that is, the component sequencing problem, and the assignment of component types to feeders of the placement machine, that is, the feeder arrangement problem. In cases where some components with the same type are assigned to more than one feeder, the component retrieval problem should also be considered. Due to their inseparable relationship, a hybrid genetic algorithm is adopted to solve these three problems simultaneously for a type of PCB placement machines called the sequential pick-and-place (PAP) machine in this paper. The objective is to minimise the total distance travelled by the placement head for assembling all components on a PCB. Besides, the algorithm is compared with the methods proposed by other researchers in order to examine its effectiveness and efficiency.

Relationship between sunlight and the age of onset of bipolar disorder:an international multisite study

Background - The onset of bipolar disorder is influenced by the interaction of genetic and environmental factors. We previously found that a large increase in sunlight in springtime was associated with a lower age of onset. This study extends this analysis with more collection sites at diverse locations, and includes family history and polarity of first episode. Methods - Data from 4037 patients with bipolar I disorder were collected at 36 collection sites in 23 countries at latitudes spanning 3.2 north (N) to 63.4 N and 38.2 south (S) of the equator. The age of onset of the first episode, onset location, family history of mood disorders, and polarity of first episode were obtained retrospectively, from patient records and/or direct interview. Solar insolation data were obtained for the onset locations. Results - There was a large, significant inverse relationship between maximum monthly increase in solar insolation and age of onset, controlling for the country median age and the birth cohort. The effect was reduced by half if there was no family history. The maximum monthly increase in solar insolation occurred in springtime. The effect was one-third smaller for initial episodes of mania than depression. The largest maximum monthly increase in solar insolation occurred in northern latitudes such as Oslo, Norway, and warm and dry areas such as Los Angeles, California. Limitations - Recall bias for onset and family history data. Conclusions - A large springtime increase in sunlight may have an important influence on the onset of bipolar disorder, especially in those with a family history of mood disorders.