我在尝试将遗传算子应用于二叉树时遇到问题。
首先,我有为初始种群生成两种类型树的方法,即Grow(可变大小的树)和Full(平衡的相同形状和大小的树) .
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);
}
}
最佳答案
我将尝试简要解释一些步骤。
在父树中随机选择一个点
这样做的一种方法是选择一个随机数,比如 k
,介于 0 和树中非叶元素的数量之间。随机点将是第 k
个元素,而 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()
方法返回直接父节点。
请注意,您还必须检查返回的随机子树是根本身的某些情况。
关于java - 二叉树上的遗传算子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32009382/