Open-Ended Evolution: Perspectives from the OEE Workshop in York

Open-endedness in synthetic biology: A route to continual innovation for biological design

Design in synthetic biology is typically goal oriented, aiming to repurpose or optimize existing biological functions, augmenting biology with new-to-nature capabilities, or creating life-like systems from scratch. While the field has seen many advances, bottlenecks in the complexity of the systems built are emerging and designs that function in the lab often fail when used in real-world contexts. Here, we propose an open-ended approach to biological design, with the novelty of designed biology being at least as important as how well it fulfils its goal. Rather than solely focusing on optimization toward a single best design, designing with novelty in mind may allow us to move beyond the diminishing returns we see in performance for most engineered biology. Research from the artificial life community has demonstrated that embracing novelty can automatically generate innovative and unexpected solutions to challenging problems beyond local optima. Synthetic biology offers the ideal playground to explore more creative approaches to biological design.

The eco-evolutionary origins of life

The origin of life remains one of the greatest enigmas in science. The immense leap in complexity between prebiotic soup and cellular life challenges historically "chemistry-forward" and "biology-backwards" approaches. Evolution must have bridged this gap in complexity, so understanding factors that influence evolutionary outcomes is critical for exploring life's emergence. Here, we review insights from ecology and evolution and their application throughout abiogenesis. In particular, we discuss how ecological and evolutionary constraints shape the evolution of biological innovation. We propose an "eco-evolutionary" approach, which is agnostic towards particular chemistries or environments and instead explores the several ways that an evolvable system may emerge and gain complexity.

Simulating emergence of novelties using agent-based models

Understanding the growth and evolution of social networks is an important area of study, as these networks form the foundation for many popular online services such as social networking sites (SNS) and online games. However, previous models developed to explain the growth mechanisms of these networks have struggled to accurately reproduce certain behaviors that are frequently observed in real data, such as waves of novelty, in which new individuals or topics receive more attention than existing ones for a short period of time. In this study, we introduce a new model that incorporates context information into existing agent-based models in order to more accurately capture the structure and growth dynamics of these networks. Context information is introduced through labels based on the timing of appearance and relationships with antecedent agents. New agents are first added to the network when they are called by existing agents, and at this time they are also given a label. Agents added to the network at the same time by the same agent will have the same label. These labels are used to classify agents and give them different selection probabilities. This newly introduced selection probability creates a mechanism in which new agents receive attention beyond preferential attachment. By comparing the results of our model with real data on ten metrics, we demonstrate that it is able to produce behavior that more closely resembles real data. This improved understanding of the dynamics of social networks has important implications for designing effective interventions, including strategies for user acquisition and retention.

Does the Field of Nature-Inspired Computing Contribute to Achieving Lifelike Features?

The main idea behind artificial intelligence was simple: what if we study living systems to develop new, practical computing systems that possess "lifelike" properties? And that's exactly how evolutionary computing emerged. Researchers came up with ideas inspired by the principles of evolution to develop intelligent methods to tackle hard problems. The efficacy of these methods made researchers seek inspiration in living organisms and systems and extend the evolutionary concept to other nature-inspired ideas. In recent years, nature-inspired computing has exhibited an exponential increase in the number of algorithms that are presented each year. Authors claim that they are inspired by a behavior found in nature to come up with a lifelike algorithm. However, the mathematical background does not match the behavior in the majority of these cases. Thus the question is, do all nature-inspired algorithms remain lifelike? Also, are there any ideas included that contribute to computing? This study aims to (a) present some nature-inspired methods that contribute to achieving lifelike features of computing systems and (b) discuss if there is any need for new lifelike features.

How Turing parasites expand the computational landscape of digital life

Why are living systems complex? Why does the biosphere contain living beings with complexity features beyond those of the simplest replicators? What kind of evolutionary pressures result in more complex life forms? These are key questions that pervade the problem of how complexity arises in evolution. One particular way of tackling this is grounded in an algorithmic description of life: living organisms can be seen as systems that extract and process information from their surroundings to reduce uncertainty. Here we take this computational approach using a simple bit string model of coevolving agents and their parasites. While agents try to predict their worlds, parasites do the same with their hosts. The result of this process is that, to escape their parasites, the host agents expand their computational complexity despite the cost of maintaining it. This, in turn, is followed by increasingly complex parasitic counterparts. Such arms races display several qualitative phases, from monotonous to punctuated evolution or even ecological collapse. Our minimal model illustrates the relevance of parasites in providing an active mechanism for expanding living complexity beyond simple replicators, suggesting that parasitic agents are likely to be a major evolutionary driver for biological complexity.

Emergence in Artificial Life

Even when concepts similar to emergence have been used since antiquity, we lack an agreed definition. However, emergence has been identified as one of the main features of complex systems. Most would agree on the statement "life is complex." Thus understanding emergence and complexity should benefit the study of living systems. It can be said that life emerges from the interactions of complex molecules. But how useful is this to understanding living systems? Artificial Life (ALife) has been developed in recent decades to study life using a synthetic approach: Build it to understand it. ALife systems are not so complex, be they soft (simulations), hard (robots), or wet(protocells). Thus, we can aim at first understanding emergence in ALife, to then use this knowledge in biology. I argue that to understand emergence and life, it becomes useful to use information as a framework. In a general sense, I define emergence as information that is not present at one scale but present at another. This perspective avoids problems of studying emergence from a materialist framework and can also be useful in the study of self-organization and complexity.

Exploring Evolved Multicellular Life Histories in a Open-Ended Digital Evolution System

Evolutionary transitions occur when previously-independent replicating entities unite to form more complex individuals. Such transitions have profoundly shaped natural evolutionary history and occur in two forms: fraternal transitions involve lower-level entities that are kin (e.g., transitions to multicellularity or to eusocial colonies), while egalitarian transitions involve unrelated individuals (e.g., the origins of mitochondria). The necessary conditions and evolutionary mechanisms for these transitions to arise continue to be fruitful targets of scientific interest. Here, we examine a range of fraternal transitions in populations of open-ended self-replicating computer programs. These digital cells were allowed to form and replicate kin groups by selectively adjoining or expelling daughter cells. The capability to recognize kin-group membership enabled preferential communication and cooperation between cells. We repeatedly observed group-level traits that are characteristic of a fraternal transition. These included reproductive division of labor, resource sharing within kin groups, resource investment in offspring groups, asymmetrical behaviors mediated by messaging, morphological patterning, and adaptive apoptosis. We report eight case studies from replicates where transitions occurred and explore the diverse range of adaptive evolved multicellular strategies.

Evolving neural networks through bio-inspired parent selection in dynamic environments

Environmental variability often degrades the performance of algorithms designed to capture the global convergence of a given search space. Several approaches have been developed to challenge environmental uncertainty by incorporating biologically inspired notions, focusing on crossover, mutation, and selection. This study proposes a bio-inspired approach called NEAT-HD, which focuses on parent selection based on genetic similarity. The originality of the proposed approach rests on its use of a sigmoid function to accelerate species formation and contribute to population diversity. Experiments on two classic control tasks were performed to demonstrate the performance of the proposed method. The results show that NEAT-HD can dynamically adapt to its environment by forming hybrid individuals originating from genetically distinct parents. Additionally, an increase in diversity within the population was observed due to the formation of hybrids and novel individuals, which has never been observed before. Comparing two tasks, the characteristics of NEAT-HD were improved by appropriately setting the algorithm to include the distribution of genetic distance within the population. Our key finding is the inherent potential of newly formed individuals for robustness against dynamic environments.

Symbiosis in Digital Evolution: Past, Present, and Future

Symbiosis, the living together of unlike organisms as symbionts, is ubiquitous in the natural world. Symbioses occur within and across all scales of life, from microbial to macro-faunal systems. Further, the interactions between symbionts are multimodal in both strength and type, can span from parasitic to mutualistic within one partnership, and persist over generations. Studying the ecological and evolutionary dynamics of symbiosis in natural or laboratory systems poses a wide range of challenges, including the long time scales at which symbioses evolve de novo, the limited capacity to experimentally control symbiotic interactions, the weak resolution at which we can quantify interactions, and the idiosyncrasies of current model systems. These issues are especially challenging when seeking to understand the ecological effects and evolutionary pressures on and of a symbiosis, such as how a symbiosis may shift between parasitic and mutualistic modes and how that shift impacts the dynamics of the partner population. In digital evolution, populations of computational organisms compete, mutate, and evolve in a virtual environment. Digital evolution features perfect data tracking and allows for experimental manipulations that are impractical or impossible in natural systems. Furthermore, modern computational power allows experimenters to observe thousands of generations of evolution in minutes (as opposed to several months or years), which greatly expands the range of possible studies. As such, digital evolution is poised to become a keystone technique in our methodological repertoire for studying the ecological and evolutionary dynamics of symbioses. Here, we review how digital evolution has been used to study symbiosis, and we propose a series of open questions that digital evolution is well-positioned to answer.

Automated exploration of DNA-based structure self-assembly networks

Finding DNA sequences capable of folding into specific nanostructures is a hard problem, as it involves very large search spaces and complex nonlinear dynamics. Typical methods to solve it aim to reduce the search space by minimizing unwanted interactions through restrictions on the design (e.g. staples in DNA origami or voxel-based designs in DNA Bricks). Here, we present a novel methodology that aims to reduce this search space by identifying the relevant properties of a given assembly system to the emergence of various families of structures (e.g. simple structures, polymers, branched structures). For a given set of DNA strands, our approach automatically finds chemical reaction networks (CRNs) that generate sets of structures exhibiting ranges of specific user-specified properties, such as length and type of structures or their frequency of occurrence. For each set, we enumerate the possible DNA structures that can be generated through domain-level interactions, identify the most prevalent structures, find the best-performing sequence sets to the emergence of target structures, and assess CRNs' robustness to the removal of reaction pathways. Our results suggest a connection between the characteristics of DNA strands and the distribution of generated structure families.

Morphological Sensitivity and Falling Behavior of Paper V-Shapes

Behavioral diversity seen in biological systems is, at the most basic level, driven by interactions between physical materials and their environment. In this context we are interested in falling paper systems, specifically the V-shaped falling paper (VSFP) system that exhibits a set of discrete falling behaviors across the morphological parameter space. Our previous work has investigated how morphology influences dominant falling behaviors in the VSFP system. In this article we build on this analysis to investigate the nature of behavioral transitions in the same system. First, we investigate stochastic behavior transitions. We demonstrate how morphology influences the likelihood of different transitions, with certain morphologies leading to a wide range of possible paths through the behavior-space. Second, we investigate deterministic transitions. To investigate behaviors over longer time periods than available in falling experiments we introduce a new experimental platform. We demonstrate how we can induce behavior transitions by modulating the energy input to the system. Certain behavior transitions are found to be irreversible, exhibiting a form of hysteresis, while others are fully reversible. Certain morphologies are shown to behave like simplistic sequential logic circuits, indicating that the system has a form of memory encoded into the morphology-environment interactions. Investigating the limits of how morphology-environment interactions induce non-trivial behaviors is a key step for the design of embodied artificial life-forms.

Evolution of Autopoiesis and Multicellularity in the Game of Life

Recently we introduced a model of symbiosis, Model-S, based on the evolution of seed patterns in Conway's Game of Life. In the model, the fitness of a seed pattern is measured by one-on-one competitions in the Immigration Game, a two-player variation of the Game of Life. Our previous article showed that Model-S can serve as a highly abstract, simplified model of biological life: (1) The initial seed pattern is analogous to a genome. (2) The changes as the game runs are analogous to the development of the phenome. (3) Tournament selection in Model-S is analogous to natural selection in biology. (4) The Immigration Game in Model-S is analogous to competition in biology. (5) The first three layers in Model-S are analogous to biological reproduction. (6) The fusion of seed patterns in Model-S is analogous to symbiosis. The current article takes this analogy two steps further: (7) Autopoietic structures in the Game of Life (still lifes, oscillators, and spaceships-collectively known as ashes) are analogous to cells in biology. (8) The seed patterns in the Game of Life give rise to multiple, diverse, cooperating autopoietic structures, analogous to multicellular biological life. We use the apgsearch software (Ash Pattern Generator Search), developed by Adam Goucher for the study of ashes, to analyze autopoiesis and multicellularity in Model-S. We find that the fitness of evolved seed patterns in Model-S is highly correlated with the diversity and quantity of multicellular autopoietic structures.

Symbiosis Promotes Fitness Improvements in the Game of Life

We present a computational simulation of evolving entities that includes symbiosis with shifting levels of selection. Evolution by natural selection shifts from the level of the original entities to the level of the new symbiotic entity. In the simulation, the fitness of an entity is measured by a series of one-on-one competitions in the Immigration Game, a two-player variation of Conway's Game of Life. Mutation, reproduction, and symbiosis are implemented as operations that are external to the Immigration Game. Because these operations are external to the game, we can freely manipulate the operations and observe the effects of the manipulations. The simulation is composed of four layers, each layer building on the previous layer. The first layer implements a simple form of asexual reproduction, the second layer introduces a more sophisticated form of asexual reproduction, the third layer adds sexual reproduction, and the fourth layer adds symbiosis. The experiments show that a small amount of symbiosis, added to the other layers, significantly increases the fitness of the population. We suggest that the model may provide new insights into symbiosis in biological and cultural evolution.

Self-Organization and Artificial Life

Self-organization can be broadly defined as the ability of a system to display ordered spatiotemporal patterns solely as the result of the interactions among the system components. Processes of this kind characterize both living and artificial systems, making self-organization a concept that is at the basis of several disciplines, from physics to biology and engineering. Placed at the frontiers between disciplines, artificial life (ALife) has heavily borrowed concepts and tools from the study of self-organization, providing mechanistic interpretations of lifelike phenomena as well as useful constructivist approaches to artificial system design. Despite its broad usage within ALife, the concept of self-organization has been often excessively stretched or misinterpreted, calling for a clarification that could help with tracing the borders between what can and cannot be considered self-organization. In this review, we discuss the fundamental aspects of self-organization and list the main usages within three primary ALife domains, namely "soft" (mathematical/computational modeling), "hard" (physical robots), and "wet" (chemical/biological systems) ALife. We also provide a classification to locate this research. Finally, we discuss the usefulness of self-organization and related concepts within ALife studies, point to perspectives and challenges for future research, and list open questions. We hope that this work will motivate discussions related to self-organization in ALife and related fields.

Evolving Complexity in Cooperative and Competitive Noisy Prediction Games

We examine the effect of cooperative and competitive interactions on the evolution of complex strategies in a prediction game. We extend previous work to the domain of noisy games, defining a new organism and mutation model, and an accompanying novel complexity metric. We find that a mix of cooperation and competition is the most effective in driving complexity growth, confirming prior results. We also compare our complexity metric with simpler metrics such as raw strategy size, and demonstrate the effectiveness of our metric in distinguishing true complexity from mere genetic bloat.

Hidden Concepts in the History and Philosophy of Origins-of-Life Studies: a Workshop Report

In this review, we describe some of the central philosophical issues facing origins-of-life research and provide a targeted history of the developments that have led to the multidisciplinary field of origins-of-life studies. We outline these issues and developments to guide researchers and students from all fields. With respect to philosophy, we provide brief summaries of debates with respect to (1) definitions (or theories) of life, what life is and how research should be conducted in the absence of an accepted theory of life, (2) the distinctions between synthetic, historical, and universal projects in origins-of-life studies, issues with strategies for inferring the origins of life, such as (3) the nature of the first living entities (the "bottom up" approach) and (4) how to infer the nature of the last universal common ancestor (the "top down" approach), and (5) the status of origins of life as a science. Each of these debates influences the others. Although there are clusters of researchers that agree on some answers to these issues, each of these debates is still open. With respect to history, we outline several independent paths that have led to some of the approaches now prevalent in origins-of-life studies. These include one path from early views of life through the scientific revolutions brought about by Linnaeus (von Linn.), Wöhler, Miller, and others. In this approach, new theories, tools, and evidence guide new thoughts about the nature of life and its origin. We also describe another family of paths motivated by a" circularity" approach to life, which is guided by such thinkers as Maturana & Varela, Gánti, Rosen, and others. These views echo ideas developed by Kant and Aristotle, though they do so using modern science in ways that produce exciting avenues of investigation. By exploring the history of these ideas, we can see how many of the issues that currently interest us have been guided by the contexts in which the ideas were developed. The disciplinary backgrounds of each of these scholars has influenced the questions they sought to answer, the experiments they envisioned, and the kinds of data they collected. We conclude by encouraging scientists and scholars in the humanities and social sciences to explore ways in which they can interact to provide a deeper understanding of the conceptual assumptions, structure, and history of origins-of-life research. This may be useful to help frame future research agendas and bring awareness to the multifaceted issues facing this challenging scientific question.

Open-Ended Evolution and Open-Endedness: Editorial Introduction to the Open-Ended Evolution I Special Issue

Nature's spectacular inventiveness, reflected in the enormous diversity of form and function displayed by the biosphere, is a feature of life that distinguishes living most strongly from nonliving. It is, therefore, not surprising that this aspect of life should become a central focus of artificial life. We have known since Darwin that the diversity is produced dynamically, through the process of evolution; this has led life's creative productivity to be called Open-Ended Evolution (OEE) in the field. This article introduces the first of two special issues on current research on OEE and on the more general concept of open-endedness. Most of the papers presented in these special issues are elaborations of work presented at the Third Workshop on Open-Ended Evolution, held in Tokyo as part of the 2018 Conference on Artificial Life.

Open-Endedness for the Sake of Open-Endedness

Natural evolution keeps inventing new complex and intricate forms and behaviors. Digital evolution and genetic algorithms fail to create the same kind of complexity, not just because we still lack the computational resources to rival nature, but because (it has been argued) we have not understood in principle how to create open-ended evolving systems. Much effort has been made to define such open-endedness so as to create forms of increasing complexity indefinitely. Here, however, a simple evolving computational system that satisfies all such requirements is presented. Doing so reveals a shortcoming in the definitions for open-ended evolution. The goal to create models that rival biological complexity remains. This work suggests that our current definitions allow for even simple models to pass as open-ended, and that our definitions of complexity and diversity are more important for the quest of open-ended evolution than the fact that something runs indefinitely.

Cardinality Leap for Open-Ended Evolution: Theoretical Consideration and Demonstration by Hash Chemistry

Open-ended evolution requires unbounded possibilities that evolving entities can explore. The cardinality of a set of those possibilities thus has a significant implication for the open-endedness of evolution. I propose that facilitating formation of higher-order entities is a generalizable, effective way to cause a cardinality leap in the set of possibilities that promotes open-endedness. I demonstrate this idea with a simple, proof-of-concept toy model called Hash Chemistry that uses a hash function as a fitness evaluator of evolving entities of any size or order. Simulation results showed that the cumulative number of unique replicating entities that appeared in evolution increased almost linearly along time without an apparent bound, demonstrating the effectiveness of the proposed cardinality leap. It was also observed that the number of individual entities involved in a single replication event gradually increased over time, indicating evolutionary appearance of higher-order entities. Moreover, these behaviors were not observed in control experiments in which fitness evaluators were replaced by random number generators. This strongly suggests that the dynamics observed in Hash Chemistry were indeed evolutionary behaviors driven by selection and adaptation taking place at multiple scales.

Evolved Open-Endedness, Not Open-Ended Evolution

Open-endedness is often considered a prerequisite property of the whole evolutionary system and its dynamical behaviors. In the actual history of evolution on Earth, however, there are many examples showing that open-endedness is rather a consequence of evolution. We suggest that this view, which we call evolved open-endedness (EOE), be incorporated more into research on open-ended evolution. This view should allow for systematic investigation of more nuanced, more concrete research questions about open-endedness and its relationship with adaptation and sustainability.

Open-Ended Technological Innovation

We detect ongoing innovation in empirical data about human technological innovations. Ongoing technological innovation is a form of open-ended evolution, but it occurs in a nonbiological, cultural population that consists of actual technological innovations that exist in the real world. The change over time of this population of innovations seems to be quite open-ended. We take patented inventions as a proxy for technological innovations and mine public patent records for evidence of the ongoing emergence of technological innovations, and we compare two ways to detect it. One way detects the first instances of predefined patent pigeonholes, specifically the technology classes listed in the United States Patent Classification (USPC). The second way embeds patents in a high-dimensional semantic space and detects the emergence of new patent clusters. After analyzing hundreds of years of patent records, both methods detect the emergence of new kinds of technologies, but clusters are much better at detecting innovations that are unanticipated and undetected by USPC pigeonholes. Our clustering methods generalize to detect unanticipated innovations in other evolving populations that generate ongoing streams of digital data.

An Overview of Open-Ended Evolution: Editorial Introduction to the Open-Ended Evolution II Special Issue

Nature's spectacular inventiveness, reflected in the enormous diversity of form and function displayed by the biosphere, is a feature of life that distinguishes living most strongly from nonliving. It is, therefore, not surprising that this aspect of life should become a central focus of artificial life. We have known since Darwin that the diversity is produced dynamically, through the process of evolution; this has led life's creative productivity to be called Open-Ended Evolution (OEE) in the field. This article introduces the second of two special issues on current research in OEE and provides an overview of the contents of both special issues. Most of the work was presented at a workshop on open-ended evolution that was held as a part of the 2018 Conference on Artificial Life in Tokyo, and much of it had antecedents in two previous workshops on open-ended evolution at artificial life conferences in Cancun and York. We present a simplified categorization of OEE and summarize progress in the field as represented by the articles in this special issue.

Toward Open-Ended Fraternal Transitions in Individuality

The emergence of new replicating entities from the union of simpler entities characterizes some of the most profound events in natural evolutionary history. Such transitions in individuality are essential to the evolution of the most complex forms of life. Thus, understanding these transitions is critical to building artificial systems capable of open-ended evolution. Alas, these transitions are challenging to induce or detect, even with computational organisms. Here, we introduce the DISHTINY (Distributed Hierarchical Transitions in Individuality) platform, which provides simple cell-like organisms with the ability and incentive to unite into new individuals in a manner that can continue to scale to subsequent transitions. The system is designed to encourage these transitions so that they can be studied: Organisms that coordinate spatiotemporally can maximize the rate of resource harvest, which is closely linked to their reproductive ability. We demonstrate the hierarchical emergence of multiple levels of individuality among simple cell-like organisms that evolve parameters for manually designed strategies. During evolution, we observe reproductive division of labor and close cooperation among cells, including resource-sharing, aggregation of resource endowments for propagules, and emergence of an apoptosis response to somatic mutation. Many replicate populations evolved to direct their resources toward low-level groups (behaving like multicellular individuals), and many others evolved to direct their resources toward high-level groups (acting as larger-scale multicellular individuals).

Evolutionary Innovations and Where to Find Them: Routes to Open-Ended Evolution in Natural and Artificial Systems

This article presents a high-level conceptual framework to help orient the discussion and implementation of open-endedness in evolutionary systems. Drawing upon earlier work by Banzhaf et al. (2016), three different kinds of open-endedness are identified: exploratory, expansive, and transformational. These are characterized in terms of their relationship to the search space of phenotypic behaviors. A formalism is introduced to describe three key processes required for an evolutionary process: the generation of a phenotype from a genetic description, the evaluation of that phenotype, and the reproduction with variation of individuals according to their evaluation. The formalism makes explicit various influences in each of these processes that can easily be overlooked. The distinction is made between intrinsic and extrinsic implementations of these processes. A discussion then investigates how various interactions between these processes, and their modes of implementation, can lead to open-endedness. However, an important contribution of the article is the demonstration that these considerations relate to exploratory open-endedness only. Conditions for the implementation of the more interesting kinds of open-endedness-expansive and transformational-are also discussed, emphasizing factors such as multiple domains of behavior, transdomain bridges, and non-additive compositional systems. In contrast to a traditional Darwinian analysis, these factors relate not to the generic evolutionary properties of individuals and populations, but rather to the nature of the building blocks out of which individual organisms are constructed, and the laws and properties of the environment in which they exist. The article ends with suggestions of how the framework can be used to categorize and compare the open-ended evolutionary potential of different systems, how it might guide the design of systems with greater capacity for open-ended evolution, and how it might be further improved.

Open-Ended Evolution and a Mechanism of Novelties in Web Services

Web services are analogous to living ecosystems in nature, in that they form an artificial ecosystem consisting of many tags and their associated media, such as photographs, movies, and web pages created by human users. In biological ecosystems, we view a tag as a species and a human as a hidden environmental resource. Our study examines the evolution of web services, in particular social tagging systems, with respect to the self-organization of new tags. The evolution of new combinations of tags is analyzed as an open-ended evolution (OEE) index. Tag meaning is computed by types of associated tags, including tags that vary their meanings temporally, which, we argue, are examples of OEE.

Escalation of Memory Length in Finite Populations

The escalation of complexity is a commonly cited benefit of coevolutionary systems, but computational simulations generally fail to demonstrate this capacity to a satisfactory degree. We draw on a macroevolutionary theory of escalation to develop a set of criteria for coevolutionary systems to exhibit escalation of strategic complexity. By expanding on a previously developed model of the evolution of memory length for cooperative strategies by Kristian Lindgren, we resolve previously observed limitations on the escalation of memory length by extending operators of evolutionary variation. We present long-term coevolutionary simulations showing that larger population sizes tend to support greater escalation of complexity than smaller ones do. Additionally, we investigate the sensitivity of escalation during transitions of complexity. The Lindgren model has often been used to argue that the escalation of competitive coevolution has intrinsic limitations. Our simulations show that coevolutionary arms races can continue to escalate in computational simulations given sufficient population sizes.

Maximum Individual Complexity is Indefinitely Scalable in Geb

Geb was the first artificial life system to be classified as exhibiting open-ended evolutionary dynamics according to Bedau and Packard's evolutionary activity measures and is the only one to have been classified as such according to the enhanced version of that classification scheme. Its evolution is driven by biotic selection, that is (approximately), by natural selection rather than artificial selection. Whether or not Geb can generate an indefinite increase in maximum individual complexity is evaluated here by scaling two parameters: world length (which bounds population size) and the maximum number of neurons per individual. Maximum individual complexity is found to be asymptotically bounded when scaling either parameter alone. However, maximum individual complexity is found to be indefinitely scalable, to the extent evaluated so far (with run times in years and billions of reproductions per run), when scaling both world length and the maximum number of neurons per individual together. Further, maximum individual complexity is shown to scale logarithmically with (the lower of) maximum population size and maximum number of neurons per individual. This raises interesting questions and lines of thought about the feasibility of achieving complex results within open-ended evolutionary systems and how to improve on this order of complexity growth.

The MODES Toolbox: Measurements of Open-Ended Dynamics in Evolving Systems

Building more open-ended evolutionary systems can simultaneously advance our understanding of biology, artificial life, and evolutionary computation. In order to do so, however, we need a way to determine when we are moving closer to this goal. We propose a set of metrics that allow us to measure a system's ability to produce commonly-agreed-upon hallmarks of open-ended evolution: change potential, novelty potential, complexity potential, and ecological potential. Our goal is to make these metrics easy to incorporate into a system, and comparable across systems so that we can make coherent progress as a field. To this end, we provide detailed algorithms (including C++ implementations) for these metrics that should be easy to incorporate into existing artificial life systems. Furthermore, we expect this toolbox to continue to grow as researchers implement these metrics in new languages and as the community reaches consensus about additional hallmarks of open-ended evolution. For example, we would welcome a measurement of a system's potential to produce major transitions in individuality. To confirm that our metrics accurately measure the hallmarks we are interested in, we test them on two very different experimental systems: NK landscapes and the Avida digital evolution platform. We find that our observed results are consistent with our prior knowledge about these systems, suggesting that our proposed metrics are effective and should generalize to other systems.

How to Make Swarms Open-Ended? Evolving Collective Intelligence Through a Constricted Exploration of Adjacent Possibles

We propose an approach to open-ended evolution via the simulation of swarm dynamics. In nature, swarms possess remarkable properties, which allow many organisms, from swarming bacteria to ants and flocking birds, to form higher-order structures that enhance their behavior as a group. Swarm simulations highlight three important factors to create novelty and diversity: (a) communication generates combinatorial cooperative dynamics, (b) concurrency allows for separation of time scales, and (c) complexity and size increases push the system towards transitions in innovation. We illustrate these three components in a model computing the continuous evolution of a swarm of agents. The results, divided into three distinct applications, show how emergent structures are capable of filtering information through the bottleneck of their memory, to produce meaningful novelty and diversity within their simulated environment.

Why Open-Endedness Matters

Rather than acting as a review or analysis of the field, this essay focuses squarely on the motivations for investigating open-endedness and the opportunities it opens up. It begins by contemplating the awesome accomplishments of evolution in nature and the profound implications if such a process could be ignited on a computer. Some of the milestones in our understanding so far are then discussed, finally closing by highlighting the grand challenge of formalizing open-endedness as a computational process that can be encoded as an algorithm. The main contribution is to articulate why open-endedness deserves a place alongside artificial intelligence as one of the great computational challenges, and opportunities, of our time.

Two Modes of Evolution: Optimization and Expansion

We document and discuss two different modes of evolution across multiple systems, optimization and expansion. The former suffices in systems whose size and interactions do not change substantially over time, while the latter is a key property of open-ended evolution, where new players and interaction types enter the game. We first investigate systems from physics, biology, and engineering and argue that their evolutionary optimization dynamics is the cumulative effect of multiple independent events, or quakes, which are uniformly distributed on a logarithmic time scale and produce a decelerating fitness improvement when using the appropriate independent variable. The appropriate independent variable can be physical time for a disordered magnetic system, the number of generations for a bacterial system, or the number of produced units for a particular technological product. We then derive and discuss a simple microscopic theory that explains the nature of the involved optimization processes, and provide simulation results as illustration. Finally, we explore the evolution of human culture and technology, using empirical economic data as a proxy for human fitness. Assuming the overall dynamics is a combined optimization and expansion process, the two processes can be separated and quantified by superimposing the mathematical form of an optimization process on the empirical data and thereby transforming the independent variable. This variable turns out to increase faster than any exponential function of time, a property likely due to strong historical changes in the web of human interactions and to the associated increase in the amount of available knowledge. A microscopic theory for this time dependence remains, however, a challenging open problem.

Zipf's Law, unbounded complexity and open-ended evolution

A major problem for evolutionary theory is understanding the so-called open-ended nature of evolutionary change, from its definition to its origins. Open-ended evolution (OEE) refers to the unbounded increase in complexity that seems to characterize evolution on multiple scales. This property seems to be a characteristic feature of biological and technological evolution and is strongly tied to the generative potential associated with combinatorics, which allows the system to grow and expand their available state spaces. Interestingly, many complex systems presumably displaying OEE, from language to proteins, share a common statistical property: the presence of Zipf's Law. Given an inventory of basic items (such as words or protein domains) required to build more complex structures (sentences or proteins) Zipf's Law tells us that most of these elements are rare whereas a few of them are extremely common. Using algorithmic information theory, in this paper we provide a fundamental definition for open-endedness, which can be understood as postulates. Its statistical counterpart, based on standard Shannon information theory, has the structure of a variational problem which is shown to lead to Zipf's Law as the expected consequence of an evolutionary process displaying OEE. We further explore the problem of information conservation through an OEE process and we conclude that statistical information (standard Shannon information) is not conserved, resulting in the paradoxical situation in which the increase of information content has the effect of erasing itself. We prove that this paradox is solved if we consider non-statistical forms of information. This last result implies that standard information theory may not be a suitable theoretical framework to explore the persistence and increase of the information content in OEE systems.

Born to learn: The inspiration, progress, and future of evolved plastic artificial neural networks

Biological neural networks are systems of extraordinary computational capabilities shaped by evolution, development, and lifelong learning. The interplay of these elements leads to the emergence of biological intelligence. Inspired by such intricate natural phenomena, Evolved Plastic Artificial Neural Networks (EPANNs) employ simulated evolution in-silico to breed plastic neural networks with the aim to autonomously design and create learning systems. EPANN experiments evolve networks that include both innate properties and the ability to change and learn in response to experiences in different environments and problem domains. EPANNs' aims include autonomously creating learning systems, bootstrapping learning from scratch, recovering performance in unseen conditions, testing the computational advantages of particular neural components, and deriving hypotheses on the emergence of biological learning. Thus, EPANNs may include a large variety of different neuron types and dynamics, network architectures, plasticity rules, and other factors. While EPANNs have seen considerable progress over the last two decades, current scientific and technological advances in artificial neural networks are setting the conditions for radically new approaches and results. Exploiting the increased availability of computational resources and of simulation environments, the often challenging task of hand-designing learning neural networks could be replaced by more autonomous and creative processes. This paper brings together a variety of inspiring ideas that define the field of EPANNs. The main methods and results are reviewed. Finally, new opportunities and possible developments are presented.

Embodied Evolution in Collective Robotics: A Review

This article provides an overview of evolutionary robotics techniques applied to online distributed evolution for robot collectives, namely, embodied evolution. It provides a definition of embodied evolution as well as a thorough description of the underlying concepts and mechanisms. This article also presents a comprehensive summary of research published in the field since its inception around the year 2000, providing various perspectives to identify the major trends. In particular, we identify a shift from considering embodied evolution as a parallel search method within small robot collectives (fewer than 10 robots) to embodied evolution as an online distributed learning method for designing collective behaviors in swarm-like collectives. This article concludes with a discussion of applications and open questions, providing a milestone for past and an inspiration for future research.

Life as an emergent phenomenon: studies from a large-scale boid simulation and web data

A large group with a special structure can become the mother of emergence. We discuss this hypothesis in relation to large-scale boid simulations and web data. In the boid swarm simulations, the nucleation, organization and collapse dynamics were found to be more diverse in larger flocks than in smaller flocks. In the second analysis, large web data, consisting of shared photos with descriptive tags, tended to group together users with similar tendencies, allowing the network to develop a core-periphery structure. We show that the generation rate of novel tags and their usage frequencies are high in the higher-order cliques. In this case, novelty is not considered to arise randomly; rather, it is generated as a result of a large and structured network. We contextualize these results in terms of adjacent possible theory and as a new way to understand collective intelligence. We argue that excessive information and material flow can become a source of innovation.This article is part of the themed issue 'Reconceptualizing the origins of life'.

Origins of life: a problem for physics, a key issues review

The origins of life stands among the great open scientific questions of our time. While a number of proposals exist for possible starting points in the pathway from non-living to living matter, these have so far not achieved states of complexity that are anywhere near that of even the simplest living systems. A key challenge is identifying the properties of living matter that might distinguish living and non-living physical systems such that we might build new life in the lab. This review is geared towards covering major viewpoints on the origin of life for those new to the origin of life field, with a forward look towards considering what it might take for a physical theory that universally explains the phenomenon of life to arise from the seemingly disconnected array of ideas proposed thus far. The hope is that a theory akin to our other theories in fundamental physics might one day emerge to explain the phenomenon of life, and in turn finally permit solving its origins.

Towards open-ended evolution in self-replicating molecular systems

In this review we discuss systems of self-replicating molecules in the context of the origin of life and the synthesis of de novo life. One of the important aspects of life is the ability to reproduce and evolve continuously. In this review we consider some of the prerequisites for obtaining unbounded evolution of self-replicating molecules and describe some recent advances in this field. While evolution experiments involving self-replicating molecules have shown promising results, true open-ended evolution has not been realized so far. A full understanding of the requirements for open-ended evolution would provide a better understanding of how life could have emerged from molecular building blocks and what is needed to create a minimal form of life in the laboratory.

Formal Definitions of Unbounded Evolution and Innovation Reveal Universal Mechanisms for Open-Ended Evolution in Dynamical Systems

Open-ended evolution (OEE) is relevant to a variety of biological, artificial and technological systems, but has been challenging to reproduce in silico. Most theoretical efforts focus on key aspects of open-ended evolution as it appears in biology. We recast the problem as a more general one in dynamical systems theory, providing simple criteria for open-ended evolution based on two hallmark features: unbounded evolution and innovation. We define unbounded evolution as patterns that are non-repeating within the expected Poincare recurrence time of an isolated system, and innovation as trajectories not observed in isolated systems. As a case study, we implement novel variants of cellular automata (CA) where the update rules are allowed to vary with time in three alternative ways. Each is capable of generating conditions for open-ended evolution, but vary in their ability to do so. We find that state-dependent dynamics, regarded as a hallmark of life, statistically out-performs other candidate mechanisms, and is the only mechanism to produce open-ended evolution in a scalable manner, essential to the notion of ongoing evolution. This analysis suggests a new framework for unifying mechanisms for generating OEE with features distinctive to life and its artifacts, with broad applicability to biological and artificial systems.

Self-Replicators Emerge from a Self-Organizing Prebiotic Computer World

Amoeba, a computer platform inspired by the Tierra system, is designed to study the generation of self-replicating sequences of machine operations (opcodes) from a prebiotic world initially populated by randomly selected opcodes. Point mutations drive opcode sequences to become more fit as they compete for memory and CPU time. Significant features of the Amoeba system include the lack of artificial encapsulation (there is no write protection) and a computationally universal opcode basis set. Amoeba now includes two additional features: pattern-based addressing and injecting entropy into the system. It was previously thought such changes would make it highly unlikely that an ancestral replicator could emerge from a fortuitous combination of randomly selected opcodes. Instead, Amoeba shows a far richer emergence, exhibiting a self-organization phase followed by the emergence of self-replicators. First, the opcode basis set becomes biased. Second, short opcode building blocks are propagated throughout memory space. Finally, prebiotic building blocks can combine to form self-replicators. Self-organization is quantified by measuring the evolution of opcode frequencies, the size distribution of sequences, and the mutual information of opcode pairs.

An Experimental Framework for Generating Evolvable Chemical Systems in the Laboratory

Most experimental work on the origin of life has focused on either characterizing the chemical synthesis of particular biochemicals and their precursors or on designing simple chemical systems that manifest life-like properties such as self-propagation or adaptive evolution. Here we propose a new class of experiments, analogous to artificial ecosystem selection, where we select for spontaneously forming self-propagating chemical assemblages in the lab and then seek evidence of a response to that selection as a key indicator that life-like chemical systems have arisen. Since surfaces and surface metabolism likely played an important role in the origin of life, a key experimental challenge is to find conditions that foster nucleation and spread of chemical consortia on surfaces. We propose high-throughput screening of a diverse set of conditions in order to identify combinations of "food," energy sources, and mineral surfaces that foster the emergence of surface-associated chemical consortia that are capable of adaptive evolution. Identification of such systems would greatly advance our understanding of the emergence of self-propagating entities and the onset of adaptive evolution during the origin of life.