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.