Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving.

Genetic Programming (GP) often uses large training sets and requires all individuals to be evaluated on all training cases during selection. Random down-sampled lexicase selection evaluates individuals on only a random subset of the training cases allowing for more individuals to be explored with the same amount of program executions. However, sampling randomly can exclude important cases from the down-sample for a number of generations, while cases that measure the same behavior (synonymous cases) may be overused. In this work, we introduce Informed Down-Sampled Lexicase Selection. This method leverages population statistics to build down-samples that contain more distinct and therefore informative training cases. Through an empirical investigation across two different GP systems (PushGP and Grammar-Guided GP), we find that informed down-sampling significantly outperforms random down-sampling on a set of contemporary program synthesis benchmark problems. Through an analysis of the created down-samples, we find that important training cases are included in the down-sample consistently across independent evolutionary runs and systems. We hypothesize that this improvement can be attributed to the ability of Informed Down-Sampled Lexicase Selection to maintain more specialist individuals over the course of evolution, while still benefiting from reduced per-evaluation costs.

Using the Comparative Hybrid Approach to Disentangle the Role of Substrate Choice on the Evolution of Cognition.

Understanding the structure and evolution of natural cognition is a topic of broad scientific interest, as is the development of an engineering toolkit to construct artificial cognitive systems. One open question is determining which components and techniques to use in such a toolkit. To investigate this question, we employ agent-based AI, using simple computational substrates (i.e., digital brains) undergoing rapid evolution. Such systems are an ideal choice as they are fast to process, easy to manipulate, and transparent for analysis. Even in this limited domain, however, hundreds of different computational substrates are used. While benchmarks exist to compare the quality of different substrates, little work has been done to build broader theory on how substrate features interact. We propose a technique called the Comparative Hybrid Approach and develop a proof-of-concept by systematically analyzing components from three evolvable substrates: recurrent artificial neural networks, Markov brains, and Cartesian genetic programming. We study the role and interaction of individual elements of these substrates by recombining them in a piecewise manner to form new hybrid substrates that can be empirically tested. Here, we focus on network sparsity, memory discretization, and logic operators of each substrate. We test the original substrates and the hybrids across a suite of distinct environments with different logic and memory requirements. While we observe many trends, we see that discreteness of memory and the Markov brain logic gates correlate with high performance across our test conditions. Our results demonstrate that the Comparative Hybrid Approach can identify structural subcomponents that predict task performance across multiple computational substrates.

The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities.

Evolution provides a creative fount of complex and subtle adaptations that often surprise the scientists who discover them. However, the creativity of evolution is not limited to the natural world: Artificial organisms evolving in computational environments have also elicited surprise and wonder from the researchers studying them. The process of evolution is an algorithmic process that transcends the substrate in which it occurs. Indeed, many researchers in the field of digital evolution can provide examples of how their evolving algorithms and organisms have creatively subverted their expectations or intentions, exposed unrecognized bugs in their code, produced unexpectedly adaptations, or engaged in behaviors and outcomes, uncannily convergent with ones found in nature. Such stories routinely reveal surprise and creativity by evolution in these digital worlds, but they rarely fit into the standard scientific narrative. Instead they are often treated as mere obstacles to be overcome, rather than results that warrant study in their own right. Bugs are fixed, experiments are refocused, and one-off surprises are collapsed into a single data point. The stories themselves are traded among researchers through oral tradition, but that mode of information transmission is inefficient and prone to error and outright loss. Moreover, the fact that these stories tend to be shared only among practitioners means that many natural scientists do not realize how interesting and lifelike digital organisms are and how natural their evolution can be. To our knowledge, no collection of such anecdotes has been published before. This article is the crowd-sourced product of researchers in the fields of artificial life and evolutionary computation who have provided first-hand accounts of such cases. It thus serves as a written, fact-checked collection of scientifically important and even entertaining stories. In doing so we also present here substantial evidence that the existence and importance of evolutionary surprises extends beyond the natural world, and may indeed be a universal property of all complex evolving systems.

Interpreting the Tape of Life: Ancestry-Based Analyses Provide Insights and Intuition about Evolutionary Dynamics.

Fine-scale evolutionary dynamics can be challenging to tease out when focused on the broad brush strokes of whole populations over long time spans. We propose a suite of diagnostic analysis techniques that operate on lineages and phylogenies in digital evolution experiments, with the aim of improving our capacity to quantitatively explore the nuances of evolutionary histories in digital evolution experiments. We present three types of lineage measurements: lineage length, mutation accumulation, and phenotypic volatility. Additionally, we suggest the adoption of four phylogeny measurements from biology: phylogenetic richness, phylogenetic divergence, phylogenetic regularity, and depth of the most-recent common ancestor. In addition to quantitative metrics, we also discuss several existing data visualizations that are useful for understanding lineages and phylogenies: state sequence visualizations, fitness landscape overlays, phylogenetic trees, and Muller plots. We examine the behavior of these metrics (with the aid of data visualizations) in two well-studied computational contexts: (1) a set of two-dimensional, real-valued optimization problems under a range of mutation rates and selection strengths, and (2) a set of qualitatively different environments in the Avida digital evolution platform. These results confirm our intuition about how these metrics respond to various evolutionary conditions and indicate their broad value.

The Evolutionary Origin of Associative Learning.

Learning is a widespread ability among animals and, like physical traits, is subject to evolution. But how did learning first arise? What selection pressures and phenotypic preconditions fostered its evolution? Neither the fossil record nor phylogenetic comparative studies provide answers to these questions. Here, we take a novel approach by studying digital organisms in environments that promote the evolution of navigation and associative learning. Starting with a nonlearning sessile ancestor, we evolve multiple populations in four different environments, each consisting of nutrient trails with various layouts. Trail nutrients cue organisms on which direction to follow, provided they evolve to acquire and use those cues. Thus, each organism is tested on how well it navigates a randomly selected trail before reproducing. We find that behavior evolves modularly and in a predictable sequence, where simpler behaviors are necessary precursors for more complex ones. Associative learning is only one of many successful behaviors to evolve, and its origin depends on the environment possessing certain information patterns that organisms can exploit. Environmental patterns that are stable across generations foster the evolution of reflexive behavior, while environmental patterns that vary across generations but remain consistent for periods within an organism's lifetime foster the evolution of learning behavior. Both types of environmental patterns are necessary, since the prior evolution of simple reflexive behaviors provides the building blocks for learning to arise. Finally, we observe that an intrinsic value system evolves alongside behavior and supports associative learning by providing reinforcement for behavior conditioning.

Suicidal selection: Programmed cell death can evolve in unicellular organisms due solely to kin selection.

ABSTRACT: Unicellular organisms can engage in a process by which a cell purposefully destroys itself, termed programmed cell death (PCD). While it is clear that the death of specific cells within a multicellular organism could increase inclusive fitness (e.g., during development), the origin of PCD in unicellular organisms is less obvious. Kin selection has been shown to help maintain instances of PCD in existing populations of unicellular organisms; however, competing hypotheses exist about whether additional factors are necessary to explain its origin. Those factors could include an environmental shift that causes latent PCD to be expressed, PCD hitchhiking on a large beneficial mutation, and PCD being simply a common pathology. Here, we present results using an artificial life model to demonstrate that kin selection can, in fact, be sufficient to give rise to PCD in unicellular organisms. Furthermore, when benefits to kin are direct-that is, resources provided to nearby kin-PCD is more beneficial than when benefits are indirect-that is, nonkin are injured, thus increasing the relative amount of resources for kin. Finally, when considering how strict organisms are in determining kin or nonkin (in terms of mutations), direct benefits are viable in a narrower range than indirect benefits. OPEN RESEARCH BADGES: This article has been awarded Open Data and Open Materials Badges. All materials and data are publicly accessible via the Open Science Framework at https://github.com/anyaevostinar/SuicidalAltruismDissertation/tree/master/LongTerm.

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).

Fluctuating environments select for short-term phenotypic variation leading to long-term exploration.

Genetic spaces are often described in terms of fitness landscapes or genotype-to-phenotype maps, where each genetic sequence is associated with phenotypic properties and linked to other genotypes that are a single mutational step away. The positions close to a genotype make up its "mutational landscape" and, in aggregate, determine the short-term evolutionary potential of a population. Populations with wider ranges of phenotypes in their mutational neighborhood are known to be more evolvable. Likewise, those with fewer phenotypic changes available in their local neighborhoods are more mutationally robust. Here, we examine whether forces that change the distribution of phenotypes available by mutation profoundly alter subsequent evolutionary dynamics. We compare evolved populations of digital organisms that were subject to either static or cyclically-changing environments. For each of these, we examine diversity of the phenotypes that are produced through mutations in order to characterize the local genotype-phenotype map. We demonstrate that environmental change can push populations toward more evolvable mutational landscapes where many alternate phenotypes are available, though purely deleterious mutations remain suppressed. Further, we show that populations in environments with harsh changes switch phenotypes more readily than those in environments with more benign changes. We trace this effect to repeated population bottlenecks in the harsh environments, which result in shorter coalescence times and keep populations in regions of the mutational landscape where the phenotypic shifts in question are more likely to occur. Typically, static environments select solely for immediate optimization, at the expensive of long-term evolvability. In contrast, we show that with changing environments, short-term pressures to deal with immediate challenges can align with long-term pressures to explore a more productive portion of the mutational landscape.

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.

Spatial Structure Can Decrease Symbiotic Cooperation.

Mutualisms occur when at least two species provide a net fitness benefit to each other. These types of interactions are ubiquitous in nature, with more being discovered regularly. Mutualisms are vital to humankind: Pollinators and soil microbes are critical in agriculture, bacterial microbiomes regulate our health, and domesticated animals provide us with food and companionship. Many hypotheses exist on how mutualisms evolve; however, they are difficult to evaluate without bias, due to the fragile and idiosyncratic systems most often investigated. Instead, we have created an artificial life simulation, Symbulation, which we use to examine mutualism evolution based on (1) the probability of vertical transmission (symbiont being passed to offspring) and (2) the spatial structure of the environment. We found that spatial structure can lead to less mutualism at intermediate vertical transmission rates. We provide evidence that this effect is due to the ability of quasi species to purge parasites, reducing the diversity of available symbionts. Our simulation is easily extended to test many additional hypotheses about the evolution of mutualism and serves as a general model to quantitatively compare how different environments affect the evolution of mutualism.

The genotype-phenotype map of an evolving digital organism.

To understand how evolving systems bring forth novel and useful phenotypes, it is essential to understand the relationship between genotypic and phenotypic change. Artificial evolving systems can help us understand whether the genotype-phenotype maps of natural evolving systems are highly unusual, and it may help create evolvable artificial systems. Here we characterize the genotype-phenotype map of digital organisms in Avida, a platform for digital evolution. We consider digital organisms from a vast space of 10141 genotypes (instruction sequences), which can form 512 different phenotypes. These phenotypes are distinguished by different Boolean logic functions they can compute, as well as by the complexity of these functions. We observe several properties with parallels in natural systems, such as connected genotype networks and asymmetric phenotypic transitions. The likely common cause is robustness to genotypic change. We describe an intriguing tension between phenotypic complexity and evolvability that may have implications for biological evolution. On the one hand, genotypic change is more likely to yield novel phenotypes in more complex organisms. On the other hand, the total number of novel phenotypes reachable through genotypic change is highest for organisms with simple phenotypes. Artificial evolving systems can help us study aspects of biological evolvability that are not accessible in vastly more complex natural systems. They can also help identify properties, such as robustness, that are required for both human-designed artificial systems and synthetic biological systems to be evolvable.

WebAL Comes of Age: A Review of the First 21 Years of Artificial Life on the Web.

We present a survey of the first 21 years of web-based artificial life (WebAL) research and applications, broadly construed to include the many different ways in which artificial life and web technologies might intersect. Our survey covers the period from 1994-when the first WebAL work appeared-up to the present day, together with a brief discussion of relevant precursors. We examine recent projects, from 2010-2015, in greater detail in order to highlight the current state of the art. We follow the survey with a discussion of common themes and methodologies that can be observed in recent work and identify a number of likely directions for future work in this exciting area.

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

We describe the content and outcomes of the First Workshop on Open-Ended Evolution: Recent Progress and Future Milestones (OEE1), held during the ECAL 2015 conference at the University of York, UK, in July 2015. We briefly summarize the content of the workshop's talks, and identify the main themes that emerged from the open discussions. Two important conclusions from the discussions are: (1) the idea of pluralism about OEE-it seems clear that there is more than one interesting and important kind of OEE; and (2) the importance of distinguishing observable behavioral hallmarks of systems undergoing OEE from hypothesized underlying mechanisms that explain why a system exhibits those hallmarks. We summarize the different hallmarks and mechanisms discussed during the workshop, and list the specific systems that were highlighted with respect to particular hallmarks and mechanisms. We conclude by identifying some of the most important open research questions about OEE that are apparent in light of the discussions. The York workshop provides a foundation for a follow-up OEE2 workshop taking place at the ALIFE XV conference in Cancún, Mexico, in July 2016. Additional materials from the York workshop, including talk abstracts, presentation slides, and videos of each talk, are available at http://alife.org/ws/oee1 .

Genetically integrated traits and rugged adaptive landscapes in digital organisms.

BACKGROUND: When overlapping sets of genes encode multiple traits, those traits may not be able to evolve independently, resulting in constraints on adaptation. We examined the evolution of genetically integrated traits in digital organisms-self-replicating computer programs that mutate, compete, adapt, and evolve in a virtual world. We assessed whether overlap in the encoding of two traits - here, the ability to perform different logic functions - constrained adaptation. We also examined whether strong opposing selection could separate otherwise entangled traits, allowing them to be independently optimized. RESULTS: Correlated responses were often asymmetric. That is, selection to increase one function produced a correlated response in the other function, while selection to increase the second function caused a complete loss of the ability to perform the first function. Nevertheless, most pairs of genetically integrated traits could be successfully disentangled when opposing selection was applied to break them apart. In an interesting exception to this pattern, the logic function AND evolved counter to its optimum in some populations owing to selection on the EQU function. Moreover, the EQU function showed the strongest response to selection only after it was disentangled from AND, such that the ability to perform AND was lost. Subsequent analyses indicated that selection against AND had altered the local adaptive landscape such that populations could cross what would otherwise have been an adaptive valley and thereby reach a higher fitness peak. CONCLUSIONS: Correlated responses to selection can sometimes constrain adaptation. However, in our study, even strongly overlapping genes were usually insufficient to impose long-lasting constraints, given the input of new mutations that fueled selective responses. We also showed that detailed information about the adaptive landscape was useful for predicting the outcome of selection on correlated traits. Finally, our results illustrate the richness of evolutionary dynamics in digital systems and highlight their utility for studying processes thought to be important in biological systems, but which are difficult to investigate in those systems.

Coevolution drives the emergence of complex traits and promotes evolvability.

The evolution of complex organismal traits is obvious as a historical fact, but the underlying causes--including the role of natural selection--are contested. Gould argued that a random walk from a necessarily simple beginning would produce the appearance of increasing complexity over time. Others contend that selection, including coevolutionary arms races, can systematically push organisms toward more complex traits. Methodological challenges have largely precluded experimental tests of these hypotheses. Using the Avida platform for digital evolution, we show that coevolution of hosts and parasites greatly increases organismal complexity relative to that otherwise achieved. As parasites evolve to counter the rise of resistant hosts, parasite populations retain a genetic record of past coevolutionary states. As a consequence, hosts differentially escape by performing progressively more complex functions. We show that coevolution's unique feedback between host and parasite frequencies is a key process in the evolution of complexity. Strikingly, the hosts evolve genomes that are also more phenotypically evolvable, similar to the phenomenon of contingency loci observed in bacterial pathogens. Because coevolution is ubiquitous in nature, our results support a general model whereby antagonistic interactions and natural selection together favor both increased complexity and evolvability.

The effect of conflicting pressures on the evolution of division of labor.

Within nature, many groups exhibit division of labor. Individuals in these groups are under seemingly antagonistic pressures to perform the task most directly beneficial to themselves and to potentially perform a less desirable task to ensure the success of the group. Performing experiments to study how these pressures interact in an evolutionary context is challenging with organic systems because of long generation times and difficulties related to group propagation and fine-grained control of within-group and between-group pressures. Here, we use groups of digital organisms (i.e., self-replicating computer programs) to explore how populations respond to antagonistic multilevel selection pressures. Specifically, we impose a within-group pressure to perform a highly-rewarded role and a between-group pressure to perform a diverse suite of roles. Thus, individuals specializing on highly-rewarded roles will have a within-group advantage, but groups of such specialists have a between-group disadvantage. We find that digital groups could evolve to be either single-lineage or multi-lineage, depending on experimental parameters. These group compositions are reminiscent of different kinds of major evolutionary transitions that occur within nature, where either relatives divide labor (fraternal transitions) or multiple different organisms coordinate activities to form a higher-level individual (egalitarian transitions). Regardless of group composition, organisms embraced phenotypic plasticity as a means for genetically similar individuals to perform different roles. Additionally, in multi-lineage groups, organisms from lineages performing highly-rewarded roles also employed reproductive restraint to ensure successful coexistence with organisms from other lineages.

The evolutionary origin of somatic cells under the dirty work hypothesis.

Reproductive division of labor is a hallmark of multicellular organisms. However, the evolutionary pressures that give rise to delineated germ and somatic cells remain unclear. Here we propose a hypothesis that the mutagenic consequences associated with performing metabolic work favor such differentiation. We present evidence in support of this hypothesis gathered using a computational form of experimental evolution. Our digital organisms begin each experiment as undifferentiated multicellular individuals, and can evolve computational functions that improve their rate of reproduction. When such functions are associated with moderate mutagenic effects, we observe the evolution of reproductive division of labor within our multicellular organisms. Specifically, a fraction of the cells remove themselves from consideration as propagules for multicellular offspring, while simultaneously performing a disproportionately large amount of mutagenic work, and are thus classified as soma. As a consequence, other cells are able to take on the role of germ, remaining quiescent and thus protecting their genetic information. We analyze the lineages of multicellular organisms that successfully differentiate and discover that they display unforeseen evolutionary trajectories: cells first exhibit developmental patterns that concentrate metabolic work into a subset of germ cells (which we call "pseudo-somatic cells") and later evolve to eliminate the reproductive potential of these cells and thus convert them to actual soma. We also demonstrate that the evolution of somatic cells enables phenotypic strategies that are otherwise not easily accessible to undifferentiated organisms, though expression of these new phenotypic traits typically includes negative side effects such as aging.

Understanding evolutionary potential in virtual CPU instruction set architectures.

We investigate fundamental decisions in the design of instruction set architectures for linear genetic programs that are used as both model systems in evolutionary biology and underlying solution representations in evolutionary computation. We subjected digital organisms with each tested architecture to seven different computational environments designed to present a range of evolutionary challenges. Our goal was to engineer a general purpose architecture that would be effective under a broad range of evolutionary conditions. We evaluated six different types of architectural features for the virtual CPUs: (1) genetic flexibility: we allowed digital organisms to more precisely modify the function of genetic instructions, (2) memory: we provided an increased number of registers in the virtual CPUs, (3) decoupled sensors and actuators: we separated input and output operations to enable greater control over data flow. We also tested a variety of methods to regulate expression: (4) explicit labels that allow programs to dynamically refer to specific genome positions, (5) position-relative search instructions, and (6) multiple new flow control instructions, including conditionals and jumps. Each of these features also adds complication to the instruction set and risks slowing evolution due to epistatic interactions. Two features (multiple argument specification and separated I/O) demonstrated substantial improvements in the majority of test environments, along with versions of each of the remaining architecture modifications that show significant improvements in multiple environments. However, some tested modifications were detrimental, though most exhibit no systematic effects on evolutionary potential, highlighting the robustness of digital evolution. Combined, these observations enhance our understanding of how instruction architecture impacts evolutionary potential, enabling the creation of architectures that support more rapid evolution of complex solutions to a broad range of challenges.

Experiments on the role of deleterious mutations as stepping stones in adaptive evolution.

Many evolutionary studies assume that deleterious mutations necessarily impede adaptive evolution. However, a later mutation that is conditionally beneficial may interact with a deleterious predecessor before it is eliminated, thereby providing access to adaptations that might otherwise be inaccessible. It is unknown whether such sign-epistatic recoveries are inconsequential events or an important factor in evolution, owing to the difficulty of monitoring the effects and fates of all mutations during experiments with biological organisms. Here, we used digital organisms to compare the extent of adaptive evolution in populations when deleterious mutations were disallowed with control populations in which such mutations were allowed. Significantly higher fitness levels were achieved over the long term in the control populations because some of the deleterious mutations served as stepping stones across otherwise impassable fitness valleys. As a consequence, initially deleterious mutations facilitated the evolution of complex, beneficial functions. We also examined the effects of disallowing neutral mutations, of varying the mutation rate, and of sexual recombination. Populations evolving without neutral mutations were able to leverage deleterious and compensatory mutation pairs to overcome, at least partially, the absence of neutral mutations. Substantially raising or lowering the mutation rate reduced or eliminated the long-term benefit of deleterious mutations, but introducing recombination did not. Our work demonstrates that deleterious mutations can play an important role in adaptive evolution under at least some conditions.

A case study of the de novo evolution of a complex odometric behavior in digital organisms.

Investigating the evolution of animal behavior is difficult. The fossil record leaves few clues that would allow us to recapitulate the path that evolution took to build a complex behavior, and the large population sizes and long time scales required prevent us from re-evolving such behaviors in a laboratory setting. We present results of a study in which digital organisms-self-replicating computer programs that are subject to mutations and selection-evolved in different environments that required information about past experience for fitness-enhancing behavioral decisions. One population evolved a mechanism for step-counting, a surprisingly complex odometric behavior that was only indirectly related to enhancing fitness. We examine in detail the operation of the evolved mechanism and the evolutionary transitions that produced this striking example of a complex behavior.