Noisy fitness evaluation in genetic algorithms and the dynamics of learning

A theoretical model is presented which describes selection in a genetic algorithm (GA) under a stochastic fitness measure and correctly accounts for finite population effects. Although this model describes a number of selection schemes, we only consider Boltzmann selection in detail here as results for this form of selection are particularly transparent when fitness is corrupted by additive Gaussian noise. Finite population effects are shown to be of fundamental importance in this case, as the noise has no effect in the infinite population limit. In the limit of weak selection we show how the effects of any Gaussian noise can be removed by increasing the population size appropriately. The theory is tested on two closely related problems: the one-max problem corrupted by Gaussian noise and generalization in a perceptron with binary weights. The averaged dynamics can be accurately modelled for both problems using a formalism which describes the dynamics of the GA using methods from statistical mechanics. The second problem is a simple example of a learning problem and by considering this problem we show how the accurate characterization of noise in the fitness evaluation may be relevant in machine learning. The training error (negative fitness) is the number of misclassified training examples in a batch and can be considered as a noisy version of the generalization error if an independent batch is used for each evaluation. The noise is due to the finite batch size and in the limit of large problem size and weak selection we show how the effect of this noise can be removed by increasing the population size. This allows the optimal batch size to be determined, which minimizes computation time as well as the total number of training examples required.

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.

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.

Investigating the molecular structures of solid dispersions by the simulated annealing method

Knowledge of the molecular structures of solid dispersions is vital, yet, despite thousands of reports in this area, it remains unclear. The aim of this research is to investigate the molecular structure of solid dispersions with hot melt preparation method by the simulated annealing method. Simulation results showed linear polymer chains form the random coils under heat and the drug molecules stick on the surface of polymer coils, while drug molecules are dispersed molecularly but irregularly within the amorphous low molecular weight carriers. This research presents more reasonable molecular images of solid dispersions than the existed theory.

Genetic algorithms for discovery of matrix multiplication methods

We present a parallel genetic algorithm for nding matrix multiplication algo-rithms. For 3 x 3 matrices our genetic algorithm successfully discovered algo-rithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied the cases with less mul-tiplications and evaluated the suitability of the methods discovered. Although our evolutionary method did not reach the theoretical lower bound it led to an approximate solution for 22 multiplications.

Improving the performance of FBG sensors in a WDM network using a simulated annealing technique

Simulated annealing technique is used to improve the performance of fiber Bragg grating (FBG) sensors in a wavelength-division-multiplexed network. Experiments demonstrated strain detection accuracy of ̃2.5 με when the spectrums of FBGs are fully or partially overlapped.

Using genetic algorithms for improved discrete sequence prediction

A statistics-based method using genetic algorithms for predicting discrete sequences is presented. The prediction of the next value is based upon a fixed number of previous values and the statistics offered by the training data. According to the statistics, in similar past cases different values occurred next. If these values are considered with the appropriate weights, the forecast is successful. Weights are generated by genetic algorithms.

Visual data mining using principled projection algorithms and information visualization techniques

We introduce a flexible visual data mining framework which combines advanced projection algorithms from the machine learning domain and visual techniques developed in the information visualization domain. The advantage of such an interface is that the user is directly involved in the data mining process. We integrate principled projection algorithms, such as generative topographic mapping (GTM) and hierarchical GTM (HGTM), with powerful visual techniques, such as magnification factors, directional curvatures, parallel coordinates and billboarding, to provide a visual data mining framework. Results on a real-life chemoinformatics dataset using GTM are promising and have been analytically compared with the results from the traditional projection methods. It is also shown that the HGTM algorithm provides additional value for large datasets. The computational complexity of these algorithms is discussed to demonstrate their suitability for the visual data mining framework. Copyright 2006 ACM.

Using genetic programming and decision trees for generating structural descriptions of four bar mechanisms

Four bar mechanisms are basic components of many important mechanical devices. The kinematic synthesis of four bar mechanisms is a difficult design problem. A novel method that combines the genetic programming and decision tree learning methods is presented. We give a structural description for the class of mechanisms that produce desired coupler curves. Constructive induction is used to find and characterize feasible regions of the design space. Decision trees constitute the learning engine, and the new features are created by genetic programming.

Optical quality for keratoconic eyes with conventional RGP lens and simulated, customised contact lens corrections:a comparison

Purpose: To compare monochromatic aberrations of keratoconic eyes when uncorrected, corrected with spherically-powered RGP (rigid gas-permeable) contact lenses and corrected using simulations of customised soft contact lenses for different magnitudes of rotation (up to 15°) and translation (up to 1mm) from their ideal position. Methods: The ocular aberrations of examples of mild, moderate and severe keratoconic eyes were measured when uncorrected and when wearing their habitual RGP lenses. Residual aberrations and point-spread functions of each eye were simulated using an ideal, customised soft contact lens (designed to neutralise higher-order aberrations, HOA) were calculated as a function of the angle of rotation of the lens from its ideal orientation, and its horizontal and vertical translation. Results: In agreement with the results of other authors, the RGP lenses markedly reduced both lower-order aberrations and HOA for all three patients. When compared with the RGP lens corrections, the customised lens simulations only provided optical improvements if their movements were constrained within limits which appear to be difficult to achieve with current technologies. Conclusions: At the present time, customised contact lens corrections appear likely to offer, at best, only minor optical improvements over RGP lenses for patients with keratoconus. If made in soft materials, however, these lenses may be preferred by patients in term of comfort. © 2012 The College of Optometrists.

Survival in the pre-senile dementia frontotemporal lobar degeneration with TDP-43 proteinopathy:effects of genetic, demographic and neuropathological variables

Factors associated with survival were studied in 84 neuropathologically documented cases of the pre-senile dementia frontotemporal dementia lobar degeneration (FTLD) with transactive response (TAR) DNA-binding protein of 43 kDa (TDP-43) proteinopathy (FTLD-TDP). Kaplan-Meier survival analysis estimated mean survival as 7.9 years (range: 1-19 years, SD = 4.64). Familial and sporadic cases exhibited similar survival, including progranulin (GRN) gene mutation cases. No significant differences in survival were associated with sex, disease onset, Braak disease stage, or disease subtype, but higher survival was associated with lower post-mortem brain weight. Survival was significantly reduced in cases with associated motor neuron disease (FTLD-MND) but increased with Alzheimer's disease (AD) or hippocampal sclerosis (HS) co-morbidity. Cox regression analysis suggested that reduced survival was associated with increased densities of neuronal cytoplasmic inclusions (NCI) while increased survival was associated with greater densities of enlarged neurons (EN) in the frontal and temporal lobes. The data suggest that: (1) survival in FTLD-TDP is more prolonged than typical in pre-senile dementia but shorter than some clinical subtypes such as the semantic variant of primary progressive aphasia (svPPA), (2) MND co-morbidity predicts poor survival, and (3) NCI may develop early and EN later in the disease. The data have implications for both neuropathological characterization and subtyping of FTLD-TDP.

Powertrain optimisation in a hybrid electric bus

This paper describes the use of a formal optimisation procedure to optimise a plug-in hybrid electric bus using two different case studies to meet two different performance criteria; minimum journey cost and maximum battery life. The approach is to choose a commercially available vehicle and seek to improve its performance by varying key design parameters. Central to this approach is the ability to develop a representative backward facing model of the vehicle in MATLAB/Simulink along with appropriate optimisation objective and penalty functions. The penalty functions being the margin by which a particular design fails to meet the performance specification. The model is validated against data collected from an actual vehicle and is used to estimate the vehicle performance parameters in a model-in-the-loop process within an optimisation routine. For the purposes of this paper, the journey cost/battery life over a drive cycle is optimised whilst other performance indices are met (or exceeded). Among the available optimisation methods, Powell's method and Simulated Annealing are adopted. The results show this method as a valid alternative modelling approach to vehicle powertrain optimisation. © 2012 IEEE.

Evolutionary neural networks : models and applications

The scaling problems which afflict attempts to optimise neural networks (NNs) with genetic algorithms (GAs) are disclosed. A novel GA-NN hybrid is introduced, based on the bumptree, a little-used connectionist model. As well as being computationally efficient, the bumptree is shown to be more amenable to genetic coding lthan other NN models. A hierarchical genetic coding scheme is developed for the bumptree and shown to have low redundancy, as well as being complete and closed with respect to the search space. When applied to optimising bumptree architectures for classification problems the GA discovers bumptrees which significantly out-perform those constructed using a standard algorithm. The fields of artificial life, control and robotics are identified as likely application areas for the evolutionary optimisation of NNs. An artificial life case-study is presented and discussed. Experiments are reported which show that the GA-bumptree is able to learn simulated pole balancing and car parking tasks using only limited environmental feedback. A simple modification of the fitness function allows the GA-bumptree to learn mappings which are multi-modal, such as robot arm inverse kinematics. The dynamics of the 'geographic speciation' selection model used by the GA-bumptree are investigated empirically and the convergence profile is introduced as an analytical tool. The relationships between the rate of genetic convergence and the phenomena of speciation, genetic drift and punctuated equilibrium arc discussed. The importance of genetic linkage to GA design is discussed and two new recombination operators arc introduced. The first, linkage mapped crossover (LMX) is shown to be a generalisation of existing crossover operators. LMX provides a new framework for incorporating prior knowledge into GAs.Its adaptive form, ALMX, is shown to be able to infer linkage relationships automatically during genetic search.

Multi-level genetic algorithm for the resource-constrained re-entrant scheduling problem in the flow shop

The re-entrant flow shop scheduling problem (RFSP) is regarded as a NP-hard problem and attracted the attention of both researchers and industry. Current approach attempts to minimize the makespan of RFSP without considering the interdependency between the resource constraints and the re-entrant probability. This paper proposed Multi-level genetic algorithm (GA) by including the co-related re-entrant possibility and production mode in multi-level chromosome encoding. Repair operator is incorporated in the Multi-level genetic algorithm so as to revise the infeasible solution by resolving the resource conflict. With the objective of minimizing the makespan, Multi-level genetic algorithm (GA) is proposed and ANOVA is used to fine tune the parameter setting of GA. The experiment shows that the proposed approach is more effective to find the near-optimal schedule than the simulated annealing algorithm for both small-size problem and large-size problem. © 2013 Published by Elsevier Ltd.