What’s holding artificial life back from open-ended evolution?
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).
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 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.
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?
- 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.
Emily Dolson is PhD Student, BEACON Center for Evolution in Action Her interests include evolutionary computation, machine learning, evolutionary biology, and ecology.