Main

The proposal that evolution could be used as a metaphor for problem solving came with the invention of the computer1. In the 1970s and 1980s the principal idea was developed into different algorithmic implementations under names such as evolutionary programming2, evolution strategies3,4 and genetic algorithms5, followed later by genetic programming6. These branches merged in the 1990s, and in the past 20 years so-called evolutionary computation or evolutionary computing has proven to be highly successful across a wide range of computational tasks in optimization, design and modelling7,8,9. For instance, urgent needs in the development of low-cost thin-film photovoltaic technologies were addressed using genetic algorithms for topology optimization10. This led to highly efficient light-trapping structures that exhibited more than a threefold increase over a classic limit, and achieved efficiency levels far beyond the reach of intuitive designs. It has also been convincingly demonstrated that evolutionary approaches are powerful methods for knowledge discovery. For example, equations were evolved to model motion-tracking data captured from various physical systems, ranging from simple harmonic oscillators to chaotic double pendula. This approach discovered, with limited prior knowledge of physics, kinematics or geometry, several laws of geometric and momentum conservation, and uncovered the 'alphabet' used to describe those systems11.

From the perspective of the underlying substrate in which the evolution takes place, the emergence of evolutionary computation can be considered as a major transition of the evolutionary principles from 'wetware', the realm of biology, to software, the realm of computers. Today the field is at an exciting stage. New developments in robotics and rapid prototyping (3D printing) are paving the way towards a second major transition: from software to hardware, going from digital evolutionary systems to physical ones12,13.

In this Review we outline the working principles of evolutionary algorithms, and briefly discuss the differences between artificial and natural evolution. We illustrate the power of evolutionary problem solving by discussing a number of successful applications, reflect on the features that make evolutionary algorithms so successful, review the current trends of the field, and give our perspective on future developments.

Evolution and problem solving

The essence of an evolutionary approach to solve a problem is to equate possible solutions to individuals in a population, and to introduce a notion of fitness on the basis of solution quality. To obtain a working evolutionary algorithm one has to go through a number of design steps. The first step is to identify a representation: a suitable data structure that can represent possible solutions to the problem. The next step is to define a way of measuring the quality of an individual based on problem-specific requirements. The final step is to specify suitable selection and variation operators (Fig. 1).

Figure 1: The principal diagram of evolutionary algorithms.
figure 1

The initialization process seeds the search with a population of randomly created solutions. After this the algorithm enters a loop of evaluating the current generation of solutions, selecting some to act as the basis for the next generation, and then creating new solutions through variation (mutation or crossover). Periodically, the algorithm checks to see whether user-specified termination criteria are met — such as reaching a desired level of fitness, or undergoing a certain number of generations without improvement.

Full size image

Analogous to natural evolution, an evolutionary algorithm can be thought of as working on two levels. At the higher level (the original problem context), phenotypes (candidate solutions) have their fitness measured. Selection mechanisms then use this measure to choose a pool of parents for each generation, and decide which parents and offspring go forward to the next generation. At the lower level, genotypes are objects that represent phenotypes in a form that can be manipulated to produce variations (Box 1). Genotype–phenotype mapping bridges the two levels. At the genotypic level, variation operators generate new individuals (offspring) from selected parents. Mutation operators are based on one parent (asexual reproduction) and randomly change some values. Recombination operators create offspring by combining values from the genotypes of two (or more) parents. Finally, an execution manager controls the overall functioning of the algorithm. It regulates the initialization of the first population, the execution of the selection–variation cycles, and the termination of the algorithm. It also manages the population size (typically kept constant) and other parameters affecting selection and variation. For instance, it determines the number of parents per generation, and whether mutation, recombination or both produce the offspring for a given set of parents.

Evolutionary algorithms are easily transferable from one application to another because only two components are problem dependent: the way that the genotypes are converted to phenotypes and the fitness function. The history of evolutionary computation has shown that suitable combinations of a few simple data structures can represent possible solutions to a huge variety of different problems (Box 1). In other words, a relatively small collection of possible genotypes can accommodate many different kinds of phenotypes. Just as the genetic mechanisms underpinning natural evolution are largely species independent, acting on DNA or RNA, so too in evolutionary computation the choice of suitable variation operators depends solely on the data structure present in the genotypes and not on the specific problem being tackled. Selection operators do not even depend on the chosen representation, as they only consider fitness information. This implies that for a certain problem a suitable evolutionary algorithm can be designed easily, as long as the problem-dependent phenotypes can be mapped to one of the 'standard' genotypes. From that point on, freely available evolutionary algorithm machinery can be used.

It should be noted that just because an algorithm is formally suitable, it does not necessarily mean it will be successful. Suitability only means that the evolutionary algorithm is capable of searching through the space of possible solutions of a problem, but gives no guarantees that this search will be either effective or efficient.

Positioning of evolutionary computation

From a historical perspective, humans have had two roles in evolution. Just like any other species, humans are the product of, and are subject to, evolution. But for millennia (in fact, for about twice as long as we have used wheels) people have also actively influenced the course of evolution in other species — by choosing which plants or animals should survive or mate. Thus humans have successfully exploited evolution to create improved food sources14 or more useful animals15, even though the mechanisms involved in the transmission of traits from one generation to the next were not understood.

Historically, the scope of human influence in evolution was very limited, being restricted to interfering with selection for survival and reproduction. Influencing other components, such as the design of genotypes, or mutation and recombination mechanisms, was far beyond our reach. This changed with the invention of the computer, which provided the possibility of creating digital worlds that are very flexible and much more controllable than the physical reality we live in. Together with the increased understanding of the genetic mechanisms behind evolution, this brought about the opportunity to become active masters of evolutionary processes that are fully designed and executed by human experimenters 'from above'.

It could be argued that evolutionary algorithms are not faithful models of natural evolution (Table 1). However, they certainly are a form of evolution. As Dennett16 said “If you have variation, heredity, and selection, then you must get evolution”.

Table 1 Main differences between natural evolution and evolutionary algorithms
Full size table

From a computer-science perspective, evolutionary algorithms are randomized heuristic search methods based on the generate-and-test principle: producing an offspring amounts to generating a new point in the search space, and testing is done through fitness evaluation. What distinguishes evolutionary algorithms from other algorithms in computer science is the unique combination of being stochastic and maintaining their working memory in the form of a population of candidate solutions. It should be noted that there are many variations of the generic evolutionary computation template under various names. Today, the family of evolutionary algorithms includes historical members: genetic algorithms, evolution strategies, evolutionary programming and genetic programming; and younger siblings, such as differential evolution and particle swarm optimization17,18,19,20,21,22,23,24,25. These differ in some details, terminology or motivational metaphor, but are, in essence, all instances of the same algorithmic template.

It is common to categorize algorithms according to completeness (can they generate every possible solution), optimality (are they guaranteed to find the best solution, and identify it as such) and efficiency. The completeness of an evolutionary algorithm can be achieved by an appropriate choice of representation and variation operators. The optimality is a more complex issue. Although optimal methods exist for many problems, their run time scales so poorly that they are impractical to use in most non-trivial cases — hence the interest in heuristic methods. As long as the heredity principle (similar individuals have similar fitness) holds, an evolutionary algorithm will have a 'basic instinct' to improve the population's fitness over time — because the selection operators are biased towards choosing fitter individuals for reproduction and survival. Thus, if we can define artificial fitness on the basis of a criterion grounded in the problem to be solved then the evolutionary algorithm will tend to find solutions that optimize the fitness values, or at least approximate them. This implies that evolutionary algorithms can be used to solve optimization problems and, consequently, any problem that can be transformed into an equivalent optimization task. This includes most problems in design, and those connected with building or learning models from data. Nevertheless, it is important to understand that evolutionary algorithms are not optimizers26, but approximators, and they are not optimal since we might not know whether the fitness of the best evolved solution is in fact the highest value possible. Yet, they become very interesting when approximate solutions are acceptable, for instance, if the global optimum is not known or not required.

Applications of evolutionary computation

The hypothesis that embedding the principles of evolution within computer algorithms can create powerful mechanisms for solving difficult, poorly understood problems is now supported by a huge body of evidence. Evolutionary problem solvers have proven capable of delivering high-quality solutions to difficult problems in a variety of scientific and technical domains, offering several advantages over conventional optimization and design methods.

One appealing example from the design domain concerns X-band antennas for the NASA Space Technology 5 (ST5) spacecraft27. The normal approach to this task is very time and labour intensive, relying heavily on expert knowledge. The evolutionary-algorithm-based approach not only discovered effective antenna designs, but could also adjust designs quickly when requirements changed. One of these antennas was actually constructed and deployed on the ST5 spacecraft, thus becoming the first computer-evolved hardware in space. This project also demonstrates a specific advantage of evolutionary over manual design. The evolutionary algorithms generated and tested thousands of completely new solutions, many with unusual structures that expert antenna designers would be unlikely to produce. Evolutionary algorithms have also been successful in many other aeronautical and aerospace engineering endeavours. Problems in this field typically have highly complex search spaces and multiple conflicting objectives. Population-based methods such as evolutionary algorithms have proven effective at meeting the challenges of this combination. In particular, so-called multi-objective evolutionary algorithms change the selection function to explicitly reward diversity, so that they discover and maintain high-quality solutions representing different trade-offs between objectives — technically, they approximate diverse segments of the Pareto front28. Many examples can also be found in bioinformatics. For instance, by mining the ChEMBL database (which contains bioactive molecules with drug-like properties), a set of transformations of chemical structures was identified that were then used as the mutation operator in an automated drug-design application29. The results showed clear benefits, particularly in accommodating multiple target profiles such as desired polypharmacology. This nicely illustrates how other approaches, or existing knowledge, can be easily co-opted or accommodated within an evolutionary computing framework.

Numerical and combinatorial optimization are important application areas of evolutionary algorithms. Particularly challenging is black-box optimization, where the nature of the objective function requires numerical (rather than analytical) methods, and gradient information can only be approximated by sampling solutions. A systematic experimental study compared mathematical programming and evolutionary computation of a range of synthetic black-box optimization problems, which were allowed different amounts of computing time and resources30. The results showed that mathematical programming algorithms — that were designed to provide quick progress in the initial stages of the search — outperform evolutionary algorithms if the maximum number of evaluations is low, but this picture changes if the computational budget is increased. Ultimately, the study concludes that an evolutionary algorithm, in particular BIPOP-CMA-ES, is able to find the optimum of a broader class of functions, solve problems with a higher precision and solve some problems faster. The power of evolution strategies (especially the very successful CMA-ES variants31) for real-life black-box optimization problems from industry has been discussed extensively32. Evidence gathered from years of academic research and development for industrial applications suggests that the niche for evolution strategies is formed by optimization tasks with a very limited budget for how many solutions can have their fitness evaluated. Although this finding is not in line with conventional wisdom within the field, there is ample support for this proposal.

Machine learning and modelling is another prominent area in which evolutionary algorithms have proved their power, especially as many contemporary approaches would otherwise rely on (often crude) greedy or local search algorithms to refine and optimize models. For example, neuroevolutionary approaches use evolutionary algorithms to optimize the structure, parameters, or both simultaneously, of artificial neural networks33,34. In other branches of machine learning, using evolutionary computing to design algorithms has been shown to be very effective as an alternative to handcrafting them, for instance, for inducing decision trees35. Furthermore, evolutionary algorithms have been applied to prediction problems. For instance, to tackle the problem of predicting the tertiary structure of a protein, an algorithm was designed to evolve a key component of automated predictors — the function used to estimate a structure's energy36. State-of-the-art methods in protein-structure prediction are limited by assuming a linear combination of energy terms, whereas a genetic programming method easily accommodates expressions based on a much richer syntax. The best energy function found by the genetic programming algorithm provided significantly better prediction guidance than conventional functions. The algorithm was able to automatically discover the most and least useful energy terms, without having any knowledge of how these terms alone are correlated to the prediction error.

The design of controllers for physical entities, such as machinery or robots, has proved to be another fruitful area. For example, control strategies for operating container cranes were evolved using a physical crane to determine fitness values37. The evolution of controllers is also possible in situ, for example in a population of robots during, and not just before, their operational period38,39. Evolutionary robotics40 is an especially challenging application area because of two additional issues that other branches of evolutionary computing do not face: the very weak and noisy link between controllable design details and the target feature or features; and the great variety of conditions under which a solution should perform well. Normally in evolutionary computing there is a three-step evaluation chain: genotype to phenotype to fitness. For robots the chain is four-step: genotype to phenotype to behaviour to fitness. In this four-step chain the robots morphology and controller form the phenotype. However, it could be argued that the behaviour should be considered as phenotype, because it is the entity that is being evaluated. Furthermore, the behaviour depends on many external factors, creating an unpredictable environment in which the robot is expected to perform. Nevertheless, since the manual design of an autonomous and adaptive mobile robot is extremely difficult, evolutionary approaches offer large potential benefits. These include the possibility of continuous and automated design, manufacture and deployment of robots of very different morphologies and control systems41. Several studies have demonstrated such benefits, in which robot control systems that were automatically generated by artificial evolution were comparatively simpler or more efficient than those engineered using other design methods42. In all cases, robots initially exhibited uncoordinated behaviour, but a few hundreds of generations were sufficient to achieve efficient behaviours in a wide range of experimental conditions.

Several state-of-the-art algorithms for applications across a great variety of problem domains are based on hybridizing evolutionary search with existing algorithms, especially local search methods. This kind of hybridization can be thought of as adding 'lifetime learning' to the evolutionary process. Freed from the restrictions of natural evolution (such as learned traits not being written back immediately to the genotype), and being able to experiment with novel types of individual and social learning, the theory and practice of so-called memetic algorithms has become an important topic in the field43,44,45. Such hybrid algorithms can often find good (or better) solutions faster than a pure evolutionary algorithm when the additional method searches systematically in the vicinity of good solutions, rather than relying on the more randomized search carried out by mutation46,47. For example, the cell suppression problem (deciding which data cells to disclose in published statistical tables in order to protect respondents' confidentiality)48 was solved using a combination of graph partitioning, linear programming and evolutionary optimization of the sequence in which vulnerable cells were considered. This produced methods that could protect published statistical tables at a size that was several orders of magnitude greater than had previously been possible. Memetic algorithms have obtained an eminent place among the best approaches to solving really hard problems.

State of the art

Although initially considerable scepticism surrounded evolutionary algorithms, over the past 20 years evolutionary computation has grown to become a major field in computational intelligence7,8,9. As well as solving hard problems in various application areas, the emphasis of evolutionary algorithms on randomness as a source of variation has been shown to have particular advantages: the lack of problem-specific preconceptions and biases of the algorithm designer opens up the way to unexpected 'original' solutions that can even have artistic value49,50,51 (http://endlessforms.com/). The perception of evolution as a problem solver has broadened from seeing evolution as a heuristic algorithm for (parametric) optimization to considering it to be a powerful approach for (structural) design52,53.

In general, evolutionary algorithms have proven competitive in solving hard problems in the face of challenging characteristics like non-differentiability, discontinuities, multiple local optima, noise and nonlinear interactions among the variables, especially if the computational budgets are sufficiently high. Evolution is a slow learner, but the steady increase in computing power, and the fact that the algorithm is inherently suited to parallelization, mean that more and more generations can be executed within practically acceptable timescales.

The performance of evolutionary algorithms has also been compared with that of human experts, and there is now substantial and well-documented evidence of evolutionary algorithms producing measurably human-competitive results54. The annual Humies competition (http://www.genetic-programming.org/combined.php), which rewards human-competitive results from evolutionary computation, highlights the great variety of hard problems for which evolutionary algorithms have delivered excellent solutions.

The success and popularity of evolutionary algorithms can be attributed to a number of algorithmic features, which makes them attractive. First, they are assumption free because applying an evolutionary algorithm consists of specifying the representation for candidate solutions and providing an external function that first transforms the genotype into a candidate solution and then provides an evaluation. Internally, evolutionary algorithms make no explicit assumptions about the problem, hence they are widely applicable and easily transferable at low cost. Second, they are flexible because they can be easily used in collaboration with existing methods, such as local search; they can be incorporated within, or make use of, existing toolsets; and combinations with domain-specific methods often lead to superior solvers because they can exploit the best features of different approaches. Third, they are robust, owing to the use of a population and randomized choices, which mean evolutionary algorithms are less likely to get trapped in suboptimal solutions than other search methods. They are also less sensitive to noise or infidelity in the models of the system used to evaluate solutions, and can cope with changes in the problem. Fourth, they are not focussed on a single solution because having a population means that an algorithm terminates with a number of solutions. Thus, users do not have to pre-specify their preferences and weighting in advance, but can make decisions after they see what is possible to achieve. This is a great advantage for problems with many local optima, or with a number of conflicting objectives. Finally, they are capable of producing unexpected solutions because they are blind to human preconceptions and so can find effective, but non-intuitive solutions, which are often valuable in design domains.

The theoretical underpinning of evolutionary algorithms remains a hard nut to crack. Mathematical analysis can illuminate some properties, but even digital evolutionary processes exhibit very complex dynamics that allow only limited theory forming, despite the diverse set of tools and methods ranging from quantitative genetics to statistical physics55. One important theoretical result is the no free lunch theorem. This states that evolutionary algorithms are not generic super solvers — but neither is any other method, because there is no such thing56. Instead, “an evolutionary algorithm is the second best solver for any problem”, meaning that in many cases a carefully hand-crafted solver that exploits problem characteristics is superior for the problem at hand, but that it might take years to create that solver. A long-standing issue for theorists is algorithm convergence. Early results were based on Markov-chain analysis and addressed convergence in general57, but more recent work found specific relationships between algorithmic set-up and expected run times58. Despite all the difficulties, the field is making progress in theory59,60.

Important research trends

The development of evolutionary computation continues along a number of research threads.

Automated design and tuning of evolutionary algorithms

Experience has shown that there are several design choices behind an evolutionary algorithm that greatly influence its performance. To reduce the number of design decisions to be made, and the impact of poor choices, the community is working on automated design aids. These can customize an initial algorithm set-up for a given problem offline (before the run) or online (during the run)61. Techniques such as automated parameter tuning62,63,64,65 and adaptive parameter control continue to make advances in this area66,67,68,69.

Using surrogate models

Increasingly, evolutionary algorithms are being used for problems in which evaluating each population member over many generations would take too long to permit effective evolution given the resources available. A range of approaches — collectively known as surrogate models — are being developed that use computationally cheaper models in place of full fitness evaluations, and that refine those models through occasional full evaluations of targeted individuals70,71,72,73.

Handling many objectives

Having proven highly successful for finding solutions to problems with multiple objectives (typically up to ten)74, the community is now making rapid advances in the field of many objectives — moving way beyond the capabilities of other algorithms75,76,77. In tandem with algorithmic advances, this has spurred renewed interest in interactive evolutionary algorithms, which have been successfully applied to elicit user preferences and knowledge in many areas from design to art51 (http://picbreeder.org). Results suggest a useful synergy with periodic user interaction to incorporate preferences that help to focus the search down to a more manageable set of dimensions78. Importantly, this involves eliciting user preferences in response to what is discovered to be possible, rather than a priori.

Generative and developmental representations

Further to the conventionally simple genotype–phenotype mappings, the use of indirect encodings is gaining traction. Such generative and developmental representations allow the reuse of code, which helps to scale up the complexity of artificially evolved phenotypes, for instance, in evolutionary robotics, artificial life and morphogenetic engineering79,80,81,82,83.

Outlook

The range of problems to which evolutionary algorithms have been successfully applied has grown year on year, and there is every reason to expect this to continue. In the future, we expect to see increasing interest in applying evolutionary algorithms to embodied or embedded systems; that is, employing evolution in populations for which the candidate solutions are controllers or drivers that implement the operational strategy for some situated entities, and are evaluated within the context of some rich dynamic environment; not for what they are, but for what they do. Examples include policies for Web-crawlers, information retrieval strategies, software for machinery and smart devices, and controllers for autonomous robots84,85. In such cases the evolved solutions are embedded in entities that exist and act in a 'habitat', the internet or the physical world, that is too complex and dynamic to be modelled perfectly. Enhancing the system with the ability to evolve and adapt after deployment can complement the offline optimization approach employed during the design stage. The novelty of such systems is that evolutionary changes take place within the operational period. These systems will be different because they replace the conventional design-and-deploy approach by a design–deploy–adapt loop in which the evolutionary component is a principal part of the system.

This approach is already gaining traction in two areas. In the field of search-based software engineering, evolutionary algorithms are gaining prominence in response to the mismatch between the availability of expert software engineers and the explosion of interconnected devices requiring new and/or updated software86. Meanwhile, recent developments in rapid fabrication technologies (3D printing) and ever smaller and more powerful robotic platforms mean that evolutionary computing is now starting to make the next major transition to the automated creation of physical artefacts and 'smart' objects87 (Fig. 2). In the long term this could lead to a disruptive robotic technology in which design and production are replaced by selection and reproduction without the involvement of human designers and human-operated facilities.

Figure 2: Two major transitions in the history of artificial evolution.
figure 2

In the twentieth century computer technology enabled artificial Darwinian processes in silico — the evolution of digital entities. In the twenty-first century, developments in robotics, materials science and 3D printing will enable the evolution of physical artefacts or machines.

Full size image

Last but not least, we foresee a fruitful cross-fertilization with biology in the coming decade based on a bidirectional flow of inspiration, understanding and knowledge. On the one hand, the advancing insights in molecular and evolutionary biology can be used to make more sophisticated evolutionary algorithms and may help to solve previously intractable problems. The opportunities and challenges of this avenue have been outlined in a research agenda to transform artificial evolution to computational evolution88. On the other hand, a new kind of artificial evolution — the evolution of things — opens new horizons for biologists. In 1992, the evolutionary biologist John Maynard Smith commented: “So far, we have been able to study only one evolving system and we cannot wait for interstellar flight to provide us with a second. If we want to discover generalizations about evolving systems, we will have to look at artificial ones”89. Artificial evolution implemented on real hardware, as in evolutionary robotics, offers a new research instrument to this end42,90,91,92,93,94,95. The use of real hardware overcomes the principal deficiency of software models, which lack the richness of matter that is a source of challenges and opportunities not yet matched in artificial algorithms96. Hence, they can provide new insights into fundamental issues such as the factors influencing evolvability, resilience, the rate of progress under various circumstances, or the co-evolution of mind and body. Using a non-biochemical substrate for such research is becoming technologically ever more feasible, and it increases the generalizability of the findings. In particular, using a different medium for evolutionary studies can separate generic principles and ground truth from effects that are specific for carbon-based life as we know it.