Creating a binary tree in Java for Genetic Programming Purposes

Question

I'm working on a project for a software engineering class I'm taking. The goal is to design a program that will use genetic programming to generate a mathematical expression that fits provided training data.

I've just started working on the project, and I'm trying to wrap my head around how to create a binary tree that will allow for user-defined tree height and keep each node separate to make crossover and mutation simpler when I get to implementing those processes.

Here are the node classes I've created so far. Please pardon what I am sure is my evident 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 accomplishes everything I need out of the nodes themselves, but I'm running into problems trying to figure out how to turn these into a larger tree. I realize I need to use a collection type of some sort, but can't seem to find one in the Library that seems appropriate for what I'm trying to do.

Even a nudge in the right direction would be greatly appreciated.

Bighorn

Not really an answer to your question, but have you looked at jgap? jgap.sourceforge.net – Garris

I'd run across it, but we get extra credit for building it from scratch, and really, this is something I just want to understand for my personal benefit. – Bighorn

Answer 1

So you want to build a random tree of OperatorNodes, OperandNodes, and XNodes? And you said you want to make the tree depth user defined?

Define a recursive function called buildRandomTree or something similar. It should take a single int parameter for tree depth. If the depth parameter is 1, return a random leaf node (OperandNode or XNode). If the depth parameter is more than 1, generate a random OperatorNode, and make recursive calls to generate the left and right subtrees (with depth 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 will probably want to generate textual representations of your expression trees. For that, you can define toString() on each of the node classes. (OperatorNode.toString() will have to call toString() on the left and right subtrees.)

You will probably also want to evaluate the expression trees (with given values for the variables). For that, you can define another recursive function, perhaps called evaluate(). It will have to take one parameter, probably a Map, which will give the variable values (or "bindings") which you want to evaluate the expression with. (Right now your expression trees can only contain a single variable "x", but I imagine you may want to add more. If you are sure you will only ever use a single variable, then evaluate can take a single numeric argument for the value of "x".)

The implementation of evaluate for your 3 node classes will all be very simple. OperandNode and VariableNode will just return a value directly; OperatorNode will have to call evaluate on the left and right subtrees, combine the values using the appropriate operation, then return the result.

Buskus

This was basically the direction I was headed in, but what's confusing me is how to go about retrieving Node values after I create them. Without a collection or unique identifier, aren't I just creating disembodied Node objects that I can't retrieve? – Bighorn

Answer 2

Maybe looking at this will help you.

Ecstatic

Going through it and trying to wrap my head around it. Thanks for the link. – Bighorn