OEE1: Open Ended Evolution: Recent Progress and Future Milestones

Barry McMullin

Dublin City University, Ireland

Karl Popper, artificial life, and the curious tale of the hopeful behavioural monster

Darwinian evolution is the foundation on which Karl Popper effectively built an entire philosophical system, now generally referred to as critical rationalism or (my preference) evolutionary epistemology. Notwithstanding this biological foundation, it is rare - almost unknown - to find references to Popper in the literature of Artificial Life. I think this is a pity and an oversight. To that end, my contribution will be to (re-)present a little known thought experiment developed by Popper over half a century ago; an experiment which we can properly (if somewhat anachronistically) classify as a foray into the philosophy of Artificial Life. I will argue that this experiment, dated as it will seem, might still provide some useful conceptual clarity to better understand the problems of "open ended" evolution.

Wolfgang Banzhaf

Memorial University of Newfoundland, Canada

Open-endedness and novelty in evolution

It is clear that a deep connection exists between the concepts of open-endedness of an evolutionary process and it ability to continuously create novelty. As a result, different types of novelty produce different types of open-endedness in a system. We shall discuss these relations by examples with a particular emphasis on the underlying driving forces.

Tim Taylor

University of York, UK

Requirements for open-ended evolution in natural and artificial systems

Open ended evolutionary dynamics remains an elusive goal for artificial evolutionary systems. Many ideas exist in the biological literature beyond the basic Darwinian requirements of variation, differential reproduction and inheritance. I argue that these ideas can be seen as aspects of five fundamental requirements for open ended evolution: (1) robustly reproductive individuals, (2) a medium allowing the existence of complex individuals and interactions, (3) individuals capable of producing more complex offspring, (4) mutational pathways to other viable individuals, and (5) drive for continued evolution. I briefly discuss implications of this view for the design of artificial systems with greater evolutionary potential.

Guillaume Beslon

INRIA, France

Is biological evolution open-ended?

Open-Ended Evolution (OEE) is a central topic in artificial life. One on the main claims in the field is that life is the sole system that really shows open-endedness. However, this claim is in striking contrast with the fact the OEE is almost never discussed in the field of evolutionary biology. Indeed, evolutionary biology often concentrates its effort on mechanisms that are likely to preclude open-endedness (e.g., stabilising selection, purifying selection, neutrality...) that, on the opposite, are overlooked by artificial life. In my presentation, I will try to discuss that point and try to show that it provides interesting insights on what Open-Ended Evolution may be and why we would like to simulate it.

Dave Ackley

University of New Mexico, USA

Indefinite Scalability for Open-Ended Evolution

We expect open-ended evolution to display major transitions in which subpopulations coalesce and share fate, the unit of selection expands in space and time, and the spatiotemporal variance of the prior unit of selection largely vanishes. In a fixed-size discrete evolutionary model, at best a fixed number of such transitions can occur before the unit of selection's effective population size drops to one, its lifetime becomes unbounded, and evolutionary innovation stops, regardless of model runtime. Although any spatially-unbounded model element -- such as a variable genome size -- can technically avoid this argument, without a robust spatial design the potential transitions are likely to be tortured and exponentially unreachable. Evolutionary models framed as indefinitely scalable computations -- which explicitly reject all spatial limits, both obvious and subtle -- stand to offer a first-principles alternative.

Alastair Channon

Keele University, UK

Normalised evolutionary activity statistics and the need for phenotypic evidence

This short talk will briefly revisit the definition of open-ended evolution (OEE) used for the Artificial Life XI (2008) theme on OEE, my system Geb, which was designed to produce OEE, the use of normalised evolutionary activity statistics in its analysis, and its empirical results. I will then discuss its weaknesses in order to draw out the following critical future research milestones: more systems with an OEE classification from normalised evolutionary activity statistics; evidence of complex artefacts or behaviours arising from evolutionary changes (rather than from a very small number of mutations from a hard-coded ancestor); and evidence of non-trivial long (evolutionary) sequences of evolved artefacts or behaviours.

Norman Packard

Earth Life Science Institute, Tokyo Institute of Technology, Japan & ProtoLife Inc, USA

Emergence of emergence

(Work in collaboration with Nicholas Guttenberg, Earth Life Science Institute, Tokyo Institute of Technology, Japan)

Evolutionary processes are paradigmatic examples of emergence, with innovations surviving in a population through survival of the fittest. But how do evolutionary processes emerge from non-evolutionary dynamics? We hold that understanding this "first step" of evolution, where the essentially novel functionality of chemical encoding emerges, is key to understanding open-ended evolution more generally. We show that a broad class of high dimensional dynamical systems whose dynamics have a characteristic alternation between non-stable and stable fixed point behavior tend to sequester information so that it persists on long time scales, and can serve as a proto-genetic code on which evolutionary processes may begin to act. We show that this information sequestration occurs through the action of an information bottleneck caused by the alternation between stable fixed-point dynamics (Lyapunov spectrum λi ≤ 0 ∀ i), and non-stable dynamics (Lyapunov spectrum λi ≥ 0 for at least one value of i). Attractors that characterize the asymptotic behavior of low-dimensional systems are replaced by migrations between long time-scale metastable states, for these proto-evolutionary systems. We suggest that information bottlenecks may be a general mechanism at work in other examples of emergent functionality.

Nathaniel Virgo

Earth Life Science Institute, Tokyo Institute of Technology, Japan

Open-ended fitness landscapes

I suggest that in principle, open-ended evolution can be achieved using nothing but the traditional genetic algorithm paradigm of a population of binary strings evaluated with a fixed fitness function. The core challenge is to find a fitness function where a more complex solution is always possible, and always accessible from the current state. This seems to arise often in the physical world because of the large number of degrees of freedom in physical systems. Solutions can differ not only in fitness but also in evolvability, and I argue that this is a crucial part of the picture. We may now have the computing power to observe open-ended innovation in silico; by understanding it in the absence of factors such as niche construction and ecological interactions we may better appreciate the role they play.

Mark Bedau

Reed College, USA

Empirical measurements of "door-opening" evolution of technology

This talk describes current work on empirical measurements of a specific form of open-endedness in the evolution of technology. The form of evolution is termed door-opening, because it involves the production of a rich and diverse array of different kinds of new technologies. The International Patent Classification (IPC) categories assigned by human patent examiners can be combined with the citations that existing patents accumulate when new inventions refer to the "prior art" in the new invention to measure the degree to which a patent opens doors to new kinds of technological innovation (Buchanan et al 2011). The idea is that the scope of a patent’s impact on new technologies can be measured by the diversity of the IPC categories of the new patents that it helps spawn. By focusing on a real example of cultural evolution (Chalmers et al. 2010), this work complements other studies of open-ended evolution in real biological populations or computer models.

Simon Hickinbotham

University of York, UK

The OEE measure - will it blend?

In the "will it blend" infomercials, Tom Dickson attempts to blend various unusual items in order to show off the power of his blender. I suggest OEE measures are similar - they crunch numbers and create graphics, but you'd never want them to be used on the system you hold dear. I'll be presenting two papers in the main ECAL conference that use a new measure of evolutionary activity to compare different configurations of ALife systems (Tierra in one paper, Stringmol in another). In this "lightning talk" I'll give a two-slide overview of the measure, showing how it can be used to compare similar systems with respect to evolutionary activity. In the spirit of this workshop, I shall focus on the shortcomings of OEE measures in general, and suggest a few milestones we might agree on in developing and measuring OEE systems.

Steen Rasmussen

University of Southern Denmark & Santa Fe Institute, USA

Minimal life and open-ended evolution

We have for more than a decade studied how the environment, self-assembly (dG ≤ 0) and self-organization (dG > 0) may play together to generate (minimal) self-replicating physicochemical systems. Although we have not yet been able to integrate all the necessary processes to implement a fully autonomous protocell, we have a pretty clear idea of the protocell’s observable properties including a lacking ability to evolve in an open-ended manner. Our current design only allows an optimization of its metabolic rate through a selection of appropriate compositional information on its "genes". How could this simple and concrete system be enriched/engineered to accommodate more interesting evolutionary innovations? Is a more complex environment enough?

Emily Dolson

BEACON Center, Michigan State University, USA

Understanding complexity barriers in evolving systems

Limitations to open-ended evolution can be reframed and quantified by considering them as complexity barriers. We can measure organismal complexity as the information content of genomes, while community complexity is the cumulative information distributed across a population. Understanding the mechanisms by which information is acquired and synthesized by genomes has practical implications, including rectifying shortcomings in artificial systems’ ability to reflect natural dynamics and broadening the complexity of problems solvable in evolutionary computation. As such, we are systematically exploring how environmental characteristics (such as density dependent selection, spatial heterogeneity, or group-level selection) influence the acquisition of genetic information.

Takashi Ikegami

University of Tokyo, Japan

A new design principle for open-ended evolution

Biological evolution is the unique example of "open-ended evolution (OEE)", except for the technological advances progressed by mankind. Do we need a human brain/living system to have OEE? Does OEE paraphrase what is life as we also paraphrase living states as time flow? Can we design an artificial life that has OEE? I will discuss necessary and sufficient conditions for OEE based on the analysis of the Web dynamics, proposing a new design principle for making OEE possible in alife.

Tom Froese

National Autonomous University of Mexico, Mexico City

Groundlessness avoids openness reduction in hierarchies of emergence

One way of measuring open-endedness is in terms of the maintenance or increase of degrees of freedom. If emergence is defined as the collective dynamics resulting from nonlinear coupling between two or more components, then the degrees of freedom of the emergent phenomenon cannot in principle be greater than the sum of degrees of freedom of its underlying components. In practice, it tends to be less than that sum because the collective dynamics are subject to more constraints than the isolated dynamics of each component. The same logic applies to the creation of novelty at each emergent level of organization, thereby rapidly choking off possibilities for open-ended emergence of new layers of complexity. This is not a problem in practice if we consider nature to have sufficient degrees of complexity to begin with (although this is a problem for simulations). I propose that this is not even a problem in principle if we consider nature to be groundless (although this excludes simulations by definition).