Creating a binary tree in Java for genetic programming purposes

Question

I am working on a project for the software development class that I take. The goal is to develop a program that will use genetic programming to generate a mathematical expression that matches the provided training data.

I just started working on a project, and I'm trying to wrap my head around how to create a binary tree that will allow you to define a user-defined tree height and save each individual node section to make crossover and mutation easier when I get the implementation of these processes.

Here are the node classes that I have created so far. Sorry, I'm sure this is my obvious inexperience.

public class Node { Node parent; Node leftchild; Node rightchild; public void setParent(Node p) { parent = p; } public void setLeftChild(Node lc) { lc.setParent(this); leftchild = lc; } public void setRightChild(Node rc) { rc.setParent(this); rightchild = rc; } } public class OperatorNode extends Node { char operator; public OperatorNode() { double probability = Math.random(); if (probability <= .25) { operator = '+'; } else if (probability > .25 && probability <= .50) { operator = '-'; } else if (probability > .50 && probability <= .75) { operator = '*'; } else { operator = '/'; } } public void setOperator(char op) { if (op == '+' || op == '-' || op == '*' || op == '/') { operator = op; } } /** * Node that holds x variables. */ public class XNode extends Node { char x; public XNode() { x = 'x'; } } import java.util.Random; public class OperandNode extends Node { int operand; /** * Initializes random number generator, sets the value of the node from zero to 9. */ public OperandNode() { Random rand = new Random(); operand = rand.nextInt(10); } /** * Manually changes operand. */ public void setOperand(int o) { operand = o; } } 

This does everything I need from the nodes themselves, but I run into problems trying to figure out how to turn them into a larger tree. I understand that I need to use a collection type of some type, but I can't seem to find it in the Library, which seems appropriate for what I'm trying to do.

Even a push in the right direction would also be appreciated.

Answer 1

So you want to build a random tree of OperatorNode s, OperandNode s and XNode s? And you said you want the tree depth determinant to be determined?

Define a recursive function called buildRandomTree or something similar. For the depth of the tree, one int parameter must be used. If the depth parameter is 1, return a random leaf node (OperandNode or XNode). If the depth parameter is greater than 1, generate a random OperatorNode and make recursive calls to create the left and right subtrees (with a depth of 1 less than the current level).

Depending on what you want to do with the nodes, you will have to define other recursive functions. For example, you probably want to create textual representations of your expression trees. To do this, you can define toString() for each of the node classes. ( OperatorNode.toString() will need to call toString() in the left and right subtrees.)

You might also want to evaluate expression trees (with given values ​​for variables). To do this, you can define another recursive function, possibly called evaluate() . He will have to take one parameter, possibly Map , which will give the variable values ​​(or "bindings") that you want to evaluate with the expression. (Right now, your expression trees can only contain one variable "x", but I think you can add more. If you are sure that you will use only one variable, then evaluate can take one numeric argument for the value "x".)

Implementing evaluate for your 3 node classes will be very simple. OperandNode and VariableNode will simply return the value directly; OperatorNode will have to call evaluate in the left and right subtrees, combine the values ​​with the appropriate operation, and then return the result.

Answer 2

Perhaps a look will help you.