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);

Answer 2

You'll need to create two functions that add elements to a tree. For the GROW function you could do something like below...

Basically, you have to start setting the leaf nodes based on the criteria you decide. This isn't a perfect example but may help you move in the right direction.

I have not run this, but this should demonstrate how to grow a tree. You may need to add functions to make it work how you want.

Tree head = new Tree(new Value("*"));
for ( int x = 0; x < 5; x++){
    head.grow(new Tree(x));
}

Tree:

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

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

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

   // Getter & setter for the value.
   public Value getValue(){
      return value;}
   public void setValue(Value 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;}

      public void grow(Tree t){

    if(value.compareTo(t) < 0){
      if(right == null){
          setRight(t);
      } else{
          getRight().grow(t);
      }
     else{
      if(left == null){
          setLeft(t);
      } else{
          getLeft().grow(t);
      }

    }

    public toString(){
       if(left == null && right == null)
           return value.oper;
       else{
           return value.val;
    }
}

Value:

public class Value{ String oper; Integer val

    public value(String str){
         oper = str;
         val = Integer.MIN_VALUE;
    }

    public value(Integer x){
        oper = "non";
        val = x;
     }

    public int compareTo(Value o){
      if(o.val < val) return -1;
      if(o.val > val) return 1;
      return 0;
    } 

}