April 2014


Options: Use Monospaced Font
Show HTML Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Sean Luke <[log in to unmask]>
Reply To:
ECJ Evolutionary Computation Toolkit <[log in to unmask]>
Mon, 14 Apr 2014 12:42:15 -0400
text/plain (19 lines)
On Apr 12, 2014, at 2:16 PM, Raymond Shpeley <[log in to unmask]> wrote:

> Having the extra resources of the university's server didn't help much in 
> controlling the memory exploitation issue of strong data typing. I didn't have 
> time to look into the root issue in ECJ with strong data typing, but I assume it 
> uses a greedy algorithm in tree construction. Maybe I'll look into it later. This 
> post is for the benefit of others who may need to work around the issue as I 
> did.

I don't know the details of your issue exactly, but from what you've described, I'm pretty certain it has nothing to do with ECJ's implementation.

Strong typing is simple.  Types are either atomic types or they are set types: these are both very small objects, and only a small number of them are stored in ECJ's GPNodeConstraints, not in the GPNodes themselves.  So there's no memory issue there.  Furthermore, there's no memory problem in doing type constraint satisfaction, that's just a very simple, practically O(1) comparison.

Next, conider how typing affects breeding operators.  Again, this is very simple: when ECJ must do crossover (for example), it repeatedly searches, randomly and uniformly through rejection sampling, until it finds to type-compatible points, then swaps them.  There's no memory issue here at all.

The only thing left is tree generation.  Here strong typing can have a strong effect on the nature of the trees; but it's not an ECJ implementation thing, it's just a GP tree generation thing.  If you select types which are too constrained, ECJ will have a hard time finding trees which meet the constraints.  The GROW, FULL, and RAMPED HALF-AND-HALF algorithms are simple depth-first algorithms which grow and grow until a certain depth is reached.  These algorithms have no size constraints, only depth constraints, and if your typing is set up just so, it coult make big trees.  An alternative which I strongly suggest is to use PTC2 and specify the tree sizes you want.  Note that to make sure that typing doesn't fail on you, you must have a leaf node for every kind of return type.