Nils Aall Barricelli was, to my knowledge, the first person to actually run artificial evolution experiments on computers [Barricelli 57], [Barricelli 62], [Barricelli 63]. He conducted a series of experiments, starting in 1953, to investigate the evolution of life (and not, as many others after him, purely to investigate the use of evolution as an optimisation technique). Barricelli explicitly discussed in his work what it would take in addition to reproduction and random variation in order for us to consider his evolved organisms `alive'. In fact, he decided that the term `life' was too poorly defined to be of use in the context, as mentioned in Section 2.1.3. Barricelli introduced the concept of symbiogenesis3.21 in his work as an additional requirement for his organisms (which he then called `symbioorganisms'), and, instead of asking whether these symbioorganisms were alive, asked the reciprocal question of ``whether the objects we are used to call[ing] living beings are a particular class of symbioorganisms'' [Barricelli 63] (p.7).
The basic model used by Barricelli can be considered as a one-dimensional cellular automaton, where each state persists from one time step to the next depending upon the state of other cells in certain neighbouring positions. In this way, cooperative configurations of states can arise. Among the phenomena that Barricelli observed in this system are: self-reproduction of certain collections of states (i.e. symbioorganisms); crossing of material between two symbioorganisms; spontaneous formation of symbioorganisms; parasitism; self-maintaining symbioorganisms; and, evolution [Barricelli 62]. Barricelli's method and results are similar in a number of ways to those of many of the more recent studies described in the previous section, such as Rasmussen's and Ray's. The fact that these experiments were run using the computing equipment available in the 1950s makes them all the more impressive. It is highly regrettable that Barricelli's work has been largely forgotten or ignored by today's artificial life community,3.22 although there are a few signs that it is at last beginning to achieve some recognition (e.g. [Dyson 97], [Fogel 98]). Although many might argue over the central role that Barricelli gave to the process of symbiogenesis in his work, his experiments are strengthened by the fact that he at least proposed an explicit list of the assumptions behind the model, and also by the simplicity of the model he developed. In these respects, his work is of more scientific value than much of the more recent work on these subjects.
In addition, Barricelli conducted some experiments in which the individual symbioorganisms were also decoded into a strategy for playing a simple game (i.e. they had a phenotype) [Barricelli 63]. When two symbioorganisms were competing to reproduce into the same space, they played the game according to their individual strategies, and the winner was allowed to reproduce. This is similar in some ways to the dual selection pressures in Avida and Koza's work reported above, but has the advantage (from the point of view of open-ended evolution) that the additional selection pressure is determined by other organisms within the system, rather than being externally defined. Barricelli met with mixed results in these experiments ([Barricelli 63], [Barricelli 72]), partly because symbioorganisms which had developed good strategies for playing the game often became infected by parasites. I suspect that Barricelli's system was more open to these types of phenomena than are systems such as Avida, because the individual cells within a symbioorganism reproduce by themselves rather than en masse. As such, they behave more as individually `selfish genes' [Dawkins 76], and the symbioorganisms as a whole should therefore not necessarily be expected to be good at finding `optimal' solutions to given problems.
There has been some more recent work within the artificial life community on the subject of symbiogenesis. Some of the issues involved in incorporating symbiogenesis (and symbioses in general) in artificial life models are discussed in [Daida et al. 96], and studies of the general conditions under which symbioses may occur are reported in [Bull & Fogarty 95]. Some practical implementations, incorporating the ideas of symbiogenesis, have been successful at solving particular problems (for example, [Ikegami & Kaneko 90], [Numaoka 95]), but as organisms in these systems have a limited behavioural repertoire and are solving a specific, externally defined task, their capacity for truly open-ended evolution is restricted.
Gordon Pask also describes some early work with artificial life models [Pask 69], although the evolutionary potential of his automata is limited by the rather small set of actions which they may perform. A rather more interesting system was developed by Michael Conrad and Howard Pattee [Conrad & Pattee 70]. In this model, individual organisms, with a genotype representation and a phenotype obtained by interpreting the genotype as instructions (cf. Barricelli's game-playing symbioorganisms), compete in a one-dimensional world for the possession of `chips' which they use for self-repair and reproduction. It is closely related in many ways to Ray's later Tierra model, but with a smaller number of instructions representing a limited set of possible interactions between organisms, rather than a computationally complete instruction set as in Tierra (although even in Tierra there is still only a limited number of types of interaction between organisms). Also, it has a notion of conservation of matter, lacking in Tierra, to model ecosystem interactions. Having said this, there is only one type of matter in the model (a `chip'), and it has a fairly arbitrary connection to the structure of an organism. For example, an organism's genome is represented as a string of `states' rather than a string of matter--an organism's store of chips is only used to determine when it can repair itself and when it can reproduce. The major consequence of disassociating the structure of the organism from the `matter' in the world is that the structure must therefore be predefined and is not able to evolve, whereas, had it been embedded in the material world, new organism structures could emerge from new organisations of the matter. This problem of predefining a non-material structure for organisms is shared by Tierra and other models described in this and the previous section, and will be discussed further in Chapter 7. The organisms in Conrad and Pattee's model had the potential to engage in symbiotic relationships with other organisms (by sharing chips), and also to reproduce sexually. The results showed that symbiosis was often selected for, but sexuality generally was not. However, in summarising the results, the authors conclude that:
``It is evident that the richness of possible interactions among organisms and the realism of the environment must be increased if the model is to be improved ... One point is clear, that the processes of variation and natural selection alone, even when embedded in the context of an ecosystem, are not necessarily sufficient to produce an evolution process ... Experience with the present model re-enforces our feelings that the most profound and significant processes of evolution--the innovations, the origins of new hierarchical levels of organization--are still outside the scope of this type of program and remain to be discovered.'' [Conrad & Pattee 70] (pp.407-409).
Many people claim that these processes remain outside the scope of artificial life models even today (e.g. [Stewart 97], [Bedau 98a]).3.23
In the mid-1970s, John Holland proposed a collection of models he collectively referred to as the `α-Universes' as a suitable environment in which to study the spontaneous emergence of self-reproducing systems [Holland 76]. The design is similar in many ways to Conrad and Pattee's model, but was influenced by an analogy with the spontaneous emergence of life in a `primordial soup' of biochemical molecules. A feature shared by both models (and by some of Barricelli's work) is that individual components are acted upon by certain predefined operators (the `physics' of the world), but (adjacent collections of) components can also be interpreted as encodings of further operators (phenotypes, or `emergent operators' in Holland's terminology), giving the models a more open-ended quality. Also, as in Rasmussen and colleagues' work discussed in the previous section, the configurations which are reproduced in the α-Universes are not individual structures, but collections of structures. In Barry McMullin's detailed analysis of the α-Universes [McMullin 92a], he suggests that these collective structures might alternatively be regarded as autopoietic (roughly, self-producing and self-maintaining) organisations. However, McMullin observes that ``the `higher-level', properly autonomous entities, are not, in general, self-reproducing in any sense, and are certainly not genetically self-reproducing in the von Neumann sense of permitting an open-ended growth in complexity'' [McMullin 92a] (p.269, original emphasis).
Holland's original work was based upon a mathematical analysis of phenomena that he expected to emerge in the system. Fifteen years later, the α-Universes were implemented as a computer program by McMullin ([McMullin 92a], [McMullin 92b]). He found a number of problems with the design that were not anticipated by Holland and which meant that it did not produce the `life-like' behaviour that he postulated. As many of the problems were ultimately due to components in the world being unable to control their local environment and maintain their own structure, McMullin has subsequently gone on to investigate software implementations of autopoiesis [McMullin & Varela 97].3.24
After the α-Universes, Holland developed the `Echo' model of complex adaptive systems ([Holland 95], [Hraber et al. 97]). Echo places more emphasis on ecological interactions and exchange of resources than do most of the other models reviewed. In particular, in Echo Holland takes the view that it is the `market' that emerges from exchanges of resources between individual agents that is the source of much of the interesting behaviour of a complex system. Individual agents are modelled at a fairly high level, with a predefined structure. In the basic model, agents can participate in a limited set of interactions with other agents (e.g. to exchange resources), and reproduce automatically when they have collected sufficient raw materials [Holland 95]. Interactions are governed by each agent's collection of `tags'--short strings of symbols which are encoded on the agent's genome (or `chromosome' in the Echo terminology). Each tag is used for a specific set of interactions, where the outcome of the interaction is partially determined by comparing corresponding tags in the interacting agents in some predefined way. Various extensions to this basic model are also described, to add features such as multicellularity, metabolism and selective mating (ibid.). The design is based upon a core set of principles which Holland believes are common to all complex adaptive systems. One feature that distinguishes Echo from other models reviewed in this chapter is that it has been successfully used for several ecological studies (e.g. [Schmitz & Booth 96], [Hraber & Milne 97]).
I have now discussed what I consider to be the most important practical examples of artificial life models aimed at self-reproduction and open-ended evolution. To end this section, I will briefly mention a number of other studies which have also made relevant contributions.
In my discussion of Avida and Koza's system in the previous section, I made the distinction between selection pressure that originates from other programs (organisms) within the environment, and that which originates from externally defined functions. This distinction was emphasised by Norman Packard, who used the terms intrinsic and extrinsic adaptation respectively [Packard 88]. He argues (as have many others mentioned in this section and the last) that models with intrinsic adaptation are more appropriate for modelling biological evolution. Packard described a model which he used to study evolutionary dynamics, which is distinguished by its simplicity. He says ``I make every attempt to strip down most of the complexity of real biological systems, with the aim of discovering a minimal model that displays evolutionary behavior'' (ibid. p.142). However, as his organisms only have two genes, the relevance of the model in the current context of studying open-ended evolution is limited.
Larry Yaeger has described a system called PolyWorld [Yaeger 94], which is in many ways the antithesis of Packard's minimal approach. PolyWorld models many features of biological life, such as a simple `metabolism', a nervous system and vision. Yaeger describes it as an attempt to evolve Artificial Intelligence through the evolution of nervous systems in an ecology. In PolyWorld, organisms controlled by (genetically determined) neural networks move around a two-dimensional environment, collecting energy, fighting and mating. Yaeger's model is one of the very few artificial worlds in which distinct species of organisms have evolved and coexisted.3.25 Unfortunately, the results of PolyWorld have not been analysed in sufficient detail to enable many useful scientific conclusions to be drawn from it, and the complexity of the model does not help in this respect.
Early attempts at allowing variable length genomes in an artificial life simulation are described by Robert Collins in his PhD thesis [Collins 92], which extends previous work by David Jefferson, Charles Taylor and colleagues (e.g. [Taylor et al. 88], [Jefferson et al. 91]). In this work, an organism's genome encodes a neural network which controls its behaviour. By allowing variable length genomes, larger networks are able to evolve, which are capable of producing more complex behaviour. Along the same lines, Inman Harvey has worked on extending the theory and the design of the standard genetic algorithm to allow open-ended evolution by permitting the length of genomes to increase over time [Harvey 93]. The approach is called SAGA, and, like Collins et al.'s work, is concerned with extrinsic adaptation (i.e. situations where an external fitness function is applied). This method has proved useful for a number of practical purposes, mostly concerned with evolutionary robotics, but it is not clear how relevant it is for many of the systems I have described in the last two sections. I suspect that some of the assumptions upon which Harvey based his analysis of the need to extend the `schema theorem' of genetic algorithms for open-ended evolution (ibid. Chapter 6) might not be valid for these models. In particular, it is not clear how the notion of fitness used in the analysis can be related to models with intrinsic adaptation. Furthermore, Harvey's analysis assumed a system with low epistasis, and it is questionable whether models such as Tierra meet this requirement.
Finally, it is worth noting that some of the most spectacular examples of artificial evolution that have been produced to date model co-evolutionary processes of one form or another (e.g. [Hillis 90], [Sims 94a], [Sims 94b], [Miller & Cliff 94], [Cliff & Miller 96], [Floreano et al. 98], [Nolfi & Floreano 98]). In these studies, the success of organisms in one population depends upon the success of organisms in another, coevolving population. However, these studies have all been geared towards producing organisms which are good at performing a particular task. To this end, the coevolving organisms are still generally competing in some pre-specified (extrinsically defined) game, and they are not given the potential for truly open-ended evolution in which they could develop entirely new games to play.