Binary Tree Genetic Programming

Question

I have just got started with Genetic Programming and I am having issues initializing my population.

I am needing a tree to represent each candidate solution - The problem being, I am unfamiliar with trees.

There are two ways of initializing that I need, namely Grow (tree of variable size) and Full (balanced same shape and size tree).

    FULL                        GROW
     (*)                         (*)  
  (+)   (-)                   (5)   (-)
(1)(2) (3)(4)                     (6) (7)

I have initialized my Tree class, however, I do not know how to proceed from here onwards to populate the tree (either Full or Grow).

public class Tree{
   Object value;
   Tree left, right;

   public Tree(Object value)
   {
      this.value=value;
   }   

   public Tree (Object value, Tree left, Tree right) 
   {
      this.value = value;
      this.left = left;
      this.right = right;
   } 

   // Getter & setter for the value.
   public Object getValue(){
      return value;}
   public void setValue(Object value){
      this.value = value;}

   // Getters & setters for left & right nodes.
   public Tree getLeft(){
      return left;}
   public Tree getRight(){
      return right;}
   public void setLeft(Tree ln){
      left = ln;}
   public void setRight(Tree rn){
      right = rn;}


}

Could anyone kindly tell me how this can be done, or even just a nudge in the right direction.

I am trying to randomly populate the trees till a predefined depth.

• Operators (+ - / *) are inserted everywhere apart from leaf nodes.
• Operands (1-100) are inserted ONLY on the leaf nodes

Thanks.

Answer 1

It is not very clear what you want. Are you asking how to represent the examples you gave, or how to implement methods to generate random trees according to one of the two strategies?

Your examples can be represented with your Tree class this way:

Tree full = new Tree("*",
        new Tree("+", new Tree(1), new Tree(2)),
        new Tree("-", new Tree(3), new Tree(4)));

Tree grow = new Tree("*",
        new Tree(5),
        new Tree("-", new Tree(6), new Tree(7)));

---

[EDIT]

You can randomly generate trees using the methods in the following class:

class TreeGenerator {
    private static final String[] OPERATORS = {"+", "-", "/", "*"};
    private static final int MAX_OPERAND = 100;

    private static Random random = new Random();

    public static Tree full(int depth) {
        if (depth > 1) {
            String operator = OPERATORS[random.nextInt(OPERATORS.length)];
            return new Tree(operator, full(depth - 1), full(depth - 1));
        } else {
            return new Tree(random.nextInt(MAX_OPERAND) + 1);
        }
    }

    public static Tree grow(int depth) {
        if (depth > 1 && random.nextBoolean()) {
            String operator = OPERATORS[random.nextInt(OPERATORS.length)];
            return new Tree(operator, grow(depth - 1), grow(depth - 1));
        } else {
            return new Tree(random.nextInt(MAX_OPERAND) + 1);
        }
    }

}

Then, you can just do:

Tree full3 = TreeGenerator.full(3);
Tree grow4 = TreeGenerator.grow(4);