java - 二叉树上的遗传算子

我在尝试将遗传算子应用于二叉树时遇到问题。

首先，我有一些方法可以为初始种群生成两种类型的树，即生长(可变大小的树)和全(平衡的形状和大小的树)。

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

每棵树的类如下所示:

public class Tree<E>{

   E element;
   Tree<E> left, right;
   double rawFit;
   int hitRat;

   public Tree(E element)
   {
      this.element=element;
   }

   public Tree (E element, Tree left, Tree right)
   {
      this.element = element;
      this.left = left;
      this.right = right;
       }

        //MORE
        //CODE
}

现在，在这里我很难理解如何实现遗传算子，即突变和交叉

从最初的种群中随机选择一棵树，我该如何应用这些遗传算子？
对于突变:

我需要在父树中随机选择一个点。

删除该选定点以下的整个子树。

生成深度与已删除子树相似的新子树。

将其替换回原始父树和所选点。

现在是后代。

图形描述:

                             PARENT
                              (*)
randomly chosen point -->  (+)   (-)
                         (1)(2) (3)(4)

       OFFSPRING         RANDOM SUBTREE
         (*)
    (NULL)  (-)     +        (*)
          (3) (4)          (5) (6)

     NEW OFFSPRING
          (*)
      (*)    (-)
    (5)(6) (3) (4)

我还需要为Crossover做类似的事情。

从理论上讲似乎很简单，但是我不知道如何编写此代码(Java)。任何帮助，将不胜感激。

编辑:我用于生成完整树的方法如下所示:

private static final String[] OPERATORS = {"+", "-", "/", "*"};
private static final int MAX_OPERAND = 100;
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);
        }
    }

最佳答案

我将尝试简要地解释一些步骤。

在父树中随机选择一个点

一种方法是在0和树中非叶元素的数量之间选择一个随机数，即k。随机点将是k th元素，而是traversing the tree in order。

将整个子树替换到该选定点以下。

只需将子树设置为新生成的树即可。像这样:

public class Tree<E> {

    public void mutate() {
        Tree tree = this.getRandomSubtree();
        tree.replace(NEW_RANDOM_TREE);
    }

    public void replace(Tree<E> newTree) {
        if(this.isLeftChild()) this.getParent().setLeft(newTree);
        else                   this.getParent().setRight(newTree);
    }
    ...
}

getRandomSubtree()方法返回树中的随机点。
树的getParent()方法返回直接父节点。

请注意，您还必须检查某些情况，其中返回的随机子树是根本身。