Gene list/galapagos simplification

Replies to This Discussion

Permalink Reply by Mateusz Zwierzycki on April 8, 2012 at 7:54am

This wont work. Read more here :

http://ieatbugsforbreakfast.wordpress.com/2011/07/31/on-getting-luc...

Permalink Reply by Mateusz Zwierzycki on April 8, 2012 at 11:32am

Even if you manage to do it all with gene list, you wont succeed with galapagos. Every slider is a dimension, as David made some math -> with 12 sliders/dimensions probability of finding "that" one combination is nearly 0 (of course with 1 try). You have about 100 (?) dimensions... its just impossible to do it well. Even with billions of random genotypes for 1st generation.

Its like 1:googol (10^100) to succeed. If youll try and run it on your pc, youll probably consume all the energy in universe, and it will take longer time than our universe will exist.

Sorry :(

EDIT : As David wrote in his post - every added dimension results with almost half of "success ratio". So as with one slider you have e.g. 1:2 ratio of success, with 100 sliders you have :

1:633825300114114700748351602688 (2^99) 

To somebody more familiar with math -> correct me if Iam wrong :)

Permalink Reply by Mateusz Zwierzycki on April 8, 2012 at 11:48am

Or more like 

1:1267650600228229401496703205376 (2^100)

Permalink Reply by David Rutten on April 8, 2012 at 12:05pm

Well, it becomes impossible to get anywhere near the correct answer during the first iteration. But that doesn't mean the answer cannot be found during subsequent iterations. As long as the fitness landscape slopes towards good answers, you'll get there reasonably fast.

During a recent lecture I solved a problem in real-time which had 10^300 unique states in less than 30 seconds.

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Permalink Reply by Mateusz Zwierzycki on April 8, 2012 at 12:23pm

"As long as the fitness landscape slopes towards good answers" 

From my own experience - I tried to place 4 points and remake manually made 3d curve - not even close ;/ (primary curve was also made with 4 points).

You can easily find a x^2 equation minimal value, and slider can have 2^300 unique states (lots of .0000, nearly .00(0) ;) ) 

Can you tell more about problem from your lecture ?

And about randomness - you use system.random class to generate first generation (and mutations) ?

I know that this class generates statistically good results, but when evaluating 2d space with uv coords you can see some patterns...this makes me think is there any better idea to generate random values ? (I know more-less how random class works)

Permalink Reply by David Rutten on April 8, 2012 at 1:42pm

The problem is a made up one, during a lecture it's important that the audience can see that a correct solution has been reached. In this case, a gene list with 50 sliders (0.0000 to 100.0000, so one-million-and-one possible values each, I round to one million from now on) is used to position 25 points on the XY plane. Then I optimize the positions so that the distance from each point to its two nearest neighbours equals a constant value.

 

Now, 50 sliders with 10⁶ values each equals a total of (10⁶)⁵⁰ (one million raised to the power fifty) which equals 10³⁰⁰ different possible unique slider permutations.

 

Of course, there are many different possible solutions that all satisfy the constraints. This is a woefully underconstrained problem because the 50-dimensional phase space has all sorts of lower dimensional 'filaments' in it that connect solutions with equal (optimal) fitness. But adding further constraints would make it very difficult to visually see that the solution found was indeed the best of all possible states.

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

Attachments:

• HighDimensionPhaseSpace.gh, 6 KB

Permalink Reply by Hannes Löschke on April 8, 2012 at 12:44pm

I'd be interested in that problem.

We had a similar discussion during the 2nd parametric workshop at HTWK-Leipzig. My point was/is: the stronger the relationship between input and output, and the less chaotic the relationship (fewer possible extrema), the faster you'll see convergence. (and the better it'll match what you might expect)

Question is: If there is a strong relationship, like force flow in a simple truss, why use galapagos at all? Setting up like 300 sliders to contol the position in a single span truss seems overkill to me, when you can calculate the line of minimal stress with one single formula.

I mean, if you make the truss really complex, you'll get more and more possible "optimal solitions" and Galapagos will randomly select just one. But then the probability to find "the one" solution decreases. If there were 300 random solutions to the truss and maybe one, that is symmetric, the chances to find a symmetric solution get pretty small. If symmetry was a key factor to the solution, you wouldn't need Galapagos to find out.

I'm not totally sure about this, though. Are there problems, that solve fast in Galapagos without any clear pure math solution?

Permalink Reply by Mateusz Zwierzycki on April 8, 2012 at 1:06pm

"Are there problems, that solve fast in Galapagos without any clear pure math solution?"

Yes, e.g. :

http://www.youtube.com/watch?v=eNa_kQ33In0&feature=plcp&con...

This one I made to have some fun, after all its really awesome (as for me). Depending on branch shape (input curve) leafs are different. "Effective area" is area not shadowed by other leaf. Now try to do it other way :)

Permalink Reply by David Rutten on April 8, 2012 at 1:54pm

"My point was/is: the stronger the relationship between input and output, and the less chaotic the relationship (fewer possible extrema), the faster you'll see convergence. (and the better it'll match what you might expect)"

Pretty much true. My wording would be somewhat different though. The less detail is generated by the fitness function —i.e. the smoother the fitness landscape— the faster a solver will converge. This is less true for the Annealing solver though as it is less hampered by noise in the fitness landscape.

The relationship between inputs and fitness is not important, it may be incredibly chaotic, the only place where you should avoid chaos is the fitness landscape itself.

"Question is: If there is a strong relationship, like force flow in a simple truss, why use galapagos at all?"

Absolutely. Galapagos supplies generic solvers, if you can get away with a specific solver, that is almost always a better approach. Specific solvers can be highly optimized for performance and they can also sometimes provide a guarantee of finding the best solution, two things which are not possible with Galapagos.

"I mean, if you make the truss really complex, you'll get more and more possible "optimal solitions" and Galapagos will randomly select just one."

This means you have an underconstrained problem. Constraintness is not related to dimensionality, you can have low dimensional problems that are under or overconstrained as well as high-dimensional problems. If however you do have an underconstrained problem —I call this "filament topology" in the fitness landscapes, as there are filaments that connect multiple states with identical (optimal) fitness— then indeed Galapagos will home in on an unpredictable solution, and quite possibly a different solution the next time it runs.

"Are there problems, that solve fast in Galapagos without any clear pure math solution?"

Yes. The only thing you need for Galapagos to quickly solve a problem is a fitness landscape that slopes towards the optimal solution. The more parts of your fitness landscape slope away from the ideal solution the longer it will take to find the best solution.

--

David Rutten

david@mcneel.com

Poprad, Slovakia