Opened 3 years ago

Closed 2 years ago

#2307 closed defect (rejected)

Investigate problem with parents and SymbolicExpressionTreeBottomUpSimilarityCalculator

Reported by: ascheibe Owned by: gkronber
Priority: low Milestone: HeuristicLab 3.3.12
Component: Problems.DataAnalysis.Symbolic.Regression Version: 3.3.10
Keywords: Cc:

Description

If I use the SymbolicExpressionTreeBottomUpSimilarityCalculator together with the VOSGA branch I get exceptions because of a problem with parent relations in symbolic expression trees. Not sure if this is a problem in the algorithm or in the opertors.

Attachments (1)

SubtreeCrossover.cs.patch (880 bytes) - added by bburlacu 3 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 3 years ago by ascheibe

  • Owner changed from ascheibe to bburlacu
  • Status changed from new to assigned

comment:2 Changed 3 years ago by ascheibe

  • Milestone changed from HeuristicLab 3.3.12 to HeuristicLab 3.3.11

comment:3 Changed 3 years ago by bburlacu

  • Status changed from assigned to accepted

comment:4 Changed 3 years ago by bburlacu

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

The problem can be described as follows:

  • two parents P0 and P1 are selected for crossover
  • a subtree S from P1 is inserted into P0 as a child to node N, and S.Parent is set to N
  • as a consequence to the above operation, inside P1 the subtree S will have the wrong parent node
  • SymbolicExpressionTreeBottomUpSimilarityCalculator relies on the parent information to perform the bottom-up matching, and will fail when S.Parent does not point to the actual parent inside the tree (in the case of P1)

I attached a patch that fixes this problem by cloning the swapped subtree before inserting it into P0. Since this change affects an essential operator I would suggest assigning this ticket to one of the architects for review.

Changed 3 years ago by bburlacu

comment:5 Changed 3 years ago by gkronber

  • Owner changed from ascheibe to gkronber

Ok I will review this.

comment:6 Changed 3 years ago by gkronber

  • Milestone changed from HeuristicLab 3.3.11 to HeuristicLab 3.3.12

This error occurred when calculating the similarity of a child with it's parents directly after crossover. Usually, the parents are not used after crossover and immediately discarded. Since this occurs only for this particular case (VOSGA) and cloning might have effects (runtime) that cannot be estimated easily we decided to move this ticket to the next milestone.

comment:7 Changed 2 years ago by gkronber

  • Resolution set to rejected
  • Status changed from reviewing to closed

We discussed this and decided to close this without a fix.

In HeuristicLab solution candidates are already fully cloned by the parent selection operator. This is not strictly necessary because it would be possible to clone solutions by the crossover operator instead. In the case of symbolic expression trees only the parts remaining in the child need to be cloned. This kind of cloning would also fix the issue described in the ticket (and would prevent multiple cloning).

Note: See TracTickets for help on using tickets.