Artificial Evolution by Viability Rather Than Competition

Evolutionary algorithms are widespread heuristic methods inspired by natural evolution to solve difficult problems for which analytical approaches are not suitable. In many domains experimenters are not only interested in discovering optimal solutions, but also in finding the largest number of different solutions satisfying minimal requirements. However, the formulation of an effective performance measure describing these requirements, also known as fitness function, represents a major challenge. The difficulty of combining and weighting multiple problem objectives and constraints of possibly varying nature and scale into a single fitness function often leads to unsatisfactory solutions. Furthermore, selective reproduction of the fittest solutions, which is inspired by competition-based selection in nature, leads to loss of diversity within the evolving population and premature convergence of the algorithm, hindering the discovery of many different solutions. Here we present an alternative abstraction of artificial evolution, which does not require the formulation of a composite fitness function. Inspired from viability theory in dynamical systems, natural evolution and ethology, the proposed method puts emphasis on the elimination of individuals that do not meet a set of changing criteria, which are defined on the problem objectives and constraints. Experimental results show that the proposed method maintains higher diversity in the evolving population and generates more unique solutions when compared to classical competition-based evolutionary algorithms. Our findings suggest that incorporating viability principles into evolutionary algorithms can significantly improve the applicability and effectiveness of evolutionary methods to numerous complex problems of science and engineering, ranging from protein structure prediction to aircraft wing design.

Viability evolutionary algorithms and applications to neuroscience and biology

Andrea Maesani

Evolutionary algorithms are heuristic methods that operate on a population of individuals, which represent candidate solutions to optimization problems. Individuals with better quality, or fitness, are reproduced at a higher rate than less fit individuals by recombination and mutation. This process of selection and reproduction, based on fitness, models competition between individuals and leads to survival-of-the-fittest. Although this process lays at the foundation of evolutionary algorithms, the simplistic assumption that a single criterion can describe the quality of individuals is often unmet in real world problems, where multiple objectives or constraints have to be combined in the same fitness function. Furthermore, in nature, survival-of-the-fittest does not derive uniquely from competition, but is better seen as the outcome of an ongoing process of competition in parallel to a process of elimination of non-fit individuals. To resolve this mismatch and model different criteria for individuals separately, the Viability Evolution paradigm has been proposed in the literature. While the idea was previously introduced at a conceptual level, it had not yet been put to the test and lacks experimental validation. Here, we bridged this gap and tested whether viability-inspired evolutionary algorithms could confer advantages over the traditional evolutionary computation paradigm based on fitness. We started by investigating the evolutionary dynamics of a simple viability evolutionary method, and we analyzed the diversity of evolving populations. We also showed that the additional information available to a viability-based algorithm, such as the number of non-viable individuals for each viability criteria, can be exploited during the search for achieving better performance on optimization problems. In particular, we devised viability algorithms for constrained optimization, which outperformed current state-of-the-art methods on a well-known set of constrained optimization benchmarks. Furthermore, we embedded one of our algorithms into a novel framework for predicting structures of protein assemblies at atomic resolution. Finally, we used evolutionary methods to optimize neural networks in the context of a neuroscience investigation on the role of noise in animal behaviors. Noise is a ubiquitous feature of neural systems, but how it affects behaviors is far from being fully understood. After collecting large-scale measurements of Drosophila walking, we used evolutionary algorithms to search for neural networks that could match observed patterns of Drosophila spontaneous and odor-induced walking. By combining dynamical systems analysis and simulations, we showed how a noise-mediated memory of odor exposure accounts for the observed responses. In conclusion, this thesis contributes to evolutionary computation by testing the Viability Evolution paradigm and by proposing efficient viability evolutionary algorithms for constrained optimization. Furthermore, this thesis contributes to biology, by providing a new viability-based framework for predicting protein assemblies and by elucidating a mechanism through which neural noise may shape animal behaviors.

EPFL2015

Multi-objective optimisation applied to industrial energy problems

Geoffrey Basil Leyland

This thesis presents the development of a new multi-objective optimisation tool and applies it to a number of industrial problems related to optimising energy systems. Multi-objective optimisation techniques provide the information needed for detailed analyses of design trade-offs between conflicting objectives. For example, if a product must be both inexpensive and high quality, the multi-objective optimiser will provide a range of optimal options from the cheapest (but lowest quality) alternative to the highest quality (but most expensive), and a range of designs in between – those that are the most interesting to the decision-maker. The optimisation tool developed is the queueing multi-objective optimiser (QMOO), an evolutionary algorithm (EA). EAs are particularly suited to multi-objective optimisation because they work with a population of potential solutions, each representing a different trade-off between objectives. EAs are ideal to energy system optimisation because problems from that domain are often non-linear, discontinuous, disjoint, and multi-modal. These features make energy system optimisation problems difficult to resolve with other optimisation techniques. QMOO has several features that improve its performance on energy systems problems – features that are applicable to a wide range of optimisation problems. QMOO uses cluster analysis techniques to identify separate local optima simultaneously. This technique preserves diversity and helps convergence to difficult-to-find optima. Once normal dominance relations no longer discriminate sufficiently between population members certain individuals are chosen and removed from the population. Careful choice of the individuals to be removed ensures that convergence continues throughout the optimisation. Preserving of the "tail regions" of the population helps the algorithm to explore the full extent of the problem's optimal regions. QMOO is applied to a number of problems: coke factory placement in Shanxi Province, China; choice of heat recovery system operating temperatures; design of heat-exchanger networks; hybrid vehicle configuration; district heating network design, and others. Several of the problems were optimised previously using single-objective EAs. QMOO proved capable of finding entire ranges of solutions faster than the earlier methods found a single solution. In most cases, QMOO successfully optimises the problems without requiring any specific tuning to each problem. QMOO is also tested on a number of test problems found in the literature. QMOO's techniques for improving convergence prove effective on these problems, and its non-tuned performance is excellent compared to other algorithms found in the literature.

EPFL2002

A practical evolutionary method for the multi-objective optimisation of complex integrated energy systems including vehicle drivetrains

Adam Molyneaux

Concern for the environment has been steadily growing in recent years, and it is becoming more common to include environmental impact and pollution costs in the design problem along with construction, investment and operating costs. To further complicate matters governmental controls on emissions are still changing and the effect of increased emissions taxes may be critical in choosing a particular design solution. Thermo-economic and environmental analysis has been used previously at LENI to model investment, operating and pollution costs and aggregate them into a single objective that can be minimised. This has the drawback of requiring multiple optimisations in order to determine the sensitivity of the optimum solution to the presumed pollution costs. In addition, designers usually prefer a choice of different technological solutions as well as a clear idea of the trade-offs between multiple objectives without the need to define a common indicator (for example cost). Frequently, the thermodynamic and economic simulation of an energy system is non-linear, disjoint and with multiple local optima making it difficult to optimise with derivative based optimisation methods. This work presents the development of a multi-modal, multi-objective optimisation tool to respond to this need, and then demonstrates it on two complex problems – the design of a district heating system and the configuration of an advanced vehicle drivetrain. Multi-objective optimisation techniques aim to find the trade-off between two or more conflicting objectives. For example, if a design must be both efficient and low cost, then a multi-objective optimisation will find a range of solutions between the lowest cost but least efficient solution and the most efficient but most expensive solution, including some solutions that are fairly efficient and reasonable cost. Multi-modal optimisation techniques aim to keep different local optima. The optimisation tool developed here is the clustering pareto evolutionary algorithm (CPEA). As with other evolutionary algorithms (EAs) it works with a population of solutions, each individual representing a different trade-off between objectives. New solutions are produced using real variable crossover and mutation techniques and the population is ranked and thinned to avoid excessively large populations and maintain convergence pressure. The algorithm uses statistical clustering techniques on the independent variables to keep multiple different local optima simultaneously. The clusters maintain diversity in the population and identify local optima. In problems with many variables multi dimensional scaling (MDS) is used to reduce the number of variables before clustering. Applying the CPEA to the problem of designing a district heating system for minimum costs with and without pollution costs, it was possible to repeat previous work in a fraction of the time. For the same effort it was also possible to produce complete trade-off curves for cost and pollution, showing the dramatic change in optimal solution when pollution costs were included. The clustering and in particular the MDS were found to be key factors in the solution of this problem – without them the best overall solution was not found. A three objective problem was solved and the results compared favourably to a combined two objective problem, although convergence was found to be slower. A parallel version of the CPEA was also applied to the optimisation of a vehicle drivetrain simulation with respect to performance, emissions and costs over a test cycle. The multi-modal nature of the CPEA allowed the simultaneous solution of multiple hybrid and conventional solutions at no extra cost and improving overall convergence. The pollution costs calculated using the same level of taxation as in the district heating problem were found to be of little influence compared to the operating and investment costs, suggesting that pollution costs from the energy domain are unlikely to promote hybrid vehicle technology.

EPFL2002

Multi-objective optimisation applied to industrial energy problems

Geoffrey Basil Leyland

EPFL2002

A practical evolutionary method for the multi-objective optimisation of complex integrated energy systems including vehicle drivetrains

Adam Molyneaux

EPFL2002

Viability evolutionary algorithms and applications to neuroscience and biology

Andrea Maesani

EPFL2015