The Evolutionary Biology Lecture of the Week for May 1, 2006 is now
available at:
http://aics-research.com/lotw/
The talks center primarily around evolutionary biology, in all of its
aspects: cosmology, astronomy, planetology, geology, astrobiology,
ecology, ethology, biogeography, phylogenetics and evolutionary biology
itself, and are presented at a professional level, that of one scientist
talking to another. All of the talks were recorded live at conferences.
This week's lecture is the first of three lectures that will discuss
whether or not Darwinian evolutionary theory is sufficient to explain
all of the phenomena we see in nature.
=====================================
May 1, 2006
Part I: Is Evolution Sufficient?
Accelerating Problem Solving by Combining
Machine Learning and Human Learning
David Fogel, Natural Selection, Inc.
28 min.
The most salient aspect of Darwinian evolutionary theory is that it is a
learning algorithm, no different in effect than the learning that we
imply to individuals.
If a process is well understood, it can be exploited for engineering
purposes, and indeed evolutionary theory is likely to become the
dominant algorithm in computer engineering in the coming decades,
providing it with an economic worth comparable to biology's contribution
to medicine and agriculture.
But can evolution design anything of quality in any reasonable time? The
common perception is that the evolutionary process is both
excruciatingly slow and random. Engineers are not only an impatient
bunch, they're picky about the quality of their solutions.
In this talk, presented to an engineering audience at Stanford a few
months ago, David Fogel talks about this promise, but in the short time
available speeds by two attributes of his work that are of profound
philosophical importance to biology: (i) the speed of evolution and (ii)
the credit-assignment problem.
The Speed of Evolution
Engineering has its common lab problems too, just as biology has
Drosophila and Arabidopsis. Among these are the traveling salesman
problem (TSP), checkers and chess.
The TSP is easily stated: determine the shortest possible path to visit
a specified list of cities, visiting each city only once, and then
return home. It is however a problem that grows in complexity amazingly
quickly. If there are only 4 cities on the list, there are only 3
possible paths. But if there are 16 cities, then 653,000,0000,000 paths
need to be examined to determine the shortest path, and if there are 100
cities, 10^155 possible paths arise.
It's the 100-city problem that is of interest here. Could we find the
solution by simple enumeration (that is, by trying every possibility)?
It only takes a quick calculation to demonstrate that the answer is no.
If we were to presume that we could evaluate one trial in a femtosecond
(10^-15 s), the fastest that any known physical process operates, and if
we were to evaluate a million million of these solutions per femtosecond
for the length of the age of the galaxy, 10 billion years, then only
10^44 trials could have been examined. This still leaves 10^155
solutions to be examined. Clearly, if we were to employ this procedure,
we would make no headway at all, and thus this simple calculation
becomes prevalent in the creationist literature, denying any possibility
of unguided evolution.
But this isn't of course the way that evolution operates. It doesn't
explore the entirety of the experiential state space. Rather, it merely
retains the best of the current phenotypes at each generation, no matter
how poor they are. Nonetheless, when this simple process is repeated
generation after generation, it quickly generates solutions of
astounding quality.
In David's example, which he demonstrates in real-time, a population of
only 100 individuals is iterated over 10,000 generations and yet creates
a solution within 2% of the expected best path. The procedure takes less
than one second on his 1 GHz laptop. This short time doesn't afford you
sufficient time to understand the profundity of what happened without
first understanding the difficulty of the problem.
The Credit-Assignment Problem
It only seems intuitive to reward good behavior and punish the bad, and
thus "weights" are commonly assigned to optimization problems: in
manufacturing, where a machinist is paid by the number of widgets he
produces per hour, in mathematical genetics, where individual genes are
given selection coefficients, and in chess, where the pieces are
assigned relative worths.
But this process is also known to generate such poor solutions that it's
been given a name, the credit-assignment problem. If weights are in
effect, the factory fills up with widgets it can't use.
This too is not how evolution operates. It does a species no good to
produce individuals with intestines of extraordinary quality but with
defective hearts. The competitiveness of the species' phenotypes is
judged by the whole of their responses, not by their individual parts.
In the second half of David's talk, his checkers game experiments are
specifically programmed to eliminate the credit-assignment problem. Not
only do his evolving populations of neural nets not know the rules of
the game that they're playing, he doesn't even tell them if they've won
or lost individual games so as to miminize any sense of credit or blame
being assigned to individual moves.
Nevertheless, in a relatively short time, with the neural nets competing
among themselves on a single, slow machine, they evolved into structures
that can outcompete 99.5% of all human contestants.
Perhaps of even greater interest, if the physics of the game should
suddenly change, so that red becomes black and vice versa, the evolved
structures would for a time do exceptionally poorly under the new rules,
but they would also immediately begin to re-evolve, adapting to the new
rules and eventually once again become exceptionally competitive.
======================================
.
|
