Crossover does not remove swapped subtrees from the non-root parent

[bburlacu]

The standard subtree crossover in HeuristicLab acts in-place, replacing a subtree from the first (root) parent with another subtree from the second (non-root) parent.

The issue is that the replacement subtree is added to the structure of the first parent (adjusting child and parent links accordingly within the tree), but it is not removed from the list of children of its parent node in the second parent.

We were able to identify a concrete use-case where this becomes a real problem, in combination with the serialization/deserialization logic for symbolic expression trees. The conditions where this problem appears are described below:

1) The issue with crossover described above leaves some trees in the population in an inconsistent state. Trees involved in crossover as non-root parents still contain in their strucure subtrees that were actually supposed to be swapped.

2) The algorithm is paused and then saved/serialized, for example on the Hive when runs are paused/moved to slaves.

3) Parent links in symbolic expression tree nodes are not explicitly serialized, but they are recreated during deserialization.

4) During deserialization, some subtrees are referenced correctly from within the structure of their correct actual containing trees, while they are also referenced incorrectly from within the structure of fake parents (non-root parents from which crossover "forgot" to remove the reference/remove the subtree from the list of subtrees of its old parent node).

5) Since trees are deserialized in an unspecified order, and node-parent links are recreated during deserialization, this results in inconsistent parent links for some nodes.

6) Inconsistent parent links cause an exception in the bottom-up tree similarity calculator, which is the only operator in HeuristicLab which actually makes use of the node parent property.

Solution A fix for this problem could be achieved by either ensuring structural consistency (eg, by cloning the swapped subtree or simply removing it from the non-root parent before putting it in the root parent), or by explicitly adding the [Storable] attribute to the parent member of SymbolicExpressionTreeNode. The goal is to come up with a fix that will not change the behavior and reproducibility of old experiments.

[bburlacu]

r14221: Addressed the issue described above by adding the [Storable] attribute to the SymbolicExpressionTreeNode parent member, and cloning the swapped subtree during crossover.

[bburlacu]

r14223: Fix logical mistake.

[bburlacu]

r14224: Remove obsolete comment.

[mkommend]

Reviewed r14221, r14223, r14224.