Глубокое копирование и обмен поддеревьями в Java
Спасибо, что нашли время, чтобы прочитать это (извините за стену текста).
Фон
Да, это школьный проект. Нет, я не прошу тебя сделать это для меня. Я сделал всю работу сам, я был просто озадачен самой Java, не столько проблема.
Проект об основах генетического программирования. Я случайным образом генерирую деревья (которые представляют основные математические выражения), оцениваю их соответствие данным целевой функции (значения x, y), затем манипулирую множеством, удаляя действительно удаленные, слегка изменяя некоторые, а затем выполняю Операция "кроссовер" для двух наиболее подходящих выражений. Кроссовер это проблема. Я создал алгоритм, который работает, но он постоянно изменяет два исходных дерева, которые я хочу сохранить в случае, если кроссовер генерирует два дерева, которые находятся далеко.
Чтобы решить эту проблему, я попытался скопировать древовидную структуру, что оказалось довольно трудно достичь. Я изучил пару различных методов, во-первых, сериализацию. Попробовав и прочитав несколько примеров, я попробовал сам и потерпел неудачу. Я понял, что недостаточно хорошо разбираюсь в Java, чтобы использовать эту технику. Поэтому я решил использовать конструктор рекурсивных копий для класса Node, а простой - для класса GPTree (см. Ниже).
Я не могу объяснить, что происходит, и особенно тяжело, если ты этого не видишь, но потерпи меня. Потратив некоторое время на отладку в Eclipse, проблема, кажется, начинается в GPTree.crossover метод. Конкретно следующие высказывания:
Node t1Node = getRandomNode(t1.root);
Node t1NodeParent = t1Node.parent;
Node t2Node = getRandomNode(t2.root);
Node t2NodeParent = t2Node.parent;
Когда я смотрю на информацию отладчика для первых двух узлов (t1Node а также t1NodeParent) например, t1NodeИдентификатор будет (все числа составлены для примера) 18, а идентификатор его родительского узла будет 22. Затем, после присвоения t1NodeParent, t1NodeParentИдентификатор будет 22 (как и должно быть), но ни у его левого, ни у правого детей не будет идентификатора 18 (как у ребенка)! Из-за этого if пункты ниже этих назначений испорчены, и тогда деревья просто испортились, также. Иногда (не каждый раз, как ни странно) оригинальные деревья также меняются.
Я предполагаю, что это как-то связано с тем, как я пытался копировать деревья, так как это единственное, что изменилось. Но я не могу сказать вам, почему он так поступает.
Итак, спасибо за чтение этого многословного вопроса.,, Я надеюсь, что вы можете помочь.:/
Вот мой сильно урезанный код, который демонстрирует мою проблему:
GPEnv.java ( gist)
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 ( суть)
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)
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);
}
}
2 ответа
Похоже, что вы не пытаетесь исправить родительские ссылки, когда вы делаете копию.
Представьте себе основное выражение 1+2. Когда вы копируете "+", скажем, id 22, вы создаете новый узел "+" с копиями двух его дочерних элементов и ссылкой на его исходного родителя (ноль). Скажем, исходный узел '1' имеет идентификатор 5, а недавно созданный узел '1' имеет идентификатор 18. Вы сохранили родительскую ссылку до 22, когда создавали новый узел '1', потому что при создании копии вы не делали пока есть доступ к новому родителю.
Выходом из этой проблемы при глубоком копировании круговых структур данных является предоставление специальной операции копирования, которая принимает нового родителя в качестве параметра. Глубокая копия должна вызывать эту специальную копию с неполным новым родительским узлом для каждого из его дочерних элементов.
Что-то вроде
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;
}
Node.copy() метод - вы могли бы назвать его Name.clone() а затем заставить весь класс реализовать Cloneable, Более того: вы клонируете и настраиваете детей, но забываете, что у этих детей будет новый родитель. После клонирования вы должны установить родителя на новые, например:
- клонировать детей,
- передать их частному конструктору только для клонов, который вызовет некоторые
setParent(this)метод.
Без этого вы просто создаете новые узлы, которые используют родительских клонированных узлов в качестве своих родительских, что может быть самой причиной того, что что-то идет не так.