algorithmic modeling for Rhino
i was looking through some programming techniques used in design search and optimization, i was wondering if there are any grasshopper applications or samples to these types, techniques such as linear programming, heuristics, evolutionary (i think Galapagos would work for this one) or maybe we are doing them without recognize them ?
sorry, missed your post. There's quite a lot of stuff done on optimization and heuristics. Mostly you'll find small proof-of-concept java applets that run on websites showing off a specific algorithm. The other large bulk of work done is solver libraries. Microsoft has something called the Solver Foundation, but there are many more.
Galapagos is a bit of a goose, since it's a ready-to-use program that is not aimed at specific problems. Because of this it is very flexible, but also slower than most other solutions you'll find. But most other solutions will require a hefty integrative coding investment on your part.
If you're trying to solve a specific problem, and you're not afraid of semi-colons and curly brackets, then I suggest you try and hook into one of the available libraries out there.
but david what if we trying to build our own in Grasshopper
i usedto use python all the time to build customized scripts, but still very complicated when ity came to build our own script, for example , to build a script for evolutionary system , it is very hard to build all that classes which open at the same time and work together
is there is any way to have a grasshopper system to be able to build computing systems, or optimizing systems, our own using components rather than scripts
my wish was to know exactly what programming are we using when using grasshopper, is it integer programming, is it genetic algorithms, is it ....etc ... :)
You can link a solver with Grasshopper no problem. I did the same for Galapagos. Galapagos.dll is a stand-along library I wrote (it knows nothing of Rhino or Grasshopper or even 3D). Then GalapagosComponent.gha is the component library that exposes that solver within Grasshopper.
I can help you out with that part. The biggest question is, do you want your solver to run as part of the solution, or do you want it to sit on top of the solution (like Galapagos)?
what am looking for is to have it on top of the solution ,
the solution, lets say is trying to satisfy some constrainstss
then i want to compare between two heuristics or between evolutionary method and heuristic method to see which one is more consistent and reliable in solve the specific problem
what am really looking for is to have the ability to build optimization scripts using the grasshopper connection wires, for example, a python editor using wire connections rather than writing, building classes for a script using wiring ...etc, classes which work together, imagine if you want to build an evolutionary optimizer using grasshopper connections, connecting selection class, with mutation class... etc
> what programming are we using when using grasshopper
From this point of view, Galapagos might be considered an exception within Grasshopper, as it is state-based, as many looping constructs. This is also true for some other components, such as the data recorder, the value tracker and Hoopsnake.
thanks Giulio this is really clear
what i was trying to understand is the names of solutions, or optimizers
Galapagos currently runs an Evolutionary Solver. This is also often referred to as Genetic Algorithms. The two seem to be different, but for the life of me I've never been able to understand what this difference consists of.
An Evolutionary Solver/Genetic Algorithm is an implementation of Metaheuristics. Metaheuristics tend to be flexible solvers, applicable to a wide variety of problems, fairly easy to implement, but slow. Other examples of Metaheuristic algorithms would be Random Search, Scatter Search, Simulated Annealing and do on. These algorithms are often modelled on physical or biological processes.
Simulated Annealing for example simulates the physical process of annealing (who'd have thunk it), which is basically the slow cooling of a material which allows it to settle into a crystalline lattice, i.e. a low energy distribution of all the atoms. I'm currently adding an SA solver to Galapagos, and in fact just yesterday managed to get the first successful run: http://www.youtube.com/watch?v=VWtYLv-4oP0
Metaheuristics are especially useful for those cases where little is known about the problem ahead of time. If the problem search-space is mathematically well defined (differentiable, especially), then you can use more targeted algorithms such as the Newton-Raphson method, Pareto-search or Uphill search. You can still use these methods on non-differentiable search-spaces, but it involves sampling the local region to death to get an estimate of the differential. This can be a very costly enterprise, especially in high dimensional search-spaces. In a two-dimensional search-space you'll need 3 to get a lame estimate and 4 to get a halfway decent estimate and 8 to get a good estimate. In three-dimensional search space you already need 26 samples, and the number of samples grows exponentially with higher dimensions.
If you have a specific problem you're trying to solve, Metaheuristics are probably not the best solution, even though they may be easiest to program. Rhino uses something akin to Newton-Raphson for certain problems and that's fast enough to run in real-time.
Divide-and-Conquer algorithms are also quite popular. Sometimes they are called Binary-Search or Tree-Search algorithms as well. Their basic premise is to sample the search-space at a few intervals (but enough to capture the needed detail), then find two neighbours with promising values and sample again in between these two. Then repeat. Each new iteration typically doubles accuracy, which is great because then you only need ~30 ~40 iterations to get an answer as good as possible with double-precision floating point accuracy. However not all problems lend themselves well to this sort of search and in higher dimensions it starts getting slow with disconcerting alacrity.
About the difference between genetic algorithms and evolutionary algorithms:
if we take by example Genetic Programming, you could evolve an entire Grasshopper solution with GP(populations in GP are programs, often represented in tree or graph structures), while a genetic algorithm can only evolve data (like sliders).
One could say that Genetic Programming simulates behaviors evolution, while Genetic Algorithms only simulate aspects or phenotypes.
Thats why Koza used GP to optimize virtual ants looking for food in a maze, with a GA you could find good ants phenotype(number of legs, etc), with a GP you can find good ants behaviors (follow the left wall, drop pheromone etc).
I still don't see the difference. A program structure is data. Everything inside the computer is data if it's supposed to be there, or a hardware malfunction if it's not.
I'll admit there's a certain I-know-it-when-I-see-it difference here, but it sounds like a very graded set of definitions.
I see your point, in this case I think the 'I-know-when-I-see-it' difference would be a bit like working in grasshopper with or without tree structures.
Operating on a flat single list of data, or on a complex graph structure (data or program) offers vastly different possibilities and methods, even if they are ultimately both just series of 0 and 1 in a computer.
A little bit like atoms in a rock and in a mouse, just atoms, following same physical rules, but not quite organized the same (well its a grossly exagerated comparison).
As much as I'm concerned, GP provides much more variation than GA as it was explained by Systemiq. Besides the difference during crossover, the main advantage of GP is the evolutionary pressure on the phenotypes produced. I understand it's constantly in a certain variation. But in GA's case, the products get more and more similar features through the process, which means a static result.
In Paul Coates' book, he compares them as well. I'm just pasting the pictures to see them. He also references Koza's works.
I am just wondering if GP would make more reliable solutions for the problem of an urban design work (in contrast to Jose Duarte's work using GA). What must have encouraged him to use GA? Please bear with me, if this is so simple or not clear.
Run of Genetic Programming
Run of Genetic Algorithm