Multiple-vector self-adaptation in evolutionary algorithms.

Self-adaptation is a common method for learning online control parameters in an evolutionary algorithm. In one common implementation, each individual in the population is represented as a pair of vectors (x, sigma), where x is the candidate solution to an optimization problem scored in terms of f(x), and sigma is the so-called strategy parameter vector that influences how offspring will be created from the individual. Experimental evidence suggests that the elements of sigma can sometimes become too small to explore the given response surface adequately. The evolutionary search then stagnates, until the elements of sigma grow sufficiently large as a result of random variation. A potential solution to this deficiency associates multiple strategy parameter vectors with a single individual. A single strategy vector is active at any time and dictates how offspring will be generated. Experiments are conducted on four 10-dimensional benchmark functions where the number of strategy parameter vectors is varied over 1, 2, 3, 4, 5, 10, and 20. The results indicate advantages for using multiple strategy parameter vectors. Furthermore, the relationship between the mean best result after a fixed number of generations and the number of strategy parameter vectors can be determined reliably in each case.

Do evolutionary processes minimize expected losses?

Evolution by variation and natural selection is often viewed as an optimization process that favors those organisms which are best adapted to their environment. This leaves open the issue of how to measure adaptation and what criterion is implied for optimization. This problem has been framed and analysed mathematically under the assumption that individuals compete to minimize expected losses across a series of decisions (e.g. choice of behavior), where each decision offers a stochastic payoff. But the fact that a particular analysis is tractable for a specified criterion does not imply the fidelity of that criterion. Computer simulations involving a version of the k -armed bandit problem can address the veracity of the hypothesis that individuals are selected to minimize expected losses. The results offered here do not support this hypothesis.

Rapid automated molecular replacement by evolutionary search.

A new procedure for molecular replacement is presented in which an efficient six-dimensional search is carried out using an evolutionary optimization algorithm. In this procedure, a population of initially random molecular-replacement solutions is iteratively optimized with respect to the correlation coefficient between observed and calculated structure factors. The sensitivity and reliability of the method is enhanced by uniform sampling of the rotational-search space and the use of continuously variable rotational and translational parameters. The process is several orders of magnitude faster than a systematic six-dimensional search, and comparisons show that it can identify solutions using significantly less accurate or less complete search models than is possible with two existing molecular-replacement methods. A program incorporating the method, EPMR, allows the rapid and highly automated solution of molecular-replacement problems involving single or multiple molecules in the asymmetric unit. EPMR has been used to solve a number of difficult molecular-replacement problems.

Fitness distributions in evolutionary computation: motivation and examples in the continuous domain.

Evolutionary algorithms are, fundamentally, stochastic search procedures. Each next population is a probabilistic function of the current population. Various controls are available to adjust the probability mass function that is used to sample the space of candidate solutions at each generation. For example, the step size of a single-parent variation operator can be adjusted with a corresponding effect on the probability of finding improved solutions and the expected improvement that will be obtained. Examining these statistics as a function of the step size leads to a 'fitness distribution', a function that trades off the expected improvement at each iteration for the probability of that improvement. This paper analyzes the effects of adjusting the step size of Gaussian and Cauchy mutations, as well as a mutation that is a convolution of these two distributions. The results indicate that fitness distributions can be effective in identifying suitable parameter settings for these operators. Some comments on the utility of extending this protocol toward the general diagnosis of evolutionary algorithms is also offered.

Evolving neural networks to play checkers without relying on expert knowledge.

An experiment was conducted where neural networks compete for survival in an evolving population based on their ability to play checkers. More specifically, multilayer feedforward neural networks were used to evaluate alternative board positions and games were played using a minimax search strategy. At each generation, the extant neural networks were paired in competitions and selection was used to eliminate those that performed poorly relative to other networks. Offspring neural networks were created from the survivors using random variation of all weights and bias terms. After a series of 250 generations, the best-evolved neural network was played against human opponents in a series of 90 games on an internet website. The neural network was able to defeat two expert-level players and played to a draw against a master. The final rating of the neural network placed it in the "Class A" category using a standard rating system. Of particular importance in the design of the experiment was the fact that no features beyond the piece differential were given to the neural networks as a priori knowledge. The process of evolution was able to extract all of the additional information required to play at this level of competency. It accomplished this based almost solely on the feedback offered in the final aggregated outcome of each game played (i.e., win, lose, or draw). This procedure stands in marked contrast to the typical artifice of explicitly injecting expert knowledge into a game-playing program.

Evolving artificial neural networks for screening features from mammograms.

Disagreement or inconsistencies in mammographic interpretation motivates utilizing computerized pattern recognition algorithms to aid the assessment of radiographic features. We have studied the potential for using artificial neural networks (ANNs) to analyze interpreted radiographic features from film screen mammograms. Attention was given to 216 cases (mammogram series) that presented suspicious characteristics. The domain expert (Wasson) quantified up to 12 radiographic features for each case based on guidelines from previous literature. Patient age was also included. The existence or absence of malignancy was confirmed in each case via open surgical biopsy (111 malignant, 105 benign). ANNs of various complexity were trained via evolutionary programming to indicate whether or not a malignancy was present given a vector of scored input features in a statistical cross validation procedure. For suspicious masses, the best evolved ANNs generated a mean area under the receiver operating characteristic curve (AZ) of 0.9196 +/- 0.0040 (1 S.E.), with a mean specificity of 0.6269 +/- 0.0272 at 0.95 sensitivity. Results when microcalcifications were included were not quite as good (AZ = 0.8464), however, ANNs with only two hidden nodes performed as well as more complex ANNs and better than ANNs with only one hidden node. The performance of the evolved ANNs was comparable to prior literature, but with an order of magnitude less complexity. The success of small ANNs in diagnosing breast cancer offers the promise that suitable explanations for the ANN's behavior can be induced, leading to a greater acceptance by physicians.

Linear and neural models for classifying breast masses.

Computational methods can be used to provide an initial screening or a second opinion in medical settings and may improve the sensitivity and specificity of diagnoses. In the current study, linear discriminant models and artificial neural networks are trained to detect breast cancer in suspicious masses using radiographic features and patient age. Results on 139 suspicious breast masses (79 malignant, 60 benign, biopsy proven) indicate that a significant probability of detecting malignancies can be achieved at the risk of a small percentage of false positives. Receiver operating characteristic (ROC) analysis favors the use of linear models, however, a new measure related to the area under the ROC curve (AZ) suggests a possible benefit from hybridizing linear and nonlinear classifiers.

On the instability of evolutionary stable strategies.

Evolutionary stable strategies (ESSs) are often used to explain the behaviors of individuals and species. The analysis of ESSs determines which, if any, combinations of behaviors cannot be invaded by alternative strategies. However, two of the assumptions required to generate ESSs, an infinite population and payoffs described only on the average, are not particularly realistic in natural situations. Previous experiments have indicated that under more natural conditions of finite populations and stochastic payoffs, populations may evolve in trajectories that are unrelated to an ESS, even in very simple evolutionary games. Those earlier simulations are extended here under a variety of conditions. The results suggest that ESSs may not provide a good explanation of a finite population's behavior even when the conditions correspond closely with the infinite population model. The implications of these results are discussed briefly in light of previous literature claiming that ESSs generated suitable explanations of real-world data.

A step toward computer-assisted mammography using evolutionary programming and neural networks.

Artificial intelligence techniques can be used to provide a second opinion in medical settings. This may improve the sensitivity and specificity of diagnoses, as well as the cost effectiveness of the physician's effort. In the current study, evolutionary programming is used to train artificial neural networks to detect breast cancer using radiographic features and patient age. Results from 112 suspicious breast masses (63 malignant, 49 benign, biopsy proven) indicate that a significant probability of detecting malignancies can be achieved using simple neural architectures at the risk of a small percentage of false positives.

Evolving continuous behaviors in the Iterated Prisoner's Dilemma.

Evolutionary programming experiments are conducted on a variant of the Iterated Prisoner's Dilemma. Rather than assume each player having two alternative moves in the stage-game, cooperate or defect, a continuum of possible moves are available. Players' strategies are represented by feed-forward perceptrons with a single hidden layer. The population size and the number of nodes in the hidden layer are varied across a series of experiments. The results of the simulations indicate a minimum amount of complexity is required in a player's strategy in order for cooperation to evolve. Moreover, under the evolutionary dynamics of the simulation, cooperation does not appear to be a stable outcome.

Evolving neural networks for detecting breast cancer.

Artificial neural networks are applied to the problem of detecting breast cancer from histologic data. Evolutionary programming is used to train the networks. This stochastic optimization method reduces the chance of becoming trapped in locally optimal weight sets. Preliminary results indicate that very parsimonious neural nets can outperform other methods reported in the literature on the same data. The results are statistically significant.

Molecular recognition of the inhibitor AG-1343 by HIV-1 protease: conformationally flexible docking by evolutionary programming.

BACKGROUND: An important prerequisite for computational structure-based drug design is prediction of the structures of ligand-protein complexes that have not yet been experimentally determined by X-ray crystallography or NMR. For this task, docking of rigid ligands is inadequate because it assumes knowledge of the conformation of the bound ligand. Docking of flexible ligands would be desirable, but requires one to search an enormous conformational space. We set out to develop a strategy for flexible docking by combining a simple model of ligand-protein interactions for molecular recognition with an evolutionary programming search technique. RESULTS: We have developed an intermolecular energy function that incorporates steric and hydrogen-bonding terms. The parameters in this function were obtained by docking in three different protein systems. The effectiveness of this method was demonstrated by conformationally flexible docking of the inhibitor AG-1343, a potential new drug against AIDS, into HIV-1 protease. For this molecule, which has nine rotatable bonds, the crystal structure was reproduced within 1.5 A root-mean-square deviation 34 times in 100 simulations, each requiring eight minutes on a Silicon Graphics R4400 workstation. The energy function correctly evaluates the crystal structure as the global energy minimum. CONCLUSIONS: We believe that a solution of the docking problem may be achieved by matching a simple model of molecular recognition with an efficient search procedure. The necessary ingredients of a molecular recognition model include only steric and hydrogen-bond interaction terms. Although these terms are not necessarily sufficient to predict binding affinity, they describe ligand-protein interactions faithfully enough to enable a docking program to predict the structure of the bound ligand. This docking strategy thus provides an important tool for the interdisciplinary field of rational drug design.

A comparison of methods for self-adaptation in evolutionary algorithms.

Evolutionary algorithms, including evolutionary programming and evolution strategies, have often been applied to real-valued function optimization problems. These algorithms generally operate directly on the real values to be optimized, in contrast with genetic algorithms which usually operate on a separately coded transformation of the objective variables. Evolutionary algorithms often rely on a second-level optimization of strategy parameters, tunable variables that in part determine how each parent will generate offspring. Two alternative methods for performing this second-level optimization have been proposed and are compared across a series of function optimization tasks. The results appear to favor the approach offered originally in evolution strategies, although the applicability of the findings may be limited to the case where each parameter of a parent solution is perturbed independently of all others.

An introduction to simulated evolutionary optimization.

Natural evolution is a population-based optimization process. Simulating this process on a computer results in stochastic optimization techniques that can often outperform classical methods of optimization when applied to difficult real-world problems. There are currently three main avenues of research in simulated evolution: genetic algorithms, evolution strategies, and evolutionary programming. Each method emphasizes a different facet of natural evolution. Genetic algorithms stress chromosomal operators. Evolution strategies emphasize behavioral changes at the level of the individual. Evolutionary programming stresses behavioral change at the level of the species. The development of each of these procedures over the past 35 years is described. Some recent efforts in these areas are reviewed.

On the effectiveness of crossover in simulated evolutionary optimization.

There has been renewed interest in using simulated evolution to address difficult optimization problems. These simulations can be divided into two groups: (1) those that model chromosomes and emphasize genetic operators; and (2) those that model individuals or populations and emphasize the adaptation and diversity of behavior. Recent claims have suggested that genetic models using recombination operators, specifically crossover, are typically more efficient and effective at function optimization than behavioral models that rely solely on mutation. These claims are assessed empirically on a broad range of response surfaces.

An information criterion for optimal neural network selection.

The choice of an optimal neural network design for a given problem is addressed. A relationship between optimal network design and statistical model identification is described. A derivative of Akaike's information criterion (AIC) is given. This modification yields an information statistic which can be used to objectively select a ;best' network for binary classification problems. The technique can be extended to problems with an arbitrary number of classes.