在java中深度复制和交换子树 [英] Deep copying and swapping subtrees in java
问题描述
感谢您抽出时间阅读这篇文章（对于文字墙很抱歉）。
thanks for taking the time to read this (sorry for the wall of text).
是的，这是一个学校项目。不，我不是要你为我做这个。我自己做了所有的工作，我刚刚被Java本身困扰，不是那么多的问题。
Yes, this is a school project. No, I'm not asking you to do this for me. I've done all the work myself I've just been stumped by Java itself, not so much the problem.
这个项目是关于基因编程的基础。我随机生成树（代表基本的数学表达式），评估它们对来自目标函数（x，y值）的数据的适应度，然后通过消除一些真正遥远的变量来处理集合， 交叉操作对两个最适合的表达式。交叉是问题。我已经创建了一个算法工作，但它永久性地改变两个原始的树，我想保持在交叉的情况下，生成两棵树，离开。
The project is about the basics of genetic programming. I randomly generate trees (which represent basic mathematical expressions), evaluate their fitness against data from the target function (x, y values), then manipulate the set by eliminating some that are really far off, mutating some ever so slightly, then performing a "crossover" operation on the two most fit expressions. The crossover is the issue. I have created an algorithm that works but it permanently changes the two original trees, which I want to keep around in case the crossover generates two trees that are way off.
为了解决这个问题，我考虑复制树结构，结果是相当难以实现。我研究了几种不同的方法，首先是序列化。尝试使用并阅读了几个示例后，我尝试了自己和失败。我意识到我没有足够的掌握Java来使用这种技术。所以我决定在Node类上使用递归复制构造函数，并且在GPTree类中有一个简单的构造函数（见下文）。
To fix this issue, I looked into copying the tree structure, which turned out to be fairly difficult to achieve. I looked into a couple different methods, firstly serialization. After trying it out and reading a few examples I tried it myself and failed. I realized I don't have a good enough grasp of Java to use that technique. So I decided to go with a recursive copy constructor on the Node class, and have a simple one on the GPTree class (see below).
我不能解释什么错了，如果你看不到它是特别困难，但忍受我。在Eclipse中调试一段时间后，问题似乎在 GPTree.crossover 方法中开始。具体如下语句：
I can't explain what's going wrong, and it's especially hard if you can't see it, but bear with me. After spending a while debugging in Eclipse, the issue seems to start in the GPTree.crossover method. Specifically the following statements:
Node t1Node = getRandomNode(t1.root);
Node t1NodeParent = t1Node.parent;
Node t2Node = getRandomNode(t2.root);
Node t2NodeParent = t2Node.parent;
当我查看前两个节点的调试器信息时（ t1Node 和 t1NodeParent ）例如， t1Node 的ID将是示例）18和它的父节点的id将为22.然后，在 t1NodeParent ， t1NodeParent id将是22（像它应该是），但它的左或右孩子都不会有18的id（像孩子的）！因此，这些分配下的如果子句弄乱了，然后树也被弄乱了。
When I look at the debugger information for the first two nodes (t1Node and t1NodeParent) for example, t1Node's id will be (all numbers made up for the example) 18 and its parent node's id will be 22. Then, after the assignment to t1NodeParent, t1NodeParent's id will be 22 (like it's supposed to be), but neither of its left or right children will have the id of 18 (like the child's)! Because of this, the if clauses below these assignments get messed up and then the trees just get messed up, too. Sometimes (not every time, oddly enough) the original trees will be changed as well.
我假设这和我尝试复制树有关，因为这是唯一改变了。但是，对我的生活，我不能告诉你为什么这样做。
I assume this has something to do with how I tried to copy the trees, since that's the only thing that has changed. But, for the life of me, I could not tell you why it's doing that.
所以，谢谢你阅读这个长期问题。 。 。我希望你能帮助。 ：/
So, thank you for reading this long-winded question . . . I hope you can help. :/
这是我严重剥离的代码，显示我的问题：
Here is my severely stripped down code that demonstrates my problem:
import java.util.ArrayList;
public class GPEnv {
private final int MAX_HEIGHT = 4;
private ArrayList<GPTree> trees;
public GPEnv(int numTrees) {
trees = new ArrayList<GPTree>();
for (int i = 0; i < numTrees; i++) {
trees.add(new GPTree(MAX_HEIGHT));
}
}
public void crossover() {
System.out.println(trees.get(0));
System.out.println(trees.get(1));
System.out.println();
/*
This commented version works, but it permanently alters the original trees.
GPTree[] res = GPTree.crossover(
trees.get(0),
trees.get(1)
);
*/
GPTree[] res = GPTree.crossover(
trees.get(0).copy(),
trees.get(1).copy()
);
System.out.println(res[0]);
System.out.println(res[1]);
System.out.println();
System.out.println(trees.get(0));
System.out.println(trees.get(1));
}
public static void main(String[] args) {
GPEnv env = new GPEnv(2);
env.crossover();
}
}
Expression.java =https://gist.github.com/dunnza/7687224#file-expression-java =nofollow> gist ）
Expression.java (gist)
public abstract class Expression {
protected static enum Token {
PLUS("+"),
MINUS("-"),
TIMES("*"),
DIVIDE("/"),
NUMBER(""),
VARIABLE("x");
private final String symbol;
Token(String symbol) {
this.symbol = symbol;
}
public String toString() {
return this.symbol;
}
}
protected static class Node {
protected Token token;
protected Node parent, left, right;
protected double value;
public Node() {
this.parent = null;
this.left = this.right = null;
}
public Node(int number) {
this();
this.token = Token.NUMBER;
this.value = number;
}
public Node(Token token) {
this();
this.token = token;
this.value = Double.NaN;
}
private Node(Token token, double number, Node parent, Node left, Node right) {
switch (token) {
case PLUS:
this.token = Token.PLUS;
this.value = Double.NaN;
break;
case MINUS:
this.token = Token.MINUS;
this.value = Double.NaN;
break;
case TIMES:
this.token = Token.TIMES;
this.value = Double.NaN;
break;
case DIVIDE:
this.token = Token.DIVIDE;
this.value = Double.NaN;
break;
case NUMBER:
this.token = Token.NUMBER;
this.value = Double.parseDouble(number + "");
break;
case VARIABLE:
this.token = Token.VARIABLE;
this.value = Double.NaN;
break;
}
this.parent = parent;
this.left = left;
this.right = right;
}
public void setParent(Node rent) {
this.parent = rent;
}
public boolean isOperator() {
switch (this.token) {
case PLUS:
case MINUS:
case TIMES: // intentional fall-throughs
case DIVIDE:
return true;
default:
return false;
}
}
public String toString() {
if (this.token == Token.NUMBER) {
return this.value + "";
}
return this.token.toString();
}
public Node copy() {
Node left = null;
Node right = null;
if (this.left != null) {
left = this.left.copy();
}
if (this.right != null) {
right = this.right.copy();
}
return new Node(token, value, parent, left, right);
}
}
protected Node root;
private void postOrderTraverse(Node node, StringBuilder sb) {
if (node != null) {
postOrderTraverse(node.left, sb);
postOrderTraverse(node.right, sb);
sb.append(node + " ");
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
postOrderTraverse(this.root, sb);
return sb.toString();
}
}
GPTree.java（ gist ）
GPTree.java (gist)
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;
public class GPTree extends Expression {
private static final int MIN_HEIGHT = 2;
private static final int MAX_MUTATED = 4;
private static final Random rand = new Random();
private int maxHeight;
public GPTree(int maxHeight) {
super();
this.maxHeight = maxHeight;
generateRandomTree();
}
private GPTree(Node root, int maxHeight) {
this.root = root;
this.maxHeight = maxHeight;
}
private static Node getRandomNode(Node node) {
if (node.left == null && node.right == null) {
return node;
} else if (rand.nextInt(10) > 6) {
return node;
}
if (rand.nextInt(2) == 0) {
return getRandomNode(node.left);
} else {
return getRandomNode(node.right);
}
}
private void generateRandomTree(Node node, int depth) {
if (depth == maxHeight) {
node.left = new Node(rand.nextInt(10));
node.left.setParent(node);
node.right = new Node(rand.nextInt(10));
node.right.setParent(node);
return;
}
if (rand.nextInt(2) == 0) {
node.left = new Node(Token.values()[rand.nextInt(4)]);
generateRandomTree(node.left, depth + 1);
} else {
// give numbers an increased chance of occuring (60%)
if (rand.nextInt(10) > 3) {
node.left = new Node(rand.nextInt(10));
} else {
node.left = new Node(Token.VARIABLE);
}
}
if (rand.nextInt(2) == 0) {
node.right = new Node(Token.values()[rand.nextInt(4)]);
generateRandomTree(node.right, depth + 1);
} else {
// give numbers an increased chance of occuring (60%)
if (rand.nextInt(10) > 3) {
node.right = new Node(rand.nextInt(10));
} else {
node.right = new Node(Token.VARIABLE);
}
}
if (depth < MIN_HEIGHT && (!node.left.isOperator() && !node.right.isOperator())) {
if (rand.nextInt(2) == 0) {
node.left = new Node(Token.values()[rand.nextInt(4)]);
generateRandomTree(node.left, depth + 1);
} else {
node.right = new Node(Token.values()[rand.nextInt(4)]);
generateRandomTree(node.right, depth + 1);
}
}
node.left.setParent(node);
node.right.setParent(node);
}
public void generateRandomTree() {
if (this.root == null) {
this.root = new Node(Token.values()[rand.nextInt(4)]);
}
generateRandomTree(this.root, 1);
}
public static GPTree[] crossover(GPTree t1, GPTree t2) {
GPTree[] result = new GPTree[2];
Node t1Node = getRandomNode(t1.root);
Node t1NodeParent = t1Node.parent;
Node t2Node = getRandomNode(t2.root);
Node t2NodeParent = t2Node.parent;
t2Node.parent = t1NodeParent;
if (t1NodeParent == null) {
t1.root = t2Node;
} else {
if (t1NodeParent.left == t1Node) {
t1NodeParent.left = t2Node;
} else {
t1NodeParent.right = t2Node;
}
}
t1Node.parent = t2NodeParent;
if (t2NodeParent == null) {
t2.root = t1Node;
} else {
if (t2NodeParent.left == t2Node) {
t2NodeParent.left = t1Node;
} else {
t2NodeParent.right = t1Node;
}
}
result[0] = t1;
result[1] = t2;
return result;
}
public GPTree copy() {
return new GPTree(root.copy(), maxHeight);
}
}
推荐答案
您在制作副本时似乎并未尝试修正父级链接。
It appears that you are not attempting to fix up the parent links when you make the copy.
想象一下基本表达式1 + 2。当你复制'+'，比如id 22时，你创建一个新的'+'节点，它的两个子节点的副本和对它的父节点（null）的引用。假设原始'1'节点具有ID 5，新创建的'1'节点具有ID 18.当您构建新的1节点时，您将父链接保留为22，因为在进行复制时，
Imagine a basic expression 1+2. When you copy the '+', say id 22, you create a new '+' node with copies of its two children and a reference to its original parent (null). Say the original '1' node has id 5, and the newly-created '1' node has id 18. You preserved the parent link back to 22 when you built your new '1' node, because when making the copy you did not yet have access to the new parent.
当深层复制循环数据结构时，提供一个特殊的复制操作，使新的父类作为一个参数。
A way out of this problem when deep-copying circular data structures is to provide a special copy operation that takes the new parent as a parameter. The deep copy should call this special copy with the incomplete new parent node for each of its children.
像
public Node copy() {
return copyWithParent( parent );
}
public Node copyWithParent( Node parentOverride ) {
Node out = new Node( token, value, parentOverride, null, null );
if (this.left != null) {
out.left = this.left.copyWithParent( out );
}
if (this.right != null) {
out.right = this.right.copyWithParent( out );
}
return out;
}
这篇关于在java中深度复制和交换子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
