gp._generate fails if there are terminals but not primitives of appropriate type about deap HOT 4 CLOSED

From felix.antoine.fortin on July 03, 2012 07:42:28

Could you provide more details on the actual problem you encountered?

If you do not to provide primitives that can solve your problem,
what do you think the generation function should do else then failing?

Labels: -Priority-Medium Priority-Low

from deap.

From [email protected] on July 08, 2012 05:12:22

If I have a function A, that takes arguments of type_n, those arguments can
be either other functions that return type_n, or terminals of type_n. If
the primitive set defines only terminals of type_n, but no functions that
return that type, the tree generation algorithm should, when it encounters
the node that requires that type, opt to use the terminal instead of a
function.

There is one simple solution: on line 376 in gp.py instead of
if condition(max_depth):
should say
if condition(max_depth) or not len(pset.primitives[type_]):

Obviously it can be argued both ways (especially for genFull, which now can
generate trees of smaller than asked size). But I don't think that it is
realistic to expect that in gp systems with many parameter types, all have
both functions and terminals defined for every type.

Anyway, thanks for your help, deap is becoming a very nice library. IMO, it
would be nice to also include other heuristics, there is no need to stay
tied to 'evolutionary' part, since it could easily support them. I might
contribute some later this year, most likely Ant systems, if you are
interested.

from deap.

From marc.andre.gardner on July 08, 2012 08:48:47

While I agree that the behavior of gp.generate should be clarified, and that the proposed patch is clear and simple, I do not think that this would be the right way to do it :

• First because as you point it out, genFull and genGrow would not behave as they should. When you call genFull, you expect a balanced tree of a certain height. With this modification, not only the generated tree might be smaller than the requested height, but it may also be unbalanced. The whole purpose of having two generate functions is that they create different kinds of trees, and thus provide a good diversity. With this modification, this would not be the case, and might affect the overall performance of the evolution (although this would have to be proved).
• Second because if we support that, then, following the same rationale, we should also support the opposite (when the primitive set defines functions of type_n, but no terminals of that type), and that would be a mess, as it may easily produce an infinite recursion in generate.

I also did a quick check on other frameworks :

• OpenBeagle does not support that either, but instead of raising an error, it loops while a valid tree is not generated -- obviously this affects the diversity of the population. See GP/initFullConstrainedOp.cpp if you want to see more.
• ECJ does support that, but it warns the user and the code is commented with "no nonterminals, hope the guy knows what he's doing!"... See gp/koza/KozaBuilder.java

Overall, I think that we should clarify the error message, maybe also match the OpenBeagle behavior and simply loop when a tree generation fails in this way.
But I'm not sure that hidding this problem shall be the right way to fix it...

Obviously I can be wrong, and I let this bug report open as we might have to discuss more on that issue...

Status: Accepted
Labels: Component-Logic Usability

from deap.

From [email protected] on January 18, 2013 07:25:56

A more comprehensive error is now shown to the user when this situation appears.

Status: Fixed
Owner: felix.antoine.fortin

from deap.