Galapagos Day 04

Minor changes to the interface. Lots of changes under the hood.

This image shows Galapagos trying to find the closest point on a surface. Of course dedicated algorithms can solve this problem in less than 2 milliseconds, but Galapagos managed to find a solution in about 10~12 generations (with 50 individuals per generation) that was quite close to the correct result. At 15 generations the exact answer was found.

I'm still amazed at how well the solver works given that it has no understanding whatsoever of the problem (it doesn't even know there is such a thing as spatial dimensions).

5 members like this

View Full Size

Tags:

Comment

You need to be a member of Grasshopper to add comments!

Comment by Mårten Nettelbladt on March 18, 2010 at 4:25pm: Cool!

Comment by Yukio Minobe on January 28, 2010 at 6:21am: yes, i forgot including that. as Annarita suggested properly, Frazer's work is still inspirational, and we can get his copy here.

Comment by Annarita Papeschi on January 28, 2010 at 5:38am: Carlo have a look at John Frazer's work. Evolutionary Architecture, the book. It will give you an idea of the potential of the tool. Great job David! As usual.

Comment by Yukio Minobe on January 24, 2010 at 1:35am: hello carlo,
actually, we can get hundreds of thousands of materials regarding genetic algorithms through the internet, so i'm afraid whether my contribution might be redundant, but i'll leave some useful references below.

*Introduction to Genetic Algorithms
*Genetic Algorithms in Plain English
*Genetic Algorithms by Daniel Shiffman
*Introduction to Genetic Algorithms
*Evolutionary Computation by Craig Reynolds
*Evolved Virtual Creatures by Karl Sims (legend...)

Comment by Olivier Suire on January 23, 2010 at 5:46am: Sounds like Monte Carlo with a twist.
I wanna try this !

Comment by David Rutten on January 23, 2010 at 2:14am: A Dedicated Algorithm which is designed to find the closest point on a surface can be said to "know" what it is doing. It has a clear "understanding" of what a surface is, the geometry, the topology, the mathematics behind it. Also, this algorithm can have certainty regarding a specific outcome; it will "know" that the solution it came up with is indeed the best possible one.

Galapagos is unaware of any kind of geometry. It doesn't know what points are, or lines, or distances, or surfaces. All it knows about is that genes can have different values and that each genome has a certain fitness. The fact that it manages to come up with the same solution as the dedicated algorithm I find somewhat surprising. Or maybe exhilarating would be a better word.

Thus, an Evolutionary Algorithm can be used to solve a much wider variety of problems than Dedicated Algorithms, but it typically takes a lot longer to get there.

There are limits to what Galapagos can theoretically solve, and almost certainly much tighter limits to what it can practically solve. Certain problem cannot be formulated in a way that allows some form of continuity between gene values and fitness values. These kind of problems are by definition beyond the reach of Evolutionary Algorithms. Typically such problems involve some kind of chaotic or fractal components, which cause very different outcomes for very similar inputs.

Comment by Jon Malkovich on January 23, 2010 at 1:14am: Hi David...
very amazing indeed.
What do you mean by "the solver...has no understanding whatsoever of the problem" ?

Comment by David Rutten on January 22, 2010 at 1:08pm: Galapagos is a dll with a (so far) very basic implementation of a generic Evolutionary Solver/Algorithm. I wrote it myself, but since it's a dll it needs to be run by another program. Right now Grasshopper is the only application which is aware of Galapagos, but it's thinkable other people might incorporate it once it has been released.

This Wikipedia article explains the basics. Essentially, the slider objects become the genes in the genome, and the entire Grasshopper network becomes the fitness-function.

So the way it works is basically:
1) Create a new founder population of N individuals, each of which has the sliders set at random locations.
2) Evaluate the fitness of all these individuals, and pick the fittest ones to populate the next generation.
3) Repeat (2)

There's a lot of technical details involved in the mechanism by which genomes are combined to create offspring, about the possible mutations that can occur, about which genomes get to become parents and about how mates are picked from the population, but that 3-step list is the basic gist of it.

Comment by Carlo Beltracchi on January 22, 2010 at 12:57pm: Hi David,
this tool seems to be something great! I'm trying to understand how it works.
I'm searching references on the web to understand what an "evolutionary solver" is, and if Galapagos is a stand alone software or a kind of plug in linked with GH.

Can anyone give me some hints?

As ever, thank you for your brilliant effort!