Maximum tree depth? nodes?

[Jeannie Fitzgerald]

Hello,

This morning I received the following error from DEAP:

MemoryError: DEAP : Error in tree evaluation : Python cannot evaluate a tree higher than 90. To avoid this problem, you should use bloat control on your operators. See the DEAP documentation for more information. DEAP will now abort.

I am unable to find the requisite section in the deap documentation. Can you point me to where this information is please? Also, what does 90 represent? I am running DEAP under Ubuntu on a VM to which I have allocated 2GB of memory - is the maximum size of the tree dependent on this?

Really loving the framework in general though - thanks:-)

Many thanks,

Jeannie

[François-Michel De Rainville]

Dear Jeannie,

The problem you mention is rather a Python limitation than a problem with DEAP. As Marc-Andre mentionned in a now closed bug report on DEAP :

The Python parser has a depth limit somewhere between 92 and 99 when parsing an expression. For instance,
     
eval("("*100+"3"+")"*100)

will fail with a MemoryError exception thrown.

This means that you cannot open more that 92 (or 99) parenthesis without closing a single one.

This is what happens when GP trees have more than ~90 levels, plus the DEAP stuff around the tree evaluation that makes the stack larger than 92 or 99.

Anyhow, I doubt the problem you are tackling really requires trees that large and I think you are probably suffering from a common problem in GP called bloat, where trees are accumulating a lot of not useful stuff and the fitness stagnates.

As I'm not an expert on bloat control but Marc-Andre is. I'll leave it to him to suggest you a suitable solution. In the mean time, there are two operators that can help you in the bloat control section of the operator list:

http://deap.readthedocs.org/en/master/api/tools.html#operators

Don't hesitate to contact us if you have problems applying them. I don't think there are any example of bloat control out there.

Have fun with DEAP,
Best regards,
François-Michel

--
You received this message because you are subscribed to the Google Groups "deap-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to deap-users+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jeannie Fitzgerald]

Hi,

Thank you for your response, I am glad to understand the reason for the limitation. There is no need to respond further with regard to bloat - as I can deal with this myself.

thanks again,

Jeannie

[Jeannie Fitzgerald]

Hello again,

Today I tried to implement static limits on crossover and mutation as described in a related thread but received an error about gp.staticDepthLimit:

MAX_HEIGHT = 17

toolbox.register("mate", gp.cxOnePoint)

toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)

toolbox.decorate("mate", gp.staticDepthLimit(MAX_HEIGHT))

toolbox.decorate("mutate", gp.staticDepthLimit(MAX_HEIGHT))

<module>

    toolbox.decorate("mate", gp.staticDepthLimit(MAX_HEIGHT))

AttributeError: 'module' object has no attribute 'staticDepthLimit'

What do you think I have overlooked here?

many thanks,

Jeannie

On Thursday, September 4, 2014 10:41:28 AM UTC+1, Jeannie Fitzgerald wrote:

[Félix-Antoine Fortin]

The operator has since been renamed "staticLimit".

See gp.staticLimit documentation : http://deap.readthedocs.org/en/1.0.x/api/tools.html#deap.gp.staticLimit

Félix-Antoine Fortin

Félix-Antoine Fortin

--

[Jeannie Fitzgerald]

Hi Félix-Antoine,

Thanks for your very prompt response! It works fine now.

j

On Thursday, September 4, 2014 10:41:28 AM UTC+1, Jeannie Fitzgerald wrote:

[Jeannie Fitzgerald]

Hi again,

I have applied the bloat control method as suggested and it works ok most of the time. However, today I again received the same error. I have set my maximum tree depth to 17 - which is a fairly standard value. Is there no possibility of handling this problem in Deap by say breaking down the tree evaluation into sub evaluations? 

thanks,

Jeannie

On Thursday, September 4, 2014 10:41:28 AM UTC+1, Jeannie Fitzgerald wrote:

[François-Michel De Rainville]

When producing individuals do you use this kind of loop:

for c1, c2 in zip(pop[:-1:2], pop[1::2]):

    toolbox.mate(c1, c2)

or this one:

offspring = map(toolbox.clone, population))

for i in range(1, len(offspring), 2):
    offspring[i-1], offspring[i] = toolbox.mate(offspring[i-1], offspring[i])

The second form gets the static limit job done while the first fails. The reason is that the decorator does not modify in place the individuals, but only returns the good ones leaving the "pop" of the first loop with oversized individuals.

Regards,

François-Michel

--

[Jeannie Fitzgerald]

Hi,

I simply defined the decorated mate and mutate  operators as described in an earlier post and used the default population generation. Which algorithm does that use?

thanks,

jeannie

On Thursday, September 4, 2014 10:41:28 AM UTC+1, Jeannie Fitzgerald wrote:

[François-Michel De Rainville]

All the algorithms from the algorithms module use the correct version.

What algorithm do you use? Can you provide a minimum example that reproduce the behavior?

Regards,
François-Michel

--

[Jeannie Fitzgerald]

Hi again,

Ok, problem solved. I had started to use the recently updated custom NSGA-11 algorithm which uses the older method. 

thanks,

Jeannie

On Thursday, September 4, 2014 10:41:28 AM UTC+1, Jeannie Fitzgerald wrote: