二叉树遗传编程

Question

我刚开始接触遗传编程，现在在初始化我的种群时遇到了问题。

我需要用一棵树来表示每个候选解 - 问题是，我对树结构不熟悉。

我需要两种初始化方法，即Grow（变量大小的树）和Full（平衡相同形状和大小的树）。

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

我已经初始化了我的Tree类，但是我不知道如何继续从这里开始填充树（无论是完整的还是生长的）。

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）仅插入到叶节点上。

谢谢。

- Leo

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

- Helder Pereira

---

抱歉，我已经编辑了原帖以使其更加清晰。我正在尝试使用运算符和操作数随机生成一个预定义深度的树形结构。 - Leo

谢谢！这正是我在寻找的！ - Leo

Answer 2

您需要创建两个添加元素到树中的函数。对于 GROW 函数，您可以像下面这样做...

基本上，您必须根据您决定的标准开始设置叶节点。这不是一个完美的例子，但可能会帮助您朝着正确的方向前进。

我还没有运行过这个程序，但这应该演示了如何生长一棵树。您可能需要添加功能以使其按照您想要的方式工作。

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

树：

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

值：

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

}

- Pumphouse

---

我使用了Object Value，因为我的树由运算符（char）和操作数（int）组成。我不知道是否有更好的方法。 - Leo

@Leo，你可能需要创建自己的自定义类来保存运算符或原始数据。然后你可以重写compareTo方法并使用object.equals(t)。上面的代码仍然表明你需要一个函数来添加叶子节点。然后你可以编写一个for循环，在每次迭代中向树的头部添加一个新节点。 - Pumphouse

非常感谢您的解释。我一定会尝试一下。 - Leo

Answer 3

你可以查看Tiny GP的实现http://cswww.essex.ac.uk/staff/rpoli/TinyGP/（由Ricardo Poli完成）。然而，该实现需要深入了解C编程语言。

或者，您可以使用具有染色体线性表示的GP变体（例如线性GP、笛卡尔GP、基因表达式编程、多表达式编程等）。这些具有更简单和易于理解的实现。例如，查看Multi Expression Programming的源代码：http://www.mepx.org/source_code.html

- Mihai Oltean