Part 2. MOO methods for multidisciplinary design using parallel evolutionary algorithms, game theory and hierarchical topology. (Part 2.) Numerical aspects and implementation of model test cases

These lecture notes describe the use and implementation of a framework in which mathematical as well as engineering optimisation problems can be analysed. The foundations of the framework and algorithms described -Hierarchical Asynchronous Parallel Evolutionary Algorithms (HAPEAs) - lie upon traditional evolution strategies and incorporate the concepts of a multi-objective optimisation, hierarchical topology, asynchronous evaluation of candidate solutions , parallel computing and game strategies. In a step by step approach, the numerical implementation of EAs and HAPEAs for solving multi criteria optimisation problems is conducted providing the reader with the knowledge to reproduce these hand on training in his – her- academic or industrial environment.

Part 3. MOO methods for multidisciplinary design using parallel evolutionary algorithms, game theory and hierarchical topology. (Part 3.) Practical application to the design and optimisation of UAV systems

These lecture notes highlight some of the recent applications of multi-objective and multidisciplinary design optimisation in aeronautical design using the framework and methodology described in References 8, 23, 24 and in Part 1 and 2 of the notes. A summary of the methodology is described and the treatment of uncertainties in flight conditions parameters by the HAPEAs software and game strategies is introduced. Several test cases dealing with detailed design and computed with the software are presented and results discussed in section 4 of these notes.

Genetic and phenotypic evidence supports evolutionary divergence of the American flamingo (Phoenicopterus ruber) population in the Galapagos islands

The Galapagos archipelago is characterized by a high degree of endemism across many taxa, linked to the archpelago's oceanic origin and distance from other colonizing land masses. A population of ~ 500 American Flamingos (Phoenicopterus ruber) resides in Galapagos, which is thought to share an historical origin with the American Flamingo currently found in the Caribbean region. Genetic and phenotypic parameters in American Flamingos from Galapagos and from the Caribbean were investigated. Microsatellite and microchondrial DNA markers data showed that the American Flamingo population in Galapagos differs genetically from that in the Caribbean. American Flamingos in Galapagos form a clade which differs by a single common nucleotide substitution from American Flamingos in the Caribbean. The genetic differentiation is also evident from nuclear DNA in that microsatellite data reveal a number of private alleles for the American Flamingo in Galapagos. Analysis of skeletal measurements showed that American Flamingos in Galapagos are smaller than those in the Caribbean primarily due to shorter tarsus length, and differences in body shape sexual dimorphism. American Flamingo eggs from Galapagos have smaller linear dimensions and volumes than those from the Caribbean. The findings are consistent with reproductive isolation of American Flamingo population in Galapagos.

Mission path planning of aerial survey tasks using hybrid game evolutionary algorithm

The work presented in this report is aimed to implement a cost-effective offline mission path planner for aerial inspection tasks of large linear infrastructures. Like most real-world optimisation problems, mission path planning involves a number of objectives which ideally should be minimised simultaneously. Understandably, the objectives of a practical optimisation problem are conflicting each other and the minimisation of one of them necessarily implies the impossibility to minimise the other ones. This leads to the need to find a set of optimal solutions for the problem; once such a set of available options is produced, the mission planning problem is reduced to a decision making problem for the mission specialists, who will choose the solution which best fit the requirements of the mission. The goal of this work is then to develop a Multi-Objective optimisation tool able to provide the mission specialists a set of optimal solutions for the inspection task amongst which the final trajectory will be chosen, given the environment data, the mission requirements and the definition of the objectives to minimise. All the possible optimal solutions of a Multi-Objective optimisation problem are said to form the Pareto-optimal front of the problem. For any of the Pareto-optimal solutions, it is impossible to improve one objective without worsening at least another one. Amongst a set of Pareto-optimal solutions, no solution is absolutely better than another and the final choice must be a trade-off of the objectives of the problem. Multi-Objective Evolutionary Algorithms (MOEAs) are recognised to be a convenient method for exploring the Pareto-optimal front of Multi-Objective optimization problems. Their efficiency is due to their parallelism architecture which allows to find several optimal solutions at each time

The plasticity of NBS resistance genes in sorghum is driven by multiple evolutionary processes

Background Increased disease resistance is a key target of cereal breeding programs, with disease outbreaks continuing to threaten global food production, particularly in Africa. Of the disease resistance gene families, the nucleotide-binding site plus leucine-rich repeat (NBS-LRR) family is the most prevalent and ancient and is also one of the largest gene families known in plants. The sequence diversity in NBS-encoding genes was explored in sorghum, a critical food staple in Africa, with comparisons to rice and maize and with comparisons to fungal pathogen resistance QTL. Results In sorghum, NBS-encoding genes had significantly higher diversity in comparison to non NBS-encoding genes and were significantly enriched in regions of the genome under purifying and balancing selection, both through domestication and improvement. Ancestral genes, pre-dating species divergence, were more abundant in regions with signatures of selection than in regions not under selection. Sorghum NBS-encoding genes were also significantly enriched in the regions of the genome containing fungal pathogen disease resistance QTL; with the diversity of the NBS-encoding genes influenced by the type of co-locating biotic stress resistance QTL. Conclusions NBS-encoding genes are under strong selection pressure in sorghum, through the contrasting evolutionary processes of purifying and balancing selection. Such contrasting evolutionary processes have impacted ancestral genes more than species-specific genes. Fungal disease resistance hot-spots in the genome, with resistance against multiple pathogens, provides further insight into the mechanisms that cereals use in the “arms race” with rapidly evolving pathogens in addition to providing plant breeders with selection targets for fast-tracking the development of high performing varieties with more durable pathogen resistance.

Not drowning, (hand)waving? Molecular phylogenetics, biogeography and evolutionary tempo of the ‘Gondwanan’ midge Stictocladius Edwards (Diptera: Chironomidae)

Many insect clades, especially within the Diptera (true flies), have been considered classically ‘Gondwanan’, with an inference that distributions derive from vicariance of the southern continents. Assessing the role that vicariance has played in the evolution of austral taxa requires testing the location and tempo of diversification and speciation against the well-established predictions of fragmentation of the ancient super-continent. Several early (anecdotal) hypotheses that current austral distributions originate from the breakup of Gondwana derive from studies of taxa within the family Chironomidae (non-biting midges). With the advent of molecular phylogenetics and biogeographic analytical software, these studies have been revisited and expanded to test such conclusions better. Here we studied the midge genus Stictocladius Edwards, from the subfamily Orthocladiinae, which contains austral-distributed clades that match vicariance-based expectations. We resolve several issues of systematic relationships among morphological species and reveal cryptic diversity within many taxa. Time-calibrated phylogenetic relationships among taxa accorded partially with the predicted tempo from geology. For these apparently vagile insects, vicariance-dated patterns persist for South America and Australia. However, as often found, divergence time estimates for New Zealand at c. 50 mya post-date separation of Zealandia from Antarctica and the remainder of Gondwana, but predate the proposed Oligocene ‘drowning’ of these islands. We detail other such ‘anomalous’ dates and suggest a single common explanation rather than stochastic processes. This could involve synchronous establishment following recovery from ‘drowning’ and/or deleteriously warming associated with the mid-Eocene climatic optimum (hence ‘waving’, which refers to cycles of drowning events) plus new availability of topography providing of cool running waters, or all these factors in combination. Alternatively a vicariance explanation remains available, given the uncertain duration of connectivity of Zealandia to Australia–Antarctic–South America via the Lord Howe and Norfolk ridges into the Eocene.

Selection procedures for module discovery : exploring evolutionary algorithms for cognitive science

Evolutionary algorithms are playing an increasingly important role as search methods in cognitive science domains. In this study, methodological issues in the use of evolutionary algorithms were investigated via simulations in which procedures were systematically varied to modify the selection pressures on populations of evolving agents. Traditional roulette wheel, tournament, and variations of these selection algorithms were compared on the “needle-in-a-haystack” problem developed by Hinton and Nowlan in their 1987 study of the Baldwin effect. The task is an important one for cognitive science, as it demonstrates the power of learning as a local search technique in smoothing a fitness landscape that lacks gradient information. One aspect that has continued to foster interest in the problem is the observation of residual learning ability in simulated populations even after long periods of time. Effective evolutionary algorithms balance their search effort between broad exploration of the search space and in-depth exploitation of promising solutions already found. Issues discussed include the differential effects of rank and proportional selection, the tradeoff between migration of populations towards good solutions and maintenance of diversity, and the development of measures that illustrate how each selection algorithm affects the search process over generations. We show that both roulette wheel and tournament algorithms can be modified to appropriately balance search between exploration and exploitation, and effectively eliminate residual learning in this problem.

Numerical investigation of upstream fuel injection through porous media for scramjet engines via surrogate-assisted evolutionary algorithms

A multi-objective design optimization study has been conducted for upstream fuel injection through porous media applied to the first ramp of a two-dimensional scramjet intake. The optimization has been performed by coupling evolutionary algorithms assisted by surrogate modeling and computational fluid dynamics with respect to three design criteria, that is, the maximization of the absolute mixing quantity, total pressure saving, and fuel penetration. A distinct Pareto optimal front has been obtained, highlighting the counteracting behavior of the total pressure against the mixing efficiency and fuel penetration. The injector location and size have been identified as the key design parameters as a result of a sensitivity analysis, with negligible influence of the porous properties in the configurations and conditions considered in the present study. Flowfield visualization has revealed the underlying physics associated with the effects of these dominant parameters on the shock structure and intensity.

The land hoarding and land inspector dilemma in China : an evolutionary game theoretic perspective

China has experienced considerable economic growth since 1978, which was accompanied by unprecedented growth in urbanization and, more recently, by associated rising urban housing and land banking issues. One such issue is that of land hoarding - where real estate developers purchase land to hold unused in the rising market for a future lucrative sale, often several years later. This practice is outlawed in China, where land use is controlled by increasingly strengthened Government policies and inspectors. Despite this, land hoarding continues apace, with the main culprits being the developers and inspectors working subversively. This resembles a game between two players - the inspector and the developer - which provides the setting for this paper in developing an evolutionary game theory model to provide insights into dealing with the dilemmas faced by the players. The logic and dilemma of land banking strategy and illegal land banking issues are analysed, along with the land inspector’s role from a game theory perspective by determining the replication dynamic mechanism and evolutionary stable strategies under the various conditions that the players face. The major factors influencing the actions of land inspectors, on the other hand, are the costs of inspection, no matter if it is strict or indolent, conflict costs, and income and penalties from corruption. From this, it is shown that, when the net loss for corruption (income from corruption minus the penalties for corruption and cost of strict inspections) is less than the cost of strict inspections, the final evolutionary stable strategy of the inspectors is to carry out indolent inspections. Then, whether penalising developers for hoarding is severe or not, the evolutionary strategy for the developer is to hoard. The implications for land use control mechanisms and associated developer-inspector actions and counteractions are then examined in the light of the model's properties.

Evolutionary game design : automated game design comes of age

The "Humies" awards are an annual competition held in conjunction with the Genetic and Evolutionary Computation Conference (GECCO), in which cash prizes totalling $10,000 are awarded to the most human-competitive results produced by any form of evolutionary computation published in the previous year. This article describes the gold medal-winning entry from the 2012 "Humies" competition, based on the LUDI system for playing, evaluating and creating new board games. LUDI was able to demonstrate human-competitive results in evolving novel board games that have gone on to be commercially published, one of which, Yavalath, has been ranked in the top 2.5% of abstract board games ever invented. Further evidence of human-competitiveness was demonstrated in the evolved games implicitly capturing several principles of good game design, outperforming human designers in at least one case, and going on to inspire a new sub-genre of games.

Evolutionary optimization and game strategies for advanced multi-disciplinary design : applications to aeronautics and UAV design

Many complex aeronautical design problems can be formulated with efficient multi-objective evolutionary optimization methods and game strategies. This book describes the role of advanced innovative evolution tools in the solution, or the set of solutions of single or multi disciplinary optimization. These tools use the concept of multi-population, asynchronous parallelization and hierarchical topology which allows different models including precise, intermediate and approximate models with each node belonging to the different hierarchical layer handled by a different Evolutionary Algorithm. The efficiency of evolutionary algorithms for both single and multi-objective optimization problems are significantly improved by the coupling of EAs with games and in particular by a new dynamic methodology named “Hybridized Nash-Pareto games”. Multi objective Optimization techniques and robust design problems taking into account uncertainties are introduced and explained in detail. Several applications dealing with civil aircraft and UAV, UCAV systems are implemented numerically and discussed. Applications of increasing optimization complexity are presented as well as two hands-on test cases problems. These examples focus on aeronautical applications and will be useful to the practitioner in the laboratory or in industrial design environments. The evolutionary methods coupled with games presented in this volume can be applied to other areas including surface and marine transport, structures, biomedical engineering, renewable energy and environmental problems.

Determining reverse salient types and evolutionary dynamics of technology systems with performance disparities

Technological system evolution is marked by the uneven evolution of constituent sub-systems. Subsequently, system evolution is hampered by the resulting state of unevenness, or reverse salience, which results from the presence of the sub-system that delivers the lowest level of performance with respect to other sub-systems, namely, the reverse salient. In this paper, we develop absolute and proportional performance gap measures of reverse salience and, in turn, derive a typology of reverse salients that distinguishes alternative dynamics of change in the evolving system. We subsequently demonstrate the applicability of the measures and the typology through an illustrative empirical study of the PC (personal computer) technological system that functions as a gaming platform. Our empirical analysis demonstrates that patterns of temporal dynamics can be distinguished with the measurement of reverse salience, and that distinct paths of technological system evolution can be identified as different types of reverse salients emerge over time.

The evolutionary history of termites as inferred from 66 mitochondrial genomes

Termites have colonized many habitats and are among the most abundant animals in tropical ecosystems, which they modify considerably through their actions. The timing of their rise in abundance and of the dispersal events that gave rise to modern termite lineages is not well understood. To shed light on termite origins and diversification, we sequenced the mitochondrial genome of 48 termite species and combined them with 18 previously sequenced termite mitochondrial genomes for phylogenetic and molecular clock analyses using multiple fossil calibrations. The 66 genomes represent most major clades of termites. Unlike previous phylogenetic studies based on fewer molecular data, our phylogenetic tree is fully resolved for the lower termites. The phylogenetic positions of Macrotermitinae and Apicotermitinae are also resolved as the basal groups in the higher termites, but in the crown termitid groups, including Termitinae + Syntermitinae + Nasutitermitinae + Cubitermitinae, the position of some nodes remains uncertain. Our molecular clock tree indicates that the lineages leading to termites and Cryptocercus roaches diverged 170 Ma (153-196 Ma 95% confidence interval [CI]), that modern Termitidae arose 54 Ma (46-66 Ma 95% CI), and that the crown termitid group arose 40 Ma (35-49 Ma 95% CI). This indicates that the distribution of basal termite clades was influenced by the final stages of the breakup of Pangaea. Our inference of ancestral geographic ranges shows that the Termitidae, which includes more than 75% of extant termite species, most likely originated in Africa or Asia, and acquired their pantropical distribution after a series of dispersal and subsequent diversification events.

RNASeqBrowser: A genome browser for simultaneous visualization of raw strand specific RNAseq reads and UCSC genome browser custom tracks

Background Strand specific RNAseq data is now more common in RNAseq projects. Visualizing RNAseq data has become an important matter in Analysis of sequencing data. The most widely used visualization tool is the UCSC genome browser that introduced the custom track concept that enabled researchers to simultaneously visualize gene expression at a particular locus from multiple experiments. Our objective of the software tool is to provide friendly interface for visualization of RNAseq datasets. Results This paper introduces a visualization tool (RNASeqBrowser) that incorporates and extends the functionality of the UCSC genome browser. For example, RNASeqBrowser simultaneously displays read coverage, SNPs, InDels and raw read tracks with other BED and wiggle tracks -- all being dynamically built from the BAM file. Paired reads are also connected in the browser to enable easier identification of novel exon/intron borders and chimaeric transcripts. Strand specific RNAseq data is also supported by RNASeqBrowser that displays reads above (positive strand transcript) or below (negative strand transcripts) a central line. Finally, RNASeqBrowser was designed for ease of use for users with few bioinformatic skills, and incorporates the features of many genome browsers into one platform. Conclusions The features of RNASeqBrowser: (1) RNASeqBrowser integrates UCSC genome browser and NGS visualization tools such as IGV. It extends the functionality of the UCSC genome browser by adding several new types of tracks to show NGS data such as individual raw reads, SNPs and InDels. (2) RNASeqBrowser can dynamically generate RNA secondary structure. It is useful for identifying non-coding RNA such as miRNA. (3) Overlaying NGS wiggle data is helpful in displaying differential expression and is simple to implement in RNASeqBrowser. (4) NGS data accumulates a lot of raw reads. Thus, RNASeqBrowser collapses exact duplicate reads to reduce visualization space. Normal PC’s can show many windows of NGS individual raw reads without much delay. (5) Multiple popup windows of individual raw reads provide users with more viewing space. This avoids existing approaches (such as IGV) which squeeze all raw reads into one window. This will be helpful for visualizing multiple datasets simultaneously. RNASeqBrowser and its manual are freely available at http://www.australianprostatecentre.org/research/software/rnaseqbrowser webcite or http://sourceforge.net/projects/rnaseqbrowser/ webcite

A Strength Pareto Evolutionary Algorithm for live migration of multiple interdependent virtual machines in data centers

Although live VM migration has been intensively studied, the problem of live migration of multiple interdependent VMs has hardly been investigated. The most important problem in the live migration of multiple interdependent VMs is how to schedule VM migrations as the schedule will directly affect the total migration time and the total downtime of those VMs. Aiming at minimizing both the total migration time and the total downtime simultaneously, this paper presents a Strength Pareto Evolutionary Algorithm 2 (SPEA2) for the multi-VM migration scheduling problem. The SPEA2 has been evaluated by experiments, and the experimental results show that the SPEA2 can generate a set of VM migration schedules with a shorter total migration time and a shorter total downtime than an existing genetic algorithm, namely Random Key Genetic Algorithm (RKGA). This paper also studies the scalability of the SPEA2.