Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
09/23/14 17:08:59 (10 years ago)
Author:
bburlacu
Message:

#1772: Simplified fragment tracing code in the before/after manipulation operators.

Location:
branches/HeuristicLab.EvolutionTracking
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking/3.4/Operators/BeforeManipulatorOperator.cs

    r11383 r11387  
    5353    public override IOperation Apply() {
    5454      // since mutation always takes place after crossover, the vertex for the current child is already in the tree
    55       var childVertex = (IGenealogyGraphNode<T>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
     55      var childVertex = GenealogyGraph.GetByContent(ChildParameter.ActualValue);
    5656      var clonedVertex = (IGenealogyGraphNode<T>)childVertex.Clone();
    5757      clonedVertex.Rank = childVertex.Rank - 0.5;
     
    6464        GenealogyGraph.AddArc(new GenealogyGraphArc(p, clonedVertex));
    6565      }
    66       clonedVertex.InArcs.Last().Data = arcs.Last().Data; // preserve fragment data
     66      // by convention, the arc connecting child with parent (non-root parent in case of crossover)
     67      // holds fragment data when applicable. the following line of code preserves this data
     68      // the graph arcs are now connecting parent (rank n) --> clone (rank n+0.5) --> child (rank n+1)
     69      clonedVertex.InArcs.Last().Data = arcs.Last().Data;
    6770      GenealogyGraph.AddArc(new GenealogyGraphArc(clonedVertex, childVertex));
    6871
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionAfterManipulatorOperator.cs

    r11253 r11387  
    2020#endregion
    2121
    22 using System;
    23 using System.Collections.Generic;
    2422using System.Linq;
    2523using HeuristicLab.Core;
     
    3028  public class SymbolicDataAnalysisExpressionAfterManipulatorOperator : AfterManipulatorOperator<ISymbolicExpressionTree> {
    3129    public override IOperation Apply() {
    32       var childVertex = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
    33       var nodesBefore = (List<ISymbolicExpressionTreeNode>)childVertex.InArcs.First().Data;
    34       var nodesAfter = ChildParameter.ActualValue.IterateNodesPrefix().ToList();
    35       IFragment<ISymbolicExpressionTreeNode> fragment = null;
    36 
    37       // try to find if a subtree was replaced by comparing references
    38       for (int i = 0; i < Math.Min(nodesBefore.Count, nodesAfter.Count); ++i) {
    39         if (nodesAfter[i] != nodesBefore[i]) {
    40           fragment = new Fragment<ISymbolicExpressionTreeNode> {
    41             Root = nodesAfter[i],
    42             Index1 = i,
    43             Index2 = i
    44           };
    45         }
    46       }
    47       // if the fragment could not be identified by reference comparison, we try to identify it by comparing node labels
    48       // the fragment root will be the lowest common ancestor of all the differing nodes
    49       if (fragment == null) {
    50         var list = new List<ISymbolicExpressionTreeNode>();
    51         var root = ChildParameter.ActualValue.Root;
    52 
    53         for (int i = 0; i < Math.Min(nodesBefore.Count, nodesAfter.Count); ++i) {
    54           var a = nodesAfter[i];
    55           var b = nodesBefore[i];
    56 
    57           if (!Equals(a.ToString(), b.ToString())) // label comparison is sufficient
    58             list.Add(a);
    59         }
    60 
    61         var lca = LowestCommonAncestor(root, list);
    62         int index = nodesAfter.IndexOf(lca);
    63         fragment = new Fragment<ISymbolicExpressionTreeNode> {
    64           Root = lca,
    65           Index1 = index,
    66           Index2 = index
    67         };
    68       }
    69 
    70       if (fragment == null)
    71         throw new ArgumentNullException("Could not identify fragment.");
    72 
    73       childVertex.InArcs.First().Data = fragment;
     30      var child = ChildParameter.ActualValue;
     31      var childVertex = GenealogyGraph.GetByContent(child);
     32      var parent = childVertex.Parents.First().Data;
     33      var subtree = child.Difference(parent);
     34      int index = child.IterateNodesPrefix().TakeWhile(node => node != subtree).Count();
     35      var fragment = new Fragment<ISymbolicExpressionTreeNode> { Root = subtree, Index1 = index, Index2 = index };
     36      childVertex.InArcs.Last().Data = fragment;
    7437      return base.Apply();
    75     }
    76 
    77     private static ISymbolicExpressionTreeNode LowestCommonAncestor(ISymbolicExpressionTreeNode root, List<ISymbolicExpressionTreeNode> nodes) {
    78       if (nodes.Count == 0)
    79         throw new ArgumentException("The nodes list should contain at least one element.");
    80 
    81       if (nodes.Count == 1)
    82         return nodes[0];
    83 
    84       int lowestLevel = nodes.Min(x => root.GetBranchLevel(x));
    85 
    86       // bring the nodes in the nodes to the same level (relative to the root)
    87       for (int i = 0; i < nodes.Count; ++i) {
    88         var node = nodes[i];
    89         var level = root.GetBranchLevel(node);
    90         for (int j = lowestLevel; j < level; ++j)
    91           node = node.Parent;
    92         nodes[i] = node;
    93       }
    94 
    95       // while not all the elements in the nodes are equal, go one level up
    96       while (nodes.Any(x => x != nodes[0])) {
    97         for (int i = 0; i < nodes.Count; ++i)
    98           nodes[i] = nodes[i].Parent;
    99       }
    100 
    101       return nodes[0];
    10238    }
    10339  }
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs

    r11253 r11387  
    2828  public class SymbolicDataAnalysisExpressionBeforeManipulatorOperator : BeforeManipulatorOperator<ISymbolicExpressionTree> {
    2929    public override IOperation Apply() {
    30       var result = base.Apply(); // add the vertex in the genealogy graph
    31 
    32       var vChild = (IGenealogyGraphNode<ISymbolicExpressionTree>)GenealogyGraph.GetByContent(ChildParameter.ActualValue);
     30      // the call below does the following things:
     31      // 1) creates a clone of the individual to be manipulated, and adds it in the genealogy graph with rank = currentRank - 0.5.
     32      //    the cloning will also clone the vertex data object, therefore reference comparison of node lists will not work
     33      // 2) replaces the parent of the current individual with the clone, and alters graph connections accordingly
     34      //    therefore, vChild will be the vertex of the child, and vClone the vertex of the cloned parent
     35      var result = base.Apply();
     36      var vChild = GenealogyGraph.GetByContent(ChildParameter.ActualValue);
    3337      var vClone = vChild.Parents.Last();
    34       vChild.InArcs.First().Data = vClone.Data.IterateNodesPrefix().ToList();
    3538
    3639      var fragment = (IFragment<ISymbolicExpressionTreeNode>)vClone.InArcs.Last().Data;
    3740      if (fragment != null) {
    3841        // this step must be performed because the fragment root actually references the original child (not the clone).
    39         // then, a mutation operation (acting on the original child), could disrupt it
     42        // when mutation occurs the fragment root would point to the mutated subtree in the child instead of the original one in the clone
    4043        fragment.Root = vClone.Data.IterateNodesPrefix().ElementAt(fragment.Index1);
    4144      }
Note: See TracChangeset for help on using the changeset viewer.