Python DEAP individual to an AST

[George Kouzmov]

I'm trying to convert an individual (a gp program) into python code. However when I call evaluate() I'm getting an error I'm not sure how to fix. I'm solving symbolic regression problem and these are my primitives.

    pset = gp.PrimitiveSet("MAIN", 1)
    pset.addPrimitive(operator.add, 2)
    pset.addPrimitive(operator.sub, 2)
    pset.addPrimitive(operator.mul, 2)
    pset.addPrimitive(safeDiv, 2)
    pset.addEphemeralConstant(lambda: random.randint(-1,1))
    pset.renameArguments(ARG0='x')

The error I'm getting is:

    NameError: name 'x' is not defined

Also I'm not getting any solutions to the problem even though I've restricted the primitive set and I've increased the number of populations and generations.

[Félix-Antoine Fortin]

Hi George,

The gp module provides two function to transform a tree into Python code:

- gp.lambdify: return a function that can arguments

- gp.evaluate: return a code object, generally used with primitives that are methods of an object.

When doing symbolic regression, you will want to produce a function that can be called on different values, therefore you need gp.lambdify. This is also what is registered in the toolbox in the example you are referring to.

The gp.evaluate function is used when the primitives are for examples methods of an object. We use it to manipulate the ant simulator in the ant example

http://deap.gel.ulaval.ca/doc/default/examples/gp_ant.html

TL;DR: replace gp.evaluate by gp.lambdify in your toolbox.

Do not hesitate if you have any remaining questions,

Félix-Antoine Fortin

[George Kouzmov]

Hi Felix,

Thanks for the answer.

However I want to do evaluation over the web. A cloud service will be taking an individual and returning the values of the fitness evaluation, which I'll return to the DEAP code and create the new generation. I need evaluate in order to get executable python code so I can execute it on the web service without the need of the primitive functions but as I said I'm getting an error which I don't really understand how to fix.

Regards,
George

--
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/groups/opt_out.

[Félix-Antoine Fortin]

Hi George,

Python code object produced by lambdify and evaluate are not transferable between computers, at least no easily. lambdify returns a lambda function, while evaluate returns a partial, both are not picklable.

Moreover, as I said earlier, you cannot use gp.evaluate when doing symbolic regression. lambdify create a lambda function with arguments, while evaluate simply wraps a series of statements in a function without argument. The error you mentioned is related to the fact the the primitive 'x' is never defined by evaluate, because in the primitive set it is supposed to be an argument of the function, while evaluate produce a function without arguments.

Now, if you want to evaluate individuals remotely, you need to transfer the individuals, not the functions produced by gp.lambdify. You could also convert the individual in a string of Python code using gp.stringify, then execute that string remotely. If you only to distribute the evaluations on different computers, wether they are in the cloud or somewhere near, the easiest way to do it is by using SCOOP, which was developed in collaboration with DEAP. http://deap.gel.ulaval.ca/doc/dev/tutorials/basic/part3.html

Feel free to ask more questions if needed. However, we might need to see more you code to better help you as the content of the primitive set does not tell us much about you are using DEAP.

Regards,

Félix-Antoine

[George Kouzmov]

Hi Félix-Antoine,

Thanks for the great answer. I took a look at SCOOP but it's not what I need.

Just to clarify. In order to get an individual compiling on a remote computer I need to send an individual, set the primitive functions at the remote computer in DEAP's toolbox and lambdify the individual, correct?

Again, many thanks for the help!

George

P.S. I know it's not a related topic but I didn't see how to use the decorator in order to set maximum depth of the tree.

[Félix-Antoine Fortin]

Hi George,

You are almost correct. On the remote computer, you will need to define the PrimitiveSet and the evaluation function. The latter will pass the primitive set to lambdify when compiling a lambda function for each individual.

Best regards,

Félix-Antoine

[George Kouzmov]

Hi Felix,
I'm keeping this approach in mind and thanks for the help. However I have an idea.

Since initially in DEAP I'm setting up the primitive sets, based on them and the semi-code in the individuals I can create a full AST which can later be executed anywhere (including on my remote web service). In theory it should work, I'll be testing this idea in the next few days. However if it work do you think I can contribute to the DEAP framework with this module?

Regards,
George 

[Félix-Antoine Fortin]

Hi George,

We are always looking for contributions, so if you propose something new for DEAP GP, we will definitely look at it.

That said, I invite you to look at the code of PrimitiveSet and lambdify. We have considered in the past building AST from GP individuals. The solution we developed did not make the cut because converting individuals to ASTs was actually slower than evaluating the code.

Furthermore, even when using AST, you will still need to assure that the primitive (i.e.: operator.add, math.sin, etc.) are imported in the scope where the tree is evaluated. AST or bytecode are not standalone objects. This is why in the PrimitiveSet, we currently keep a dictionary that maps the name of the primitive to its Python function equivalent, the context attribute. The Python code generated from an individual is evaluated with that dictionary as a local context. Therefore, if you want to evaluate the individual remotely, you will at least need to communicate to your remote web service, the PrimitiveSet context attribute and the individuals.

Looking forward to your contribution,

Félix-Antoine

[George Kouzmov]

Hi Felix,
I'm sorry to bother you again but I'm experiencing a bug that I don't really understand where it's coming from.Little on the project I am working on: 

I'm doing a framework for copying or improving a web service through GP and I'm using DEAP for the genetic programming. Since one of the requirements is evaluate individuals what I'm doing is I'm specifying a target service that you've set up to evaluate the individuals ( this is inteded to be used as a cloud so multiple instances can be evaluated simultaneously but it's still in testing period so it's only one). So I have the primitive set and toolbox declared both at the web service and at the local machine. I took your advice, looked at lambdify and see how it works and changed it a little for my purposes like this:

# expr is stringifyed individual

 def lambdify(self,expr, pset):

        args = ",".join(arg for arg in pset.arguments)

        lstr = "lambda {args}: {code}".format(args=args, code=expr)

        return eval(lstr, dict(pset.context))

For the purpose of testing ( the project is a proof of concept) I'm using symbolic regression so my REST web services that I'm copying simply take numerics arguments and return result based on some expression

While I'm setting up the toolbox and declaring max depth for mutate and mate and I'm declaring them like this:

        creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin, pset=self.pset)

        self.toolbox.register("expr", gp.genRamped, pset= self.pset, min_=self.depthInitialMin, max_=self.depthInitialMax)

        self.toolbox.register("individual", tools.initIterate, creator.Individual,  self.toolbox.expr)

        self.toolbox.register("population", tools.initRepeat, list,  self.toolbox.individual)

        self.toolbox.register("select", tools.selTournament, tournsize=3)

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

        self.toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)

        self.toolbox.register('mutate', gp.mutUniform, expr= self.toolbox.expr_mut)

        self.toolbox.decorate('mutate',gp.staticDepthLimit(self.maxDepthLimit))

        self.toolbox.decorate('mate',gp.staticDepthLimit(self.maxDepthLimit))

However I'm still getting an error related to the parser:

File "/home/mrjew/Dropbox/dev/Dev/pycharm/darwin/baseCherryPy.py", line 44, in evaluateCopy

    func = self.lambdify(individual,self.configuration.pset)

  File "/home/mrjew/Dropbox/dev/Dev/pycharm/darwin/baseCherryPy.py", line 18, in lambdify

    return eval(lstr, dict(pset.context))

MemoryError

I've checked the individuals and they seem to be fine, none of them is exceeding the given depth, problem is this is happening after some time running, If I'm copying a simple web service everything is fine. Didn't find any solution related to the parser and though it might be some kind of a DEAP issue and you might be able to help. Sorry for the long post and taking so much from your time.

Regards,
George

[Félix-Antoine Fortin]

Hi George,

MemoryError exceptions are raised by the Python interpreter when it runs out of memory.

http://docs.python.org/2/library/exceptions.html#exceptions.MemoryError

Essentially, if your trees never have depth higher than 90, it could simply mean that at some point in the evolution, with the trees getting bigger, you do not have enough memory to evaluate the individuals. Have you looked at the memory footprint of your optimization process? How many individuals do you have? What is the average depth when the evolution crashes?

The attribute height returns the depth of a tree.

http://deap.gel.ulaval.ca/doc/dev/api/gp.html#deap.gp.PrimitiveTree.height

Regards,

Félix-Antoine

[George Kouzmov]

Hi all,
Thank you for the response. Now that I tested seeing the individual's height, apparently it goes above 93 at some points and hence I get memory error, however I still don't understand why isn't the decorator working then. Am I doing something wrong?

       

        creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin, pset=self.pset)

        self.toolbox.register("expr", gp.genRamped, pset= self.pset, min_=self.depthInitialMin, max_=self.depthInitialMax)

        self.toolbox.register("individual", tools.initIterate, creator.Individual,  self.toolbox.expr)

        self.toolbox.register("population", tools.initRepeat, list,  self.toolbox.individual)

        self.toolbox.register("select", tools.selTournament, tournsize=3)

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

        self.toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)

        self.toolbox.register('mutate', gp.mutUniform, expr= self.toolbox.expr_mut)

        self.toolbox.decorate('mutate',gp.staticDepthLimit(self.maxDepthLimit))

        self.toolbox.decorate('mate',gp.staticDepthLimit(self.maxDepthLimit))

Regards,
George

[Marc-André Gardner]

Hi George,

Some thoughts about your problem :

1) The static depth limit decorator only guarantees that you will not exceed the depth limit given that the input individuals are valid (i.e. under depth limit). Otherwise, it would fail. So if your initialization step produce individuals higher than 90 (which is unlikely, I admit), if you seed the population with external individuals whom may not respect the depth limit, or if you use another operator on the individuals without having it decorated (say, for instance, that you want to use another mutation type in some cases), then it may indeed fail as you observe.

2) As I recall, the MemoryError related to a too high number of nested functions begins by something like "s_push: parser stack overflow". Is that your case?

3) Which version of DEAP are you using? I think I remember we experience some problems with the decorators prior to 0.9.

4) In your program, are you sure that the register operation may not be executed twice (once _before_ the decorator is applied, one _after_, which would void the effect of the decorator).

If nothing of this work, maybe you could add some debug data to this topic, for instance, by scanning the whole population for excessively high trees and try to figure out from where they come and if this is reproductibe (so, in the case it is a bug in our framework, find the problem and fix it).

Do not hesitate if you have any other question, and merry Christmas!

Marc-André

[George Kouzmov]

Hi Marc-André,

Merry Christmas! Thank you for the attention during the holiday season!

1) I'm specifically setting the depth of the initial individuals and I think it's done like that:

    self.toolbox.register("expr", gp.genRamped, pset= self.pset, min_=self.depthInitialMin, max_=self.depthInitialMax)

I'm not using any decorators besides the ones for mutate and mate since I'm not using any other evolution method so I have two decorators only for the two of them

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

    self.toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)

    self.toolbox.register('mutate', gp.mutUniform, expr= self.toolbox.expr_mut)

    self.toolbox.decorate('mutate',gp.staticDepthLimit(self.maxDepthLimit))

    self.toolbox.decorate('mate',gp.staticDepthLimit(self.maxDepthLimit))

2) Yes I'm getting parser overflow error. Now that Felix told me how to look at an individual's height (depth) I realized the error is coming from there since some individuals go to depth up to 115 even though I've set maxDepthLimit to 17 . However I don't know why

3) I am working with DEAP 0.9 reason was 1.0 wasn't stable yet when I started learning. However if 1.0 is a better option for me know and there are considerable improvements I can easily change versions I guess.

4) Not sure how to detect this however I'll give it a try. It might be related to the way I'm using the framework. As I explained before I have a client and a web service that evaluates the individual however the web service is using nothing from the toolbox, only the primitive set in order to get the functions for the evaluation and then the fitness value is passed back to the client but it doesn't seem to interfere with the reproduction process.

One thing to have in mind is I'm not using the toolbox for the reproduction process rather I'm splitting up the process so I can isolate the evaluation. ( I just realized I could use the framework the standard way ( as in the examples ) if I capture the individuals in the evaluate function so I'll rewrite it and give it a try). Maybe this can be the problem?

def crossover(self,offspring):

        """ Given a generation it mates all the individuals based on the crossover parameter"""

        for child1, child2 in zip(offspring[::2], offspring[1::2]):

            if random.random() < self.configuration.cx:

                self.toolbox.mate(child1, child2)

                del child1.fitness.values

                del child2.fitness.values

    def mutation(self,offspring):

        """ Given a generation it mutates the individuals based on the mutation parameter"""

        for mutant in offspring:

            if random.random() < self.configuration.mut:

                self.toolbox.mutate(mutant)

                del mutant.fitness.values

    def nonEvaluated(self,offspring):

        """ Crete a list of all nonevaluated individuals in the population """

        return [ind for ind in offspring if not ind.fitness.valid]

     def populate(self):

        """ Generates all the populations that are evaluated, mutated, mated and when

            all the generations finish it returns a list of the top 20 individuals"""

        for gen in range(self.configuration.gen):

            offspring = self.toolbox.select(self.population, len(self.population))

            offspring = map(self.toolbox.clone, offspring)

            self.crossover(offspring)

            self.mutation(offspring)

            invalid_ind = self.nonEvaluated(offspring)

            fitnesses = self.toolbox.map(self.evaluate, invalid_ind)

            for ind, fit in zip(invalid_ind, fitnesses):

                ind.fitness.values = fit

            self.population = offspring

            self.hof.update(self.population)

Thank you a lot for the help. I'll try to do some more tests in the next few days hopefully I'll find something.

Regards and Happy Holidays,
George

[Marc-André Gardner]

Hi George,

I am not on my computer right now, so I cannot validate it, but I just had an insight on your problem.

I looked again at the decorator code ( https://code.google.com/p/deap/source/browse/deap/gp.py#743 ) and I think you have unveil a potential bug ( or at least a documentation flaw) in Deap.

Thé decorator only modifies the returned individuals, and NOT the ones returned by reference. In your crossover function, you discard thé returned individuals (which would ne normally OK with standard, undecorated operators).

Coule you try to use the return value in your crossover and mutate functions, like :
child1, child2 = toolbox.mate(child1, child2)

I think it may solve your issue. If so, please tell us and we will think of a potential fix ( at least a doc update).

Have a good day, and sorry again for the typos, it is not easy to type this on a phone ;-)

Marc-André

[George Kouzmov]

Hi Marc-André,

In the crossover function I captured the child's height and in this case they go over 10 even though I setted up to be maximum of 10.

new_child1, new_child2 = self.toolbox.mate(child1, child2)

print "CHILDS",new_child1.height, new_child2.height

In the case of my code I'm simply not assigning the return statements. However I still get individuals with height over 10

self.toolbox.mate(child1, child2)

In your case you want me to generate a new generation with the assigned individuals and substitute it in the toolbox, is that correct or am I mistaking? However even individuals generated this way are with height over 10. I will however try to substitute this setup with a more standard one (by using algorithms.eaSimple() ) by moving all the functionality to the evaluate function. However even if it works I don't get why the approach I'm using is causing such a problem.

Here is the GitHub repository where all my code is in case you need more reference: https://github.com/MrJew/darwin

Sadly it's holiday time and I don't have so much time so I can't do a lot of tests, I think I can find some time tomorrow and the day after it for little bit re factoring. I appreciate your time and thanks for the response again.

Regards,

George

[George Kouzmov]

Hi Everyone,
It's been time since an update on the thread. I've been focusing on other parts of the framework but now I'm testing in real life and this appears to get out of control especially when the set of primitives is larger. So for revising purposes I'll go through my code again.

Everything is being configured and later ran in a class. Here is the configuration of the toolbox where I'm using the decorator to set staticDepthLimit to mutate and mate:

def configure(self):
        """ Creates the toolbox and sets all the needed parameters"""
        self.setPrimitiveFunctions()
        self.setTerminals(self.terminals)


        if not self.isMax   : creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
        else                : creator.create("FitnessMax", base.Fitness, weights=(-1.0,))

        creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin, pset=self.pset)
        self.toolbox.register("expr", gp.genRamped, pset= self.pset, min_=self.depthInitialMin, max_=self.depthInitialMax)
        self.toolbox.register("individual", tools.initIterate, creator.Individual,  self.toolbox.expr)
        self.toolbox.register("population", tools.initRepeat, list,  self.toolbox.individual)
        self.toolbox.register("select", tools.selTournament, tournsize=3)
        self.toolbox.register("mate", gp.cxOnePoint)
        self.toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
        self.toolbox.register('mutate', gp.mutUniform, expr= self.toolbox.expr_mut)


        self.toolbox.decorate('mutate',gp.staticDepthLimit(self.maxDepthLimit))
        self.toolbox.decorate('mate',gp.staticDepthLimit(self.maxDepthLimit))

        self.configureArguments()

Later on for the evaluation of individuals I'm using this code.

        self.outputIndividuals()

However I get individuals with size over 90 hence maximum recursion depth is exceeded. I hope we can brainstorm again over this issue and maybe find where I've gone wrong. Is the problem in the split of the code?

Thank you,

George

[George Kouzmov]

Hi again,

https://github.com/MrJew/darwin here is the entire code for the framework I'm executing the DEAP code is in configuration and populator files for more information

Regards,

George 

[François-Michel De Rainville]

In your crossover and mutation function the good individuals are in the returned variables of the mate and mutate tools. Decorators cannot change the arguments by reference-like.

Try something like (or look for the varAnd function source code)

children = toolbox.mate(child1, child2)

offspring.extend(children)

and

mutants = toolbox.mutate(mutant)

offspring.extend(mutants)

It should work properly. I take a note to put this forward in the documentation.

Regards,

François-Michel

[George Kouzmov]

Hi François,
Thanks a lot ! That worked perfectly

George

[George Kouzmov]

Hey François,

I'm not sure I completely understand what is happening; offspring.extend(children) simply adds the new children generated into the offspring but who is removing old individuals from the offspring. Also if I'm modifying the offspring like this,

does this mean I need to return it in order to update it?

Thanks,
George

[François-Michel De Rainville]

Ok I gave you the simplified version in my last mail. In fact, you have to loop on indices instead of the offspring to replace the appropriate ones. Here is the exact deap.algorithms.varAnd function

offspring = [toolbox.clone(ind) for ind in population]

    

# Apply crossover and replace individuals

for i in range(1, len(offspring), 2):

    if random.random() < cxpb:

        offspring[i-1], offspring[i] = toolbox.mate(offspring[i-1], offspring[i])

        del offspring[i-1].fitness.values, offspring[i].fitness.values

# Apply mutation and replace individuals

for i in range(len(offspring)):

    if random.random() < mutpb:

        offspring[i], = toolbox.mutate(offspring[i])

        del offspring[i].fitness.values

return offspring

I hope it clarifies things,

Have fun,

François-Michel

[George Kouzmov]

Thank you very much. It seems to be working correctly. No individuals are exceeding the chosen depth and it runs smoothly through all without problem with the offspring.

Kind Regards,
George