What’s holding artificial life back from open-ended evolution?

Posted September 1, 2015 by Emily Dolson in Research / 7 Comments

At ECAL 2015, Tim Taylor, Mark Bedau, and Alastair Channon organized a fascinating workshop on Open-Ended Evolution, which I presented at (you can watch the video here, but this post will basically cover the same points). Several of us in the Devolab have been thinking about this topic for a while; below is a collection of our thoughts for the sake of continuing this discussion.

The question of open-ended evolution emerged from a practical place: organisms and ecosystems in computational evolutionary systems were far less diverse, complex, and interesting than those that seen in nature. The people studying these systems were concerned that this was the result of a fundamental limitation to the systems (although some have also argued that this is just an issue of scale). They began characterizing the dynamics of these systems in an effort to figure out how open-ended they were; that is, to what extent the systems were capable of continuously dooing “interesting” things. In theory, it should be possible to compare systems and figure out what properties facilitate various kinds of interesting dynamics. However, progress toward achieving these sorts of comparisons has proved challenging. There is still a lack of consensus on how to define open-ended evolution, and without that, it’s hard to build a solid foundation for a sub-field.

We propose that it might be useful to turn the question on its head: When are we sure that a system is not open-ended? If a system isn’t open-ended, it must be getting stuck somehow. Indeed, we can identify several ways in which evolution may stagnate:

  1. The population stops changing at all after a certain point: As is often the case in genetic algorithms, the population may converge to a local optimum and never leave.
  2. Novel organisms stop appearing in the population: Perhaps the population doesn’t completely converge, but instead oscillates among a set survival strategies.
  3. Organismal complexity stops increasing: The organisms hit a limit on the amount of environmental information that they can incorporate into their genomes, preventing them from producing more sophisticated behaviors.
  4. Ecosystem diversity stagnates: The population as a whole hits a limit on the sum total of information about the environment that it is able to incorporate across genomes. Note that other organisms are part of the environment that any given organism experiences, so this effectively amounts to organisms creating new niches and trophic levels via their interactions with other organisms.
  5. Shifts in individuality are impossible. In nature, major transitions in evolution often change what it means to be an individual — the most profound example being the transition to multicellularity. Systems that pre-define what it means to be an individual fundamentally limit the types of evolution possible; theoretically an open-ended system should be able to undergo any number of such shifts.

This re-framing of the problem gives us a language to talk about the presence or absence of specific dynamics that we seek: Change, Novelty, Complexity, Ecology, and Transitions. As a result, we can focus on figuring out what properties of a system lead to which dynamics, and what the long-term outcomes of those dynamics tend to be. For example, the change barrier has long plagued evolutionary algorithms and is now well understood. Because of the resulting research, we have a variety of diversity maintenance techniques that can generally overcome this barrier (demonstrated in Figures 1 and 2). Similarly, novelty search has made great strides toward overcoming the novelty barrier.

Fig. 1: Potential of a simple NK bitstring model to resist getting stuck at the change barrier over 250 generations. Here, we measure change potential as the number of genotypes in the population that appeared after being absent for at least 10 generations and then survived one round of selection. This omits change due to non-beneficial mutations. Notice that change potential quickly drops off as the population converges to a local optimum.
Fig 2: Adding fitness sharing (a standard diversity maintenance technique involving negative frequency dependence) to the above set-up is sufficient to maintain consistently high change potential over evolutionary time.



Asking these types of questions allows us to formulate testable hypotheses by breaking down open-ended evolution into its fundamental components. Additionally, it allows us to classify the types of problems that a given system is able to solve in the context of evolutionary computation. Have a problem where you need to keep producing new solutions? Well, you better use an algorithm that’s better at overcoming the novelty barrier!

Notice the phrasing of that last sentence – some systems will be better or worse at overcoming a given barrier. These barriers are not a binary “you’re either stuck or you’re not”, just as we don’t think that it makes sense to frame open-ended evolution as a whole as a binary rather than a continuum. You can instead think of barriers as places where a system might get stuck. So the useful quantity to measure is a system’s potential to overcome a given barrier.

There are some clear relationships to the five barriers that we’ve defined so far (see Figure 3). If a system has novelty potential (i.e. it is capable of resisting the novelty barrier), then it must also have change potential; if new things keep appearing in the population, then it must also be true that that set of things in the population does not always remain the same. If a system has complexity potential, then it must also have novelty potential (and therefore also change potential), because if more complex organisms keep being produced, they must also be novel. Similarly, if a system has ecological potential, then it must also have novelty and change potential, because the new niches that keep getting created and filled must be filled with novel organisms. The relationship between complexity potential and ecological potential is less clear. Intuitively, it seems like they should facilitate each other. However, this is likely a question that requires empirical results to answer. Finally, if a system has individuals transition into new forms, such a change will likely involve increases in complexity and the opening of new niches, but neither is technically required for there to be a transition.

Flow chart indicating the dependencies of the four complexity barriers:. Novelty potential implies that there is change potentiall. Complexity potential and ecological potential both imply that there is novelty potential. The relationship between complexity potential and ecological potential is less clear. Transition potential clearly implies novelty potential and, in practice, compleixty potential and ecological potential. However, the latter two are not mathematically provable.
Fig. 3: Relationships between the potential to resist each of the five complexity barriers.

Our goal with these four complexity barriers is to provide metrics that can be rigorously mathematically tested in a broad range of systems. We’re in the process of implementing the analysis necessary to measure the potential of Avida experiments to overcome the first four of these barriers and would love to see them tested in many other systems as well. We’re also working on ideas on how to test the fifth, but the moment you no longer have a well defined concept of individual, the entire problem becomes much more challenging.

Do these five barriers capture the idea of open-ended evolution? Do you have ideas on how to measure them? Would biological systems be able to overcome some or all of these barriers?

Want to cite or review this post? Conveniently, we also posted it on The Winnower, so you can do just that!

Emily Dolson

I’m a doctoral student in the Ofria Lab at Michigan State University, the BEACON Center for Evolution in Action, and the departments of Computer Science and Ecology, Evolutionary Biology, & Behavior. My interests include studying eco-evolutionary dynamics via digital evolution and using evolutionary computation techniques to interpret time series data. I also have a cross-cutting interest in diversity in both biological and computational systems. In my spare time, I enjoy playing board games and the tin whistle.

More Posts - Website - Twitter

7 responses to “What’s holding artificial life back from open-ended evolution?

  1. Dear Emily,
    this is a very nice analysis. I am a physicist, so digital evolution is just a hobby of mine, but I have some observations based on my program called Evoversum. In my simulations, the complexity of the organisms seems to always hit a limit after several weeks of simulation. However, plotting various statistics (e.g. population size) shows that change is still present. Based on subjective assessment, novel organisms still appear but in a limited way.
    World size and habitat diversity is a huge factor. Genome representation is also important — Evoversum 2.2 actually manifests better evolvability than the 0.3_preview version, which has a different computation model.
    This I consider a relevant insight regarding evolvability: https://youtu.be/UBI33yXJZxg?t=13m55s
    Based on this insight, I intend to add some “fetal development” period to Evoversum. I cannot work on this now, but in November I intend to start working on the simulation again.

  2. I think the local peaks barrier is an artificial one due to us relying on ‘random’ landscapes, with this randomness resulting in computationally simple optimization problems. This seems like an unjustified assumption given that we don’t have any large (say on more than 20 genes) complete fitness landscapes, never-mind having an idea of what distributions over a family of fitness landscapes would look like. If we move away from randomly generating fitness landscapes then it is relatively easy to build families of hard landscapes where local peaks are hard to find: i.e. regardless of the (polynomial time computable) process we use to implement evolutionary dynamics, we can’t find even a local peak in polynomial. If we restrict our dynamics to just adaptive evolution or even further to fittest mutant or random fitter mutant then even rather simple seeming single-peaked landscapes can be difficult to find peaks in. See my preprint. for more info.

    Unfortunately, in that example — similar to the LTEE — I am looking at fitness as the measure. It could be argued that the organisms aren't really getting more "complex" (they are just bit strings, after all) as they increase in fitness. But I still think we can learn a lesson from this for richer models: pick environmental challenges or fitness landscapes that aren't random but are instances of problems that are known to be hard for complexity classes like polynomial local search.

    • I’ve only had a chance to skim your paper so far, but it looks interesting! Thanks for the link and the feedback! We’ve been doing a lot of this research with Mike Wiser, who did the work on unboundedness in the LTEE, so I completely agree that the change barrier is unlikely to be much of an issue in natural systems. However, within the realm of computational systems, getting stuck indefinitely on a local peak is pretty common across a wide variety of non-random fitness landscapes (including known hard problems). This may well be avoidable via the choice of different genetic representations and mutation operators, but in practice it remains a common problem. Since a big part of our goal with this framework is to understand the source of potential discrepancies between evolution inside a computer and evolution outside of a computer, we felt that that was an important obstacle to acknowledge.

Leave a Reply