|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--ec.gp.GPNodeBuilder | +--ec.gp.build.Uniform
Uniform implements the algorithm described in
Bohm, Walter and Andreas Geyer-Schulz. 1996. "Exact Uniform Initialization for Genetic Programming". In Foundations of Genetic Algorithms IV, Richard Belew and Michael Vose, eds. Morgan Kaufmann. 379-407. (ISBN 1-55860-460-X)
The user-provided requested tree size is either provided directly to the Uniform algorithm, or if the size is NOSIZEGIVEN, then Uniform will pick one at random from the GPNodeBuilder probability distribution system (using either max-depth and min-depth, or using num-sizes).
Further, if the user sets the true-dist parameter, the Uniform will ignore the user's specified probability distribution and instead pick from a distribution between the minimum size and the maximum size the user specified, where the sizes are distributed according to the actual number of trees that can be created with that size. Since many more trees of size 10 than size 3 can be created, for example, size 10 will be picked that much more often.
Uniform also prints out the actual number of trees that exist for a given size, return type, and function set. As if this were useful to you. :-)
The algorithm, which is quite complex, is described in pseudocode below. Basically what the algorithm does is this:
Dealing with Zero Distributions
Some domains have NO tree of a certain size. For example, Artificial Ant's function set can make NO trees of size 2. What happens when we're asked to make a tree of (invalid) size 2 in Artificial Ant then? Uniform presently handles it as follows:
Func NumTreesOfType(type,size) If NUMTREESOFTYPE[type,size] not defined, N[type] = all nodes compatible with type NUMTREESOFTYPE[type,size] = Sum(n in N[type], NumTreesRootedByNode(n,size)) return NUMTREESOFTYPE[type,size] // check to make sure we can put 0% probability items // in our probability distributions Func NumTreesRootedByNode(node,size) If NUMTREESROOTEDBYNODE[node,size] not defined, count = 0 left = size - 1 If node.children.length = 0 and left = 0 // a valid terminal count = 1 Else if node.children.length <= left // a valid nonterminal For s is 1 to left inclusive // yeah, that allows some illegal stuff, it gets set to 0 count += NumChildPermutations(node,s,left,0) NUMTREESROOTEDBYNODE[node,size] = count return NUMTREESROOTEBYNODE[node,size] Func NumChildPermutations(parent,size,outof,pickchild) // parent is our parent node // size is the size of pickchild's tree that we're considering // pickchild is the child we're considering // outof is the total number of remaining nodes (including size) yet to fill If NUMCHILDPERMUTATIONS[parent,size,outof,pickchild] is not defined, count = 0 if pickchild = parent.children.length - 1 and outof==size // our last child, outof must be size count = NumTreesOfType(parent.children[pickchild].type,size) else if pickchild < parent.children.length - 1 and outof-size >= (parent.children.length - pickchild-1) // maybe we can fill with terminals cval = NumTreesOfType(parent.children[pickchild].type,size) tot = 0 For s is 1 to outof-size // some illegal stuff, it gets set to 0 tot += NumChildPermutations(parent,s,outof-size,pickchild+1) count = cval * tot NUMCHILDPERMUTATIONS [parent,size,outof,pickchild] = count return NUMCHILDPERMUTATIONS[parent,size,outof,pickchild] For each type type, size size ROOT_D[type,size] = probability distribution of nodes of type and size, derived from NUMTREESOFTYPE[type,size], our node list, and NUMTREESROOTEDBYNODE[node,size] For each parent,outof,pickchild CHILD_D[parent,outof,pickchild] = probability distribution of tree sizes, derived from NUMCHILDPERMUTATIONS[parent,size,outof,pickchild] Func CreateTreeOfType(type,size) Choose node from ROOT_D[type,size] If size > 1 FillNodeWithChildren(node,0,size-1) return node Func FillNodeWithChildren(parent,pickchild,outof) If pickchild = parent.children.length - 1 // last child Fill parent.children[pickchild] with CreateTreeOfType(parent.children[pickchild].type,outof) Else choose size from CHILD_D[parent,outof,pickchild] Fill parent.pickchildren[pickchild] with CreateTreeOfType(parent.children[pickchild].type,size) FillNodeWithChildren(parent,pickchild+1,outof-size) return
Parameters
base.true-dist bool= true or false (default) |
(should we use the true numbers of trees for each size as the distribution for picking trees, as opposed to the user-specified distribution?) |
Field Summary | |
java.util.Hashtable |
_functionsets
|
java.math.BigInteger[][][] |
_truesizes
|
static int |
CHECKBOUNDARY
|
double[][][][][] |
CHILD_D
|
java.util.Hashtable |
funcnodes
|
GPFunctionSet[] |
functionsets
|
int |
maxarity
|
int |
maxtreesize
|
java.math.BigInteger[][][][][] |
NUMCHILDPERMUTATIONS
|
int |
numfuncnodes
|
java.math.BigInteger[][][] |
NUMTREESOFTYPE
|
java.math.BigInteger[][][] |
NUMTREESROOTEDBYNODE
|
static java.lang.String |
P_TRUEDISTRIBUTION
|
static java.lang.String |
P_UNIFORM
|
ec.gp.build.UniformGPNodeStorage[][][][] |
ROOT_D
|
boolean[][][] |
ROOT_D_ZERO
|
double[][][] |
truesizes
|
boolean |
useTrueDistribution
|
Fields inherited from class ec.gp.GPNodeBuilder |
CHECK_BOUNDARY, maxSize, minSize, NOSIZEGIVEN, P_MAXSIZE, P_MINSIZE, P_NUMSIZES, P_SIZE, sizeDistribution |
Constructor Summary | |
Uniform()
|
Method Summary | |
void |
computePercentages()
|
Parameter |
defaultBase()
Returns the default base for this prototype. |
int |
intForNode(GPNode node)
|
GPNode |
newRootedTree(EvolutionState state,
GPType type,
int thread,
GPNodeParent parent,
GPFunctionSet set,
int argposition,
int requestedSize)
|
java.math.BigInteger |
numChildPermutations(int functionset,
GPNode parent,
int size,
int outof,
int pickchild)
|
java.math.BigInteger |
numTreesOfType(int functionset,
int type,
int size)
|
java.math.BigInteger |
numTreesRootedByNode(int functionset,
GPNode node,
int size)
|
int |
pickSize(EvolutionState state,
int thread,
int functionset,
int type)
|
void |
preprocess(EvolutionState state,
int _maxtreesize)
|
void |
setup(EvolutionState state,
Parameter base)
Sets up the object by reading it from the parameters stored in state, built off of the parameter base base. |
Methods inherited from class ec.gp.GPNodeBuilder |
canPick, pickSize, protoClone, protoCloneSimple |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
public static final java.lang.String P_UNIFORM
public static final java.lang.String P_TRUEDISTRIBUTION
public static final int CHECKBOUNDARY
public GPFunctionSet[] functionsets
public java.util.Hashtable _functionsets
public java.util.Hashtable funcnodes
public int numfuncnodes
public int maxarity
public int maxtreesize
public java.math.BigInteger[][][] _truesizes
public double[][][] truesizes
public boolean useTrueDistribution
public java.math.BigInteger[][][] NUMTREESOFTYPE
public java.math.BigInteger[][][] NUMTREESROOTEDBYNODE
public java.math.BigInteger[][][][][] NUMCHILDPERMUTATIONS
public ec.gp.build.UniformGPNodeStorage[][][][] ROOT_D
public boolean[][][] ROOT_D_ZERO
public double[][][][][] CHILD_D
Constructor Detail |
public Uniform()
Method Detail |
public Parameter defaultBase()
Prototype
public void setup(EvolutionState state, Parameter base)
Prototype
For prototypes, setup(...) is typically called once for the prototype instance; cloned instances do not receive the setup(...) call. setup(...) may be called more than once; the only guarantee is that it will get called at least once on an instance or some "parent" object from which it was ultimately cloned.
setup
in class GPNodeBuilder
public int pickSize(EvolutionState state, int thread, int functionset, int type)
public void preprocess(EvolutionState state, int _maxtreesize)
public final int intForNode(GPNode node)
public java.math.BigInteger numTreesOfType(int functionset, int type, int size)
public java.math.BigInteger numTreesRootedByNode(int functionset, GPNode node, int size)
public java.math.BigInteger numChildPermutations(int functionset, GPNode parent, int size, int outof, int pickchild)
public void computePercentages()
public GPNode newRootedTree(EvolutionState state, GPType type, int thread, GPNodeParent parent, GPFunctionSet set, int argposition, int requestedSize) throws java.lang.CloneNotSupportedException
newRootedTree
in class GPNodeBuilder
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |