二叉树遗传编程

Question

我刚开始使用遗传编程,我在初始化人口时遇到了问题.

我需要一棵树来代表每个候选解决方案 - 问题在于,我对树木不熟悉.

我需要两种初始化方法,即Grow(可变大小的树)和Full(平衡相同的形状和大小的树).

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

我已经初始化了我的Tree类,但是,我不知道如何从这里开始填充树(Full或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;}


}

任何人都可以告诉我如何做到这一点,甚至只是在正确的方向上轻推.

我试图随机填充树木直到预定义的深度.

• 除了叶节点之外,操作符(+ - /*)被插入到处.
• 操作数(1-100)仅插入叶节点上

谢谢.

Answer 1

不太清楚你想要什么。您是在问如何表示您给出的示例，或者如何实现根据两种策略之一生成随机树的方法？

您的示例可以用 Tree 类表示，如下所示：

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

[编辑]

您可以使用以下类中的方法随机生成树：

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

}

然后，你可以这样做：

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