Take the 2-minute tour ×

I'm trying to develop a plugin for Rhino which generates architectural floor plans (based on Shape Grammars). The plugin is written in C# using the RhinoCommon API. Using different rules, represented as genes in a chromosome, I transform a starting geometry. Using GA, a fitness function determines the optimum sequence of transformation rules to generate a geometry that matches parametric criteria (area, views, minimal construction, etc.).

As the geometry represents architecture, there are some constructive rules to adhere to. My question is about the general approach of Genetic Algorithms: When do I check the validity of the geometry created by the chromosome? At the gene insertion point or do I just give invalid geometries a bad fitness value?

When I add a gene (representing a geometric transformation operation) to the chromosome, I can check if this leads to invalid geometry. For example: My starting shape is a rectangle:


One transformation option is to divide one rectangle side in two parts. The gene would look something like this: [DIVIDE:TOP:0.25]. This will create a side containing of two segments, split at the quarter mark:

split rectangle

If I already know that a segment has to be of a certain length, this gene could be creating invalid geometry. In the example above the red segment on the top is too short. Do I implement this geometry check (which could potentially be more complex for other rules than in the shown example) at the gene-insertion point, or do I wait until the fitness function to validate it? In this example a check would be that when I add a segment-split gene, I check if the resulting segments are within an allowed range? Not checking could lead to a population consisting of chromosomes that generate invalid geometry, or individuals with a very bad fitness. Checking could guarantee a population with "valid" chromosomes, but the generation of the chromosomes could possibly take much longer.

What would be a better strategy?

share|improve this question
I just wanted to add that, syntactically, there is nothing wrong with the rule [DIVIDE:TOP:0.25], it is the length of the top side that makes it potentially invalid. If the side is short, 25% of it could make it shorter than the allowed segment length. A solution could be to change the rule, the gene, to [DIVIDE:SIDE:(double within segment length range)], this would always guarantee a valid geometry. That is, no check, but a solid gene application rule. This doesn't work for all rules though. –  Eirik Feb 6 '13 at 11:28

2 Answers 2

I think the check has to be in the embryogeny (mapping) function and in the fitness, because a crossover between the two valid parents (DIVIDE:TOP:0.25) and (DIVIDE:BOTTOM:0.05) could create offspring like (DIVIDE:TOP:0.05) which would create much too short segments, even if the syntax is allowed. As this would have to be valued by the fitness function, a check at the Gene-creation or mutation-point is superfluous.

share|improve this answer

I think that either approach should actually work fine, and depending on your other parameters, will have almost identical behavior. As long as invalid genomes are never selected to be parents, letting invalid genomes through will be the same as removing them at gene insertion point, as long as in the first case your population is significantly bigger than in the second case. Let's say you estimate that about 33% of your gene insertions result in invalid genomes. Then, you'd want your population when letting invalid genomes through to be 3 times as large as if you reject invalid genomes when they are produced. In both cases, the algorithm will allow only valid genomes to be selected as parents, leading to very similar results.

In your case though, it might just be easier to reject invalid genomes at insertion point, which will ensure that all potential parents are valid.

I would finally like to point out that if you are using a significant amount of your evaluation time rejecting invalid genomes, you might want to consider ways of changing your genetic operators so that they can only produce valid genomes. I'm not sure the best way to do this in your GA, but often in genetic programming a developmental approach is used, which enforces only valid changes to be made to an "embryonic" solution.

share|improve this answer
thanks for your comment Tom. After giving it some more thought and researching, I think that, depending on the crossover function, valid parents can create children, therefore there has to be a check in the fitness. And there is no need to check twice? –  Eirik Feb 8 '13 at 14:03
Yeah, I see no reason to check twice for valid children. Once should be enough. –  Tom Feb 8 '13 at 15:29

Your Answer


