References about Galapagos?

Replies to This Discussion

Permalink Reply by David Rutten on July 16, 2010 at 3:25am

Hi Sangsu,

I'm not quite certain in what category Galapagos falls in terms of Genetic Algorithms. In a way it hardly matters. What matters is how it works. And unfortunately there is no documentation available yet on this front.

Here's a basic breakdown:

1. Galapagos populates the first generation (G[0]) with random individuals. Basically the sliders are all set at random values.

2. Now we step into the generic evolutionary loop, so G[0] becomes G[n], as this is the same for all generations.

3. For each individual in G[n] the fitness is computed. This is the most time consuming operation in the solver.

4. The individuals in G[n] must populate G[n+1], there are two ways in which this can happen:
     - Individuals 'survive' the generation gap and are present in both G[n] and G[n+1]
     - Individuals mate to produce offspring that populates G[n+1]
    Often, fit individuals will use both vectors.

5. Creating offspring is a complex procedure and there are many factors that affect it.

5a. Coupling: this step involves picking individuals from G[n] for mating couples. Individuals can be picked isotropically (i.e. everyone has an equal chance of being picked, regardless of fitness), exclusively (i.e. only the fittest X% are allowed to mate, but they are all equally likely to mate) and biased (i.e. the fitter an individual, the higher the chance it finds a mate, but everybody has a chance)

5b. Mate selection: this step involves someone picking a mate from G[n]. When an individual has been selected to mate (step 5a), he/she needs to find a mate. Instead of picking another fit individual, mate selection happens based on genetic distance. For example, individuals could be said to prefer very similar individuals, or they could be said to prefer very different individuals, or something in between. This is called the "Inbreeding factor" in Galapagos. A high inbreeding factor will result in 'incestuous' couples, a low factor will result in 'zoophilic' couples. Neither extreme is healthy.

5c. Coalescence: Once a couple has been formed, offspring needs to be generated. Basically coalescence defines how the genomes of mommy and daddy are combined to produce little johnny. The best analogy with biological coalescence is crossover, where P out of Q genes are inherited from mom and (Q - P) genes are inherited from dad. In Galapagos, these genes are always consecutive, thus if the genome consists of 5 genes, the first 3 come from mom and the last 2 come from dad. Or the first 1 comes from mom and the last 4 come from dad. The amount of genes per parent is random. Genes can also be interpolated (there is no analogy for this in biological evolution). Since a single gene in Galapagos is nothing more than a slider position, it is quite easy to average the positions for mom and dad. Finally, genes can be created via preference blending. Very similar to interpolation, but the blending is weighted by the relative fitness of both parents.

5d. Mutations: Once the offspring genome has been created in step 5c, mutations are applied. Mutations are random events that affect gene values in random ways. Although the Galapagos engine supports several kinds of mutations, in Grasshopper it only makes sense to allow for point mutations, as it it not possible grow or shrink the number of sliders.

6. Finally, a new generation is populated and solved for fitness. There is an optional final step which can ensure that fit individuals do not get lost in the process. The "Maintain High Fitness" value controls what percentage of individuals from G[n] are allowed to displace individuals in G[n+1] provided they are fitter. By default this percentage is 10. Which basically means that the 10% fittest individuals in G[n] are compared to the 10% lamest individuals in G[n+1] and if grandpa is indeed fitter, he's allowed to bump junior off the list.

7. This process (step 2 - step 6) repeats until the maximum number of generations has been reached, until no progress has been made for a specified number of generations or until a specific fitness value has been reached.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

• ▶ Reply

Permalink Reply by Sangsu Lee on July 17, 2010 at 5:02am

Thank you, David! This will be of great help to me and other fellows who are interested in Galapagos.

• ▶ Reply

Permalink Reply by Kris Hammerberg on July 27, 2010 at 8:40pm

Hey David,
I gather from this that the genes can only be sliders.

What would be the best way to control a large number of boolean genes?
Do I just need a large number of integer sliders with a maximum value of 1 and a minimum of 0?
This seems like an inelegant solution. Could it be possible to link it to a list of booleans?

To give some context I'm thinking of a surface grid with a distribution of 2 kinds of panels based on some yet-to-be-determined fitness function.

I'd appreciate your thoughts!
Thanks

• ▶ Reply

Permalink Reply by David Rutten on July 29, 2010 at 8:54am

Hi Kris,

at the moment yes, only sliders are accepted. I'm planning to add the ability to also support Number and Integers parameters with any number of disassociated values. This is some way off though as I have some pretty big jobs on my plate at the moment.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

• ▶ Reply

Permalink Reply by Kris Hammerberg on July 29, 2010 at 9:24am

Hey David,

That's good to hear. I will content myself (and there is much to be contented by) with the latest release for now! Its probably best to get a base understanding before tackling anything with huge lists of potential "genetic material" anyway...

Cheers!

• ▶ Reply

Permalink Reply by Richard Schaffranek on January 19, 2011 at 3:27pm

Hi David

 

I have been working with Galapagos and for some task it's really fine. Presently I was trying to calculate the longest, not intersecting path form a set of edges.

By doing this I ran into two problems:

First in order to make the longest path computation work I would need to generate one slider for each edge. The slider would than pick an edge from the list. Joining all edges at the end.
Did you ever think of letting Galapagos control lists in some way?

 

Second it would be great to control the coupling in some sort. i.e.:

To find the longest path it would be great to not randomly merge genomes but only merge the paths that physicaly intersect at one point, this would give the GA a little more aim...

 

Knowing that I am asking much

 

Richard

• ▶ Reply

Permalink Reply by David Rutten on January 20, 2011 at 5:28am

Hi Richard,

 

I am planning to add a special Galapagos number generator to replace a large (or even variable) amount of sliders.

 

I'm not quite sure what you're asking for with your second request. What do you imagine the interface looks like for a specialized coupling algorithm like this?

 

--

David Rutten

david@mcneel.com

Poprad, Slovakia

• ▶ Reply

Permalink Reply by Richard Schaffranek on January 20, 2011 at 6:23am

Hard one....

 

Well it would be nice if you could use the components that already exist...
Here a sample for the coupling proces that I would imagin for the longest path def I made.

 

Please note in order to use the definition there have to be at least as many sliders as there are curves you selected. I have tested it with a grid structure where it preforms at about 80%.

 

Richard

Attachments:

• longestPathSample.rar, 90 KB

• ▶ Reply

Permalink Reply by Arthur Mani on September 16, 2010 at 2:56pm

Thanks David,
Could you please say a bit more about the zoophilic and incestuous couples?
In nature isn't it more healthy for a couple to have very different genes?
thanks,
Arthur

• ▶ Reply

Permalink Reply by Luis Fraguada on September 16, 2010 at 3:38pm

I am not sure if genetic diseases affect Galapagos generations...the consequence of our genetic code are much nastier than the digital sort...but then again, if there is a high level of incest, and that generation's parents are not necessarily the cream of the crop, this will go on...on the other hand...if two good parents which are also brother and sister have an offspring, this reinforces the good gene? In the end, its a mix of who's getting it on (as the tag line suggests)... there are positive and negative consequences of the incest parameter being at either end of the extreme...

ok, that was my crap answer...would love to hear David wax poetic about this in Vienna next week!

• ▶ Reply

Permalink Reply by David Rutten on September 17, 2010 at 6:44am

Hi Arthur,

just like in nature, both extremes are unhealthy. incestuous couples tend to remove diversity from the population, which can result in entire solutions being missed. They literally become inbred. Zoophilic couples introduce too much diversity into a population, meaning that even relatively fit parents will give birth to unfit offspring. This is especially the case if there are multiple sub-populations, all climbing different Mt. Improbables. Their offspring will end up in the valley in between (i.e. Arkansas).

Typically a value of about 50~75 will provide good results. Even so, I've added some random behaviour to this behind the scenes, so every now and again someone does mate beyond the confines.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

• ▶ Reply

Permalink Reply by Manuel Vasquez Eyzaguirre on September 22, 2010 at 8:46am

Al terminar galápagos de buscar la mejor solución en la cantidad de generaciones señaladas, genera un Record. En el cual se me generan un par de dudas:
Qué función cumple y a que se refiere con:
Genome:
Fitness:
Genes:

Saludos, es muy interesante este tema.
Manuel Vásquez E.
Manuel.ale.vasquez@gmail.com

• ▶ Reply

• ‹ Previous
• 1
• 2
• Next ›
• Page