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.

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.

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.

Digital Evolution for Ecology Research: A Review

In digital evolution, populations of computational organisms evolve via the same principles that govern natural selection in nature. These platforms have been used to great effect as a controlled system in which to conduct evolutionary experiments and develop novel evolutionary theory. In addition to their complex evolutionary dynamics, many digital evolution systems also produce rich ecological communities. As a result, digital evolution is also a powerful tool for research on eco-evolutionary dynamics. Here, we review the research to date in which digital evolution platforms have been used to address eco-evolutionary (and in some cases purely ecological) questions. This work has spanned a wide range of topics, including competition, facilitation, parasitism, predation, and macroecological scaling laws. We argue for the value of further ecological research in digital evolution systems and present some particularly promising directions for further research.

Adaptive Phenotypic Plasticity Stabilizes Evolution in Fluctuating Environments

Fluctuating environmental conditions are ubiquitous in natural systems, and populations have evolved various strategies to cope with such fluctuations. The particular mechanisms that evolve profoundly influence subsequent evolutionary dynamics. One such mechanism is phenotypic plasticity, which is the ability of a single genotype to produce alternate phenotypes in an environmentally dependent context. Here, we use digital organisms (self-replicating computer programs) to investigate how adaptive phenotypic plasticity alters evolutionary dynamics and influences evolutionary outcomes in cyclically changing environments. Specifically, we examined the evolutionary histories of both plastic populations and non-plastic populations to ask: (1) Does adaptive plasticity promote or constrain evolutionary change? (2) Are plastic populations better able to evolve and then maintain novel traits? And (3), how does adaptive plasticity affect the potential for maladaptive alleles to accumulate in evolving genomes? We find that populations with adaptive phenotypic plasticity undergo less evolutionary change than non-plastic populations, which must rely on genetic variation from de novo mutations to continuously readapt to environmental fluctuations. Indeed, the non-plastic populations undergo more frequent selective sweeps and accumulate many more genetic changes. We find that the repeated selective sweeps in non-plastic populations drive the loss of beneficial traits and accumulation of maladaptive alleles, whereas phenotypic plasticity can stabilize populations against environmental fluctuations. This stabilization allows plastic populations to more easily retain novel adaptive traits than their non-plastic counterparts. In general, the evolution of adaptive phenotypic plasticity shifted evolutionary dynamics to be more similar to that of populations evolving in a static environment than to non-plastic populations evolving in an identical fluctuating environment. All natural environments subject populations to some form of change; our findings suggest that the stabilizing effect of phenotypic plasticity plays an important role in subsequent adaptive evolution.

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

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.

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.

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.

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

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.

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 10¹⁴¹ 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.

The phenotype of an organism comprises the set of morphological and functional traits encoded by its genome. In natural evolving systems, phenotypes are organized into mutationally connected networks of genotypes, which increase the likelihood for an evolving population to encounter novel adaptive phenotypes (i.e., its evolvability). We do not know whether artificial systems, such as self-replicating and evolving computer programs—digital organisms—are more or less evolvable than natural systems. By studying how genotypes map onto phenotypes in digital organisms, we characterize many commonalities between natural and artificial evolving systems. In addition, we show that phenotypic complexity can both facilitate and constrain evolution, which harbors lessons not only for designing evolvable artificial systems, but also for synthetic biology.

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.

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.

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.

Evolving digital ecological networks

"It is hard to realize that the living world as we know it is just one among many possibilities" [1]. Evolving digital ecological networks are webs of interacting, self-replicating, and evolving computer programs (i.e., digital organisms) that experience the same major ecological interactions as biological organisms (e.g., competition, predation, parasitism, and mutualism). Despite being computational, these programs evolve quickly in an open-ended way, and starting from only one or two ancestral organisms, the formation of ecological networks can be observed in real-time by tracking interactions between the constantly evolving organism phenotypes. These phenotypes may be defined by combinations of logical computations (hereafter tasks) that digital organisms perform and by expressed behaviors that have evolved. The types and outcomes of interactions between phenotypes are determined by task overlap for logic-defined phenotypes and by responses to encounters in the case of behavioral phenotypes. Biologists use these evolving networks to study active and fundamental topics within evolutionary ecology (e.g., the extent to which the architecture of multispecies networks shape coevolutionary outcomes, and the processes involved).

Task-switching costs promote the evolution of division of labor and shifts in individuality

From microbes to humans, the success of many organisms is achieved by dividing tasks among specialized group members. The evolution of such division of labor strategies is an important aspect of the major transitions in evolution. As such, identifying specific evolutionary pressures that give rise to group-level division of labor has become a topic of major interest among biologists. To overcome the challenges associated with studying this topic in natural systems, we use actively evolving populations of digital organisms, which provide a unique perspective on the de novo evolution of division of labor in an open-ended system. We provide experimental results that address a fundamental question regarding these selective pressures: Does the ability to improve group efficiency through the reduction of task-switching costs promote the evolution of division of labor? Our results demonstrate that as task-switching costs rise, groups increasingly evolve division of labor strategies. We analyze the mechanisms by which organisms coordinate their roles and discover strategies with striking biological parallels, including communication, spatial patterning, and task-partitioning behaviors. In many cases, under high task-switching costs, individuals cease to be able to perform tasks in isolation, instead requiring the context of other group members. The simultaneous loss of functionality at a lower level and emergence of new functionality at a higher level indicates that task-switching costs may drive both the evolution of division of labor and also the loss of lower-level autonomy, which are both key components of major transitions in evolution.

Selective pressures for accurate altruism targeting: evidence from digital evolution for difficult-to-test aspects of inclusive fitness theory

Inclusive fitness theory predicts that natural selection will favour altruist genes that are more accurate in targeting altruism only to copies of themselves. In this paper, we provide evidence from digital evolution in support of this prediction by competing multiple altruist-targeting mechanisms that vary in their accuracy in determining whether a potential target for altruism carries a copy of the altruist gene. We compete altruism-targeting mechanisms based on (i) kinship (kin targeting), (ii) genetic similarity at a level greater than that expected of kin (similarity targeting), and (iii) perfect knowledge of the presence of an altruist gene (green beard targeting). Natural selection always favoured the most accurate targeting mechanism available. Our investigations also revealed that evolution did not increase the altruism level when all green beard altruists used the same phenotypic marker. The green beard altruism levels stably increased only when mutations that changed the altruism level also changed the marker (e.g. beard colour), such that beard colour reliably indicated the altruism level. For kin- and similarity-targeting mechanisms, we found that evolution was able to stably adjust altruism levels. Our results confirm that natural selection favours altruist genes that are increasingly accurate in targeting altruism to only their copies. Our work also emphasizes that the concept of targeting accuracy must include both the presence of an altruist gene and the level of altruism it produces.

Natural selection fails to optimize mutation rates for long-term adaptation on rugged fitness landscapes

The rate of mutation is central to evolution. Mutations are required for adaptation, yet most mutations with phenotypic effects are deleterious. As a consequence, the mutation rate that maximizes adaptation will be some intermediate value. Here, we used digital organisms to investigate the ability of natural selection to adjust and optimize mutation rates. We assessed the optimal mutation rate by empirically determining what mutation rate produced the highest rate of adaptation. Then, we allowed mutation rates to evolve, and we evaluated the proximity to the optimum. Although we chose conditions favorable for mutation rate optimization, the evolved rates were invariably far below the optimum across a wide range of experimental parameter settings. We hypothesized that the reason that mutation rates evolved to be suboptimal was the ruggedness of fitness landscapes. To test this hypothesis, we created a simplified landscape without any fitness valleys and found that, in such conditions, populations evolved near-optimal mutation rates. In contrast, when fitness valleys were added to this simple landscape, the ability of evolving populations to find the optimal mutation rate was lost. We conclude that rugged fitness landscapes can prevent the evolution of mutation rates that are optimal for long-term adaptation. This finding has important implications for applied evolutionary research in both biological and computational realms.

On the gradual evolution of complexity and the sudden emergence of complex features

Evolutionary theory explains the origin of complex organismal features through a combination of reusing and extending information from less-complex traits, and by needing to exploit only one of many unlikely pathways to a viable solution. While the appearance of a new trait may seem sudden, we show that the underlying information associated with each trait evolves gradually. We study this process using digital organisms, self-replicating computer programs that mutate and evolve novel traits, including complex logic operations. When a new complex trait first appears, its proper function immediately requires the coordinated operation of many genomic positions. As the information associated with a trait increases, the probability of its simultaneous introduction drops exponentially, so it is nearly impossible for a significantly complex trait to appear without reusing existing information. We show that the total information stored in the genome increases only marginally when a trait first appears. Furthermore, most of the information associated with a new trait is either correlated with existing traits or co-opted from traits that were lost in conjunction with the appearance of the new trait. Thus, while total genomic information increases incrementally, traits that require much more information can still arise during the evolutionary process.

Effects of population size and mutation rate on the evolution of mutational robustness

It is often assumed that the efficiency of selection for mutational robustness would be proportional to mutation rate and population size, thus being inefficient in small populations. However, Krakauer and Plotkin (2002) hypothesized that selection in small populations would favor robustness mechanisms, such as redundancy, that mask the effect of deleterious mutations. In large populations, by contrast, selection is more effective at removing deleterious mutants and fitness would be improved by eliminating mechanisms that mask the effect of deleterious mutations and thus impede their removal. Here, we test whether these predictions are supported in experiments with evolving populations of digital organisms. Digital organisms are self-replicating programs that inhabit a virtual world inside a computer. Like their organic counterparts, digital organisms mutate, compete, evolve, and adapt by natural selection to their environment. In this study, 160 populations evolved at different combinations of mutation rate and population size. After 10(4) generations, we measured the mutational robustness of the most abundant genotype in each population. Mutational robustness tended to increase with mutation rate and to decline with population size, although the dependence with population size was in part mediated by a negative relationship between fitness and robustness. These results are independent of whether genomes were constrained to their original length or allowed to change in size.

Balancing robustness and evolvability

Can a single unifying mathematical framework help to explain robustness - the ability of organisms to persist in the face of changing conditions - at all biological scales, from biochemical to ecological?

Ecological Specialization and Adaptive Decay in Digital Organisms

The transition from generalist to specialist may entail the loss of unused traits or abilities, resulting in narrow niche breadth. Here we examine the process of specialization in digital organisms--self-replicating computer programs that mutate, adapt, and evolve. Digital organisms obtain energy by performing computations with numbers they input from their environment. We examined the evolutionary trajectory of generalist organisms in an ecologically narrow environment, where only a single computation yielded energy. We determined the extent to which improvements in this one function were associated with losses of other functions, leading to organisms that were highly specialized to perform only one or a few functions. Our results show that as organisms evolved improved performance of the selected function, they often lost the ability to perform other computations, and these losses resulted most often from the accumulation of neutral and deleterious mutations. Beneficial mutations, although relatively rare, were disproportionately likely to cause losses of function, indicating that antagonistic pleiotropy contributed significantly to niche breadth reductions in this system. Occasionally, unused functions were not lost and even increased in performance. Here we find that understanding how the functions were integrated into the genome was crucial to predictions of their maintenance.

Sexual reproduction reshapes the genetic architecture of digital organisms

Modularity and epistasis, as well as other aspects of genetic architecture, have emerged as central themes in evolutionary biology. Theory suggests that modularity promotes evolvability, and that aggravating (synergistic) epistasis among deleterious mutations facilitates the evolution of sex. Here, by contrast, we investigate the evolution of different genetic architectures using digital organisms, which are computer programs that self-replicate, mutate, compete and evolve. Specifically, we investigate how genetic architecture is shaped by reproductive mode. We allowed 200 populations of digital organisms to evolve for over 10 000 generations while reproducing either asexually or sexually. For 10 randomly chosen organisms from each population, we constructed and analysed all possible single mutants as well as one million mutants at each mutational distance from 2 to 10. The genomes of sexual organisms were more modular than asexual ones; sites encoding different functional traits had less overlap and sites encoding a particular trait were more tightly clustered. Net directional epistasis was alleviating (antagonistic) in both groups, although the overall strength of this epistasis was weaker in sexual than in asexual organisms. Our results show that sexual reproduction profoundly influences the evolution of the genetic architecture.

Adaptive radiation from resource competition in digital organisms

Species richness often peaks at intermediate productivity and decreases as resources become more or less abundant. The mechanisms that produce this pattern are not completely known, but several previous studies have suggested environmental heterogeneity as a cause. In experiments with evolving digital organisms and populations of fixed size, maximum species richness emerges at intermediate productivity, even in a spatially homogeneous environment, owing to frequency-dependent selection to exploit an influx of mixed resources. A diverse pool of limiting resources is sufficient to cause adaptive radiation, which is manifest by the origin and maintenance of phenotypically and phylogenetically distinct groups of organisms.

Perspective: Evolution and detection of genetic robustness

Robustness is the invariance of phenotypes in the face of perturbation. The robustness of phenotypes appears at various levels of biological organization, including gene expression, protein folding, metabolic flux, physiological homeostasis, development, and even organismal fitness. The mechanisms underlying robustness are diverse, ranging from thermodynamic stability at the RNA and protein level to behavior at the organismal level. Phenotypes can be robust either against heritable perturbations (e.g., mutations) or nonheritable perturbations (e.g., the weather). Here we primarily focus on the first kind of robustness--genetic robustness--and survey three growing avenues of research: (1) measuring genetic robustness in nature and in the laboratory; (2) understanding the evolution of genetic robustness: and (3) exploring the implications of genetic robustness for future evolution.

Avida: a software platform for research in computational evolutionary biology

Avida is a software platform for experiments with self-replicating and evolving computer programs. It provides detailed control over experimental settings and protocols, a large array of measurement tools, and sophisticated methods to analyze and post-process experimental data. We explain the general principles on which Avida is built, as well as its main components and their interactions. We also explain how experiments are set up, carried out, and analyzed.

Using Avida to test the effects of natural selection on phylogenetic reconstruction methods

Phylogenetic trees group organisms by their ancestral relationships. There are a number of distinct algorithms used to reconstruct these trees from molecular sequence data, but different methods sometimes give conflicting results. Since there are few precisely known phylogenies, simulations are typically used to test the quality of reconstruction algorithms. These simulations randomly evolve strings of symbols to produce a tree, and then the algorithms are run with the tree leaves as inputs. Here we use Avida to test two widely used reconstruction methods, which gives us the chance to observe the effect of natural selection on tree reconstruction. We find that if the organisms undergo natural selection between branch points, the methods will be successful even on very large time scales. However, these algorithms often falter when selection is absent.

Selective pressures on genomes in molecular evolution

We describe the evolution of macromolecules as an information transmission process and apply tools from Shannon information theory to it. This allows us to isolate three independent, competing selective pressures that we term compression, transmission, and neutrality selection. The first two affect genome length: the pressure to conserve resources by compressing the code, and the pressure to acquire additional information that improves the channel, increasing the rate of information transmission into each offspring. Noisy transmission channels (replication with mutations) give rise to a third pressure that acts on the actual encoding of information; it maximizes the fraction of mutations that are neutral with respect to the phenotype. This neutrality selection has important implications for the evolution of evolvability. We demonstrate each selective pressure in experiments with digital organisms.

The evolutionary origin of complex features

A long-standing challenge to evolutionary theory has been whether it can explain the origin of complex organismal features. We examined this issue using digital organisms--computer programs that self-replicate, mutate, compete and evolve. Populations of digital organisms often evolved the ability to perform complex logic functions requiring the coordinated execution of many genomic instructions. Complex functions evolved by building on simpler functions that had evolved earlier, provided that these were also selectively favoured. However, no particular intermediate stage was essential for evolving complex functions. The first genotypes able to perform complex functions differed from their non-performing parents by only one or two mutations, but differed from the ancestor by many mutations that were also crucial to the new functions. In some cases, mutations that were deleterious when they appeared served as stepping-stones in the evolution of complex features. These findings show how complex functions can originate by random mutation and natural selection.

Evolution of digital organisms at high mutation rates leads to survival of the flattest

Darwinian evolution favours genotypes with high replication rates, a process called 'survival of the fittest'. However, knowing the replication rate of each individual genotype may not suffice to predict the eventual survivor, even in an asexual population. According to quasi-species theory, selection favours the cloud of genotypes, interconnected by mutation, whose average replication rate is highest. Here we confirm this prediction using digital organisms that self-replicate, mutate and evolve. Forty pairs of populations were derived from 40 different ancestors in identical selective environments, except that one of each pair experienced a 4-fold higher mutation rate. In 12 cases, the dominant genotype that evolved at the lower mutation rate achieved a replication rate >1.5-fold faster than its counterpart. We allowed each of these disparate pairs to compete across a range of mutation rates. In each case, as mutation rate was increased, the outcome of competition switched to favour the genotype with the lower replication rate. These genotypes, although they occupied lower fitness peaks, were located in flatter regions of the fitness surface and were therefore more robust with respect to mutations.

Evolution of biological complexity

To make a case for or against a trend in the evolution of complexity in biological evolution, complexity needs to be both rigorously defined and measurable. A recent information-theoretic (but intuitively evident) definition identifies genomic complexity with the amount of information a sequence stores about its environment. We investigate the evolution of genomic complexity in populations of digital organisms and monitor in detail the evolutionary transitions that increase complexity. We show that, because natural selection forces genomes to behave as a natural "Maxwell Demon," within a fixed environment, genomic complexity is forced to increase.

Genome complexity, robustness and genetic interactions in digital organisms

Digital organisms are computer programs that self-replicate, mutate and adapt by natural selection. They offer an opportunity to test generalizations about living systems that may extend beyond the organic life that biologists usually study. Here we have generated two classes of digital organism: simple programs selected solely for rapid replication, and complex programs selected to perform mathematical operations that accelerate replication through a set of defined 'metabolic' rewards. To examine the differences in their genetic architecture, we introduced millions of single and multiple mutations into each organism and measured the effects on the organism's fitness. The complex organisms are more robust than the simple ones with respect to the average effects of single mutations. Interactions among mutations are common and usually yield higher fitness than predicted from the component mutations assuming multiplicative effects; such interactions are especially important in the complex organisms. Frequent interactions among mutations have also been seen in bacteria, fungi and fruitflies. Our findings support the view that interactions are a general feature of genetic systems.