Замена поддерева в кроссовере
У меня проблема со школьным проектом, связанным с генетическим программированием.
Я использую метод пересечения поддеревьев, поэтому я должен выполнить эти шаги:
- Выберите случайный узел (точку вставки) из родительского дерева.
- Выберите случайное поддерево из материнского дерева.
- Замените точку вставки от отца на поддерево от матери.
Я почти уверен, что третий пункт не работает в моем коде. Я пробовал несколько разных подходов к этой проблеме ( глубокое копирование и замена поддеревьев в Java - это тоже), но ни один из них, похоже, не работает.
То, как я думал, это будет работать, это создать новое дерево с именем "child", которое будет копией родительского дерева, затем с помощью этого дерева найти случайный узел и просто заменить найденный узел поддеревом (так что де-факто узел тоже) из материнского дерева.
Я также пробовал искать деревья на предмет соответствия, явно обновляя родителей / детей, но все указывает на то, что это либо не решение, либо я делаю это неправильно.
Итак, я даю вам базовую версию моего кода; каждый намек на то, что не так с моим мышлением, высоко ценится.
TreeNode.java
public class TreeNode implements Iterable<TreeNode> {
protected Data data;
protected TreeNode parent;
protected List<TreeNode> children;
public static Long IDENTIFIER = 0L;
public double getValue(double xValue) {
return 0;
};
public boolean isRoot() {
return parent == null;
}
public boolean isLeaf() {
return children.size() == 0;
}
protected List<TreeNode> elementsIndex;
public TreeNode(Data data) {
this.data = data;
this.children = new LinkedList<TreeNode>();
this.elementsIndex = new LinkedList<TreeNode>();
this.elementsIndex.add(this);
this.data.setId(IDENTIFIER++);
if (this instanceof Function)
this.data.setChildAmount(2);
else if (this instanceof Terminal)
this.data.setChildAmount(0);
}
public TreeNode(Data data, TreeNode parent) {
this.parent = parent;
this.children = new LinkedList<TreeNode>();
this.elementsIndex = new LinkedList<TreeNode>();
this.elementsIndex.add(this);
this.data.setId(IDENTIFIER++);
if(this instanceof Function)
this.data.setChildAmount(2);
else if (this instanceof Terminal)
this.data.setChildAmount(0);
}
public TreeNode copyTree() {
TreeNode clone;
switch (this.getData().getType()) {
case 10:
clone = new Add(new Data(10));
break;
case 11:
clone = new Substract(new Data(11));
break;
case 12:
clone = new Multiply(new Data(12));
break;
case 13:
clone = new Divide(new Data(13));
break;
case 20:
clone = new Constant(new Data(20));
break;
case 21:
clone = new Variable(new Data(21));
break;
default:
return null;
}
clone.setData(this.getData());
clone.setParent(this.getParent());
clone.setChildren(this.getChildren());
clone.setElementsIndex(this.getElementsIndex());
return clone;
}
public TreeNode copy() {
return copyWithParent(parent);
}
public TreeNode copyWithParent(TreeNode parent) {
TreeNode out;
switch (this.getData().getType()) {
case 10:
out = new Add(new Data(10), parent);
break;
case 11:
out = new Substract(new Data(11), parent);
break;
case 12:
out = new Multiply(new Data(12), parent);
break;
case 13:
out = new Divide(new Data(13), parent);
break;
case 20:
out = new Constant(new Data(20), parent);
break;
case 21:
out = new Variable(new Data(21), parent);
break;
default:
return null;
}
if (!this.getChildren().isEmpty()) {
if (this.getChildren().get(0) != null) {
out.getChildren().get(0).copyWithParent(out);
}
if (this.getChildren().get(1) != null) {
out.getChildren().get(1).copyWithParent(out);
}
}
return out;
}
public TreeNode addChild(Data childType, TreeNode child) {
TreeNode childNode = child.copyTree();
childNode.parent = this;
this.children.add(childNode);
this.registerChildForSearch(childNode);
return childNode;
}
public int getLevel() {
if (this.isRoot())
return 0;
else
return parent.getLevel() + 1;
}
private TreeNode selectSubClass(Data data) {
switch (data.getType()) {
case 10:
return new Add(data);
case 11:
return new Substract(data);
case 12:
return new Multiply(data);
case 13:
return new Divide(data);
case 20:
return new Constant(data);
case 21:
return new Variable(data);
default:
return null;
}
}
private void registerChildForSearch(TreeNode node) {
elementsIndex.add(node);
if (parent != null)
parent.registerChildForSearch(node);
}
public TreeNode findTreeNode(Comparable<Data> cmp) {
for (TreeNode element : this.elementsIndex) {
Data elData = element.data;
if (cmp.compareTo(elData) == 0)
return element;
}
return null;
}
@Override
public String toString() {
return ((data != null) ? this.getData().toString() : "[null]");
}
public String printFunction() {
String left;
String right;
if (!this.getChildren().isEmpty()) {
left = this.getChildren().get(0).printFunction();
right = this.getChildren().get(1).printFunction();
return "(" + left + ")" + this.getData().toString() + "(" + right + ")";
}
return this.getData().toString();
}
@Override
public Iterator<TreeNode> iterator() {
TreeNodeIter iter = new TreeNodeIter(this);
return iter;
}
public Data getData() {
return data;
}
public void setData(Data data) {
this.data = data;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public List<TreeNode> getChildren() {
return children;
}
public void setChildren(List<TreeNode> children) {
this.children.addAll(children);
}
public List<TreeNode> getElementsIndex() {
return elementsIndex;
}
public void setElementsIndex(List<TreeNode> elementsIndex) {
this.elementsIndex = elementsIndex;
}
// Ghost Method - should be always overriden
public TreeNode chooseRandomChild() {
return null;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TreeNode other = (TreeNode) obj;
if (children == null) {
if (other.children != null)
return false;
} else if (!children.equals(other.children))
return false;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (elementsIndex == null) {
if (other.elementsIndex != null)
return false;
} else if (!elementsIndex.equals(other.elementsIndex))
return false;
if (parent == null) {
if (other.parent != null)
return false;
} else if (!parent.equals(other.parent))
return false;
return true;
}
}
Используемые методы из Chromosome.java
public TreeNode chooseRandomNode(TreeNode remainingSubtree, boolean isInitial, int chosenMaxLevel,
int currentLevel) {
int maxLevel = 0;
TreeNode chosenNode = remainingSubtree.getParent();
if (isInitial) {
// if method was called on tree with single node
if (remainingSubtree instanceof Terminal)
return remainingSubtree;
this.treeHeight = countTreeDepth(this.getSchema());
Random random = new Random();
maxLevel = random.nextInt(treeHeight) + 1;
} else {
maxLevel = chosenMaxLevel;
}
if (currentLevel < maxLevel) {
TreeNode temp = remainingSubtree.chooseRandomChild();
if (temp instanceof Function)
chosenNode = chooseRandomNode(temp, false, maxLevel, currentLevel + 1);
else
chosenNode = temp;
}
return chosenNode;
}
public int countTreeDepth(TreeNode node) {
if (node.equals(null)) {
return 0;
}
if (!node.getChildren().isEmpty()) {
int leftChild = countTreeDepth(node.getChildren().get(0));
int rightChild = countTreeDepth(node.getChildren().get(1));
return (leftChild > rightChild) ? leftChild + 1 : rightChild + 1;
}
return 1;
}
Метод кроссовера из Genetics.java
public static Chromosome crossover(Chromosome father, Chromosome mother) {
TreeNode child = father.getSchema();
TreeNode insertionPoint = father.chooseRandomNode(child, true, 0, 0);
TreeNode temp = insertionPoint.copy();
TreeNode motherSubTree = mother.chooseRandomNode(mother.getSchema(), true, 0, 0);
insertionPoint = motherSubTree.copyTree();
Chromosome offspring = new Chromosome();
offspring.copyIndividual(child);
return offspring;
}
Вот ссылка на наше репозиторий github со всем проектом: https://github.com/Nevaan/symbolic_regression
1 ответ
Возможно, это слишком поздно для вашего школьного проекта, но публикация ответа на случай, если он поможет кому-то с подобной проблемой:
Проблема заключается в методе CrossOver: переменная child начинается с копии схемы отца. Затем вы создаете переменную "inserttionPoint", указывающую на поддерево, которое вы хотите заменить. Но затем, когда вы присваиваете "motherSubtree" этой переменной, вы на самом деле просто заменяете локальную переменную в методе, а не поддерево в объекте. Вам на самом деле нужно "вставить" копию "motherSubtree" в новое дерево после его создания.