struct node {
int type; //integer type
double val; //value, mostly used for ephemeral constants
node *args[3]; //possible arguments, at most 3
};
The type field contains an integer type code, the val field holds the
value if the node is an ephemeral constant, and the args vector holds
pointer to up to three arguments.Subject to the limit that there must be at least on operation of each arity, operations can be turned on and off (see: Operation controls). The available node types are:
| Name | Arity | Description |
| Neg | 1 | Arithmetic negation. |
| Com | 1 | Complement of input: (Com x) is 1-x. |
| Del | 1 | Delay operator. When called this operator reports the contents of its value field, storing its current input in the value field. In effect it delays values for one evaluation. The routine InitDelay(t) can be used to set all delay value fields to zero before use. |
| Sin | 1 | Sine of input. |
| Cos | 1 | Cosine of input. |
| Atn | 1 | Artangent of input. |
| Sqt | 1 | Square root of input, save that the operation is transparent to negative numbers. So (Sqt 4) is 2 and (Sqr -4) is -2. |
| UA1 | 1 | Unary ADF number 1. |
| UA2 | 1 | Unary ADF number 2. |
| Add | 2 | Addition. |
| Sub | 2 | Subtraction. |
| Mul | 2 | Multiplication. |
| Div | 2 | Division, save that overflows are mapped to 0. |
| Max | 2 | Maximum of arguments. |
| Min | 2 | Minimum of arguments. |
| Eql | 2 | Equality predicate, returns 1 if true, 0 if false. |
| Gtr | 2 | Greater than predicate, returns 1 if true, 0 if false. |
| Les | 2 | Less than predicate, returns 1 if true, 0 if false. |
| Geq | 2 | Greater than or equal to predicate, returns 1 if true, 0 if false. |
| Leq | 2 | Less than or equal to predicate, returns 1 if true, 0 if false. |
| Neq | 2 | Inequality predicate, returns 1 if true, 0 if false. |
| BA1 | 2 | Binary ADF 1. |
| BA2 | 2 | Binary ADF 2. |
| Hil | 2 | Hill-shaped function. |
| Trx | 2 | X-direction trench-shaped function. |
| Try | 2 | Y-direction trench-shaped function. |
| ITE | 3 | If then else: if first argument is non-negative, return the second argument, otherwise return the third. |
void SetNumberOfVariables(int n);This routines sets the number of variables, X1, X2, ..., that are generated in arandom tress and in mutation operations. This nuymber of variables in the argument n. Sending the right number of variables to an evaluate routine is the user's responsibility. The SetNumberOfVeriables routine is used extensively when using ADFs that take different numbers of variables from the main parse tree.
void SetConstantRange(double min,double max);This routine sets the maximum and minimum values of the ephemeral constants generated in random trees and mutations.
void TurnOn(int OpCode);
void TurnOff(int OpCode);
| NegOP : Unary minus | DivOP : Division |
| ComOP : Complementation | MaxOP : Maximum |
| DelOP : Delay line | MinOP : Minimum |
| SinOP : Sine | EqlOP : Equals? |
| CosOP : Cosine | GtrOP : Greeater than? |
| AtnOP : Arctangent | LesOP : Less Than? |
| SqtOP : Square root | GeqOP : Greater/equal? |
| UA1OP : Unary ADF 1 | LeqOP : Less/equal? |
| UA2OP : Unary ADF 2 | NeqOP : Not equal? |
| AddOP : Addition | BA1OP : Binary ADF 1 |
| SubOP : Subtraction | BA2OP : Binary ADF 2 |
| MulOP : Multiplication | HilOP : Hill |
| TrxOP : X-trench | TryOP : Y-trench |
| ITEOP: If-then-else |
//Turn off all the trig operations TurnOff(SinOP); TurnOff(CosOP); TurnOff(AtnOP);
node *RandTree(int n);RandTree(n) generates a tree (pointer to struct type node) with n nodes. The nodes are taken from the currently enabled opeartions (see: Operation controls). If you are generating a tree with ADFs you need to reset the operation controls to have different operations available when generating the main tree and ADF. RandTree does substantial dynamic allocation.
void KillTree(node *t);KillTree(t) deallocates a tree pointed to by t. It recursively deallocates all the nodes in the tree.
node *CopyTree(node *t);CopyTree(t) generates a tree (pointer to struct type node) that is an node-for-node copy of the one passed as its argument. This routine is what you use instead of the = operator.
int SizeTree(node *t);SizeTree(t) returns the integer number of nodes in its argument.>p>
node *RandSubTree(node*t);RandSubTree(t) returns a pointer to one of the nodes in t. The choice is made uniformly at random relative to the quality of lrand48() in stdlib.
//Allocate a tree, print out its size, print out a random sub-node //copy the tree, and then give pack the storage node *t,*s; //tree type is pointer to node t=RandTree(12); cout << t << endl << "has size:" << SizeTree(t) << "." << endl; cout << "One of the sub-trees is " << RandSubTree(t) << endl; s=CopyTree(t); cout << "A copy of t looks like " << s << endl; KillTree(s); KillTree(t);
void InitDelay(node *t);The delay operator must be initialized the first time it is used - and subsequent times if you are not intentionally processing time series data. InitDelay(t) places a zero in the value field of all delay operators in t. Call InitDelay before evaluating trees.
double Eval(node *t,double *vars); double EvalU1(node *t,node *u,double *vars); double EvalU2(node *t,node *u1,node *u2,double *vars); double EvalB1(node *t,node *b,double *vars); double EvalB2(node *t,node *b1,node *b2,double *vars); double EvalUB(node *t,node *u,node *b,double *vars); double EvalUB2(node *t,node *u1,node *u2,node* b1,node *b2,double *vars);The various evaluation routines all take as arguments a main tree t and a pointer to double that holds the value of the variables X1, X2, etc. If the main tree uses ADFs the you also need the tree for that (those) ADFs. Currently the package supplies calls for a lone tree, one or two unary ADFS, one or two binary ADFs, a unary and a binary ADF, or two each unary and binary ADFs.
//Create a parse tree with three variables and
//one unary ADF and then evaluate it
node *t,*uADF1; //parse tree and ADF
double v[3]={1.0,2.0,1.5} //input variables, initialized for demo
SetNumberOfVariables(3); //three input variables
TurnOff(DelOp); //turn of the delay operation
TurnOff(UA2Op); //as well as the three
TurnOff(BA1Op); //types of ADFs
TurnOff(BA2Op); //we're not using in this demo
t=RandTree(12); //create a 12 node main tree
TurnOff(UA1Op); //turn off unary ADF to avoid calls in the ADF
uADF1=RandTree(6); //6 node ADF
cout << t << endl << uADF1 << endl << " evaluate to ";
cout << EvalU1(t,uADF1,v) << endl;
KillTree(t);
KillTree(uADF1);
void mutateST(node *t);The mutateST(t) operation takes a tree (pointer to struct node), selects a node in the tree at random, and replaces the sub tree rooted there with a new sub tree the same size.
void mutateND(node *t);The mutateND(t) operation takes a tree (pointer to struct node), selects a node in the tree at random, and replaces its operation with another selected at random from those available with the sam arity.
void cross(node *t,node *s);The cross(t,s) operation selects random nodes in s and t and exchanges the sub-trees rooted there. This is the standard subtree crossover for genetic programming.
void chop(node *t,int k);The chop(t,k) operation repeatedly promotes a subtree of the root node of t to be all of t until the size of t is at most k. Chop is used to reduce the size of trees after they grow as a side effect of crossover.
//create two trees, perform a subtree mutation on one, a node mutation //on the other, cross them over, and then make sure neither has more //than 12 nodes node *t,*s; t=RandTree(12); s=RandTree(12); cout << s << " subtree mutates to "; mutateST(s); cout << s << endl; cout << t << " node mutates to "; mutateND(t); cout << t << endl; cross(s,t); cout << "Crossover produces " << endl << s << endl << t << endl; chop(s,12); chop(t,12); cout << "Chop produces " << endl << s << endl << t << endl;