[fonc] Evolutionary Debugging :.

[Jb Labrune]

a great vid by Santa Fe's Stephanie Forrest about GenProg, a tool for automatic software repair using genetic algorithms

http://www.santafe.edu/research/videos/play/?id=f1f8dacf-0fba-4ebf-a40c-da56453405dd

( && GenProg: http://dijkstra.cs.virginia.edu/genprog/ )

made me think of the elegance of STEPS, the 60's, simplicity and what if this approach was applied to hardware, not just to software (FPGA, RALAs, Self-replicating machines...)

cheers!
jb

—
Ps: made me think also of Bo Morgan's intriguing PhD thesis http://rct.media.mit.edu/papers/morgan2013-substrate_for_accountable_layered_systems.pdf

[Pavel Bažant]

I am developing an evolutionary simulation called Evoversum. An interesting
thing I noticed on multiple occasions while developing the program was the
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

PB

Post by Jb Labrune
a great vid by Santa Fe's Stephanie Forrest about GenProg, a tool for
automatic software repair using genetic algorithms
http://www.santafe.edu/research/videos/play/?id=f1f8dacf-0fba-4ebf-a40c-da56453405dd
( && GenProg: http://dijkstra.cs.virginia.edu/genprog/ )
made me think of the elegance of STEPS, the 60's, simplicity and what if
this approach was applied to hardware, not just to software (FPGA, RALAs,
Self-replicating machines...)
cheers!
jb
—
Ps: made me think also of Bo Morgan's intriguing PhD thesis
http://rct.media.mit.edu/papers/morgan2013-substrate_for_accountable_layered_systems.pdf
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

[Chris Warburton]

Post by Pavel Bažant
I am developing an evolutionary simulation called Evoversum. An interesting
thing I noticed on multiple occasions while developing the program was the
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

Reminds me of a video I saw on YouTube (can't find it at the moment)
where a genetic algorithm evolved creatures (collections of sticks,
joints and motors) in a physics simulation. The goal was to move the
furthest distance, in the hope that they'd walk/crawl/etc. In fact, one
of them triggers a bug in the simulation which causes it to explode,
sending its body parts flying in all directions. This immediately
dominates the population, so all the creatures start exploding.

I suppose the morals are:

1) Evolutionary methods are good at finding bugs
2) Your fitness function is not selecting for what you think it is ;)

Cheers,
Chris

[Robert Feldt]

I don't think I remember the "exploding myself" strategy from Karl Sims
videos:

Do you remember where you saw that, Chris?

Cheers,

Robert Feldt


On Thu, Jan 9, 2014 at 4:29 PM, Chris Warburton

Post by Pavel Bažant

Post by Pavel Bažant
I am developing an evolutionary simulation called Evoversum. An

interesting

Post by Pavel Bažant
thing I noticed on multiple occasions while developing the program was

the

Post by Pavel Bažant
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

Reminds me of a video I saw on YouTube (can't find it at the moment)
where a genetic algorithm evolved creatures (collections of sticks,
joints and motors) in a physics simulation. The goal was to move the
furthest distance, in the hope that they'd walk/crawl/etc. In fact, one
of them triggers a bug in the simulation which causes it to explode,
sending its body parts flying in all directions. This immediately
dominates the population, so all the creatures start exploding.
1) Evolutionary methods are good at finding bugs
2) Your fitness function is not selecting for what you think it is ;)
Cheers,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
Best regards,

/Robert Feldt
--
Tech. Dr. (PhD), Professor of Software Engineering
Blekinge Institute of Technology, Software Engineering Research Lab, and
Chalmers, Software Engineering Dept
Explanea.com - Igniting your Software innovation
robert.feldt (a) bth.se or robert.feldt (a) chalmers.se or
robert.feldt (a) gmail.com
Mobile phone: [phone]
http://www.robertfeldt.net <http://www.cse.chalmers.se/~feldt>

[Chris Warburton]

It wasn't one of Sims', it's here

According to the voiceover there's not as much variation allowed as I
remember. Still amusing though :)

Post by Robert Feldt
I don't think I remember the "exploding myself" strategy from Karl Sims
http://youtu.be/JBgG_VSP7f8
Do you remember where you saw that, Chris?
Cheers,
Robert Feldt

Post by Pavel Bažant

Post by Pavel Bažant
I am developing an evolutionary simulation called Evoversum. An

interesting

Post by Pavel Bažant
thing I noticed on multiple occasions while developing the program was

the

Post by Pavel Bažant
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

Reminds me of a video I saw on YouTube (can't find it at the moment)
where a genetic algorithm evolved creatures (collections of sticks,
joints and motors) in a physics simulation. The goal was to move the
furthest distance, in the hope that they'd walk/crawl/etc. In fact, one
of them triggers a bug in the simulation which causes it to explode,
sending its body parts flying in all directions. This immediately
dominates the population, so all the creatures start exploding.
1) Evolutionary methods are good at finding bugs
2) Your fitness function is not selecting for what you think it is ;)
Cheers,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
Best regards,
/Robert Feldt
--
Tech. Dr. (PhD), Professor of Software Engineering
Blekinge Institute of Technology, Software Engineering Research Lab, and
Chalmers, Software Engineering Dept
Explanea.com - Igniting your Software innovation
robert.feldt (a) bth.se or robert.feldt (a) chalmers.se or
robert.feldt (a) gmail.com
Mobile phone: [phone]
http://www.robertfeldt.net <http://www.cse.chalmers.se/~feldt>
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

[Robert Feldt]

Thanks a lot for that link, Chris!

In 1998 I used Genetic Programming to evolve controllers for an embedded
system (aircraft arrestment) and was using a simulator of the system for
the evolutionary searches. I also found several bugs in the simulator which
had already been in heavy use by engineers for several years. Unfortunately
I did not analyze these bugs in any detail in the paper and don't remember
all the details any longer:

http://www.robertfeldt.net/publications/feldt_1998_diverse_sw_with_gp.html

I have been getting back to search-based software testing recently and
during 2014 we will release automated testing tools (an extension of our
GödelTest approach:
http://www.robertfeldt.net/publications/feldt_2013_godeltest.html ) that
use different search approaches (some evolutionary, other deterministic)
to search for test data and test case for more standard software.

Cheers,

Robert

Post by Chris Warburton
It wasn't one of Sims', it's here
http://youtu.be/STkfUZtR-Vs
According to the voiceover there's not as much variation allowed as I
remember. Still amusing though :)

Post by Robert Feldt
I don't think I remember the "exploding myself" strategy from Karl Sims
http://youtu.be/JBgG_VSP7f8
Do you remember where you saw that, Chris?
Cheers,
Robert Feldt
On Thu, Jan 9, 2014 at 4:29 PM, Chris Warburton <

Post by Pavel Bažant

Post by Pavel Bažant
I am developing an evolutionary simulation called Evoversum. An

interesting

Post by Pavel Bažant
thing I noticed on multiple occasions while developing the program was

the

Post by Pavel Bažant
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

Reminds me of a video I saw on YouTube (can't find it at the moment)
where a genetic algorithm evolved creatures (collections of sticks,
joints and motors) in a physics simulation. The goal was to move the
furthest distance, in the hope that they'd walk/crawl/etc. In fact, one
of them triggers a bug in the simulation which causes it to explode,
sending its body parts flying in all directions. This immediately
dominates the population, so all the creatures start exploding.
1) Evolutionary methods are good at finding bugs
2) Your fitness function is not selecting for what you think it is ;)
Cheers,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
Best regards,
/Robert Feldt
--
Tech. Dr. (PhD), Professor of Software Engineering
Blekinge Institute of Technology, Software Engineering Research Lab, and
Chalmers, Software Engineering Dept
Explanea.com - Igniting your Software innovation
robert.feldt (a) bth.se or robert.feldt (a) chalmers.se or
robert.feldt (a) gmail.com
Mobile phone: [phone]
http://www.robertfeldt.net <http://www.cse.chalmers.se/~feldt>
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
Best regards,

/Robert Feldt
--
Tech. Dr. (PhD), Professor of Software Engineering
Blekinge Institute of Technology, Software Engineering Research Lab, and
Chalmers, Software Engineering Dept
Explanea.com - Igniting your Software innovation
robert.feldt (a) bth.se or robert.feldt (a) chalmers.se or
robert.feldt (a) gmail.com
Mobile phone: [phone]
http://www.robertfeldt.net <http://www.cse.chalmers.se/~feldt>

[Christopher Bratlien]

Hello,

I stumbled upon this yesterday. It seems relevant to this thread.

*Flexible Muscle-Based Locomotion for Bipedal Creatures*

[video] http://vimeo.com/79098420

[paper]
http://www.cs.ubc.ca/~van/papers/2013-TOG-MuscleBasedBipeds/2013-TOG-MuscleBasedBipeds.pdf

Post by Robert Feldt
Thanks a lot for that link, Chris!
In 1998 I used Genetic Programming to evolve controllers for an embedded
system (aircraft arrestment) and was using a simulator of the system for
the evolutionary searches. I also found several bugs in the simulator which
had already been in heavy use by engineers for several years. Unfortunately
I did not analyze these bugs in any detail in the paper and don't remember
http://www.robertfeldt.net/publications/feldt_1998_diverse_sw_with_gp.html
I have been getting back to search-based software testing recently and
during 2014 we will release automated testing tools (an extension of our
http://www.robertfeldt.net/publications/feldt_2013_godeltest.html ) that
use different search approaches (some evolutionary, other deterministic)
to search for test data and test case for more standard software.
Cheers,
Robert
On Fri, Jan 10, 2014 at 12:51 AM, Chris Warburton <

Post by Chris Warburton
It wasn't one of Sims', it's here
http://youtu.be/STkfUZtR-Vs
According to the voiceover there's not as much variation allowed as I
remember. Still amusing though :)

Post by Robert Feldt
I don't think I remember the "exploding myself" strategy from Karl Sims
http://youtu.be/JBgG_VSP7f8
Do you remember where you saw that, Chris?
Cheers,
Robert Feldt
On Thu, Jan 9, 2014 at 4:29 PM, Chris Warburton <

Post by Pavel Bažant

Post by Pavel Bažant
I am developing an evolutionary simulation called Evoversum. An

interesting

Post by Pavel Bažant
thing I noticed on multiple occasions while developing the program

was the

Post by Pavel Bažant
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

Reminds me of a video I saw on YouTube (can't find it at the moment)
where a genetic algorithm evolved creatures (collections of sticks,
joints and motors) in a physics simulation. The goal was to move the
furthest distance, in the hope that they'd walk/crawl/etc. In fact, one
of them triggers a bug in the simulation which causes it to explode,
sending its body parts flying in all directions. This immediately
dominates the population, so all the creatures start exploding.
1) Evolutionary methods are good at finding bugs
2) Your fitness function is not selecting for what you think it is ;)
Cheers,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
Best regards,
/Robert Feldt
--
Tech. Dr. (PhD), Professor of Software Engineering
Blekinge Institute of Technology, Software Engineering Research Lab, and
Chalmers, Software Engineering Dept
Explanea.com - Igniting your Software innovation
robert.feldt (a) bth.se or robert.feldt (a) chalmers.se or
robert.feldt (a) gmail.com
Mobile phone: [phone]
http://www.robertfeldt.net <http://www.cse.chalmers.se/~feldt>
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
Best regards,
/Robert Feldt
--
Tech. Dr. (PhD), Professor of Software Engineering
Blekinge Institute of Technology, Software Engineering Research Lab, and
Chalmers, Software Engineering Dept
Explanea.com - Igniting your Software innovation
robert.feldt (a) bth.se or robert.feldt (a) chalmers.se or
robert.feldt (a) gmail.com
Mobile phone: [phone]
http://www.robertfeldt.net <http://www.cse.chalmers.se/~feldt>
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

[John Carlson]

I'm not sure why evolving explosions is a bug. You just want to make sure
you survive afterwards.

Post by Pavel Bažant

Post by Pavel Bažant
I am developing an evolutionary simulation called Evoversum. An

interesting

Post by Pavel Bažant
thing I noticed on multiple occasions while developing the program was

the

Post by Pavel Bažant
fact that it tends to "debug itself". The simulated organisms, as a
consequence of the Darwinian evolution taking place, are very quick to
trigger all sorts of bugs, sometimes to their advantage, sometimes
triggering undefined behavior, destroying their own world. So it seems
likely that this effect is applicable in other software domains, too.

Reminds me of a video I saw on YouTube (can't find it at the moment)
where a genetic algorithm evolved creatures (collections of sticks,
joints and motors) in a physics simulation. The goal was to move the
furthest distance, in the hope that they'd walk/crawl/etc. In fact, one
of them triggers a bug in the simulation which causes it to explode,
sending its body parts flying in all directions. This immediately
dominates the population, so all the creatures start exploding.
1) Evolutionary methods are good at finding bugs
2) Your fitness function is not selecting for what you think it is ;)
Cheers,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

[Chris Warburton]

Post by John Carlson
I'm not sure why evolving explosions is a bug. You just want to make sure
you survive afterwards.

It's a great evolutionary strategy. There's no need to survive either;
the situation is basically "you will be killed in a few seconds, but the
quicker you move in that time, the greater the chance that I'll clone
you". Exploding doesn't affect their reproduction.

The bug(s) is in the physics engine. It looks like it's naively
approximating Newtonian mechanics by integrating with a finite, constant
dt (rather than infinitesimal dt). This causes large errors in the
position of the creatures legs if they're moved fast enough, allowing
them to self-intersect.

The collision-handling code is then moving these intersecting body parts
apart, which is effectively applying a huge force to them. These forces
are unbalanced, breaking Newton's third law, so there is a net force on
the creatures, which lets them levitate.

If the collision-handler pushes apart one intersection but causes
another, the forces will build up. This rebounding allows the
collision-handler's hack to dominate the simulation and cause the
creatures to explode.

Cheers,
Chris

[John Carlson]

What I was thinking was evolving space travel. If it is a physics engine,
could it evolve warp drive? Rockets?

Post by Chris Warburton

Post by John Carlson
I'm not sure why evolving explosions is a bug. You just want to make

sure

Post by John Carlson
you survive afterwards.

It's a great evolutionary strategy. There's no need to survive either;
the situation is basically "you will be killed in a few seconds, but the
quicker you move in that time, the greater the chance that I'll clone
you". Exploding doesn't affect their reproduction.
The bug(s) is in the physics engine. It looks like it's naively
approximating Newtonian mechanics by integrating with a finite, constant
dt (rather than infinitesimal dt). This causes large errors in the
position of the creatures legs if they're moved fast enough, allowing
them to self-intersect.
The collision-handling code is then moving these intersecting body parts
apart, which is effectively applying a huge force to them. These forces
are unbalanced, breaking Newton's third law, so there is a net force on
the creatures, which lets them levitate.
If the collision-handler pushes apart one intersection but causes
another, the forces will build up. This rebounding allows the
collision-handler's hack to dominate the simulation and cause the
creatures to explode.
Cheers,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

[Martin McClure]

Post by John Carlson
What I was thinking was evolving space travel. If it is a physics
engine, could it evolve warp drive? Rockets?

It'd be fun to see rockets evolve. Should be possible; we understand the
physics involved. Warp drive -- well, if we simulate a universe in which
this works, it should be able to evolve. Or teleportation, etc...

There was a science fiction story I read years ago which involved plants
which had evolved teleportation. This proved so advantageous in
spreading their seeds to optimum locations, or having one part of the
plant located where it got sun and another part of the same plant
located at a good source of water , and so on, that most of the plant
life on this fictional planet ended up with some kind of ability to
teleport. (If anyone recognizes this story, and knows the title and
author, let me know -- I've long forgotten both)

Regards,

-Martin

[Chris Warburton]

Post by Martin McClure

Post by John Carlson
What I was thinking was evolving space travel. If it is a physics
engine, could it evolve warp drive? Rockets?

It'd be fun to see rockets evolve. Should be possible; we understand the
physics involved. Warp drive -- well, if we simulate a universe in which
this works, it should be able to evolve. Or teleportation, etc...

Even with a bug-free, sophisticated-enough Physics simulation,
completely open-ended evolution is incredibly inefficient. This issue
comes up in AI circles, where the question is 'we know that intelligence
can evolve, since ours did, so why not evolve our programs the same
way?'.

The problem is that we took billions of years to emerge from a
planet-wide search algorithm; and even so, we're still just a random
anomaly (evolution isn't 'trying' to make intelligence). Simulating this
would take so many resources that you'd be better off simulating a
virtual human brain atom by atom, with enough resources to spare that
you could increase its neuron count and processing speed by many orders
of magnitude.

A similar argument would apply here; if you want advanced technology,
the most efficient way to get it is to spend your resources thinking
about the problem. If you have enough computing capacity to simulate its
evolution, you'd be better off using it to simulate an army of
super-scientists.

Evolution can be a good approach to very targeted problems with a few
degrees of freedom, but it's terrible at anything else. It's only
managed to solve the problems of life via the law of large numbers.

Regards,
Chris

[John Carlson]

If google is solving problems with super-scientists, why can't they explain
how their AI works anymore? It would seem like AI is beyond humans now. I
think we're too focused on DNA as a means of evolution, and there may be
better ways of evolving AI the computer.

Post by Chris Warburton

Post by Martin McClure

Post by John Carlson
What I was thinking was evolving space travel. If it is a physics
engine, could it evolve warp drive? Rockets?

It'd be fun to see rockets evolve. Should be possible; we understand the
physics involved. Warp drive -- well, if we simulate a universe in which
this works, it should be able to evolve. Or teleportation, etc...

Even with a bug-free, sophisticated-enough Physics simulation,
completely open-ended evolution is incredibly inefficient. This issue
comes up in AI circles, where the question is 'we know that intelligence
can evolve, since ours did, so why not evolve our programs the same
way?'.
The problem is that we took billions of years to emerge from a
planet-wide search algorithm; and even so, we're still just a random
anomaly (evolution isn't 'trying' to make intelligence). Simulating this
would take so many resources that you'd be better off simulating a
virtual human brain atom by atom, with enough resources to spare that
you could increase its neuron count and processing speed by many orders
of magnitude.
A similar argument would apply here; if you want advanced technology,
the most efficient way to get it is to spend your resources thinking
about the problem. If you have enough computing capacity to simulate its
evolution, you'd be better off using it to simulate an army of
super-scientists.
Evolution can be a good approach to very targeted problems with a few
degrees of freedom, but it's terrible at anything else. It's only
managed to solve the problems of life via the law of large numbers.
Regards,
Chris
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc