SSIE 580B: Evolutionary Systems and Artificial Life

(Last Updated June 26, 1997)

Luis Mateus Rocha
Computer Research Group, MS P990
Los Alamos National Laboratory
Los Alamos, NM 87545

Lecture Notes
Copyright: Luis M. Rocha 1995

NOTE:These notes are also available in postscript (.ps) compressed version (.zip) and Adobe Acrobat (.pdf). Notice that in some systems you may have to press the "shift" key while clicking on this link.

On the nature of these lecture notes

This course has been re-designed as a new course now offered at Indiana University: biologically-inspired computing. The lecture notes of the new course have updated substantially the notes from the old course below; therefore, I encourage readers to looks at the new lecture notes. The old SSIE-580B course was based on several books for which you will see references below, but mainly, the first Artificial Life volume, as well as Emmeche's book "The Garden in The Machine". All the papers and books referred to in the notes are also made available to students. The goal of these notes is to supplement all these materials, namely, to identify deeper conceptual and philosophical problems facing ALife which have parallels in Systems Science, Cybernetics, Evolutionary Systems, and AI. These ideas were developed in greater detail in other publications, some of which you can also catch on-line. If you have any suggestions please drop me a line!

Syllabus - Table of Contents

1. What is Life? (Updated June 5, 1997)

2. The logical Mechanisms of Life (Updated June 5, 1997)

2.1. Life-As-It-Could-Be: but, what is non-life-as-it-could-be?

2.2. Simulations, Realizations, Systemhood, Thinghood, and Theories of Life

3. Self-Organization and Emergent Complex Behavior (Updated June 5, 1997)

3.1. Edge of Chaos

3.2. G-Type/P-Type Distinction and Emergent Behavior

4. Self - Organization and Cellular Automata (Updated June 5, 1997)

5. Von Neumann and Natural Selection (Updated June 11, 1997)

5.1 Von Neumann's Self-Reproduction Scheme

5.2 Open-ended emergent evolution and natural selection

6. Evolutionary Computation (Updated June 23, 1997)

6.1. Evolutionary Strategies and Self-Organization

6.2. development and morphogenesis: self-organization and selection come together

7. Artificial Life: Self-Organizing and Evolutionary Systems (Updated June 26, 1997)


Evaluation

Artificial Life computational project or specific topic paper to be discussed with instructor (70%) . Two small assignments (15% each): 1) Random Boolean Network; 2) Genetic algorithm.

1. What is Life?

See new version from the new lecture notes.

Naturally in order to understand Artificial Life we need to discuss the concept of Life. Several definitions can be retrieved from a dictionary:

"life adj._ n.1. the general condition that distinguishes organisms from inorganic objects and dead organisms, being manifested by growth through metabolism, a means of reproduction, and internal regulation in response to the environment. 2. the animate existence or period of animate existence of an individual. 3. a corresponding state, existence, or principle of existence conceived of as belonging to the soul. 4. the general or universal condition of human existence. 5. any specified period of animate existence. 6. the period of existence, activity, or effectiveness of something inanimate, as a machine, lease, or play. 7. animation; liveliness; spirit: The party was full of life. 8. the force that makes or keeps something alive; the vivifying or quickening principle." [Random House Webster's Dictionary, Electronic Edition]

The definitions above fall into three main categories: (1) life as an organization distinct from inorganic matter (with an associated list of properties), (2) life as a certain kind of animated behavior, and (3) life as a special, incommensurable, quality _ vitalism. Throughout this course we will see that all principles, and indeed all controversies, associated with the study of life fall into one of these categories or the differences between them. It is important to realize that for the most part of the history of humanity, this question was never an issue. Before the study of physics became important, everything was alive: the stars, the skies, the rivers and mountains, etc. There was no non-life, so the concept was of no importance. It is only when the deterministic mechanics of moving bodies become dominant that the question arises. If all matter follows simple physical laws, and we need no vitalistic explanations of the world's behavior, then what is indeed the difference between life and non-life, between biology and physics?

The (Cartesian) third category above has been discarded as a viable scientific explanation, because for science nothing is in principle incommensurable. The traditional scientific approach has lead the study of living systems into a reductionist search for answers in the nitty-gritty of the biochemistry of living organisms. This alternative sees life as nothing more than complicated physics. However, the question remains unanswered since there are many ways to obtain some complicated dynamics, but of all of these, which ones can be classified as alive? What kind of complexity are we looking for? No one disputes that life is some sort of complex material arrangement, but when do we reach a necessary threshold of complexity after which matter is said to be living? Is it a discrete step, or is life a fuzzy concept? To study it must we synthesize organizations with the same threshold of complexity (first category above), or is it enough to simulate its animated behavior (second category above)?

Traditionally life has been identified with material organizations which observe certain lists of properties, e.g. metabolism, adaptability, self-maintenance (autonomy), self-repair, growth, replicability, irritability (reactability), evolution, etc. Most living organisms follow these lists, however, there are other material systems which obey only a subset of these rules, e.g. viruses, candle flames, the Earth, certain robots, etc. This often leads to the view that life is at best a fuzzy concept and at worst something we are, subjectively, trained to recognize _ life is what we can eat _ and is thus not an objective distinction.

Objectively or subjectively, we do recognize some material organizations as being alive. It is perhaps in this ability to recognize and categorize events in our environments that an important difference between living and non-living systems lies. Life requires the ability to both categorize and control events in its environment in order to survive. This is a common characteristic of all recognized life, together with the ability to store and transmit records of categorizations and controls. It is also the locus of the gap between physics and biology. The laws of physics are, by definition, independent of particular organisms, they are universal, inexorable _ therefore immune to any control by an organism_ and exist beyond observation. In contrast, biological systems achieve a degree of material control which allows them to categorize and control relevant aspects of their material surroundings. It is this "relevant" which gives these categorizations and controls an extra attribute to mere physical action-reaction interactions. In other words, when an organization is able torecognize and act on aspects of its environment which are important to its own survival, we say that the mechanisms by which the organization recognizes and acts are functional in reference to the organization itself (self-reference). Physics is not concerned with function. For instance, a reductionist, physical, description of DNA is certainly possible, but will tell us nothing as to the function of some DNA molecule as a gene relevant to a particular organization. Only in reference to this larger organization does a piece of DNA function as a gene for some previously categorized control (e.g. an enzyme with some effect in an environment).

This issue could be rephrased in terms of the notion of emergence. Whatever organization exists after the complexity threshold for life, discrete or fuzzy, is passed, we may say that it is emergent to the physical level because its attributes cannot be completely explained by the previous level. In particular, function, control, and categorization cannot be explained by physics alone. Notice, however, that emergence does not imply vitalism or dualism. When we say that certain characteristics cannot be explained by physics alone, since they are emergent properties of some physical arrangement, we mean that they must be explained by different (Pattee's complementary) models for each level, as well as, and this is very important, a model for the connection between both levels. In other words, though function, control, and categorization cannot be explained by physics alone, they must nonetheless follow physical laws. In particular, the origin of life, is a problem of emergence of categorization and control from a physical milieu.l.

The definition of emergence as an epistemological, explanatory requirement, is related to the notion of emergence-relative-to-a-model [Rosen, 1985; Cariani, 1989] or intensional emergence [Salthe 1991]. It refers to the impossibility of epistemological reduction of the properties of a system to its components [Clark, 1996]. It acknowledges that different properties of systems may require different, qualitatively unrelated, epistemological categories and models [Pattee, 1978; Rocha, 1997]. As an example, we can think of phase transitions such as that of water in its transition from liquid to gas. Water and its properties cannot be rephrased it terms of the properties of hydrogen and oxygen, it needs a qualitatively different model.

Artificial life concerns both the simulation and realization of life in some artificial environment, usually the computer. At least regarding the second of its goals, artificial life cannot escape the main issues raised above for biological life. In this course we will discuss what kind of artificial environments are required for simulations and realizations of life. The concepts in italics above will be discussed in more detail in the context of computational environments.

Further Readings and References:

        Cariani, Peter[1989].On the Design of Devices with Emergent Semantic Functions. PhD. Dissertation. SUNY Binghamton.

        Clark, Andy [1996] "Happy couplings: emergence and explanatory interlock" In: The Philosophy of Artificial Life. M. Boden (ed.). Oxford University Press, pp. 262-281.

        Pattee, Howard H. [1978]."The complementarity principle in biological and social structures." In: Journal of Social and Biological Structures Vol. 1, pp. 191-200.

        Rocha, Luis M. (Ed.) [1995]. special issue in Self-Reference in Biological and Cognitive Systems. Communication and Cognition - AI Vol. 12, nos. 1-2 .

        Rocha, Luis M. [1997]. Evidence Sets and Contextual Genetic Algorithms: Exploring Uncertainty, Context, and Embodiment in Cognitive and Biological Systems. PhD. Dissertation. SUNY Binghamton.

        Rosen, Robert [1985], Anticipatory Systems. Pergamon Press.

        Salthe, Stanley N. [1991], "Varieties of Emergence". World Futures Vol. 32, pp.69-83

        Schròdinger, Erwin [1944]. What is Life?. Cambridge University Press.

For next lecture read:

Langton, C. [1989], "Artificial Life" In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 1-47.

        Pattee, H. [1989], "Simulations, Realizations, and Theories of Life". In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 63-77.


2. The logical Mechanisms of Life

See new version from the new lecture notes.

2.1. Life-As-It-Could-Be: but, what is non-life- as-it-could-be?

"Artificial Life [AL] is the study of man-made systems that exhibit behaviors characteristic of natural living systems. It complements the traditional biological sciences concerned with the analysis of living organisms by attempting to synthesize life-like behaviors within computers and other artificial media. By extending the empirical foundation upon which biology is based beyond the carbon-chain life that has evolved on Earth, Artificial Life can contribute to theoretical biology by locating life-as-we-know-it within the larger picture of life-as-it-could-be." [Langton, 1989, page 1]

"[AL] views life as a property of the organization of matter, rather than a property of the matter which is so organized. Whereas biology has largely concerned itself with the material basis of life, Artificial Life is concerned with the formal basis of life. [... It] starts at the bottom, viewing an organism as a large population of simple machines, and works upwards synthetically from there _ constructing large aggregates of simple, rule-governed objects which interact with one another nonlinearly in the support of life-like, global dynamics. The 'key' concept in AL is emergent behavior." [Langton, 1989, page 2]

"Artificial Life is concerned with tuning the behaviors of such low-level machines that the behavior that emerges at the global level is essentially the same as some behavior exhibited by a natural living system. [...] Artificial Life is concerned with generating lifelike behavior." [Langton, 1989, pp 4 and 5]

The previous quotes indicate the goals of Artificial Life according to Chris Langton: the search for complex, artificial, systems which observe some kind of life-like, animated, emergent behavior. There seems to be both a desire to obtain an artificial living organization, as well as obtaining some lifelike behavior. The first goal is more ambitious and related to the first definition of life introduced in lecture one, while the second goal is related to the second definition.

The methodology to reach either of these goals is also in line with the notion of emergence mentioned in lecture one: from the non-linear interaction of simple, mechanistic, components, we wish to observe the emergence of complicated, life-like, unpredictable, behavior. Natural living organisms are likewise composed of non-living components. As pointed out in lecture one, the problem of biology is precisely the emergence of life from non-living components. The material components follow, and are completely described, by physical laws, however, a physical explanation of the overall living system is incomplete. Similarly, in Artificial Life, we have formal components obeying a particular set of axioms, and from their interaction, some global behavior emerges which is not completely explained by the local formal rules. Clearly, the formal rules play the role of an artificial physics and the global behavior, if recognized as life-like, plays the role of an artificial biology in this bottom-up approach to complex behavior.

"Of course, the principle assumption made in Artificial Life is that the 'logical form' of an organism can be separated from its material basis of construction, and that 'aliveness' will be found to be a property of the former, not of the latter." [Langton, 1989, page 11]

The idea is that if we are able to find the basic principles of living organization, then the material substract used to realize life is irrelevant. By investigating these basic principles we start studying not only biological, carbon-based, life _ life-as-we-know-it _ but really the universal rules of life, or life- as-it-could-be. Several problems have been raised regarding this search for a universality without matter [Cariani, 1992; Moreno et all, 1994], which will not be discussed here. What needs to be made more explicit is the relationship between the two distinct goals of AL.

Looking at emergent behavior in formal complex systems in search of interesting behavior indicates acertain circularity. If AL is concerned with finding life-like behavior in artificial, universal, systems, we are ultimately binding life-as-could-be to the behavior of life-as-we-know-it by virtue of some subjective resemblance. This can hardly be accepted as the search for universal principles.

"They say, 'Look, isn't this reminiscent of a biological or a physical phenomenon!' They jump in right away as if it's a decent model for the phenomenon, and usually of course it's just got some accidental features that make it look like something." [Jack Cowan as quoted in Scientific American, June 1995 issue, "From Complexity to Perplexity", by J. Horgan, page 104]

"Artificial Life _ and the entire field of complexity_seems to be based on a seductive syllogism: There are simple sets of mathematical rules that when followed by a computer give rise to extremely complicated patterns. The world also contains many extremely complicated patterns. Conclusion: Simple rules underlie many extremely complicated phenomena in the world. With the help of powerful computers, scientists can root those rules out." [J. Horgan, Scientific American, June 1995 issue, "From Complexity to Perplexity", page 107]

"Artificial Life is basically a fact-free science". [John Maynard Smith as quoted in Scientific American, June 1995 issue, "From Complexity to Perplexity", by J. Horgan, page 107]

The problem is that Artificial Life must be compared to something, otherwise it becomes a factless manipulation of neat computer games with subjective resemblances to vague ideas of the behavior of real life. Again, we are faced with many possible emergent types of complex behaviors, this time formal, but what kinds of these behaviors can be classified as "life-as-could-be"?, what is the formal threshold of complexity needed? In the natural world we are, more or less, able to distinguish life from non-life, biology from physics, in the logical realm, we likewise need a formal criteria to distinguish logical life from logical non-life, artificial life from artificial physics. Only by establishing an artificial physics, from which an artificial biology can emerge, and a theory, or set of rules, distinguishing the two, can we aim at a proper science based on fact, real or artificial.

"Artificial Life must be compared with a real or an artificial nonliving world. Life in an artificial world requires exploring what we mean by an alternative physical or mathematical reality." [Pattee, 1995]

The two goals of AL are usually described as hard and soft AL respectively. The first concerns the synthesization of artificial life from computational or material (situated robotics) components. The second is interested in obtaining life-like behavior and is essentially metaphorical. To be accepted as a scientific field, AL, more than imitating subjective behavior, should be concerned with the investigation of the rules that allow us to distinguish life from non-life and which can be experimentally replicated within a scientific discourse. Whether we are interested in hard or soft AL, our artifacts and models should always make explicit the set of rules which allow us to defend that some artificial organization is alive or observes some specific life-like behavior. Naturally, the requirements for hard AL are much stricter, as we are not merely interested in behavioral thresholds that can be compared to real biological systems with looser or stricter rules, but the actual realization of an artificial organization that must be agreed to be living in all of its aspects. Soft AL, may restrict itself to particular behavioral traits which need only to be simulated to a satisfactory degree. We will be looking into several alternatives for organizational requirements of life during the remaining of this course.

2.2. Simulations, Realizations, Systemhood, Thinghood, and Theories of Life

"Boids are not birds; they are not even remotely like birds; they have no cohesive physical structure, but rather exist as information structures _ processes _ within a computer. But _ and this is the critical 'but'_ at the level of behaviors, flocking Boids and flocking birds are two instances of the same phenomenon: flocking." [Langton, 1989, page 32]

"The 'artificial' in Artificial Life refers to the component parts, not the emergent processes. If the component parts are implemented correctly, the processes they support are genuine _ every bit as genuine as the natural processes they imitate. [...] Artificial Life will therefore be genuine life _it will simply be made of different stuff than the life that has evolved on Earth." [Langton, 1989, page 33]

"Simulations and realizations belong to different categories of modeling. Simulations are metaphorical models that symbolically 'stand for' something else. Realizations are literal, material models that implement functions. Therefore, accuracy in a simulation need have no relation to quality of function in a realization. Secondly, the criteria for good simulations and realizations of a system depend on our theory of the system. The criteria for good theories depend on more than mimicry, e.g., Turing Tests." [Pattee, 1989, page 63]

The bottom line is that a simulation, no matter how good it is, will never become a realization. Nonetheless, it may still be possible to obtain artificially living organisms (realizations) if, from a simulated environment, we are able to create genuine emergent evolution. Howard Pattee [1989] has proposed that if emergent artificial organisms are able to perform measurements, or in other words, categorize and control aspects of their (artificial) environment then they may be considered realizations. Some claim that computational environments do not allow for this creative form of emergence [see Cariani, 1992; Moreno, et all, 1994]. In any case, whatever artificial environment we may use, computational or material, we need a theory allowing us to distinguish life from non-life.

Related to this issue, and in the context of systems science, is the search of those properties of the world which can be abstracted from their specific material substrate: systemhood from thinghood. Systems science is concerned with the study of systemhood properties, but there may be systems from which systemhood cannot be completely abstracted from thinghood. Life, and complexity in general, is sometimes proposed as one of those systems [see Rosen, 1986, 1991; Moreno et al, 1994; Pattee, 1995]. The difficulty for systems science, or complexity theory, lies precisely in the choice of the appropriate level of abstraction. If we abstract enough, most things will look alike, leading to a theory of factless, reminiscent analogies, exposed by Cowan and Maynard-Smith above. If we, on the other hand, abstract too little, all fields of inquiry tend to fall into more and more specific niches with little communication amongst them. In the context of life, we do not want to be tied uniquely to carbon-based life, or life-as- we-know-it, but we also do not want life-as-could-be to be anything at all. The challenge lies precisely on finding the right amounts of systemhood and thinghood, as well as the interactions between the two, necessary for a good theory of life, real or artificial.

In philosophy of biology, this problem is posed between structuralism and functionalism. Structuralism often leads into a reductionist explanation of meaningless, to a higher level, physical interactions, while functionalism may disregard important characteristics of matter. A given function may be implemented in many ways, however, not all of these structures will have the same evolutionary potential, which may even be independent of how well the function is implemented. Life is ultimately linked to some physics from which it emerges: this physics may be artificial, but the living organisms which may inhabitate it will survive depending on how well they are able to harness their environment and not only on the abstract function they may implement. Thus to study a particular life form, we cannot disregard neither its particular physical environment nor its function. To systematically study life should concern not solely matter or form alone, but precisely the interactions between the two.

In the next lectures we will study several formal mechanisms which observe certain characteristics associated with life. With all of them we must ask the following question: "granted, life follows these characteristics, but are there other characteristic not captured in this model? Are those important? Must a theory of life include them, or are we restricting life too much?" Somewhere between "any animationgoes" and "carbon-chauvinism" we must find a satisfying criteria for recognizing life from non-life. Like with anything else, the chosen theory, or theories, will be the one capable of satisfying some group's consensus, after which facts can be built upon. It should be noted that scientific consensus is not merely built upon conversational interactions, but also on the replicability of experiments available to all observers, which allows the establishment of a larger and larger consensual understanding of the world. It also binds scientific discourse to the laws of a particular world (natural or artificial), as opposed to pure linguistic interaction between participants in a given discourse.

Further Readings and References

        Cariani, P. [1992], "Emergence and Artificial Life" In Artificial Life II. C. Langton (Ed.). Addison-Wesley. pp. 775- 797.

Langton, C. [1989], "Artificial Life" In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 1-47.

Klir, G. [1991], Facets of Systems Science. Plenum Press. (On Constructivism pp. 12-13)

Maturana, H. And F. Varela [1987], The Tree of Knowledge. Shambhala Publications.

        Moreno, A., A. Etxeberria, and J. Umerez [1994], "Universality Without Matter?". In Artificial Life IV, R. Brooks and P. Maes (Eds). MIT Press. pp 406-410

        Pattee, H. [1989], "Simulations, Realizations, and Theories of Life". In Artificial Life. C. Langton (Ed.). Addison- Wesley. pp. 63-77.

        Pattee, H. [1995], "Artificial Life needs a real Epistemology". In Advances in Artificial Life. F. Moran, A Moreno, J.J. Merelo, P. Chacon (Eds.). Springer-Verlag. (In press)

        Rosen, R. [1986], "Some Comments on Systems and System Theory". In Int. Journal of General Systems. Vol. 13, No.1.

        Rosen, Robert [1991]. Life Itself: A Comprehensive Inquiry into the Nature, Origin, and Fabrication of Life. Columbia University Press.

        Sober, E. [1992], "Learning from Functionalism _ Prospects for Strong Artificial Life". In Artificial Life II. C. Langton (Ed.). Addison-Wesley. pp. 749-765.

        Zeleny, M., G. Klir, and K. Hufford [1989], "Precipitation Membranes, Osmotic Growths and Sythetic Biology". In Artificial Life. C. Langton (Ed.). Addison-Wesley. pp. 125-139.

For next lecture read:

        Chapters I and II of Emmeche's [1991], The Garden in the Machine: The Emerging Science of Artificial Life. Princeton University Press.

Continue Reading (next point 3)