/* trees.h * * J Scott Cameron adapted from Hans Kuhlmann / Mike Hollick * available at * http://www.cis.upenn.edu/~hollick/genetic/paper2.html * * This file defines node types and a GP population class */ #include "Val.h" #include using namespace std; #define NODE_BINARY 0 #define NODE_UNARY 1 #define NODE_CONST 2 #define NODE_VAR 3 //typedef double Val; typedef struct Binary_Func { Val (*eval)(Val,Val); // the function pointer char *sign; // the prefix operation sign }Binary_Func; typedef struct Unary_Func { Val (*eval)(Val); // function pointer char *sign; // the prefix operation sign } Unary_Func; // the structure of variables (used for variable terminals). This allows // for printing as well typedef struct Variable { Val *var; // pointer to the variable's value char *name; // the variable's name } Variable; Val c_rand(void); class Node { public: Node *parent; // the parent node int n_children; // number of child nodes int n_valid; // validity flag for above Node(void); // constructor ~Node(void); // destructor will reset the parent's // pointer to this node int type; // indicates the type of node void invalidate_count(void); // called when the number of children // of this node has changed virtual Val value(void) = 0; // this is the function that takes care // of everything needed to assign a // value to this node virtual int count(void) = 0; // returns the number of children virtual Node *find(int) = 0; // used to return a particular node virtual char *print(void) = 0; // prints the subtree's expression to a // string // virtual Node *read(char*) = 0; // resets the parent node void set_parent(Node *n) {parent = n;}; // accesses the parent node Node *get_parent(void) {return parent;}; }; // binary operation node class Binary_Node : public Node { public: Node *left; // left child Node *right; // right child Binary_Func *f; // the function of this node // constructor takes the parent and the function Binary_Node(Node *,Binary_Func *); ~Binary_Node(void); // destructor will delete the children // adds a node to the left void set_left(Node *l) {left = l;}; // adds a node to the right void set_right(Node *r) {right = r;}; // accesses the left child Node *get_left(void) {return left;}; // accesses the right child Node *get_right(void) {return right;}; // accesses the function Binary_Func *get_func(void) {return f;}; double fitness; // fitness of the tree (if this is the root) // value function just needs to pass the values of the children to // f Val value(void); // value function int count(void); // counter function Node *find(int); // finder function char *print(void); // printer function // Node *read(char*); }; // unary operation node class Unary_Node : public Node { public: Node *child; // the (single) child Unary_Func *f; // the function of this node // constructor takes the parent and the function Unary_Node(Node *,Unary_Func *); ~Unary_Node(void); // destructor will delete the child // adds a child node void set_child(Node *c) {child = c;}; // accesses the child node Node *get_child(void) {return child;}; // accesses the function Unary_Func *get_func(void) {return f;}; // value function just passes the value of the child to f Val value(void); // value function int count(void); // counter function Node *find(int); // finder function char *print(void); // printer function // Node *read(char*); }; // a constant value terminal node class Terminal_Const : public Node { public: Val constant; // the constant value // constructor takes the parent and value Terminal_Const(Node *, Val); // the value function just needs to return the constant Val value(void) {return constant;}; // counter function is just 1 for this node int count(void) {return 1;}; Node *find(int); // finder function char *print(void); // printer function // Node *read(char*); }; // variable terminal node. uses a Val ref for the value class Terminal_Var : public Node { public: Variable *var; // ref of the variable value // constructor takes parent and variable pointer Terminal_Var(Node *, Variable *); // the value function just returns the current variable value Val value(void) {return *var->var;}; // this returns the value pointer (for copying) Variable *val_p(void) {return var;}; // counter function is just 1 for this node int count(void) {return 1;}; Node *find(int); // finder function char *print(void); // printer function // Node *read(char*); }; class Population { public: Binary_Func **b_funcs; // the list of available binary functions int num_b_funcs; // number of available binary functions Unary_Func **u_funcs; // the list of unary functions int num_u_funcs; // number of unary functions Variable **vars; // list of variables int num_vars; // number of variables Val (*const_rand)(void); // function for generating random constants Binary_Node **trees; // list of trees in the population int size; // size of the population // these 3 are used to generate random subtrees recursively from // either a binary or unary operator node Node *new_node(Node *); void build_tree(Binary_Node *); void build_tree(Unary_Node *); // these are used when spawning a new generation void crossover(Binary_Node *,Binary_Node *,Binary_Node **,Binary_Node **); bool should_mutate(); void mutate(Node *); Node *change_type(Node *); Node *Population::open(Node* n, string* input, int* index); // constructor takes the initial size, number and list of binary funcs, // number and list of unary funcs, number and list of variables, // and a function for finding random constants Population(int,Binary_Func **,int,Unary_Func **,int,Variable **,int, Val (*)(void)); ~Population(void); // destructor cleans up memory void sort(void); // sort population by fitness void spawn(float); // spawns a new generation void evaluate(double (*)(Node *)); // sets the fitness on each member int members(void) {return size;};// returns the current size of population char *print(int); // returns the expression of a member // returns the fitness of a member double fitness(int i) {return trees[i]->fitness;}; }; Node *tree_copy(Node *src, Node *parent);