A hybridised evolutionary algorithm for multi-criterion minimum spanning tree problems

A hybridised and Knowledge-based Evolutionary Algorithm (KEA) is applied to the multi-criterion minimum spanning tree problems. Hybridisation is used across its three phases. In the first phase a deterministic single objective optimization algorithm finds the extreme points of the Pareto front. In the second phase a K-best approach finds the first neighbours of the extreme points, which serve as an elitist parent population to an evolutionary algorithm in the third phase. A knowledge-based mutation operator is applied in each generation to reproduce individuals that are at least as good as the unique parent. The advantages of KEA over previous algorithms include its speed (making it applicable to large real-world problems), its scalability to more than two criteria, and its ability to find both the supported and unsupported optimal solutions.

Landscape state machines: Tools for evolutionary algorithm performance analyses and landscape/algorithm mapping

Many evolutionary algorithm applications involve either fitness functions with high time complexity or large dimensionality (hence very many fitness evaluations will typically be needed) or both. In such circumstances, there is a dire need to tune various features of the algorithm well so that performance and time savings are optimized. However, these are precisely the circumstances in which prior tuning is very costly in time and resources. There is hence a need for methods which enable fast prior tuning in such cases. We describe a candidate technique for this purpose, in which we model a landscape as a finite state machine, inferred from preliminary sampling runs. In prior algorithm-tuning trials, we can replace the 'real' landscape with the model, enabling extremely fast tuning, saving far more time than was required to infer the model. Preliminary results indicate much promise, though much work needs to be done to establish various aspects of the conditions under which it can be most beneficially used. A main limitation of the method as described here is a restriction to mutation-only algorithms, but there are various ways to address this and other limitations.

Femtosecond pulse shaping using differential evolutionary algorithm and wavelet operators

Evolutionary meta-algorithms for pulse shaping of broadband femtosecond duration laser pulses are proposed. The genetic algorithm searching the evolutionary landscape for desired pulse shapes consists of a population of waveforms (genes), each made from two concatenated vectors, specifying phases and magnitudes, respectively, over a range of frequencies. Frequency domain operators such as mutation, two-point crossover average crossover, polynomial phase mutation, creep and three-point smoothing as well as a time-domain crossover are combined to produce fitter offsprings at each iteration step. The algorithm applies roulette wheel selection; elitists and linear fitness scaling to the gene population. A differential evolution (DE) operator that provides a source of directed mutation and new wavelet operators are proposed. Using properly tuned parameters for DE, the meta-algorithm is used to solve a waveform matching problem. Tuning allows either a greedy directed search near the best known solution or a robust search across the entire parameter space.

Parameter estimation based on stacked regression and evolutionary algorithms

A new parameter-estimation algorithm, which minimises the cross-validated prediction error for linear-in-the-parameter models, is proposed, based on stacked regression and an evolutionary algorithm. It is initially shown that cross-validation is very important for prediction in linear-in-the-parameter models using a criterion called the mean dispersion error (MDE). Stacked regression, which can be regarded as a sophisticated type of cross-validation, is then introduced based on an evolutionary algorithm, to produce a new parameter-estimation algorithm, which preserves the parsimony of a concise model structure that is determined using the forward orthogonal least-squares (OLS) algorithm. The PRESS prediction errors are used for cross-validation, and the sunspot and Canadian lynx time series are used to demonstrate the new algorithms.

Evolutionary rewiring of bacterial regulatory networks

Bacteria have evolved complex regulatory networks that enable integration of multiple intracellular and extracellular signals to coordinate responses to environmental changes. However, our knowledge of how regulatory systems function and evolve is still relatively limited. There is often extensive homology between components of different networks, due to past cycles of gene duplication, divergence, and horizontal gene transfer, raising the possibility of cross-talk or redundancy. Consequently, evolutionary resilience is built into gene networks – homology between regulators can potentially allow rapid rescue of lost regulatory function across distant regions of the genome. In our recent study [Taylor, et al. Science (2015), 347(6225)] we find that mutations that facilitate cross-talk between pathways can contribute to gene network evolution, but that such mutations come with severe pleiotropic costs. Arising from this work are a number of questions surrounding how this phenomenon occurs.

Nonlinear channel equalizer design using directional evolutionary multi-objective optimization

In this paper, a new equalizer learning scheme is introduced based on the algorithm of the directional evolutionary multi-objective optimization (EMOO). Whilst nonlinear channel equalizers such as the radial basis function (RBF) equalizers have been widely studied to combat the linear and nonlinear distortions in the modern communication systems, most of them do not take into account the equalizers' generalization capabilities. In this paper, equalizers are designed aiming at improving their generalization capabilities. It is proposed that this objective can be achieved by treating the equalizer design problem as a multi-objective optimization (MOO) problem, with each objective based on one of several training sets, followed by deriving equalizers with good capabilities of recovering the signals for all the training sets. Conventional EMOO which is widely applied in the MOO problems suffers from disadvantages such as slow convergence speed. Directional EMOO improves the computational efficiency of the conventional EMOO by explicitly making use of the directional information. The new equalizer learning scheme based on the directional EMOO is applied to the RBF equalizer design. Computer simulation demonstrates that the new scheme can be used to derive RBF equalizers with good generalization capabilities, i.e., good performance on predicting the unseen samples.

Variable selection for financial distress classification using a genetic algorithm

This paper is concerned with the use of a genetic algorithm to select financial ratios for corporate distress classification models. For this purpose, the fitness value associated to a set of ratios is made to reflect the requirements of maximizing the amount of information available for the model and minimizing the collinearity between the model inputs. A case study involving 60 failed and continuing British firms in the period 1997-2000 is used for illustration. The classification model based on ratios selected by the genetic algorithm compares favorably with a model employing ratios usually found in the financial distress literature.

Comparisons of host mitochondrial, nuclear and endosymbiont bacterial genes reveal cryptic fig wasp species and the effects of Wolbachia on host mtDNA evolution and diversity

Background Figs and fig-pollinating wasp species usually display a highly specific one-to-one association. However, more and more studies have revealed that the "one-to-one" rule has been broken. Co-pollinators have been reported, but we do not yet know how they evolve. They may evolve from insect speciation induced or facilitated by Wolbachia which can manipulate host reproduction and induce reproductive isolation. In addition, Wolbachia can affect host mitochondrial DNA evolution, because of the linkage between Wolbachia and associated mitochondrial haplotypes, and thus confound host phylogeny based on mtDNA. Previous research has shown that fig wasps have the highest incidence of Wolbachia infection in all insect taxa, and Wolbachia may have great influence on fig wasp biology. Therefore, we look forward to understanding the influence of Wolbachia on mitochondrial DNA evolution and speciation in fig wasps. Results We surveyed 76 pollinator wasp specimens from nine Ficus microcarpa trees each growing at a different location in Hainan and Fujian Provinces, China. We found that all wasps were morphologically identified as Eupristina verticillata, but diverged into three clades with 4.22-5.28% mtDNA divergence and 2.29-20.72% nuclear gene divergence. We also found very strong concordance between E. verticillata clades and Wolbachia infection status, and the predicted effects of Wolbachia on both mtDNA diversity and evolution by decreasing mitochondrial haplotypes. Conclusions Our study reveals that the pollinating wasp E. verticillata on F. microcarpa has diverged into three cryptic species, and Wolbachia may have a role in this divergence. The results also indicate that Wolbachia strains infecting E. verticillata have likely resulted in selective sweeps on host mitochondrial DNA.

Evolutionary dynamics of Staphylococcus aureus during progression from carriage to disease

Whole-genome sequencing offers new insights into the evolution of bacterial pathogens and the etiology of bacterial disease. Staph- ylococcus aureus is a major cause of bacteria-associated mortality and invasive disease and is carried asymptomatically by 27% of adults. Eighty percent of bacteremias match the carried strain. How- ever, the role of evolutionary change in the pathogen during the progression from carriage to disease is incompletely understood. Here we use high-throughput genome sequencing to discover the genetic changes that accompany the transition from nasal carriage to fatal bloodstream infection in an individual colonized with meth- icillin-sensitive S. aureus. We found a single, cohesive population exhibiting a repertoire of 30 single-nucleotide polymorphisms and four insertion/deletion variants. Mutations accumulated at a steady rate over a 13-mo period, except for a cluster of mutations preceding the transition to disease. Although bloodstream bacteria differed by just eight mutations from the original nasally carried bacteria, half of those mutations caused truncation of proteins, including a prema- ture stop codon in an AraC-family transcriptional regulator that has been implicated in pathogenicity. Comparison with evolution in two asymptomatic carriers supported the conclusion that clusters of pro- tein-truncating mutations are highly unusual. Our results demon- strate that bacterial diversity in vivo is limited but nonetheless detectable by whole-genome sequencing, enabling the study of evolutionary dynamics within the host. Regulatory or structural changes that occur during carriage may be functionally important for pathogenesis; therefore identifying those changes is a crucial step in understanding the biological causes of invasive bacterial disease.

Bacterial motility confers fitness advantage in the presence of phages

Dispersal provides the opportunity to escape harm and colonize new patches, enabling populations to expand and persist. However, the benefits of dispersal associated with escaping harm will be dependent on the structure of the environment and the likelihood of escape. Here, we empirically investigate how the spatial distribution of a parasite influences the evolution of host dispersal. Bacteriophages are a strong and common threat for bacteria in natural environments and offer a good system with which to explore parasite-mediated selection on host dispersal. We used two transposon mutants of the opportunistic bacteria, Pseudomonas aeruginosa, which varied in their motility (a disperser and a nondisperser), and the lytic bacteriophage ФKZ. The phage was distributed either in the central point of colony inoculation only, thus offering an escape route for the dispersing bacteria; or, present throughout the agar, where benefits of dispersal might be lost. Surprisingly, we found dispersal to be equally advantageous under both phage conditions relative to when phages were absent. A general explanation is that dispersal decreased the spatial structuring of host population, reducing opportunities for parasite transmission, but other more idiosyncratic mechanisms may also have contributed. This study highlights the crucial role the parasites can play on the evolution of dispersal and, more specifically, that bacteriophages, which are ubiquitous, are likely to select for bacterial motility.

Using experimental evolution to explore natural patterns between bacterial motility and resistance to bacteriophages

Resistance of bacteria to phages may be gained by alteration of surface proteins to which phages bind, a mechanism that is likely to be costly as these molecules typically have critical functions such as movement or nutrient uptake. To address this potential trade-off, we combine a systematic study of natural bacteria and phage populations with an experimental evolution approach. We compare motility, growth rate and susceptibility to local phages for 80 bacteria isolated from horse chestnut leaves and, contrary to expectation, find no negative association between resistance to phages and bacterial motility or growth rate. However, because correlational patterns (and their absence) are open to numerous interpretations, we test for any causal association between resistance to phages and bacterial motility using experimental evolution of a subset of bacteria in both the presence and absence of naturally associated phages. Again, we find no clear link between the acquisition of resistance and bacterial motility, suggesting that for these natural bacterial populations, phage-mediated selection is unlikely to shape bacterial motility, a key fitness trait for many bacteria in the phyllosphere. The agreement between the observed natural pattern and the experimental evolution results presented here demonstrates the power of this combined approach for testing evolutionary trade-offs.

Efficiency of evolutionary algorithms in water network pipe sizing

The pipe sizing of water networks via evolutionary algorithms is of great interest because it allows the selection of alternative economical solutions that meet a set of design requirements. However, available evolutionary methods are numerous, and methodologies to compare the performance of these methods beyond obtaining a minimal solution for a given problem are currently lacking. A methodology to compare algorithms based on an efficiency rate (E) is presented here and applied to the pipe-sizing problem of four medium-sized benchmark networks (Hanoi, New York Tunnel, GoYang and R-9 Joao Pessoa). E numerically determines the performance of a given algorithm while also considering the quality of the obtained solution and the required computational effort. From the wide range of available evolutionary algorithms, four algorithms were selected to implement the methodology: a PseudoGenetic Algorithm (PGA), Particle Swarm Optimization (PSO), a Harmony Search and a modified Shuffled Frog Leaping Algorithm (SFLA). After more than 500,000 simulations, a statistical analysis was performed based on the specific parameters each algorithm requires to operate, and finally, E was analyzed for each network and algorithm. The efficiency measure indicated that PGA is the most efficient algorithm for problems of greater complexity and that HS is the most efficient algorithm for less complex problems. However, the main contribution of this work is that the proposed efficiency ratio provides a neutral strategy to compare optimization algorithms and may be useful in the future to select the most appropriate algorithm for different types of optimization problems.