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

  1. 1.  BEACON Center for Evolution in Action
  2. 2.  Michigan State University

Abstract

Evolutionary artificial life systems have demonstrated many exciting behaviors. However, there is a general consensus that these systems are missing some element of the consistent evolutionary innovation that we see in nature. Many have sought to create more "open-ended" evolutionary systems in which no stagnation occurs, but have been stymied by the difficulty of quantifying progress towards such a nebulous concept. Here, we propose an alternate framework for thinking about these problems. By measuring obstacles to continued innovation, we can move towards a mechanistic understanding of what drives various evolutionary dynamics. We propose that this framework will allow for more rigorous hypothesis testing and clearer applications of these concepts to evolutionary computation.

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) (Bedau et al, 2000). 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 doing “interesting” things (Bedau et al, 1997). 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:

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

·      Novel organisms stop appearing in the population: Perhaps the population doesn’t completely converge, but instead oscillates among a set survival strategies.

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

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

·      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 (Lehman and Stanley, 2008).

igure_1

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.

igure_2

Fig 2: Adding fitness sharing (a standard diversity maintenance technique involving negative frequency dependence developed by Goldberg and Richardson (1987)) 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.

low 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?

Bibliography:

·      Bedau, Mark A., Emile Snyder, C. Titus Brown, and Norman H. Packard. "A comparison of evolutionary activity in artificial evolving systems and in the biosphere." In Proceedings of the fourth European Conference on Artificial life, pp. 125-134. MIT Press/Bradford Books, 1997, ISBN: 0262581574.

·      Bedau, Mark A., John S. McCaskill, Norman H. Packard, Steen Rasmussen, Chris Adami, David G. Green, Takashi Ikegami, Kunihiko Kaneko, and Thomas S. Ray. "Open problems in artificial life." Artificial life 6, no. 4 (2000): 363-376, doi:10.1162/106454600300103683.

·      Goldberg, David E., and Jon Richardson. 1987. “Genetic Algorithms with Sharing for Multimodal Function Optimization.” In Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, 41–49. Hillsdale, NJ: Lawrence Erlbaum, ISBN: 978-0805801590.

·      Lehman, Joel, and Kenneth O. Stanley. 2008. “Exploiting Open-Endedness to Solve Problems Through the Search for Novelty.” In ALIFE, 329–36, doi:10.1162/EVCO_a_00025.

Reviews

Showing 2 Reviews

  • Tim york office sep2015 crop
    Tim Taylor
    Confidence in paper
    Quality of figures
    Quality of writing
    Originality of work
    4

    I completely agree that there are a variety of issues that come under the umbrella term of "open ended evolution", and I think this is a very useful attempt to spell out some of those issues for the purpose of developing specific metrics for each one.

    I read two papers this morning: this one, and Maggie Boden's new paper "Creativity and ALife" (Artificial Life 21(3) 354-365, 2015). There are some interesting parallels between the two: Boden concludes that "despite the astonishing ingenuity of the living world... the *limits* on biological creativity are interesting too. ALifers might want to consider that their task is not only to describe 'life as it is' and 'life as it could be'..., but also life as it couldn't be--and to explain why." The current paper can be seen as a step in that direction.

    One important point: this paper is all about evolutionary potential and barriers, and that is perfectly fine. But on top of this, an important additional aspect of OEE is *drive*. Just because a system is theoretically capable of (say) major transitions, such transitions will only occur if the appropriate evolutionary selection pressures exist.

    [Minor typo: the sentence immediately below Fig 3: "these four complexity barriers": "four"->"five"]

    I look forward to seeing how this work develops.

    Tim Taylor

    [I have no competing interests]

  • Placeholder
    Phillip Rhodes
    Confidence in paper
    Quality of figures
    Quality of writing
    Originality of work
    0

    I like what you've done here, and definitely agree that a framework for formalizing the potential of evolutionary systems will be a valuable tool. What I'll be looking forward to now, are some specific examples of existing (or new) systems, evaluated using this framework. I may try to apply it to some of my own work soon. If I find anything useful, I'll be sure to respond.

    [I have no competing interests.]

License

This article and its reviews are distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and redistribution in any medium, provided that the original author and source are credited.