Hello. Our guest spot this week is Stephanie Forrest, who
is Professor of Computer Science at the University of New Mexico, where she
directs the Adaptive Computation Lab. Stephanie is also external professor
at the Santa Fe Institute and co-chairs the Institute’s Science
Board. Steph has been working for many years at the intersection
of computer science and biology and is an expert on genetic algorithms
which we have been studying in this unit. So welcome, Steph.
Thank you so much. It’s great to be here. So I know you’ve been studying genetic algorithms for a long time
we’ve even worked together on projects in genetic algorithms
but I wanted to get your view on why genetic algorithms are relevant to the study
of complex systems.
Well, the first thing is that genetic algorithms can be viewed
as a simple model of Darwinian evolution.
So just from a modeling perspective, they capture
one of the most important and mysterious
processes on earth -- evolution.
The second thing is that this model of Darwinian evolution
can also be viewed as a kind of design strategy.
It’s a design strategy that’s been used widely in nature
but also adapted as a computational algorithm
to help design engineering systems.
And so genetic algorithms are actually used widely in engineering as well.
So just to follow up
why do you say that evolution is mysterious?
Well, first of all not everyone
you can’t look at it, I think that’s the thing
So it’s a process
that, going back to Darwin, was proposed
as an explanation for how the world that we live in
came to be. But that’s not
a process that we can observe.
It’s very difficult to study experimentally.
There are now some experimental systems you can study in test tubes,
like viruses and bacteria that undergo evolution
and so we can study those experimentally.
But I think it’s -- when we confront the world around us
to me, it is somewhat of a mystery how the world came
to be and even though I
tend to believe that the world was produced by evolution,
it’s not always so trivial to understand how
that might have happened mechanically. Right.
I guess -- one other thing -- another mysterious
aspect of evolution are the so-called major transitions
where the system that is evolving
undergoes a major organizational shift
and the action
the evolutionary action takes place in a different
organizational level. And I think even today
most people in evolution would not claim that they understand how
those shifts take place. So you said that genetic
algorithms are a model for evolution. Do you think they can give us any insight
into biological evolution?
I do. Yes.
How, you might ask? Well, they’ve been used
to model many kinds of naturally occurring
evolutionary processes -- not just biological, by the way.
But in the realm of social sciences you can think
of genetic algorithms as modeling how innovations
spread through a community.
And how -- people have written books on the diffusion of innovation
and the idea there is really that ideas and fads
spread through populations in a process not
unlike Darwinian evolution. So you think that Darwinian
evolution is a useful idea, not just in biology, but in other
fields. Absolutely. Absolutely.
I would not claim that it’s the only idea.
Of course. I do think it’s an important idea, and certainly relevant to the study
of most complex systems. So what are you working
on now? What are you excited about? Particularly in the field of genetic algorithms.
So about ten years ago I became interested
in my own field, well, I’ve always been interested in my own field,
but particularly interested in software.
In thinking about how
software infrastructures, that is, large collections of software
for example, all the programs that are sitting on
disks of computers that are attached to the internet -- how that
large collection sort of changes over time and
whether or not it is subject to the processes of evolution.
And through that I became interested a little more directly in
whether or not it would be possible to evolve software.
For example, could we design a program rather than
hiring a highly trained programmer to write it, could we
use evolutionary processes to
produce programs. And although I can’t claim that I
have solved that problem exactly, that led me
into what is potentially an easier problem
which is using evolution to evolve
repairs to software defects
or bugs. And so the idea is that you give me a
buggy program and
I make a number of copies, typically
40 copies of that program, and each of those copies
has some random mutations, not unlike genetic
evolution -- genetic mutations -- and then we
use a genetic algorithm to select the
members of the population that are the most fit, that is
pass -- in our case fitness is measured in terms of regression test suites.
And after a few generations
evolution mysteriously produces
a program that in many cases repairs the bug.
Wow. That’s impressive. Are you going to put programmers
out of work? Well,
potentially. I mean, I do think that
software is a huge
bottleneck. And software maintenance is a huge bottleneck.
So if you look at the economics of computing and where
the money’s being spent, 90% of the cost
of software goes into maintenance. And
maintenance is -- I mean most of that is debugging.
Fixing problems in software that have been identified.
One study that’s a couple of years old
now, but one study estimated the cost of
software bugs as being
0.6% of the US GDP, which is
a significant economic impact. So even if we don’t put
all the programmers out of business, if we can accelerate
their productivity perhaps by either
proposing fixes that they can then check and decide if they want to
accept, or by taking over the tedious task of
fixing small bugs and leaving the programmers to tackle the more
interesting and complex bugs
that would be an acceptable outcome. So how far is this from being
a commercial product? Well, it’s quite a ways
from being a commercial product. We thought about commercializing it, but
so far we’ve gone the open source, public
domain route, and so all of our programs
are available on our website.
I should mention I’m not doing this work by myself. I do it in collaboration with
a professor at the University of Virginia, who knows much more about software
engineering and programming languages than I do. His name is Westley Weimer.
And the two of us have -- I think
both surprised ourselves at how well this project
has gone. And we've recently
completed a big study of over 150 bugs
randomly selected and
we pretty reliably fixed just over 50% of them on the first try.
Wow, that is really impressive. Thank you. It’s better than
most people can do. Better than I can do at this point, which is embarrassing
to admit, but -- Well you don’t need to if you’ve got your genetic algorithm to do it.
Right. But how we use it, and how
we kind of introduce it into mainstream computing is
still an open question for us. So you mentioned this idea of
genetic algorithms automatically creating programs, not
just debugging them. I know there’s a big field called genetic
programming, which has tried to address this. How difficult
a problem do you think that is? We looked at an example in our
class of creating a simple program
to move a robot around on a
screen and have it do certain
actions. But the question is how hard is this to
scale up to really complex programs? Do you think
that’s going to happen? I don’t think
it’s going to happen immediately. And in fact,
I would just point out that the problem that genetic
programming addresses is the problem of starting from scratch.
And one of the reasons that we were able to be as
successful as we’ve been in the bug repair domain
is that we’re starting with a program that is 99.999%
correct.
It’s correct in all ways except it has one bug.
And we’re just trying to fix that one bug.
Genetic programming people start at the other end
and I don’t know which end is
going to be better in the long run. My theory
is to take what we’ve done with working programs, or partially
working programs and kind of looking forward start
thinking about how to add functionality to a program that’s already
working in part. And maybe that's
the difference between evolution and the origin of life, I don’t know.
Alright. Well, thank you so much. This has been really great.
Oh you’re very welcome. It’s fun and complex
systems are wonderful. Okay, thank you.