"How does evolution produce increasingly fit organisms in environments which are highly
uncertain for individual organisms?"
"How does an organism use its experience to modify its behavior in beneficial ways (i.e. how
does
it learn or 'adapt under sensory guidance')?"
"How can computers be programmed so that problem-solving capabilities are built up by
specifying
'what is to be done' rather than 'how to do it'?" [Holland, 1975, page 1]
These were some of the questions concerning John Holland when he thought of Genetic
Algorithms
(GA's) in the 1960's. Basically, all these problems were shown to be reduced to a problem of
optimizing a
multiparameter function necessary for solving a particular problem. Nature's "problem" is to
create
organisms that reproduce more (are more fit) in a particular environment: the environment
dictates the
selective pressures, and the solutions to these pressures are organisms themselves. In the
language of
optimization, the solutions to a particular problem (say, an engineering problem), will be selected
according to how well they solve that problem. GA's are inspired by natural selection as the
solutions to
our problem are not algebraically calculated, but rather found by a population of solution
alternatives
which is altered in each time step of the algorithm in order to increase the probability of having
better
solutions in the population. In other words, GA's (or other Evolutionary Strategies (ES) such as
Evolutionary Programming (EP)), explore the multi-parameter space of solution alternatives for a
particular
problem, by means of a population of encoded strings (standing for alternatives) which undergo
variation
(crossover and mutation) and are reproduced in a way as to lead the population to ever more
promising regions
of this search space (selection)
The underlying idea of computational ES is the separation of solutions for a particular problem
(e.g. a
machine) from descriptions of those solutions (memory). GA's work on these
descriptions and not on the solutions
themselves, that is, variation is applied to descriptions, while the respective solutions are
evaluated, and
the whole (description-solution) selected according to this evaluation. Such machine/description
separation follows aspects of von Neumann's
self-reproducing scheme which is able to increase the
complexity of the machines described. However, the form of organization attained by GA's is
not self-
organizing in the sense of a boolean network of cellular automata. Even though the solutions are
obtained
from the interaction of a population of elements, and in this sense following the general rules
usually
observed by computationally emergent systems (e.g. Langton [1988], Mitchell [1992]), they do
not self-
organize since they rely on the selective pressures of some fitness function. The order so attained
is not a
result of the internal dynamics of a collection of interacting elements (like a random net), but is
instead
dictated by the external selection criteria. In this sense, ES follow a memory-based
selective organization
scheme.
Self-organization is instead equated with those behaviors of organizations that are
unavoidable and solely dependent on their internal dynamics. This is usually thought of in terms
of the
attractor behavior of state-determined dynamic systems. ES rely on different concepts: first, with
the
description-solution dichotomy the concept of memory is introduced (state-determined,
self-organizing,
systems are memoryless); second, the transition rules of ES are not state-determined _ variation
is
stochastic; third, as already discussed, selection is external to the populations of descriptions.
This way,
we can hardly say that a population of memories is interacting with any sort of
"self-dynamics": the
solutions reached by a GA do not self-organize but are a result of stochastic (population)
variation and
external selection.
Systems which are able to develop the mechanisms to harness this variation based on an
internally
defined description-solution dichotomy may follow the kind of selective based self-organizing
principle
described as semantic
closure
in section 5. However, (computational) GA's are
not closed in this sense, the coding relation
is externally imposed and not evolved within the system itself. For all the reasons above it is
therefore
natural to think of ES as completely distinct from self-organization. It is perhaps useful to think
that ES
are modeling a very different aspect of biological systems that is related to natural selection. Self-
organizing systems model the abstract, internal, characteristics of matter, while ES model the
existence
of, external, selective pressures on populations of varying memory based descriptions of some
system.
Many of the new developments of GA's have to do with the inclusion of a developmental stage
between
genotype and phenotype, in other words, the creation of some artificial morphogenesis. Basically,
the idea
has been to encode rules that will themselves self-organize to produce a phenotype, rather than
the direct
encoding of the phenotype itself. As discussed in class, these rules often use L-System grammars
which
dictate production system programs [Wilson, 1988] leading to some phenotype. The most
important
advantage of this intermediate stage, as explored by Kitano [1990], Gruau [1993], Belew [1992]
and
others, is the ability to code for much larger structures than a direct encoding allows. In practical
terms,
they have solved some of the scalability problems of encoding (e.g.) neural networks in GA's, by
reducing the
search space dramatically.
The L-system grammars are higher level descriptions of self-organizing developmental
processes.
However, these first approaches used solely context-free, state-determined, L-System grammars,
compromising epistasis (or mutual, non-linear, influence of genetic descriptions amongst each
other) in
the simulation of self-organizing development. Dellaert and Beer [1994] and Kitano [1994], for
instance,
used Kauffman's boolean networks to simulate genetic epistasis and self-organization. In other
words,
the GA will code for rules which will construct boolean networks whose nodes stand for aspects
of the
phenotypes we wish to evolve on some physical simulation. In Dellaert and Beer's model, the
nodes stand
for cell mitosis and other characteristics. This way, the solutions of the GA are self-organizing
systems whose attractor behavior dictates pre-defined phenotypic traits.
These approaches in effect offer an emergent morphology, that is, they code for rules which will
themselves self-organize into some phenotype (instead of strict programming of morphology).
The
indirect encoding further allows the search to occur in a reduced space, amplified through
development.
An interesting side effect has to do with the appearance of modularity traits on the evolved
phenotypes
[Wagner, 1995]. In Rocha [1995],
[1997] I have proposed a scheme where the
contextual elements of
development might be themselves evolved. Instead of boolean networks I utilize operations
between
fuzzy sets to simulate a material phenotype. This scheme represents a general purpose GA which
searches
the same search space for any size of phenotypic behaviors.
The most important aspect of these GA's with emergent morphologies is the utilization in the
same model
of an external selection engine (the GA) coupled to a particular self-organizing dynamics (e.g.
boolean
networks) standing for some materiality. Such schemes bring together, computationally, the two
most
important aspects of evolutionary systems: self-organization and selection. These models belong
to a
category of self-organization referred to as Selected Self-Organization which is based on
local memory
[Rocha, 1996,1998]. Selected
Self-Organization with distributed memory is also possible in
autocatalytic structures, though its evolutionary potential is much smaller than the local memory
kind.
The reason lies in Von Neumann's notion of non-trivial self-reproduction. The introduction of
symbolic
descriptions allows a much more sophisticated form of communication: structures are
constructed from
static descriptions and do not have to reproduce through some complicated process of
self-inspection. In other words,
descriptions can construct any kind of
structure, while self-inspection relies on only those
structures that happen to be able to make copies of
themselves. As an example, a non-genetic protein-
based life form, would have to rely only on those
proteins that could make direct copies of
themselves [These issues are treated in detail in Rocha
1996,
1997, 1998,].
Further Readings and References:
Belew, R.K. [1993]."Interposing an Ontogenic Model Between Genetic Algorithms and
Neural Networks." In:
Advances in neural information processing (NIPS5). J. Cowan (Ed.). Morgan
Kaufmann.
Dellaert, F. and R.D. Beer [1994]."Toward an evolvable model of development for
autonomous agent synthesis." In:
Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and
Simulation of
Living Systems. R. Brooks and P. Maes (Eds.). MIT Press.
Goldberg, D. E. [1989]. Genetic Algorithms in Search, Optimization, and Machine Learning.
Addison-Wesley.
Gruau, Frédéric [1993]."Genetic Sythesis of Modular Neural
Networks." In: Proceedings of the fifth international
conference on Genetic Alogorithms. S. Forrest. Morgan Kauffman, pp 318-325.
Holland, John H. [1975]. Adaptation in Natural and Artificial Systems. University of
Michigan Press.
Kitano, H. [1990]."Designing Networks using Genetic Algorithms with Graph Generation
System." In: Complex
Systems Vol. 4, pp 461-476.
Kitano, Hiroaki [1994]."Evolution of Metabolism for Morphogenesis." In:
Artificial Life IV: proceedings of the
fourth international workshop on the synthesis and simulation of living systems. R. Brooks
and P. Maes
(Eds.). MIT Press.
Mitchell, M. [1992]. "Genetic algorithms". In Lectures in Complex Systems. L. Nadel and D.
Stein (Eds.). SFI
Studies in the Science of Complexity Vol. V, Addison-Wesley. pp 3-87.
Rocha, Luis M. [1995]."Contextual Genetic Algorithms:
Evolving Developmental Rules." In: Advances in Artificial
Life. F. Moran, A. Moreno, J.J. Merelo, and P. Chacon (Eds.). Series: Lecture Notes
in Artificial
Intelligence, Springer-Verlag. pp. 368-382.
Rocha, Luis M. [1996]."
Eigenbehavior and symbols." In: Systems
Research Vol. 12, No. 3 (In Press).
Rocha, Luis M. [1997]. Evidence
Sets and Contextual Genetic Algorithms: Exploring Uncertainty, Context, and
Embodiment in Cognitive and Biological Systems. PhD. Dissertation. SUNY
Binghamton.
Rocha, Luis M. [1998]."Selected self-organization and the Semiotics of Evolutionary
Systems." In: Evolutionary Systems. S. Salthe and G. Van de Vijver (Eds.).
Kluwer Academic Publishers. (in
press).
Wagner, Gunter [1995] "Adaptation and the modular design of organisms". In: Advances in
Artificial Life. F. Moran,
A. Moreno, J.J. Merelo, and P. Chacon (Eds.). Series: Lecture Notes in Artificial
Intelligence, Springer-
Verlag. pp. 317-328.
Throughout this course emphasis was put on identifying the most important tools utilized in the
field of
Artificial Life. We started with self-organizing systems, exemplified with the logistics
equation, random
boolean networks, cellular automata (e.g. Conway’s game of Life), and all characterized in
terms
of dynamics systems theory. Later,
with the von Neumann self-reproduction scheme, I argued that state-determined (purely
dynamic) systems
are not able to offer open-ended evolution, that is, to increase their complexity with
genuine emergence of
new functionalities. Dynamic systems are restricted to the complexity of their attractor landscape.
For this purpose, systems inspired by von Neumann’s scheme, which demand the separation
between the
description of a machine from the machine itself, and therefore introduce the concept of
memory and
external selection, were introduced. Such systems offer a model of the mechanisms utilized by
natural
selection, and are accordingly known as evolutionary systems (or evolutionary strategies)
— e.g. genetic
algorithms and evolutionary programming. We can also refer to the mechanisms utilized to
model the kind
of evolution that natural selection offers as memory based selective strategies: selection
acting on
memory elements in order to change the dynamic structure they encode.
I further emphasized hybrid systems which try to model both the self-organizing and selective
mechanisms
of biological systems, and can therefore offer a more complete understanding of evolutionary
systems. I
referred to these systems as getting close to the category of local memory based selective
self-organization, or semantic closure. In practice I showed those approaches aiming at the
introduction of
non-deterministic, self-organizing, developmental steps between genotype and phenotype such as
the
evolution of boolean/neural networks encoded through L-System rules in a genetic algorithm.
Also discussed
were models capable of emergent computation by coupling genetic algorithms to cellular
automata in order to have
the latter solve non-trivial tasks.
The understanding of the relative importance the two basic categories of organization in artificial
systems
introduces a very powerful way to study the relative importance of self-organization and natural
selection in
biological systems themselves. In other words, by creating different forms of>
life-as-it-could-be <>with
different degrees of both these categories, we may shed some light on the credit assignment
problem of
biology: how much of evolution is a result of natural selection and how much is a result of the
self-organizing characteristics of its specific materiality.
I was able to introduce many of the usual applications of Artificial Life, from bugs and boids, to
evolutionary
robots and social evolution. Each of these applications can be a universe of investigation in itself,
so
emphasis was instead put on the basic categories of organization and their respective simulation
tools
referred above. In one way or another, all of these applications utilize in different degrees such
tools
described throughout the course. For instance, evolutionary robots may use a genetic algorithm to
evolve
a boolean network for its control system allowing it to solve some maze. To the extent that its
control
system was evolved and uses self-organizing mechanisms, we can say that such control system
was
subjected to a memory based selective type of self-organization. Naturally, the robot itself (its
moving
parts and sensors) were not evolved but engineered; the complete evolution of a robot through
self-organization and selection represents probably the most ambitious long-term goal of
Artificial Life,
showing us how far behind we still are from getting there.
Copyright Luis Rocha