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.

Tumblebug

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

Burseraceous

Hi sorry, I have edited my original post with clarity. I am trying to randomly generate a tree with a predefined depth with operators and operands. – Tumblebug

Thank you! This is exactly what I was looking for! – Tumblebug

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

}

Numen

I've used Object Value because my tree consists of operators (char) and operands (int). I don't know if there is a better way of doing so. – Tumblebug

@Tumblebug you should probably make your own custom class that holds both an operator or primitive. You can then override compareTo and use object.equals(t). The code above still demonstrates that you need a function to append leave nodes. You'd then make a for loop that added a new node to the head of the tree each iteration – Numen

Thanks alot for your explaination. I will definitely give this a try. – Tumblebug

Answer 3

you can have a look to the implementation of Tiny GP http://cswww.essex.ac.uk/staff/rpoli/TinyGP/ (done by Ricardo Poli). However, that implementation requires deep knowledge of C programming language.

alternatively you may use GP variants with linear representation of chromosomes (such as Linear GP, Cartesian GP, Gene Expression Programming, Multi Expression Programming etc). Those have a simpler and easier to understand implementation. For instance, have a look to source code of Multi Expression Programming: http://www.mepx.org/source_code.html

Niobe