From evolutionary computation to the evolution of things

Evolution has provided a source of inspiration for algorithm designers since the birth of computers. The resulting field, evolutionary computation, has been successful in solving engineering tasks ranging in outlook from the molecular to the astronomical. Today, the field is entering a new phase as evolutionary algorithms that take place in hardware are developed, opening up new avenues towards autonomous machines that can adapt to their environment. We discuss how evolutionary computation compares with natural evolution and what its benefits are relative to other computing approaches, and we introduce the emerging area of artificial evolution in physical systems.

The proposal that evolution could be used as a metaphor for problem-solving came with the invention of the computer 1 . In the 1970s and 1980s the principal idea was developed into different algorithmic implementations under names such as evolutionary programming 2 , evolution strategies 3,4 , and genetic algorithms 5 , followed later by genetic programming 6 . These branches merged in the 1990s, and in the last twenty years so-called evolutionary computation or evolutionary computing (EC) has proven highly successful across a wide range of computational tasks in optimisation, design, and modelling 7,8,9 . For instance, Wang et al. addressed urgent needs in the development of low cost thin-film photovoltaic technologies, using genetic algorithms for topology optimisation. They obtained highly efficient light trapping structures that exhibited a more than 3-fold increase over a classical limit, and achieved efficiency levels far beyond the reach of intuitive designs 10 . Evolutionary approaches have also been convincingly demonstrated to be powerful methods for knowledge discovery. For example, Schmidt and Lipson 11 evolved equations based on motion-tracking data captured from various physical systems, ranging from simple harmonic oscillators to chaotic double-pendula. With very little prior knowledge about physics, kinematics, or geometry, their algorithm discovered several laws of geometric and momentum conservation, and uncovered the 'alphabet' used to describe those systems.
From the perspective of the underlying substrate, 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: this time from software to hardware, that is, going from digital evolutionary systems to physical ones 12,13 .
In this paper 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, and review the current trends of the field. Finally, we 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 based on solution quality. To obtain a working evolutionary algorithm (EA) one has to go through a number of design steps. The first step is to identify a representation: that is to say 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. 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, see Box 1. The 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 initialisation 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.

INSERT BOX 1 HERE
Evolutionary algorithms are easily transferable from one application to another because only two components, the way that the genotypes are converted to phenotypes, and the fitness function, are problem dependent. The history of EC has shown that suitable combinations of a few simple data structures can represent possible solutions to a huge variety of different problems (see 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 EC the choice of suitable variation operators depends solely on the data types 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 EA 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 EA machinery can be used.
It should be noted that just because an algorithm is formally suitable, that does not necessarily mean it will be successful. That is to say, suitability only means that the EA 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 played two roles in evolution. Just like any other species, humans are the product of, and subject to, evolution. Also, for millennia -in fact for approximately twice as long we have used wheels -people have 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 sources 14 or more useful animals 15 , 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 the mutation and recombination mechanisms, was far beyond reach. This was changed by the invention of the computer, that 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. However, they certainly are a form of evolution. As phrased by Dennett 16 : "If you have variation, heredity, and selection, then you must get evolution". In Table 1 we compare natural evolution and artificial evolution as used in contemporary evolutionary algorithms.

INSERT TABLE 1 HERE
From the 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 EAs 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 EC template under various names. Today, the family of EAs includes historical members: genetic algorithms, evolution strategies, evolutionary programming, and genetic programming; and younger siblings, such as differential evolution and particle swarm optimization 17,18,19,20,21,22,23,24,25 . These differ in some details, terminology, or motivational metaphor, but are all in essence instances of the same algorithmic template.
It is common to categorise 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 EA can be achieved by an appropriate choice of representation and variation operators. The optimality is a more complex issue. While 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 fitnesses) holds, an EA 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 based on a criterion grounded in the problem to be solved then the EA will tend to find solutions that optimise the fitness values, or at least approximate them. This implies that EAs can be used to solve optimisation problems and, consequently, any problem that can be transformed into an equivalent optimisation task. This includes most problems in design, and those connected with building or learning models from data. Nevertheless, it is important to understand that EAs are not optimizers 26 , but 'approximizers', and they are not optimal since we might not know whether a good evolved solution is the best possible. Nevertheless, 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 would 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 hard problems in a variety of scientific and technical domains, offering several advantages over traditional optimisation and design methods.
One appealing example from the design domain concerns X-band antennas for NASA's ST5 spacecraft 27 . The normal approach to this task is very time and labour intensive, relying heavily on expert knowledge. The EA-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 computerevolved hardware in space. This project also demonstrates a specific advantage of evolutionary over manual design. The EAs generated and tested thousands of completely new solutions, many exhibiting unusual structures that expert antenna designers would be unlikely to produce. Evolutionary algorithms have been also successful in many other cases in aeronautical and aerospace engineering. Problems in this field typically suffer from highly complex search spaces and multiple conflicting objectives. Population-based methods such as EAs have proven effective at meeting the challenges of this combination. In particular, so-called multi-objective EAs, 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 front 28 . Many examples can also been found in bio-informatics. For instance, Besnard et al. mined the ChEMBL database to discover a set of transformations of chemical structures that they then used as the mutation operator in an automated drug design application 29 . The results clearly showed 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 EC framework.
Numerical and combinatorial optimisation form important application areas of EAs. A particularly challenging class is black-box optimisation, where the nature of the objective function requires numerical (rather than analytical) methods, and gradient information can only be approximated by sampling solutions. A recent systematic experimental study compared mathematical programming and evolutionary computation on a range of synthetic black-box optimisation problems when allowed different amounts of computing time and resources 30 . The results showed that mathematical programming algorithms -that were designed to provide quick progress in the initial stages of the search-outperform EAs 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 the BIPOP-CMA-ES, is able to (1) find the optimum of a broader class of functions, (2) solve problems with a higher precision, and (3) solve some problems faster. The power of evolution strategies (especially the very successful CMA-ES variant 31 ) for real-life black-box optimisation problems from industry is treated extensively in the recent book by Bäck et al. 32 . Their evidence, gathered from many years experience of both academic research, and development for industrial applications, suggests that the niche for evolution strategies is formed by optimisation tasks with a very limited budget for how many solutions can have their fitness evaluated. Although this finding is not in line with the 'common wisdom' within the field, the book, and the references therein, provide ample support for this proposal.
Machine learning and modelling is another prominent area where evolutionary algorithms have proved their power, especially as many contemporary approaches otherwise rely on (often crude) greedy or local search to refine and optimise models. For example, neuroevolutionary approaches use EAs to optimise the structure, the parameters, or both simultaneously, of artificial neural networks 33,34 . In other branches of machine learning, using EC to design algorithms has been shown to be very effective as an alternative to hand-crafting them, for instance, for inducing decision-trees 35 . Furthermore, EAs have been applied to prediction problems. For instance, Widera et al. tackled the problem of predicting the tertiary structure of a protein by evolving a key component of automated predictors, the function used to estimate a structure's energy 36 . State of the art methods in protein structure prediction are limited by assuming linear combination of energy terms here, whereas a genetic programming (GP) method easily accommodates expressions based on a much richer syntax. The best energy function found by the GP algorithm provided significantly better prediction guidance than traditional functions. Their 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 another fruitful area. For example, Filipic et al. evolved control strategies for operating container cranes using a physical crane to determine fitness values 37 . The evolution of controllers is also possible in situ -for example, in a population of robots during, and not just before, their operational period 38,39 . Evolutionary robotics 40 is an especially challenging application area because of two additional issues that other branches of EC do not face: the very weak and noisy link between controllable design details and the target feature(s); and the great variety of conditions under which a solution should perform well. Normally in EC there is a 3-step evaluation chain: genotype ⇒ phenotype ⇒ fitness; for robots the chain is 4-fold: genotype ⇒ phenotype ⇒ behaviour ⇒ fitness a . 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 systems 41 . Several studies have demonstrated such benefits, where robot control systems that were automatically generated by artificial evolution were comparatively simpler or more efficient than those engineered using other design methods 42 . 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 hybridising 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 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 field 43,44,45 . Such hybrid algorithms can often find good (or better) solutions faster than a pure EA when the additional method searches systematically in the vicinity of good solutions, rather than relying on the more randomised search carried out by mutation 46,47 . For example, Smith et al. solved the Cell Suppression Problem -deciding which data cells to suppress in published statistical tables in order to protect respondent's confidentiality 48 . Using a combination of graph-partitioning, linear programming, and evolutionary optimisation of the sequence in which vulnerable cells were considered, they produced methods that could protect published statistical tables 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
Evolutionary algorithms have overcome considerable initial scepticism, and over the last twenty years evolutionary computation has grown to become a major field in computational intelligence 7,8,9 . As well as solving hard problems in various application areas, EAs have demonstrated that their emphasis on randomness as a source of variation has special 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 value 49,50,51,52 . The perception of evolution as a problem solver has broadened from seeing evolution as a heuristic algorithm for (parametric) optimisation to considering it as a powerful approach to (structural) design 53,54 .
In general, EAs have proven competitive in solving hard problems in the face of problem 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 parallelisation, mean that more and more generations can be executed within practically acceptable wall-clock time.
The performance of evolutionary algorithms has also been compared to that of human experts, and there is now substantial and well-documented evidence of EAs producing measurably humancompetitive results 55 . The annual competition for the so-called Humies Awards for humancompetitive results highlight a great variety of hard problems for which EAs delivered excellent solutions 56 .
The success and popularity of EAs can be attributed to a number of algorithmic features. In general, EAs are attractive because they are: • Assumption-free. Applying an EA 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 EAs make no explicit assumptions about the problem, hence they are widely applicable and easily transferable at low cost.
• Flexible. EAs can easily be used in collaboration with existing methods such as local search. They can be incorporated within, or make use of, existing toolsets. Combinations with domainspecific methods often lead to superior solvers because they can exploit the best features of different approaches.
• Robust. The use of a population and the randomized choices mean EAs are less likely to get trapped in sub-optimal solutions than other search methods. They also are less sensitive to noise or infidelity in the models of the system used to evaluate solutions, and can cope with changes in the problem.
• Not focussed on a single solution. Having a population means that an EA terminates with a number of solutions. Thus, users do not have to pre-specify their preferences and weightings 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.
• Capable of producing the unexpected. EAs have often been shown to find effective, but nonintuitive solutions, as they are blind to human preconceptions -often valuable in design domains.
The theoretical underpinning of EAs remains a hard nut to crack. Mathematical analysis can illuminate some properties, but even digital evolutionary processes exhibit very complex dynamics that allows only limited theory forming, despite the diverse set of tools and methods ranging from quantitative genetics to statistical physics 57 . One important theoretical result is the No Free Lunch Theorem. This states that EAs are not generic super solvers -but neither is any other method, because there is no such thing 58 . Instead, "an EA 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 traditional issue for theorists is algorithm convergence. Early results were based on Markov-chain analysis addressing convergence in general 59 , but more recent work found specific relationships between algorithmic setup and expected runtimes 60 . Despite all the difficulties, the field is making progress in theory 61,62 .

Important Research Trends
The development of evolutionary computation continues along a number of research threads.
Automated design and tuning of EAs. Experience has shown that there are several design choices behind an EA 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 setup for a given problem off-line (before the run), or on-line (during the run) 63 . Techniques such as automated parameter tuning 64,65,66,67 and adaptive parameter control continue to make advances in this area 68,69,70,71 .
Using surrogate models. Increasingly EAs are being used for problems where 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 refine those models via occasional full evaluations of targeted individuals 72,73,74,75 .
Handling many objectives. Having proven highly successful for finding solutions to problems with multiple objectives (typically up to ten) 76 , the community is now making rapid advances in the field of many objectives -moving way beyond the capabilities of other algorithms 77,78,79 . 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 art 51,52 . Recent results suggest a useful synergy, with periodic user interaction to incorporate preferences helping to focus search down to a more manageable set of dimensions 80 . 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 traditionally simple genotypephenotype mappings, the use of indirect encodings is gaining traction. Such generative and developmental representations allow the reuse of code which helps scale up the complexity of artificially-evolved phenotypes, for instance, in evolutionary robotics, artificial life, and morphogenetic engineering 81,82,83,84,85 .

Outlook
The range of problems to which EAs 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 EAs to embodied/embedded systems: that is, employing evolution in populations where 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 what they do. Examples include policies for Web-agents, information retrieval strategies, software for machinery and smart devices, and controllers for autonomous robots 86,87 . 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 optimisation 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 traditional design-and-deploy approach by a design-deploy-adapt loop where the evolutionary component is a principal part of the system. This approach is gaining traction in two areas already. 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 software 88 . Meanwhile, recent developments in rapid fabrication technologies (3D printing) and ever smaller and more powerful robotic platforms mean that EC is now starting to make the next major transition to the automated creation of physical artefacts and "smart" objects 89 . On the long term this can lead to a disruptive robotic technology where design and production are replaced by selection and reproduction without the involvement of human designers and human operated facilities.

INSERT FIGURE 2 HERE
Last but not least, we foresee a fruitful cross-fertilisation with biology in the coming decade based on a bi-directional flow of inspiration, understanding, and know-how. On the one hand, the advancing insights in molecular and evolutionary biology can be used to make more sophisticated evolutionary algorithms and may help solve previously intractable problems. The opportunities and challenges of this avenue have been outlined in a research agenda to transform artificial evolution to computational evolution 90 . On the other hand, a new kind of artificial evolution -the Evolution of Things-opens new horizons for biologists. As early as 1992 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 have to look at artificial ones" 91 . Artificial evolution implemented on real hardware, as in evolutionary robotics, offers a new research instrument to this end 42,92,93,94,95,96,97 . 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 algorithms 98 . 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. Observed quantity: a posteriori effect of selection and reproduction ("in the eye of the observer").
Predefined a priori quantity that drives selection and reproduction.

Selection
Complex multi-factor force based on environmental conditions, other individuals of the same species and other species (e.g., predators). Viability is tested continually; reproducibility is tested at discrete times.
Randomized operator with selection probabilities based on given fitness values. Parent selection and survivor selection both happen at discrete times.

Genotypephenotype mapping
Highly complex biochemical and developmental process influenced by the environment.
Typically a simple mathematical transformation or parameterised procedure. A few systems use generative and developmental genotype-phenotype maps.

Variation
Offspring are created from one (asexual reproduction) or two parents (sexual). Horizontal gene transfer can accumulate genes from more individuals.
Unconstrained vertical gene transfer. Offspring may be generated from any number of parents, one, two, or many.

Execution
Parallel, decentralized execution; birth and death events are not synchronised.
Typically centralized with synchronised birth and death.

Population
Spatial embedding implies structured populations. Population size varies according to the relative number of death and birth events. Populations can and do go extinct.
Typically unstructured and panmictic (all individuals are potential partners). Population size is usually kept constant by synchronising time and number of birth and death events.  In the 20th century computer technology enabled artificial Darwinian processes in silico -the evolution of digital entities. In the 21st century, developments in robotics, material science, and 3D printing enable the evolution of physical artefacts or machines.
Box 1: Examples of data structures frequently used as genotypes, and one suitable mutation operator for each, with its action shown by red arrows. Note that the mutation operator must deliver a child of the same data type -e.g. a valid mutation operator for permutations must result in a valid permutation. Complex problems might require complex genotypes with appropriate mutation operators.
A. Bitstrings are the natural choice for problems where solutions are composed from on/off or true/false decisions. The most commonly used mutation operator makes an independent choice in each position whether to invert the bit value. B. Permutations can be used when the problem involves ordering a set of entities, such as in routing or scheduling. One simple mutation operator swaps the values in two randomly selected locations. C. Real-valued vectors can capture continuous optimisation problems-for example where the variables represent quantities such as dimensions, or mass. Typically the mutation operator perturbs each value by adding a (small) random number. D. Trees are branching data structures suitable for representing equations, logical expressions or program code. A common mutation operator selects a node at random, and replaces the subtree below with a new, randomly generated one.