// module that defines a bunch of arithmetic operators
#include "trees.h"
// function for adding 2 values
Val add(Val a, Val b)
{
return (a+b);
}
// the character sign for adding
char add_sign[] = " + ";
// the binary function representation
Binary_Func Add = {add, add_sign};
// function for subtraction
Val sub(Val a, Val b)
{
return (a-b);
}
// char sign
char sub_sign[] = " - ";
// func rep
Binary_Func Sub = {sub, sub_sign};
// multiplication
Val mult(Val a, Val b)
{
return (a*b);
}
char mult_sign[] = " * ";
Binary_Func Mult = {mult, mult_sign};
// safe division
Val div(Val a, Val b)
{
// if b is zero, return 1
if (b==(Val)1)
return ((Val)1);
return (a/b);
}
char div_sign[] = " / ";
Binary_Func Div = {div, div_sign};
// greater than function - this is the numerically valued function as
// described in the Koza text - it returns +1 or -1
Val gt(Val a, Val b)
{
if (a > b)
return ((Val)1);
else
return ((Val)-1);
}
char gt_sign [] = " > ";
Binary_Func GT = {gt, gt_sign};
// absolute value function
Val abs(Val a)
{
if (a < (Val)0)
return (-a);
else
return a;
}
char abs_sign[] = "ABS";
Unary_Func Abs = {abs, abs_sign};
// just defines the simple constructors for the 4 node types
#include <stdio.h>
#include <string.h>
#include "trees.h"
// node class constructor. right now just initializes some common variables
Node::Node(void)
{
// set number of children
n_children = 0;
// make this number invalid
n_valid = 0;
// set the parent ref to null
parent = NULL;
}
// node class destructor. this will reset the parent's pointer to this node
// to NULL, so nothing bad happens in the future. it also invalidate's
// the parent's child count
Node::~Node(void)
{
// reset the parent's pointer to this one.
// if there is no parent, no problemo
if (!parent)
return;
// if the parent is unary, this is easy
if (parent->type == NODE_UNARY)
// reset it
((Unary_Node *)parent)->set_child(NULL);
else {
// in this case (binary) we need to figure out if this was the left or
// right child
if (((Binary_Node *)parent)->get_left() == this)
((Binary_Node *)parent)->set_left(NULL);
else
((Binary_Node *)parent)->set_right(NULL);
}
// force a new count
parent->invalidate_count();
}
// this is called when the number of children of a node has changed. it
// sets the invalid flag of this node and its parent to force a recalculation
// when the time comes
void Node::invalidate_count(void)
{
// set the flag
n_valid = 0;
// if there is a parent, call the function
if (parent)
parent->invalidate_count();
}
// binary node constructor - takes the parent node and the function of this
// node
Binary_Node::Binary_Node(Node *parent_node, Binary_Func *func)
{
// just store the args
parent = parent_node;
f = func;
// set the type
type = NODE_BINARY;
// set left and right to null initially
left = right = NULL;
}
// destructor - deletes the right and left subtrees
Binary_Node::~Binary_Node(void)
{
// delete the left
delete left;
// delete the right
delete right;
}
// binary node counter
int Binary_Node::count(void)
{
// if the current count is valid, return that value
if (n_valid)
return n_children;
// otherwise recalculate
// sum up the left and right (if they exist yet)
n_children = 0;
if (left)
n_children += left->count();
if (right)
n_children += right->count();
// count this node
n_children++;
// this is now valid
n_valid = 1;
return n_children;
}
// binary node finder function
Node *Binary_Node::find(int number)
{
// if the number is 1, return this node
if (number==1)
return this;
// decrement the number, to count this node
number--;
// check this value against the number of children in the left subtree.
// if it is less or equal, the target node is in that subtree, so we
// should look there
if ((left) && (number <= left->count()))
return (left->find(number));
// if its not in the left, subtract the number of children of the left
// from the count
if (left)
number -= left->count();
// check this against the number of children of the right subtree.
// if it is less or equal, we will find it there
if ((right) && (number <= right->count()))
return (right->find(number));
// if its not in the left or right, we are not going to find it
return NULL;
}
// value function - pretty simple, just evaluate the function using the
// left and right children's values
Val Binary_Node::value(void)
{
// if the left or right does not exist, generate an error and return
// zero
if ((!left) || (!right)) {
fprintf(stderr,"A binary node is missing a child!\n");
return (Val)0;
}
// return it
return (f->eval(left->value(),right->value()));
}
// print function - prints the subtree's expression to a string.
char *Binary_Node::print(void)
{
// if one of the children is missing, there is an error
if ((!left) || (!right)) {
char msg[80];
sprintf(msg,"BINARY NODE MISSING CHILD");
return (strdup(msg));
}
// get the left and right children's print strings
char *left_str = left->print();
char *right_str = right->print();
// make a new string to hold the composite string
// (left length + operator length + right length + 2 for the paren's)
int newlength = strlen(left_str) + strlen(f->sign) + strlen(right_str) +
2 + 1;
char *newstr = new char[newlength];
// print into it
sprintf(newstr,"(%s%s%s)",left_str,f->sign,right_str);
// delete the 2 child strings
delete left_str;
delete right_str;
// return the new string
return (newstr);
}
// unary node constructor - like the binary one, but a different function type
Unary_Node::Unary_Node(Node *parent_node, Unary_Func *func)
{
// just store the args
parent = parent_node;
f = func;
// set the child to null initially
child = NULL;
// set the type
type = NODE_UNARY;
}
// destructor deletes the child subtree
Unary_Node::~Unary_Node(void)
{
// delete the child
delete child;
}
// unary node counter
int Unary_Node::count(void)
{
// if the current count is valid, return that value
if (n_valid)
return n_children;
// otherwise recalculate
n_children = 0;
// add in the child size (if it exists yet)
if (child)
n_children += child->count();
// count this node
n_children++;
// this is valid now
n_valid = 1;
return n_children;
}
// unary node finder function
Node *Unary_Node::find(int number)
{
// if the number is 1, return this node
if (number==1)
return this;
// decrement the number, to count this node
number--;
// check this value against the number of nodes in the child subtree.
// if it is less or equal, the target node is below this node.
if ((child) && (number <= child->count()))
return (child->find(number));
// if its not in the child subtree, we are not going to find it
return NULL;
}
// unary node value function. checks for a child, and evaluates f using
// its value
Val Unary_Node::value(void)
{
// check for missing child
if (!child) {
fprintf(stderr,"A unary node is missing its child!\n");
return (Val)0;
}
return (f->eval(child->value()));
}
// print function - prints the subtree's expression to a string.
char *Unary_Node::print(void)
{
// if one the child is missing, there is an error
if (!child) {
char msg[80];
sprintf(msg,"UNARY NODE MISSING CHILD");
return (strdup(msg));
}
// get the child's print string
char *child_str = child->print();
// make a new string to hold the composite string
// (operator length + child length + 2 for the paren's)
int newlength = strlen(child_str) + strlen(f->sign) + 2 + 1;
char *newstr = new char[newlength];
// print into it
sprintf(newstr,"%s(%s)",f->sign,child_str);
// delete the child's string
delete child_str;
// return the new string
return (newstr);
}
// constant terminal node constructor. takes parent and const value
Terminal_Const::Terminal_Const(Node *parent_node, Val c)
{
// just store them again
parent = parent_node;
constant = c;
// set the type
type = NODE_CONST;
}
// constant terminal node find function
Node *Terminal_Const::find(int i)
{
if (i==1)
return this;
else
return NULL;
}
// constant terminal node print function
char *Terminal_Const::print(void)
{
// just print the value to a string
char prn[40];
sprintf(prn,"%f",(double)constant);
// make a copy of it
char *newstr = new char[strlen(prn)+1];
strcpy(newstr,prn);
// return the copy
return newstr;
}
// variable terminal node constructor. like the above, but stores a ref
Terminal_Var::Terminal_Var(Node *parent_node, Variable *v)
{
// uh, store them
parent = parent_node;
var = v;
// set the type
type = NODE_VAR;
}
// constant terminal node find function
Node *Terminal_Var::find(int i)
{
if (i==1)
return this;
else
return NULL;
}
// variable terminal node print function
char *Terminal_Var::print(void)
{
// make a copy of the variable name
char *newstr = new char[strlen(var->name)+1];
strcpy(newstr,var->name);
// return the copy
return newstr;
}
// this recursively copies a tree. it takes a pointer to the tree to be
// copied and a pointer to the parent of the new tree. it returns a pointer
// to the new tree.
Node *tree_copy(Node *src, Node *parent)
{
// make a new node of the correct type, then go to the children if needed
switch (src->type) {
Node *dest;
case NODE_BINARY: {
// less casting
Binary_Node *bn = (Binary_Node *)src;
// make the new node
dest = (Node *)new Binary_Node(parent,bn->get_func());
// do the left child
((Binary_Node *)dest)->set_left(tree_copy(bn->get_left(),dest));
// do the right child
((Binary_Node *)dest)->set_right(tree_copy(bn->get_right(),dest));
return dest;
}
case NODE_UNARY: {
// less casting
Unary_Node *un = (Unary_Node *)src;
// make the new node
dest = (Node *)new Unary_Node(parent,un->get_func());
// do the child
((Unary_Node *)dest)->set_child(tree_copy(un->get_child(),dest));
return dest;
}
case NODE_CONST:
// make the new node
dest = (Node *)new Terminal_Const(parent,src->value());
return dest;
case NODE_VAR:
// make the new node
dest = (Node *)new Terminal_Var(parent,((Terminal_Var *)src)->val_p());
return dest;
}
}
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "population.h"
#include "util.h"
// population class constructor. takes the initial size, and lists and numbers
// of binary & unary functions, and variables that are available. also takes
// a function to be used for generating random constants (the potential values
// of these constants may vary from application to application)
Population::Population(int s, Binary_Func **bs, int num_bs,
Unary_Func **us, int num_us,
Variable **vs, int num_vs,
Val (*f)(void))
{
// first just copy in the args
size = s;
b_funcs = bs;
num_b_funcs = num_bs;
u_funcs = us;
num_u_funcs = num_us;
vars = vs;
num_vars = num_vs;
const_rand = f;
// allocate the tree pointer list
trees = new Binary_Node *[size];
// check
if (!trees) {
// output error message
fprintf(stderr,"can't allocate tree pointer list!\n");
// flag the error
size = 0;
return;
}
// initalize the random number generator
time_t *tp = NULL;
srandom((unsigned int)time(tp));
// go through the list and create new top level nodes. pick the function
// randomly from the list
for (int i=0;i<size;i++)
trees[i] = new Binary_Node(NULL,b_funcs[int_rand(num_b_funcs)]);
// now go through the nodes and recursively build the random trees
for (i=0;i<size;i++)
build_tree(trees[i]);
}
// this generates a random node, whos parent is n. it is mutually recursive
// with the build_tree's
Node *Population::new_node(Node *n)
{
// pick a node type for new node
// (MH - probably want to replace this with something that takes current
// tree depth into account to limit the complexity of the initial trees)
int type = int_rand(4);
// points to the new node
Node *newnode;
// create the new node
switch (type) {
case NODE_BINARY:
{
// create it with a random function
Binary_Node *nn= new Binary_Node(n,b_funcs[int_rand(num_b_funcs)]);
// save the pointer
newnode = (Node *)nn;
// recursively build the new subtree
build_tree(nn);
}
break;
case NODE_UNARY:
{
// create it with a random function
Unary_Node *nn = new Unary_Node(n,u_funcs[int_rand(num_u_funcs)]);
// save the pointer
newnode = (Node *)nn;
// recursively build the new subtree
build_tree(nn);
}
break;
case NODE_CONST:
{
// create it with a random constant value
Terminal_Const *nn = new Terminal_Const(n,const_rand());
// save the pointer
newnode = (Node *)nn;
}
break;
case NODE_VAR:
{
// create it with a random variable
Terminal_Var *nn = new Terminal_Var(n,vars[int_rand(num_vars)]);
// save the pointer
newnode = (Node *)nn;
}
break;
}
// return this new node
return newnode;
}
// this is responsible for generating a random subtree from a binary node base.
void Population::build_tree(Binary_Node *n)
{
// make the left subtree
Node *left = new_node((Node *)n);
// assign it to this node's left
n->set_left(left);
// make the right subtree
Node *right = new_node((Node *)n);
// assign it to this node's right
n->set_right(right);
}
// this is responsible to generating a random subtree from a unary node base
void Population::build_tree(Unary_Node *n)
{
// make the child subtree
Node *child = new_node((Node *)n);
// assign it
n->set_child(child);
}
// utility function for sorting the population
int tree_comp(const void *a1, const void *a2)
{
// recast the args
const Binary_Node *x = *((const Binary_Node **)a1);
const Binary_Node *y = *((const Binary_Node **)a2);
// do the compare
if (x->fitness > y->fitness)
return -1;
else
if (x->fitness == y->fitness)
return 0;
else
return 1;
}
// performs crossover - this is a little long but it makes a lot of sense...
// trust me.
void Population::crossover(Binary_Node *p1, Binary_Node *p2, Binary_Node **c1,
Binary_Node **c2)
{
// copy the first parent
*c1 = (Binary_Node *)tree_copy(p1,NULL);
// copy the second
*c2 = (Binary_Node *)tree_copy(p2,NULL);
//
// get the crossover sections from the parents
//
// right now this will not pick the root node
// randomly select a node number for the 1st parent (crossover point)
int cp1 = int_rand((p1->count()-1)) + 2;
// get this node (crossover section)
Node *cs1 = p1->find(cp1);
// randomly select a node number for the 2nd parent
int cp2 = int_rand((p2->count()-1)) + 2;
// get this node
Node *cs2 = p2->find(cp2);
//
// delete the section from the 1st child and copy in the 2nd parent's
// crossover section
//
// find the node that will be deleted from the 1st child
Node *delnode = (*c1)->find(cp1);
// save its parent
Node *parent = delnode->get_parent();
// if the parent is a binary node, figure out if this was a left or
// right child
int left=0;
if (parent->type == NODE_BINARY)
if (((Binary_Node *)parent)->get_left() == delnode)
left = 1;
// delete the subtree
delete delnode;
// make a copy of p2s crossover section
Node *newnode1 = tree_copy(cs2,parent);
// reset the parent's pointer
// if it was a unary pointer, its easy
if (parent->type == NODE_UNARY)
((Unary_Node *)parent)->set_child(newnode1);
// it must be a binary node then
else
if (left)
((Binary_Node *)parent)->set_left(newnode1);
else
((Binary_Node *)parent)->set_right(newnode1);
//
// now delete the cs from the 2nd child and link in a copy of the 1st
// parent's cs (begin cut-and-paste :)
//
// find the node that will be deleted from the 1st child
delnode = (*c2)->find(cp2);
// save its parent
parent = delnode->get_parent();
// if the parent is a binary node, figure out if this was a left or
// right child
left=0;
if (parent->type == NODE_BINARY)
if (((Binary_Node *)parent)->get_left() == delnode)
left = 1;
// delete the subtree
delete delnode;
// make a copy of p2s crossover section
Node *newnode2 = tree_copy(cs1,parent);
// reset the parent's pointer
// if it was a unary pointer, its easy
if (parent->type == NODE_UNARY)
((Unary_Node *)parent)->set_child(newnode2);
// it must be a binary node then
else
if (left)
((Binary_Node *)parent)->set_left(newnode2);
else
((Binary_Node *)parent)->set_right(newnode2);
// that's all for now
return;
}
// sorts the generation by fitness
void Population::sort(void)
{
// sort the population in descending order
qsort(trees,size,sizeof(Binary_Node *),tree_comp);
}
// spawns a new generation
void Population::spawn(float birth_rate)
{
// sort them first
sort();
// debug
for (int j=0;j<size;j++)
fprintf(stderr,"%i: %f\n",j,trees[j]->fitness);
// allow the best pairs to reproduce. they mate in sequential pairs
// and take over the places of the worst pairs
for (int i=0;i<((int)size*birth_rate-1);i+=2) {
// first delete the trees that will be replaced by the children
// of this pair
delete trees[size-(i+1)];
delete trees[size-(i+2)];
// do the crossover
crossover(trees[i],trees[i+1],&trees[size-(i+1)],&trees[size-(i+2)]);
// good enough for now
}
}
// uses the provided function to set the fitness of each memeber
void Population::evaluate(double (*f)(Node *))
{
// just go through each member and set it
for (int i=0; i<size; i++)
trees[i]->fitness = f(trees[i]);
}
// returns the expression string for a member of the population
char *Population::print(int n)
{
// just call it and return it
return (trees[n]->print());
}