# Galapagos to minimize mesh/surface deviation

Hello everyone,

I made a mesh from a double curved surface. The edge lengths of the mesh are varying lengths of 50, 52, 54,… with a factor 2 inbetween. I can calculate the deviation between every mesh point and the initial surface. I want to minimize the maximum deviation. By changing the measurements of the surface I can do this. However it takes a lot of time to find the surface with the lowest maximum deviation. So I want to use Galapagos for this. As fitness I take the maximum deviation and as genome I take three sliders that change the measurements of the surface. But it doesn’t work. And the solving doesn’t stop.

Thanks

Attachement:
Discrete_triangle_mesh_galapagos.gh (34.2 KB)

Discrete_triangle_mesh_galapagos (2).gh (26.8 KB)
I believe you have to change your solver and always flatten the goals. Let me know if this one works.

1 Like

Thanks @mahanmotamedi1991! I think it works now.

Hi Robin,

I had a go at developing a Galapagos solution for your problem. I’m not sure if that was in relation to your previous post on this, or this new one you’ve created.

The process works by Galapagos being able to select either the multiple of 2 higher or lower than the actual value. So if a length measures 49.3mm initially, the solver will pick between a 48mm pole or a 50mm pole. I did originally let the solver pick any multiple of 2, however this was too broad a problem and it didn’t converge very well. The fitness is the summation of all the individual deviations from the original point. Using this, I was able to get a lower overall deviation from the original points than kangaroo did, however the Galapagos solution needs to run for some time (10 minutes or so) to beat Kangaroo which gets you its solution within a few milliseconds.

The method allows you to pick between optimising for minimum overall distance between the start positions and final positions, or between final positions and the original surface. I think the first option is what you are after. The second option does result in a lower overall deviation from the surface, however there isn’t anything to tie the final position to the initial position, so the grid may end up being a little less uniformly triangular (however it does at least more closely match the surface).

The overall problem is in trying to replicate a surface with a predefined distance between points on that surface, so you will never get perfect solution, unless by pure circumstance the surface is already at those positions in the first place.

Discrete_triangle_mesh_galapagos.gh (28.3 KB)

Hello Matt,

Thanks a lot! That’s a good solution too. Yes, it’s more or less the same as the other post I created. But this is with a double curved wall and the other is with a double curved arc. The goal is to create a triangle mesh mapped on a given surface only using lengths of 480, 500, 520, 540, 560, 580, 600 or 620 mm.

I first took the maximum deviation to minimize, but your method to pick the overall deviation gives a better result indeed!

The thing is I also have constraints for the mesh. The mesh has to be fixed to the ground xy plane. Also the length of 3913 mm and width of 978 mm can’t be changed. I added a new grasshopper file with the exact measurements of the initial double curved surface and the constraints (it’s now in mm instead of cm). I also added the slider to change the height of the initial surface to Galpagos. This is because the height doesn’t need to be fixed and can move a little bit. However when I add those constraints Galapagos runs very slow and doesn’t give good results. Is it possible for Galapgos to work with these added constraints or is it too much to handle for Galapagos?

1 Like

I don’t think how you set up Galapagos can give any good output.
Those are 130 0/1 sliders, that’s 2^130 , 1.36e39 different combinations!
No, that can’t be useful.

Imagine yourself, blind, switching on/off 130 switches. Those switches control, through an “unknown logic”, a number. And you want to maximize/minimize that number.
You would go mad in a minute!

Instead, controlling 3 analogical sliders, you can imagine it like the coordinates of a cubic volume, where you search the “best spot” inside the cube.
It make much more sense and it would make the search more intuitive!

Galapagos is no better than a human,actually it is worse, but very very faster.

From my very limited experience using Galapagos, I’ve seen some nice result using 3-4 sliders controlling numbers with decimals.

Forget galapagos for this, kangaroo is the way!

See if this is any useful Discrete_triangle_mesh_galapagos_4.gh (46.2 KB)

3 Likes

I’ll have a look at your file today. First thought is that your solution likely wont be converging as you are changing the initial surface by adjusting the height as the process runs. How could it ever converge if you are literally changing the goalposts as the process runs?

I’d agree with @maje90 that Kangaroo is indeed a much more appropriate tool for finding a close approximation of the initial surface. However, I’m not sure it would ever give an answer whereby all the dimensions are locked to the required multiples of 20mm. Seeing as it is a force-based solver you’d never be able to guarantee achieving fixed dimensions EDIT - if you have conflicting constraints.

Also @RobinC , if you are going to be using Galapagos for these kind of applications, I’d recommend reading as much into how it works as you can. I found this really helpful when I first started, and find it helps me now when considering when to use it and how to set up my problem in an appropriate way. There are plenty of links to help topics within the Galapagos GH window itself.

Also I’m not sure what you mean by your additional constraints. What does the 978mm actually constrain? From what I can see, that relates to the depth of the surface, but how does that relate to the mesh you want to create? As for the 3913mm, I guess you want to create an initial facetted arc on the ground plane whereby all of the segments are a multiple of 20mm and all points have Z=0 coordinates?

I think you are misunderstanding how Kangaroo works.
It will solve constraint systems exactly when you give it constraints which do not conflict.

In the example Riccardo shared, and the ones I posted in the other thread about this, there are other goals used to guide the solution to one close to the target surface, which do prevent an exact solution to the length constraints while they are active but these goals are then reduced to zero at the end to get the exact solution (see the highlighted slider in the definition).

Also, to be accurate K2 is no longer force-based, but rather projection based. Even the old force-based approach could converge to give exact solutions for non conflicting forces though - it would just take much longer (though still nowhere near as long as it would take trying to solve a system like this to the same level of precision only with a GA, which would take millennia, for the combinatorial reasons described above).

3 Likes

This does seem like the sort of problem though where some sort of hybrid optimisation technique might be suitable. So one method for choosing between the discrete options for the lengths, followed by a relaxation to see how close it can get to the target surface while keeping these lengths.
I don’t know what the best tools currently available in Grasshopper are for tackling integer programming problems.

The length of 3913 mm and width (or depth) of 978 mm have to be fixed and the bottom of the mesh has to be fixed to the ground xy plane. The 3913 mm is constraints by fixing the points where x = 0 and x 3913 in the x direction. And the 978 mm is constraint by fixing the points where y = 0 and y = 978 in the y direction. In real live it’s a wall that has to be placed inbetween something, so I need to have those constraints.

Thanks! I just used it to find the optimal height (2730 mm) which gives the mesh with the lowest deviation.

Apologies if my explanation wasn’t super clear - I was referring to the problem at hand, where we do have conflicting constraints (at least initially). I know how Kangaroo works (granted nowhere near as well as you do!), I just hadn’t considered the approach you and others have mentioned whereby the initial constraints are in conflict, and then one is relaxed until zero so that the conflict no longer exists.

The hybrid solution you suggest is essentially the method I’m testing out - using Galapagos to select an initial set of curve lengths, and then using Kangaroo to pull those curves to the target surface. The are no doubt better ways, but this does at least give positive results (at least my first round did). Not sure how it will work with the additional restraints.

1 Like

In my solution there is a slider to set at 0, when that is 0 the only forces active are the “Length Snap” ones. So no conflicting forces

Put it at 0.9 > Reset kangaroo > slowly decrease to 0. It converge to perfect lengths in an instant to me…

1 Like

Sorry I hadn’t realised earlier that you were already using a hybrid approach.

I think it can be helpful here to distinguish between the hard constraints (which must be enforced exactly - in this case edge lengths being multiples of 20, and base points lying on a plane) and soft targets (which we want to minimise the distance from, but accept they will not be met completely, in this case points lying on the input surface).
Usually I recommend solving this with the approach above of reducing the strength of the soft targets to zero. As long as the hard constraints do not conflict with each other it should meet them.
However, this is currently hard to integrate inside another optimisation loop like Galapagos.

Perhaps I need to add something like a combination of the ‘soft&hard’ solver and the ‘zombie’ solver, that would let you separate constraints and soft targets, while also iterating to convergence without needing the reset button.

2 Likes