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