In this session we will be looking at some more advanced components and methods of using grasshopper, principally focussing on Galapagos, Grasshopper’s built-in genetic algrithm solver. Along the way, we’ll also be examining Grasshopper’s metaball component and means of flow control – the Grasshopper equivalent of ‘if statements’ in coding.
Example 7: Galapagos
Galapagos is best used to solve problems to which the optimal solution is not immediately obvious. In this example the problem which we are going to try and solve is to examine a field of points and attempt to enclose as many of those points as possible within a closed curve of a fixed maximum length. If you want a physical analog – imagine that each point is a pin and we have a loop of string that we want to fit around as many as we can.
The first step is to obtain our set of points – you can either use the one in the example file provided or create your own using the Points command and clicking lots.
In Grasshopper we will reference in these points in the usual way – add a Point parameter component, right click and select ‘Set multiple points’.
Now we want some way of drawing a closed cuve through those points. A quick way (albeit probably not an ideal one) of generating an organic-looking closed curve in Grasshopper is through the Metaball components.
Metaballs are a form of geometry known as Implicit Surfaces, so-called because rather than rather than being explicitly defined by a particular mathematical equation, they are instead implicitly defined as isosurfaces (i.e. contours) through some scalar energy field.
The centre of each metaball might be considered an energy source with a falloff in the level of energy with distance from the point. The surfaces of the metaballs then represent all of the points within that energy field with a particular energy value.
Metaballs can be found in a variety of other modelling packages, where they are most commonly used to generate ‘gooey blobby things’ as the combination of energy fields tends to result in metaballs in close proximity bleeding into one another.
If you are familiar with metaballs from elsewhere, or even if you’re not, the Grasshopper implementation of them might seem a little weird. Firstly, metaballs in Grasshopper are not actually balls at all, or even 3d, or even (despite being found on the Mesh tab) meshes. Instead, Grasshoppper currently only provides components to generate curves which represent flat 2d slices through a set of metaballs. If you did want to create 3d metaballs from these you would need to generate a number of these on different planes and then construct the 3d form yourself.
Nonetheless, for what we want right now only a flat curve is required, so the components provided should be adequate.
Firstly, we want to be able to control the source point of each metaball. More to the point, we want Galapagos to be able to control the source point of each metaball, and that means that we need to set up sliders to control the x and y coordinates of each point, since Galapagos can only exert control over slider (and, as we’ll see in a second, slider-like) components.
We could just use our old friend Number Slider for this, but as we will be creating multiple source points with multiple x and y coordinates, instead we will use the Gene Pool component. Grab one from Params/Util box and add it to the canvas.
A Gene Pool is basically a bunch of Number Sliders all bolted together into one component. Rather than giving us a single number, they will give us a list of numbers with each number being controlled by a different slider in the pool. We could use multiple Number Sliders for exactly the same purpose, but Gene Pools have the advantage of being slightly easier to set up.
Double-click on the Gene Pool to open the editor. The Minimum and Maximum fields work the same way as with Number Sliders, only they affect all of the sliders in the pool. We want our range of positions to encompass all of our points, so enter some suitable values based on the maximum and mimimum extents of your point field on the x and y axes. The ‘Gene Count’ is the number of sliders to be contained within the pool. Set this to 3.
This first Gene Pool will represent the x-coordinates of our, source points. Create a copy of it to represent the y-coordinates and then plug them both into the relevent inputs of a Construct Point component (Vector/Point). Adjust the minimum and maximum extents of the Gene Pools if necessary so that the source points can move anywhere within our point field.
Now add a Metaball(t) Custom component from Mesh/Triangulation to the canvas. Plug the output of our Construct Point component into P. Add another Gene Pool with a Gene Count of 3 and plug it into C – this will control the charge of each point source. Try moving the source points around and changing the charge values to see how the metaballs join together and come apart.
This now generates the curve(s) which we are going to try to fit around as many points as possible – this is as complicated as our actual geometry is going to get this time around. However, before we can use Galapagos we need to get some kind of numeric feedback about the current arrangement. Specifically, we need to know the number of points inside the curve and also the length of the curve.
To determine the number of points inside the curve we will use the Point In Curves component from Curve/Analysis. Note the s – we could conceivably have multiple curves coming out of our Metaball component, so the alternative, Point In Curve component will not give us what we want. Plug our inital point field into P and our Metaball curve into C. The R output will return an integer which depends on whether each point is outside the curves (0), inside the curves (2) or directly on one of the curve (1 – rather unlikely in this setup!). Using this, we want to count all of the points which are inside, i.e. all of the ones which give us an output of 2.
If we were scripting rather than using Grasshopper, we could use an ‘if statement’ to check whether a particular condition was met and then take action accordingly. For example, in C#:
if (R == 2)
//R is 2, do something
//R is not 2, do something else
Grasshopper doesn’t have if statements, but we can do something very similar by combining two different components – one which tests a particular conditional (i.e. is R equal to 2) to give us either a true or false and another which directs the flow of data accordingly.
Feed the R output into a new Equality component (Maths/Operators) and set the other input to the number 2. This will perform our conditional check and then return either true or false, depending on whether the condition is satisfied. In turn, feed that output from = into the P input of a Dispatch component. Plug our original point field into L. The Dispatch component will take in a a list of objects into L and a list of boolean values (i.e. true or false) into P. If the value in P is true, then the matched item from L will be sent to the A output, else if it is false it will instead be sent to the B output. This makes this a very useful component for sorting out objects into two lists given particular requirements. If you plug a new Point parameter component into A and select it then you should see that it is giving us all of the points in our field which lie inside the curve (while B is all of the points that lie on or outside the curve).
For our purposes, all we really care about is how many of them there are – use a List Length component from Sets/List to count them.
Next, add a Galapagos component to the canvas from Params/Util. The Galapagos component looks a little weird, which is fitting considering it works in a very different way to most Grasshopper components. It has a nodule on the left hand side called ‘Genome’. The ‘Genome’ is the inputs which we will allow Galapagos to control. Drag a wire out from this nodule and connect it to the first of our Gene Pools. Hold down the shift key (exactly as if we were plugging multiple outputs to the same input) and also connect the remaining Gene Pools. This lets Galapagos know that it has free reign to modify those inputs. Any other input components which we do not connect in this way will remain constant at their current value when Galapagos is run.
On the bottom of Galapagos is another nodule marked ‘Fitness’. This is where we connect a single, numeric value which tells Galapagos how good (or not) the current solution is. Add a new Number parameter component (Params/Primitive) and drag a connector from the fitness nodule to this new component. Whatever we plug into this Number component will now be taken as Galapagos’s fitness score.
We now have all that we need to run Galapagos – if you like you can jump ahead to the Galapagos section below and run Galapagos using just the number of points as our fitness value. However, we are unlikely to get very good results out at this stage – Galapagos will simply try to enclose as many points as it possibly can (and may struggle to do that, since the problem is fairly underconstrained at this point).
This one number alone however does not give us the full picture – we also care about how long the curve is. To be specific; we want to tell Galapagos not to let the curve go longer than a certain length. To do this we need to check what the cumulative curve length is, check it against some limit and if it is exceeded, apply a penalty to the fitness score to let galapagos know that this is not an evolutionary path it wants to go down.
Plug a Length component (Curve/Analysis) into the back of the metaball component, then add a Mass Addition component (Maths/Operators) to the back of that. This will take care of the cases where we have more than one curve coming out of the metaball component and will give us the total length of all curves.
Now add a Number Slider to control the length limit and use a Larger Than component (Maths/Operators) to compare it to the actual length. This will return true if the length exceeds the limit. In this case we want to subtract a penalty score from our fitness, or alternatively if it is false we do not want to subtract anything. Add a Pick ‘n’ Choose component from Sets/List. This component is a close cousin of the Dispatch component we used earlier but works in the opposite way – rather than taking in one input and splitting it between two outputs based on a pattern, the Pick ‘n’ Choose component takes in two inputs and returns one of them based on a pattern. Plug the Larger Than output into P (this asks for an integer which defines the input number to take, but plugging in a boolean will work as well, as false will convert to 0 and true will convert to 1). Plug the number o into the 0 input (here typed into a Panel). Into 1 we need to plug our penalty value – we will use the cumulative curve length itself so that the penalty will increase the greater the amount by which this exceeds the limit.
Finally, use a Subtraction component (Maths/Operators) to subtract the result of the Pick ‘n’ Choose component from the fitness score. By manually playing around with the Gene Pool sliders, you should see that so long as the curve length is lower than the limit the fitness score will be the number of points contained within. If the curve length exceeds the limit then the score will be significantly decreased. The maximum score possible will be for a situation that encloses as many points as possible but which does not exceed the specified limit and it is this situation that we have thus instructed Galapagos to find. The key to using Galapagos effectively is to contrive some kind of ‘scoring system’ such as this where our ideal outcome will score highest (and other options will score progressively worse the further away from this ideal they are).
Galapagos is a ‘genetic’ or ‘evolutionary’ solver, so called because it mimics the process of natural selection and evolution in order to produce increasingly ‘fit’ solutions to a problem. In this analogy, we might think of each particular arrangement option as an individual animal in a population, with the input parameters used to generate it being equivalent to that animal’s genes.
Initially, a completely random set of these options will be generated and assessed for fitness. Of this initial group, a certain percentage of the best options (i.e. those with the highest fitness scores) will be retained and the rest discarded, to be replaced by new options created by randomly combining the input parameters of the surviving elite. This process is repeated over and over again, with the fittest members of the population surviving to ‘breed’ with one another and create new options, which inherit the beneficial characteristics of their parents. Over time, the worst combinations of parameters are weeded out and the best have their parameters combined to produce increasingly more optimal solutions.
In brief; Galapagos is basically numbers having sex with each other.
(Galapagos also contains another kind of optimisation engine which uses simulated annealing, but I’m only going to cover the genetic algorithm one here.)
To use galapagos to optimise your input parameters, double-click on the Galapagos component. This will open the following form:
The important options here are:
Fitness: Whether galagapos should try to make the fitness scores as high as possible or as low as possible. Which option you want will depend on how you’ve set up your fitness score. In our case, higher is better, so we want ‘Maximize’.
Threshold: You can use this to set a target fitness score that you want Galapagos to reach. Once it reaches that score, it will stop and won’t try to optimise any further. It’s usually best to leave this blank so that you get the best possible solution you can.
Runtime Limit: Lets you set a maximum duration for Galapagos to run before it gives up.
Max. Stagnant: This is the number of generations that Galapagos will continue to run after it has found the last best option before it will give up.
Population: The number of options to include in each generation. This option is very important – the higher it is the longer the solver will take to run, but with low numbers you run the risk of not having enough different options being tested to make sure that you are finding the best ones, so only reduce this when you have a definition that takes a long time to generate each option.
Initial Boost: This is the number by which the population will be multiplied for the very first run. This ensures a good spread of initial options.
Maintain: The percentage of best options to keep from each generation.
Inbreeding: The percentage of options in each generation which will be generated from combining the best options from the last generation. The remainder will be randomly generated.
Once you’re happy with these settings, click onto the ‘Solvers’ tab. To run the optimisation, click on ‘Start Solver’ – however if you want to see what is going on step by step it’s a good idea to click the option ‘Display all options in the Rhino viewport’ on the right hand side of the top bar:
When the solution starts running you should see the metaball curves start to fly everywhere and then gradually settle down into an optimum arrangement. In the Galapagos window itself, you should also see a bunch of confusing-looking diagrams begin to populate themselves. Here is what it all means:
1. Solver option – switch between the genetic and annealing solvers.2. Start and stop solver.
3. Rhino update controls – determines when the main Rhino viewport will update its display. Having it set to show every option is more fun, but also slows things down slightly.
4. The main fitness graph. The yellow zone shows the range of fitness values in each generation.
5. These little white markers indicate when a new optimum option has been found.
6. Options for the number of genomes to display.
7. Mutation button. You can use this to manually add new random combinations into the current population. Use this when galapagos looks like it’s got ‘stuck’ investing a particular arrangement and is missing a possible optimum elsewhere.
8. The current population – clusters of points represent options which are similar to one another.
9. The current range of parameter values. Each point on this graph represents a different Gene Pool/Slider value.
10. A list of the best-scoring options. Select one and hit ‘Reinstate’ to set the input parameters back to those values.
When the solver has finished you should find that you have a curve which is probably just below the maximum length limit and which encloses as many of the points as it reasonably can.
- Everything Galapagos does is random. Because of this it’s possible for it to completely miss the ‘evolutionary path’ where the optimum arrangement can be found. Using a high enough population (and especially initial boost value) can help with this, with the occasional judicious use of the mutation button to give it a little nudge every now and then. Even so, it’s common to run the solver twice and get two slightly different answers out.
- Compared to other optimisation routines, genetic algorithms have the advantage of being extremely flexible, easy to apply to multiple parameters and occasionally producing results which are surprising. They have the disadvantage that they are extremely inefficient and need a lot of iterations to produce good results and as noted above can fail to find an exact optimum.
- The minimum and maximum values of sliders that you let Galapagos control are important because they define the range of values Galapagos can assign to that parameter. Make this range large enough to contain all reasonable values but not so large that Galapagos wastes time trying extreme values.
- Because Galapagos can potentially come up with any possible combination of input parameters, your definition will need to be robust enough that it will work for any possible combination of input parameters.
- Beware geometric bias. Certain types of option can gain an ‘unfair’ advantage in the selection process because it is more likely that the definition will produce them with a random input set; hence there will be more of that kind of arrangement produced and they can potentially overwhelm better, but rarer, options. In the example above there is a geometric bias towards curves centered around the middle of the possible range, because of the way that Metaballs combine. This will be more pronounced the greater the number of metaballs that you use.
You can download the example files for this session here:
AADRL 2013 – Example 7
As a further example of Galapagos in use, here is a video where I use it in conjunction with my own structrual interoperability plugin, Salamander, to structurally optimise a truss: