Transcript Universal Darwinism: How Computer Science has Validated

Universal Darwinism: How
Computer Science has Validated
the Theory of Evolution
Don Baker
September 2, 2007
Lonestar Mensa
About the Speaker



Ph.D. in Computer Science
Work for a telecommunications company as a
researcher in the field of Computer-Supported
Cooperative Work (CSCW)
Adjunct Assistant Professor, Computer Science at UT
–


Taught the theory of computation
Vice President of the Atheist Community of Austin
Interests include atheism, memetics, evolutionary
biology
Disclaimer: I have no professional expertise in biology.
Why I'm Giving this Talk

Interest in Alan Turing and his contributions
–
–
–
–

Interest in evolutionary biology and its application to other areas
–

Turing is considered the father of Computer Science
Laid the foundations of computability and its power and limitations
Turing Machines as problem solvers
In 1948, Turing suggested that evolution may be an alternate way to generate
a problem solving mechanism: “There is the genetical or evolutionary search
by which a combination of genes is looked for, the criterion being the survival
value.”
Richard Dawkins advanced the concepts of replicators and memes
The advance of the Intelligent Design movement
–
–
–
Despite a lack of evidence for ID, it has gotten a lot of traction
Much of the traction among the lay audience is because the theory of
evolution requires some thinking and imagination—it’s not an immediately
compelling explanation
ID has effectively traded in building doubt in this “gap”
Why Evolution is not Compelling
(in an “armchair reasoning” sense)

So much apparent design in living things
–
Amazing complexity within organisms

–


eyes, sonar, wings, camouflage, hunting strategies
Stunning diversity of species
The gist of Darwin’s theory is very simple
People generally cannot reason about the vast
amounts of time involved
“How can something so simple create something so
complex in so little time?”
Evolution is Difficult to Study
Experimentally

Need a controlled environment with many organisms
that are given a chance to evolve over many
generations

But we have learned:
–
Animal husbandry and agronomy have yielded important
practical results


–
Dog breeds
Hybrid crops
We have seen evolution in bacteria and other species
How Might Computer Science
Help?



One definition of computer science:
Constructive models of the world and their
implications.
Evolution is effectively an algorithm
Computers can be used to create virtual
environments in which simulations can run at
speeds faster than their biological counterparts
Recasting the Problem



Can we capture the essence of evolution in a
simulation and, by inference, learn about the
potential of evolution?
In particular, is evolution alone able to create
complex designs?
Can diverse designs be created, perhaps with
different characteristics?
What is the Essence of Evolution?

Outward traits as an expression of instructions
–
–

Instruction inheritance from parent(s) to child
–
–

Phenotype determined by genotype
Genotype may either be a blueprint or a recipe
Genotypic inheritance
The possibility of copying mistakes (mutation)
Culling of individuals through natural selection based
on a fitness criteria applied to outward traits
–
–
–
i.e. death vs. having lots of offspring
Competition for resources
Better instructions become more prevalent over time
Evolution really operates on the instructions.
Outward Traits as an Expression of
Instructions



Instructions are digitally encoded
Instructions are drawn from a “space” of possibilities
Examples:
–
–
–
–
–
Cooking recipe  The dish it describes
Architectural blueprint  The building it describes
A game playing strategy  A game where one side uses it
Computer program  Output or other behavior
Electronic circuit diagram  Signal response of the physical
circuit
Instruction Inheritance from
Parent(s) to Child

High-fidelity (digital) copy, but not perfect
–
–


Sexual (crossover) or asexual inheritance
Mechanism of copying is not important
–

“Telephone” game vs. computer viruses
Instructions with mistakes have some possibility of generating
a viable result
In computer simulations, inheritance is performed explicitly
A set of instructions need only have a slight positive
effect on the prevalence of instructions in future
generations
Natural Selection on External Traits

Continued existence of an individual is based on a
fitness criteria as measured on the external traits
–
–
–


No “intelligent designer” making choices
More “fit” individuals generate more offspring
Even a large amount of random chance is ok
The fitness criteria creates a landscape over the
instruction space
Natural selection can be likened to hill climbing
(optimization)
Fitness Criteria

In a computer simulation, the fitness criteria ranks the
possible results according to some fixed metric
–
–
–

Speed, cost, size, etc.
Even simplicity or elegance (if they can be quantified)
Any combination of the above
In biological evolution, the fitness criteria is just the
fecundity of the individual
–
–
Changes in selection pressure due to weather, catastrophes,
continental drift, etc.
Changes in selection pressure due to the evolution of other
species (co-evolution)
Capturing Evolution in a
Genetic Algorithm (GA)
A genetic algorithm is a probabilistic search
algorithm that iteratively transforms a set (called a
population) of mathematical objects (typically
fixed-length binary character strings), each with an
associated fitness value, into a new population of
offspring objects using the Darwinian principle of
natural selection and using operations that are
patterned after naturally occurring genetic
operations, such as crossover (sexual
recombination) and mutation. -- Koza
Genetic Algorithms Can Solve a
Large Variety of Problems

Relate the problem to an instruction space (genome)
–

Create a means of random mutation and possibly crossover inheritance
–

e.g. “the least squares distance in frequency response of the circuit compared
with the idealized frequency response of an amplifier”
Start with an “Eve” individual from the instruction space
–

e.g. Alter the circuit by adding or removing a component or changing value
Create a fitness criteria as a function of the instruction space
–

e.g. all possible electronic circuits involving resistors, capacitors, inductors of
standard values
e.g. a circuit with no components
Run the GA and wait
–
–
May want to define a termination criteria based on a “good enough” result
Might still have to wait many generations (hundreds to thousands)
Note that the GA hasn’t been told how to design, but the
winners in this race are solution designs.
Areas Where GAs have been
Applied
















Acoustics
Aerospace engineering
Astronomy and astrophysics
Chemistry
Electrical engineering
Financial markets
Game playing
Geophysics
Materials engineering
Mathematics and algorithmics
Military and law enforcement
Molecular biology
Pattern recognition and data mining
Robotics
Routing and scheduling
Systems engineering
Hemispherical Coverage Antenna
…a circularly polarized seven-segment
antenna with hemispherical coverage. Each
individual in the GA consisted of a binary
chromosome specifying the threedimensional coordinates of each end of
each wire. Fitness was evaluated by
simulating each candidate according to an
electromagnetic wiring code, and the bestof-run individual was then built and tested.
The authors describe the shape of this
antenna, as "unusually weird" and "counterintuitive" (p.52), yet it had a nearly uniform
radiation pattern with high bandwidth both
in simulation and in experimental testing,
excellently matching the prior specification.
Load-bearing Truss

…that could be assembled in
orbit and used for satellites,
space stations and other
aerospace construction
projects. The result, a twisted,
organic-looking structure that
has been compared to a
human leg bone, uses no
more material than the
standard truss design but is
lightweight, strong and far
superior at damping out
damaging vibrations, as was
confirmed by real-world tests
of the final product.
Lowpass Filter Circuit
Lowpass filter frequency response
Evolved Campbell Filter
(U. S. patent 1,227,113
George Campbell
American Telephone and
Telegraph 1917)
Acoustics
Sato et al. 2002 used genetic algorithms to design a
concert hall with optimal acoustic properties,
maximizing the sound quality for the audience, for the
conductor, and for the musicians on stage. This task
involves the simultaneous optimization of multiple
variables. Beginning with a shoebox-shaped hall, the
authors' GA produced two non-dominated solutions,
both of which were described as "leaf-shaped" (p.526).
The authors state that these solutions have proportions
similar to Vienna's Grosser Musikvereinsaal, which is
widely agreed to be one of the best - if not the best concert hall in the world in terms of acoustic properties.
Robocup Autonomous Robot
Soccer Controller
To solve this difficult problem,
Andre and Teller provided the
genetic programming algorithm
with a set of primitive control
functions such as turning,
moving, kicking, and so on.
Out of 34 teams in its division,
Darwin United ultimately came in
17th, placing squarely in the
middle of the field and outranking
half of the human-written entries.
A (human designed) entry
Are the Designs “Intelligent”?




How do we measure the intelligence of a nonhuman designer?
Can compare against human performance
Are humans intelligent? …sometimes
Rephrasing: “Can GAs create humancompetitive designs?”
Eight Possible Criteria for HumanCompetitiveness (Koza)








The result was patented as an invention in the past, is an improvement over a
patented invention, or would qualify today as a patentable new invention.
The result is equal to or better than a result that was accepted as a new scientific
result at the time when it was published in a peer-reviewed scientific journal.
The result is equal to or better than a result that was placed into a database or
archive of results maintained by an internationally recognized panel of scientific
experts.
The result is publishable in its own right as a new scientific result—independent of
the fact that the result was mechanically created.
The result is equal to or better than the most recent human-created solution to a
long-standing problem for which there has been a succession of increasingly better
human-created solutions.
The result is equal to or better than a result that was considered an achievement in
its field at the time it was first discovered.
The result solves a problem of indisputable difficulty in its field.
The result holds its own or wins a regulated competition involving human
contestants (in the form of either live human players or human-written computer
programs).
To Date, 36 Human-Competitive
Results Have Been Obtained



According to the criteria just given
Several new patents have been generated
Many designs are considered counterintuitive
or not well understood by experts in the field
from which the design is drawn
Improving on Genetic Algorithms

Improving on nature
–

GAs are computationally expensive, but inherently
parallel
–

Many variations on inheritance mechanism are being
considered by the GA community
Many challenges to build efficient GAs and computer hardware
to support them
GAs over computer programs are called Genetic
Programming
–
Most general type of GA, as most design problems can be
expressed in the form of a computer program
Genetic Programming
(Evolution of computer programs)


Program represented as parse tree in GP
Mutations involve random changes to parse tree
including
–
–
–
–
–


Localized statement changes
Structural rearrangements
Duplication of subtrees
Changing sub-trees into routines
Etc.
Phenotype is the behavior of the running program
Fitness measured by comparison of actual output to
desired output for a given input
Genetic Programming is a General
Problem Solving Technique




Computer programs can solve entire classes of
problems (i.e. Universal Turing Machine)
But programs have to be designed
In 1948, Turing suggested that evolution may be a way
to generate a problem solving mechanism
The “General Problem Solver” has been something of
a holy grail of computer science research
–

Work in this area has spawned the field of artificial intelligence
This important goal has been achieved!
Universal Darwinism




Darwin’s theory applies to more than just biological
evolution
Evolution alone is able to create complex designs to a
diversity of problems
Application of Darwinian evolution within Computer
Science has provided a powerful validation of his
theory
Genetic Programming is a general problem solving
technique that has resulted from Darwin’s ideas
Parting Shot

“Once a Darwinian process gets going in a
world, it has an open-ended power to generate
surprising consequences: us, for example.”
–Richard Dawkins
Further Exploration
(My material came primarily from these sources)

“Evolving Inventions”, Koza, et. al.
–

Genetic Programming web site (Koza’s work)
–

http://www.genetic-programming.org
“Genetic Algorithms and Evolutionary Computation” by
Adam Marczyk available via the Talk Origins archives
–

Scientific American, February 2003
http://talkorigins.org/faqs/genalg/genalg.html
“Does Intelligent Design Require a Creator?” by Don
Baker
–
http://www.christianitymeme.org/intel-design.shtml
Richard Dawkins’ Biomorphs
Introduced in “The Blind Watchmaker”
Use the Program to Play God
Example Creatures
http://www.well.com/~hernan/biomorphs/biomorphs.html
Controversies




Real evolution doesn’t have a goal
Isn’t defining the fitness criteria in effect
“playing God”?
There is “design” in the starting point
No new information is being generated
Response to the ID Proponents

If something is a science then:
–
–
–

Paley’s watchmaker argument (~1802) is older than
the theory of Evolution (~1859)
–

Predictions can be made from it
Technology can arise from it
Benefits to mankind can be derived
ID/creationism has born no technologic fruit
Evolution has made advances in biology and other
fields, including computer science