From: Brian Ferris (bdferris@cs.washington.edu)
Date: Wed Dec 01 2004 - 11:54:21 PST
In "The evolutionary origin of complex features" by Lenski et. al., an
attempt is made to experimentally verify one of the fundamental
concepts in Darwin's theory of evolution. The theory states that
complex biological features, such as the eye, must evolve over a series
of incremental adaptations and mutations. While evidence does exist to
support this model, the inability to examine the complete evolutionary
history of an organism over time makes support difficult. The authors
seek to make the complete examination of the evolution of a complex
feature possible by examining the evolution of digital organisms.
The experimental setup involved an digital organisms defined uniquely
as a loop of processing instructions. The environment allowed for
replication, mutation and competition amongst organisms in the
following way. Replication is asexual and occured using binary
fission. Mutation occurred during copying, by way of point mutations,
insertions, and deletions. Finally, competition was implemented by
rewarding organisms for performing logic operations. The only logic
operation available in the base instruction set was a nand-op, from
which all other operations can be constructed. Reward increased
exponentially up to EQUALS operation, which is both highest in
complexity and reward.
The actual experiment evolved the examination of a case-study group and
then a few experiments to determine how altering the environment
affected the evolutionary process. Their examination of genetic lines
that evolved to include the EQUALS operation raised a number of points.
First, while there were a large number of positive mutations along the
line, roughly sixteen percent of the mutations were negative in nature.
Examinations of these evolutionary backwards moves showed that their
combination with subsequent mutations lead to highly beneficial
results, suggesting that evolutionary advancement is not completely
uphill.
Another interesting point was that no intermediate logic function, such
as OR, NOR, XOR, et-cetera, was specifically required in the
evolutionary path, as all of the genetic lines evolving to EQUALS had a
case with at least one sub-operation left unimplemented. This point
was corroborated when they modified the environment to remove the
reward from specific operations or pairs of operations, and the EQUALS
operation still consistently evolved.
One could consider the digital evolution performed in this experiment
as just another form of search. Each unique collection of processing
instructions defines a unique organism and a unique state in the search
space. State transitions occur during replication, with different
branches encompassing different mutations. The authors point out that
there are ~5.6 x 10^70 genotypes possible in this search space, so an
uniformed search is obviously out of the question. However, the two
points the raised about the properties of the evolutionary path raise
interesting questions about implementing an informed search.
The key issue in determining a heuristic for informing EQUALS evolution
is that genetic lines evolving to success often involved deleterious
mutations. That is, straight hill climbing towards our goal has to
navigate multiple local maxima. Thus, informed search would likely
need to be combined with some stochastic element such as randomly
ignoring the heuristic or simulated annealing to properly advance the
search.
A point I found interesting was that no one sub-operation was key in
the evolutionary chain of successful genetic lines. I believe the
selected reward values for performing the various logical operations
might play some role in the evolutionary cycle, but the details on the
selection of these weightings was not in-depth and no experiments
exploring alternate weightings was explored.
This archive was generated by hypermail 2.1.6 : Wed Dec 01 2004 - 11:53:17 PST