Opened 11 months ago

Closed 3 months ago

#2647 closed defect (done)

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

Reported by: bburlacu Owned by: mkommend
Priority: medium Milestone: HeuristicLab 3.3.15
Component: Encodings.SymbolicExpressionTreeEncoding Version: 3.3.14
Keywords: Cc:

Description (last modified by 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.

Change History (6)

comment:1 Changed 11 months ago by bburlacu

  • Description modified (diff)
  • Status changed from new to accepted

comment:2 Changed 11 months ago by bburlacu

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

comment:3 Changed 11 months ago by bburlacu

  • Owner changed from bburlacu to mkommend
  • Status changed from accepted to reviewing

r14223: Fix logical mistake.

comment:4 Changed 11 months ago by bburlacu

r14224: Remove obsolete comment.

comment:5 Changed 11 months ago by mkommend

  • Status changed from reviewing to readytorelease

Reviewed r14221, r14223, r14224.

comment:6 Changed 3 months ago by mkommend

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.