|
|
|
Evolution of Complex Behavior
An Artificial Life Paper
|
|
The paper suggests that natural evolution also involves
the discovery and assimilation of hidden laws and correlations of the
environment into the genetic makeup of organisms. Based on a simulation
study of evolution in an artificial world with its own hidden laws, we
suggest that the genetic algorithms of nature explore manifestations of
hidden laws, like causal connections and correlations between events in
the physical world. A chain of such causal connections and correlations
(which we call a domino event chain) can be assimilated into the
genetic makeup of an organism over evolutionary time, which would show
up as its instinct. We also present an abstract and simplified model of
evolution based on creature logic and environment logic in an attempt
to explain how such discoveries might take place. This model is then
used to suggest how insect colonies and other interesting relationships
among species might evolve.
|
|
February 1997
Rekesh John, Senior Project Officer: Innovative
techniques in computer science.
Dept. of Computer Science and Engineering,
Indian Institute of Technology,
Madras, India.
Prof. C.R.Muthukrishnan,
Dept. of Computer Science and Engineering
Indian Institute of Technology
Madras, India.
|
|
Introduction
|
|
Complex and intricate patterns of interaction are all
too commonly observed in nature. A bee gets attracted to a flower,
lands and drinks nectar and flies off to the next one. It has started
an event sequence of pollination which leads to further events in the
lives of the plants and the bee as well. A newly born turtle on the
beach moves in the direction of a brighter light gradient and enters
into the ocean where further events await. It does not "know"
that the ocean exists and it is supposed to go there. It was
conveniently born at the sea shore, ready to go in when it emerged. A
parasitic worm that infects cows spends its larvae stage in the abdomen
of an ant. One of the larvae burrows its way into the brain of the ant,
changing its behavior so that during cold evenings the ant climbs up a
blade of grass and hangs on to it with its jaws. The cows that graze in
the evenings devour these ants and the larvae make their way into the
cow's abdomen where the rest of their life histories are played out.
That there exists an intricate web of interaction logic
in nature is undeniable. Almost any trivial event like throwing a stone
into a lake can have far reaching consequences which may not be easily
traceable. These consequences may vary from instance to instance of the
causative event. However, there will usually be a subset of such events
(consequences) that are "invariant" so to speak - meaning
that they occur "as a rule". Formation of ripples is an
obvious consequence when throwing a stone into a lake, and so also the
contribution of the ripples to the minute sand beaches at the edge of
the lake. These "invariant" events may be considered to be
manifestations of the "laws" of the environment.
Can organisms over evolutionary time genetically
"discover" and thus make use of hidden laws of its changing
environment, laws which are not apparent during its own lifetime? That
is, if creatures are exposed to varying environments during their
evolutionary history, won't the genetic drive result in their
"discovering" to advantage what is common among all the
variations they have experienced? Won't they use these discovered laws,
principles, correlations or whatever we may call them, constructively?
For example, the sky has been relatively the same for millions of years.
Don't this mean that many species shall learn to navigate (among
others) by the sun and the stars, given the known history of the earth?
We use the term domino event to refer to a
causal connectivity or a correlation between two sets of physical
events. If physical event e1 causes event e2, or
there is a correlation between event e1 and e2 in
time, then e1 -> e2 is called a domino event
E. A domino event chain would be a sequence of domino events E1
E2 E3 ... En ,
such that e1 -> e2 -> e3 ->
... -> en+1 where Ei
represents the ei -> ei+1
connection. Note that a domino event is not a physical event in itself,
but a logical connection between two sets of physical events,
that one set implies the other under some circumstances. Any physical
event e may internally be composed of sub-events in combinations. A
domino event is an information abstraction, expressible in terms of
logic, similar to a rule in a production system, or to some circuit in
a logic network. Domino event chains may be viewed as representative of
the laws and correlations of the environment. It is suggested that
evolution also involves the discovery and assimilation of domino event
chains into the genetic makeup of organisms, which show up as their
instinct. To make a crude analogy, evolution might discover
correlation chains within the logic of the environment, like an
inference engine that runs through a production system and discovers
new inferences. The sections that follow attempt to elucidate on this
concept.
Back
to Index
|
|
An
Artificial World
|
|
Here we describe a study of evolution in an artificial
world of our own creation, a world with its own hidden "laws"
and correlations.
The world consists of an MxN
cylindrical grid in which organisms are populated. An organism at the
beginning of its life finds itself somewhere on the first row (of the M
rows) of this world. Reminiscent of the snakes and ladders game, this
world is populated with three types of snakes and ladders (Fig. 1). The
"ultimate goal" set for an organism is to reach the highest
row, viz. the Mth row of the world,
navigating the snakes and ladders on its path..
An organism encountering a snake's head is swallowed, to find itself at
the tail end of the snake. Similarly, an organism encountering the base
of a ladder would find itself at its top. The snakes and ladders are
"colored" red, green or blue.
A world is generated according to certain rules. The
maximum and minimum possible number of each type of snake and each type
of ladder in the world is fixed. They may be positioned almost
arbitrarily in the world, but subject to the following rules:
1.
Whenever a red snake is generated into the
world at some arbitrary position, there will always be a green ladder
starting two cells away to the right from the tail end of the snake, on
the same row. This ladder will be longer (in rows) than the red snake
it accompanies.
2.
Whenever a red ladder is generated (again at
some arbitrary position), there will always be a green snake starting
at the cell just above the top of the ladder. This snake will be longer
than the ladder it accompanies.
3.
Green ladders and green snakes may also occur freely,
independent of any correlations with the red snakes and ladders.
4.
Blue snakes and blue ladders may occur freely,
without any dependencies at all.
Organisms are embodied with sensors, actuators, memory
and some DNA. This DNA is but a string of bytes, interpreted as a set
of operational instructions which may be used for evaluating the
sensors, moving a step in some relative direction, or performing some
arithmetic and logical operations. An organism can potentially sense
only its immediate neighborhood of atmost 8
cells. Its behavior is controlled by a DNA
transcription logic, which is reminiscent of those in prokaryotes [4].
A gene is defined as having a header, weight, codons
and a trailer (or the header of another gene). The header (H) and
trailer (T) are bit patterns which tend to attach or detach an "executionase" (E) (Fig. 2). The "executionase" is an abstract entity that has
affinity to a particular bit pattern on the DNA sequence. The executionase "attaches" to a gene and
moves along it, interpreting the "codons"
until it finds a trailer pattern or gets prematurely disassociated by
some specific codons (instructions). Some codons may cause the executionase
to "jump" across a specified number of codons
within the gene as well.
The affinity of the "executionase"
to a gene depends on the "closeness" of the gene header
pattern to a specific pattern of the executionase.
Therefore it is this affinity that defines the number of active genes
in the DNA sequence as well as their order of execution.
The gene is also endowed with a dynamic weight (W)
which is not used in the simulation described here. This weight can be
modified during the lifetime of the organism, changing the affinity of
the executionase to the gene dynamically.
Such a mechanism is useful in allowing an organism to learn from the
environment (changing the weights based on positive and negative
feedback). However, a modified weight is not transmitted to progeny,
thus avoiding Lamarckian inheritance.
The sensors and actuators are memory mapped to make
their control easier. A memory read of a sensory location
"evaluates" the sensor and returns an integer value. A memory
write to an actuator may cause the organism to move in some relative
direction, or emit pheromone (of a type depending on the actuator). In
this simulation, however, pheromones are not used.
Thus the memory, the dna
string, and the executionase together
represent the organism. The executionase
"runs" continuously, interpreting the codons
and thus generating the behavior of the organism.
Back
to Index
|
|
Simulation
|
|
A population of P organisms are
generated from random dna sequences. For each
such organism, a world is generated subject to the rules mentioned
earlier and the organism is placed at a random column on the first row
of the world. The executionase of the
organism is activated and is allowed to run for a maximum of CYCLEMAX
cycles or until the organism reaches its goal (the Mth
row) whichever occurs first. The fitness f of the organism in this
world is then computed. This process is repeated for Nw newly generated worlds for the same organism, and the resulting Nw
fitness values are averaged to get the effective fitness e of the
organism (see Fig. 3). This is done to counter the possibility that an
organism may get lucky by chance meeting of some long ladder. Therefore
the true worth of an organism is estimated by putting it through a
number of worlds or "situations". In nature this is so, since
almost every day organisms replay their strategies of survival.
The above procedure is repeated for each of the P
organisms. The top 10% best fit among these are selected and random
mutation and cross-over are applied to generate a new population of P
organisms. The simulation is iterated over this new population.
The fitness criteria is based on the number of moves
(m) the organism makes in the world, as well as the row ( r ) that it
finds itself at the end of a run. The term r2 is used so
that an organism that has reached the 6th row at the end of a run by
making 3 moves is more fit than that which has reached only the 4th row
making 2 moves.
Back
to Index
|
|
Simulation
Results
|
|
We used a grid of size 100x20 (to reasonably fit on a graphics
display), a DNA string size of 2Kb, mutation rate of 0.01% with Nw=(10 to 20) and an
initial population P = (300 to 1000) organisms in various runs. The codons represented 2 or 3 byte instructions for
memory, arithmetic and logical operations. Simulations were run for
weeks due to CPU requirements. The following behavior
were noted (by picking samples of the 10% best-fit in the
populations and "executing" them graphically).
1.
The organisms learned (over evolutionary time)
to recognize snakes as dangerous and ladders as beneficial.
2.
Many of them learned to avoid the red ladder
initially, but later overcame the difficulty.
3.
|
They learned to recognize a red snake as beneficial,
and would take the plunge, make the two steps and climb up the green
ladder.
|
4.
Sometimes this behavior evolved within a few
hundred generations, and sometimes it took a few thousand generations.
5.
The best performers often had a tendency to
move diagonally in the world, probably because this would result in their
encountering more variety. An organism moving straight would get to
sense only 3 new cells during each move in an 8 cell neighborhood. But
a diagonally moving one would get to sense 5 new cells per move. With a
genome fit to handle these more frequent encounters, they moved to
their "goal" faster than those which moved otherwise.
Back
to Index
|
|
Behavior
vs. Internal Efficiency
|
|
Initially the fitness criteria used the number of cycles
of CPU time an organism took rather than the number of moves it made.
Thus the best performer was decided based on the amount of CPU time
taken. The result was disappointing. Neither
behaviors (2 & 3) emerged, and the populations tended to
become uninteresting and monotonic. That is to say, it looked like
behavioral variety soon ceased to exist. Because of the evolutionary
drive for tighter and faster coding the populations were restricted in
developing complex behaviors. Then we realized that, in nature, the
environment rewards behavior, and not the internal efficiency of
organisms. Thus it meant that if we wanted complexity of behavior to
increase, then the fitness criteria should evaluate the organism's
behavior as it is apparent in the world. Therefore the criteria was changed to the number of moves an
organism made in the world. This however is not meant to imply that
internal efficiency is not a criteria, for it
would be reflected n behavioral efficiency. In our case, if an organism
took too many CPU cycles to make a move, then it would make only a few
moves and end up consuming CYCLEMAX cycles. Its would
tend to be less fit than one that moved faster and consumed less CPU
cycles. One that moved too fast and consumed very small amount of CPU
cycles would tend to be "dumb" and thus less fit.
Fig 4. is a plot of the
fitness of the best individual in a population, over generations. The y
axis is the approximate number of moves an individual took to reach its
goal. Actually it plots the value (1002/ef). It
can be seen that the fitness fluctuates within a band, owing to
variations in the environment, where one strategy may not always be as
successful as it was in the previous round.
Back
to Index
|
|
Discussion
|
|
In the simulation described above, the organisms
discovered "hidden" rules or correlations within the
environment to their advantage. These rules or correlations remained
invariant, so to speak, over the generations, and were assimilated into
the genetic makeup of the evolving organisms. One may extend the rules
so that correlations may exist between say, the position of green
ladders (associated with red snakes) and blue ladders, which the
organisms will make use of in further evolution. One might say that
evolution tends to internalize chains of correlations (what we call
domino event chains) into the genetic makeup of its organisms. These
correlations need not be discovered in any particular order unless
constrained by their nature. Parts of a complex correlation web which
is persistent over evolutionary time may thus be internalized in terms
of small correlation chains, leading to leaps in species fitness.
To pick an example from nature, female canaries are
brought into reproductive condition by a change in day length and other
external stimuli. These result in a change in the endocrinal state,
leading to nest building behavior. Stimuli from the resulting nest
cause further changes in the bird's behavior [3]. To cite examples of
inventions in biosystems, we may consider the
cilia and flagella "motors" of the bacteria E. Coli, the
transport mechanisms in cells, photosynthesis in plants, the sonar of
bats, electric eels, the chemical gun of bombardier beetles, migration
of birds using the earth's magnetic field and so on. One might be
tempted to predict that nature is abounding with plenty of such hi-tech
biosystems, especially among species which
have a low life-time expectancy and high reproduction rate.
Back
to Index
|
|
Evolution
in a Logic Network
|
|
We would like to suggest a simplified scenario as in
Fig. 5 where the environment is depicted as some complex logic network with
state. This environmental logic network has input/output terminals
which may be tapped by organisms using their sensors and actuators. The
inputs to this net represent actions performed by the organisms on the
environment. The outputs are sensory evaluations of the organisms or
actions performed from the environment on the organisms. These
organisms are also pictured as logic networks, their organization
dictated by dna. In this scenario, creature
evolution may be viewed as the functional optimization of the creature
networks based on interactions with the net terminals. The genetic
algorithms of nature would then cause the creature logic, with its
limited set of input/output terminals, to "guess" the
functionality and features of the net to its benefit. Mutations would
help not only in modifying creature logic, but also in tapping new
terminals. Thus over evolutionary time, creatures should be born with
some "knowledge" of certain causal connections and
correlations of its environment. A knowledge which we would call
instinct. This "knowledge" would consist of a set of wired-in
responses to certain cues or signals from the environment logic. In
nature, some species of fish (as well as some trees and plants) emit
certain chemicals into the environment when attacked. Other fish (or
trees or any threatened species) could genetically discover this
correlation and act upon it. No doubt such correlations exist plentiful
in nature, and may lead to interesting hunting and evasion skills among
species. In the snake-and-ladder world, the discovered behavior 3
(under simulation results) could be extended by more correlations so
that the organisms would follow up behavior 3 with yet another. Thus
automated responses may also involve a sequence of actions towards accomplishing
a beneficial task.
Back
to Index
|
|
Colonies
and Distributed Control
|
|
In Fig. 5, creature logic interacts with one another
through the environment logic. The environment logic would be explored
by variations of signals on the input/output terminals, or by selection
of new terminals. To quote an example, there has
been instances of electrical transformers attracting and killing
mosquitoes in large numbers because of the electrical system emitting
certain frequencies that resulted in a mosquito response. Evolution
should drive creature logic systems to discover new ways of interaction
by making use of hidden subsystems within the environmental logic.
Perhaps insect colonies would be of interest in this perspective. A
colony may be thought of as a distributed logic network consisting of
individual creature logic networks, controlling and/or being controlled
by one another through the environment logic. Consider a termite colony
for example. The number of termite soldiers in the colony is regulated
automatically without any centralized control. The soldiers emit
certain "pheromones" which suppress the morphogenesis of eggs
into further soldiers. When some soldiers die, their pheromone
concentration comes down and some eggs start developing into soldiers,
to replace the ones that died. In such colonies we usually find
distributed and centralized controls which result in emergent behaviors
when actions are performed en masse. (e.g.
bees fanning their wings to keep the hive temperature under control).
Back
to Index
|
|
Behavioral
Attractors
|
|
There are other interesting possibilities to be
considered. Given that correlation/causality chains may get assimilated
and complex interactions might develop, these chains may form attractors.
Random boolean networks are known to settle
into attractors quickly [4]. This may not be the exact situation here,
but we might expect some assimilated set of actions of an organism to
be stable and repetitive due to certain recurring signals from the
environment. Like a gramophone needle getting stuck, playing a short
piece of music again and again. Such a set of recurring actions may be
called a behavioral set. If the causative recurring signal ceases to
exist, or a higher priority one comes into existence, then the creature
logic system might fall into some other attractor, resulting in the
organism exhibiting some other behavioral set. We may be thus tempted
to think that apparent creature behaviors, as diverse as foraging,
fighting, courting, breeding, parenting, etc. may have some connection
to the formation of such attractors. Remove a mother bird's nest of
eggs and it may initially fret about for a while and then go on its way
(perhaps foraging) as if nothing has happened. A young bird in the nest
opening its mouth or pecking at its mother's beak and the mother bird
regurgitating food into its mouth could be a set of event sequences
based on mutual triggers. Cases of neglect by parent birds of its young
which have fallen just outside the nest rim also imply their following
event sequences based on triggers [3].
Back
to Index
|
|
Morphogenesis
|
|
All these interactions ultimately have a cellular
basis. An organism is able to interact highly meaningfully with another
of the same species due to genetic programming that defines its instinct.
We may call this as self-referentiality,
where a genome is programmed to interact with copies of itself. The same would be true at the level of
cellular interaction. Cells are able to coordinate with one another and
form a "society" with rules and controls and some wired-in
knowledge of the complete system i.e. the body of the organism.
Specializations within an insect colony, like the queen, workers,
soldiers etc. may be compared, though at a different scale, to cell
specialization. Each soldier in an insect colony responds to specific
signals from its environment and is "trapped" in one or more
behavioral attractors. The same is the case among cells. It is quite
conceivable that the complex cellular interactions during morphogenesis
result in patterns of cellular signalling
(attractors) that cause the cells to specialize in many ways.
Earlier we noted an example of how pheremone
concentration can affect a termite egg developing into a soldier. Once
attractors are established, differentiation should cease and growth
should proceed along these attractors. It is possible that a wasp
making a home on a leaf disturbs the attractors of the leaf using
chemical signals so that the growth pattern is modified to provide a
home for the wasp.
Morphogenesis itself may be thought of as happening in
a universe or world of its own, where different kinds of attactors are generated by genomes for selection.
These are attractors (patterns of signalling)
that result in cell specialization and function. This is indeed a
natural selection process since the outcome of any single morphogenesis
has to function in its environment. Whatever evolutionary strategies
are developed outside the world of morphogenesis, it must be discovered
first within, albeit in an indirect way. Thus true evolution may be
said to take place within this world, though it is not directly in
touch with the real world where form and function are selected for.
This is basically developing "innate" knowledge of an
external environment, as suggested in figure 5. Many systems that
undergo morphogenesis gain indirect "knowledge" of one
another. In this light, we may regard morphogenesis as perhaps the most
complex process taking place on the planet.
In summary, we may hypothesize that in any scenario
where sets of logic systems evolve against a collective logic, in
addition to innate knowledge, self-referentiality
as well as specialization will come into existence. This is true for
cells, organisms and the human society (social, cultural and
technological) - but at various levels of coupling.
Back
to Index
|
|
Conclusions
|
|
In conclusion, we suggest that there is a drive towards
the discovery and assimilation of laws and correlations of nature into
the genetic makeup of organisms. We would say that organisms of today
are extremely hi-tech. And we shouldn't be too surprised if they are
even using quantum effects to their advantage!.
We have attempted to provide some explanation of how event sequences of
behavior may be internalized over evolutionary time. The principles
underlying genetic algorithms are nothing new, and their potential as
optimizers is well known. In this sense, we have not suggested any new
unknown principle at work, but have attempted to view and highlight its
workings from a different perspective.
In our discussions here, we have not considered the
issue of co-evolution of the environment logic with the creature-logic
systems. We also have not considered "learning" during
lifetime and its effects over evolutionary time (Baldwin
effect) in moulding behavior [1]. Here we are
more interested in inherited behavior as it is transmitted
"blindly" without lifetime learning, though acquired behavior
is also expected to come from discovery of domino event chains. For
example, in forests, monkeys set out in groups for feeding
destinations, leaving a flutter of insects in their path. Birds learn
to follow these groups, dining on the insects they scatter. However,
such chains may not be persistent over evolutionary time for genetic
assimilation. Evolution of parental imitation would help, though.
We also have not attempted to separate out
self-organization and emergent behavior from the event chains and their
outcomes. It is expected that in a complex interconnected system like
nature, almost every event has some immediate effect on the environment
which leads to some form of emergent effect through the working of some
natural law. Therefore many an observable functionality of organisms
would involve self-organization and emergent behavior at various levels
(molecular, biochemical, physical, ecological, to even astronomical).
It would be interesting to see whether a simulation
study of evolution in the logic model suggested here, with random
creature logic networks evolving against a sufficiently complex
environment logic, would result in patterns of interactions like
distributed control, attractors, symbiosis, parasitism etc. This is an
avenue for further research.
|
|
References
|
|
[1] Baldwin J.M. (1896), A new factor in evolution,
American Naturalist, 30, 441-451
[2] Eldredge, N., Gould S.J. (1972), Punctuated equilibria: an
alternative to phyletic gradualism. Models in
Paleontology, ed. T.J.M. Schopf, pp. 82-115. San Francisco: Freeman,
Cooper & Co.
[3] Hinde, R.A. (1982), Ethology,
ed. Frank Kermode, William Collins Sons & Co. Ltd, Glasgow.
[4] Lehninger L.A.,., Nelson L.D., Cox M.M
(1993), Principles of Biochemistry, Worth Publishers
|
|
|
|