Changeset 8557


Ignore:
Timestamp:
09/03/12 15:26:04 (7 years ago)
Author:
bburlacu
Message:

#1772: Introduced base class and interface for tracing operators. Introduced SymbolicExpressionTreeNodeComparer interface to be implemented by node matching operators. Fixed bug in the TracingSymbolicExpressionTreeManipulator where nodes modified by the Full- and OnePoint tree shakers were not correctly detected. The SymbolicExpressionTreeNodeSimilarityComparer is now injected in the tracing genetic operators as a parameter.

Location:
branches/HeuristicLab.EvolutionaryTracking
Files:
3 added
13 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/TracingSymbolicExpressionTreeCrossover.cs

    r8213 r8557  
    2828using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2929
    30 using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
    31 using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
    32 
    3330namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3431  /// <summary>
     
    3734  [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
    3835  [StorableClass]
    39   public abstract class TracingSymbolicExpressionTreeCrossover : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
     36  public abstract class TracingSymbolicExpressionTreeCrossover : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeCrossover {
    4037    private const string ParentsParameterName = "Parents";
    4138    private const string ChildParameterName = "Child";
    42     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
    43     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
    44     private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
     39
    4540
    4641    #region Parameter Properties
     
    5045    public ILookupParameter<ISymbolicExpressionTree> ChildParameter {
    5146      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[ChildParameterName]; }
    52     }
    53     public LookupParameter<CloneMapType> GlobalCloneMapParameter {
    54       get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
    55     }
    56     public LookupParameter<TraceMapType> GlobalTraceMapParameter {
    57       get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
    58     }
    59     public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
    60       get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
    6147    }
    6248    #endregion
     
    7056      set { ChildParameter.ActualValue = value; }
    7157    }
    72     public CloneMapType GlobalCloneMap {
    73       get { return GlobalCloneMapParameter.ActualValue; }
    74     }
    75     public TraceMapType GlobalTraceMap {
    76       get { return GlobalTraceMapParameter.ActualValue; }
    77     }
    78     public CloneMapType GlobalFragmentMap {
    79       get { return GlobalFragmentMapParameter.ActualValue; }
    80     }
    8158    #endregion
    8259
     
    8562      : base(deserializing) {
    8663    }
    87 
    8864    protected TracingSymbolicExpressionTreeCrossover(TracingSymbolicExpressionTreeCrossover original, Cloner cloner)
    8965      : base(original, cloner) {
    9066    }
    91 
    9267    protected TracingSymbolicExpressionTreeCrossover()
    9368      : base() {
    9469      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(ParentsParameterName, "The parent symbolic expression trees which should be crossed."));
    9570      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(ChildParameterName, "The child symbolic expression tree resulting from the crossover."));
    96       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
    97       Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
    98       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
     71
    9972    }
    100 
    10173    public sealed override IOperation Apply() {
    10274      if (Parents.Length != 2)
    10375        throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
    10476
    105       // add global trace cache if not already present in global scope
    106       var gScope = ExecutionContext.Scope;
    107       while (gScope.Parent != null)
    108         gScope = gScope.Parent;
    109       if (GlobalTraceMap == null)
    110         gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
    111       if (GlobalFragmentMap == null)
    112         gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
    113 
    114       // get original parents (this info will be needed later to construct the genealogy graph)
    115       var originalParents = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x]));
     77      AddTracingVariablesToGlobalScope();
    11678
    11779      // save the nodes of parent0 in a list so we can track what modifications are made by crossover
     
    12486      var nodes1 = Child.IterateNodesBreadth().ToList();
    12587
    126       // compare the two nodes lists and check the difference (comparing node references so we avoid false functional identity).
    127       // if no difference is found, then it is assumed that the whole tree was swapped with itself (it can happen), so the index is 0
    128       int i, min = Math.Min(nodes0.Count, nodes1.Count);
    129       for (i = 0; i != min; ++i)
    130         if (nodes0[i] != nodes1[i]) break;
     88      // compare the two node lists and check the difference (comparing node references so we avoid false functional identity).
     89      int i = 0, min = Math.Min(nodes0.Count, nodes1.Count);
     90      while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
     91
    13192      // add heredity information into the global variables
    132       GlobalTraceMap[Child] = originalParents; // map child to its corresponding parents from the previous generation
    133       GlobalFragmentMap[Child] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]); // map child to the index of its fragment
     93      GlobalTraceMap[Child] = new ItemList<IItem>(Parents.Select(x => GlobalCloneMap[x])); ; // map child to its corresponding parents from the previous generation
     94      GlobalFragmentMap[Child] = new GenericWrapper<ISymbolicExpressionTreeNode>(i == min ? null : nodes1[i]); // map child to the index of its fragment
    13495      return base.Apply();
    13596    }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/GenericWrapper.cs

    r8213 r8557  
    66  [Item("Generic wrapper", "Wrapper class for non-item HeuristicLab objects")]
    77  [StorableClass]
    8   public class GenericWrapper<T> : NamedItem where T : class {
     8  public class GenericWrapper<T> : NamedItem where T : class, IDeepCloneable {
     9    [Storable]
    910    public T Content { get; private set; }
    10 
    11     private GenericWrapper() {
    12     }
    1311
    1412    public GenericWrapper(T content) {
     
    1715
    1816    [StorableConstructor]
    19     protected GenericWrapper(bool serializing)
    20       : base(serializing) {
    21     }
     17    private GenericWrapper(bool serializing) : base(serializing) { }
    2218
    2319    private GenericWrapper(GenericWrapper<T> original, Cloner cloner)
    2420      : base(original, cloner) {
     21      this.Content = cloner.Clone(Content);
    2522    }
    2623
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r8213 r8557  
    167167    <Compile Include="Compiler\SymbolicExpressionTreeCompiler.cs" />
    168168    <None Include="Plugin.cs.frame" />
     169    <Compile Include="Interfaces\Operators\ITracingSymbolicExpressionTreeOperator.cs" />
     170    <Compile Include="TracingSymbolicExpressionTreeOperator.cs" />
    169171    <Compile Include="Creators\TracingSymbolicExpressionTreeCreator.cs" />
    170172    <Compile Include="Creators\FullTreeCreator.cs">
     
    181183    <Compile Include="Interfaces\ISymbolicExpressionGrammarBase.cs" />
    182184    <Compile Include="Interfaces\ISymbolicExpressionTreeGrammar.cs" />
     185    <Compile Include="Interfaces\ISymbolicExpressionTreeNodeComparer.cs" />
    183186    <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeArchitectureAlteringOperator.cs" />
    184187    <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeGrammarBasedOperator.cs" />
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs

    r8213 r8557  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using HeuristicLab.Common;
     
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2930
    30 using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
    31 using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
    32 
    3331namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3432  /// <summary>
     
    3735  [Item("TracingSymbolicExpressionTreeManipulator", "A base class for operators that manipulate symbolic expression trees.")]
    3836  [StorableClass]
    39   public abstract class TracingSymbolicExpressionTreeManipulator : SymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
     37  public abstract class TracingSymbolicExpressionTreeManipulator : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
    4038    private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
    41     private const string GlobalTraceMapParameterName = "GlobalTraceMap";
    42     private const string GlobalCloneMapParameterName = "GlobalCloneMap";
    43     private const string GlobalFragmentMapParameterName = "GlobalFragmentMap";
    4439
    4540    #region Parameter Properties
    4641    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
    4742      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SymbolicExpressionTreeParameterName]; }
    48     }
    49     public LookupParameter<CloneMapType> GlobalCloneMapParameter {
    50       get { return (LookupParameter<CloneMapType>)Parameters[GlobalCloneMapParameterName]; }
    51     }
    52     public LookupParameter<TraceMapType> GlobalTraceMapParameter {
    53       get { return (LookupParameter<TraceMapType>)Parameters[GlobalTraceMapParameterName]; }
    54     }
    55     public LookupParameter<CloneMapType> GlobalFragmentMapParameter {
    56       get { return (LookupParameter<CloneMapType>)Parameters[GlobalFragmentMapParameterName]; }
    5743    }
    5844    #endregion
     
    6147    public ISymbolicExpressionTree SymbolicExpressionTree {
    6248      get { return SymbolicExpressionTreeParameter.ActualValue; }
    63     }
    64     public CloneMapType GlobalCloneMap {
    65       get { return GlobalCloneMapParameter.ActualValue; }
    66     }
    67     public TraceMapType GlobalTraceMap {
    68       get { return GlobalTraceMapParameter.ActualValue; }
    69     }
    70     public CloneMapType GlobalFragmentMap {
    71       get { return GlobalFragmentMapParameter.ActualValue; }
    7249    }
    7350    #endregion
     
    7956      : base() {
    8057      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree on which the operator should be applied."));
    81       Parameters.Add(new LookupParameter<CloneMapType>(GlobalCloneMapParameterName, "A global map keeping track of trees and their clones (made during selection)."));
    82       Parameters.Add(new LookupParameter<TraceMapType>(GlobalTraceMapParameterName, "A global cache containing tracing info."));
    83       Parameters.Add(new LookupParameter<CloneMapType>(GlobalFragmentMapParameterName, "A global map keeping track of tree fragments received via crossover."));
    8458    }
    8559
     
    8761      ISymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
    8862
    89       var gScope = ExecutionContext.Scope;
    90       while (gScope.Parent != null)
    91         gScope = gScope.Parent;
     63      AddTracingVariablesToGlobalScope();
    9264
    93       if (GlobalTraceMap == null)
    94         gScope.Variables.Add(new Variable(GlobalTraceMapParameterName, new TraceMapType()));
    95       if (GlobalFragmentMap == null)
    96         gScope.Variables.Add(new Variable(GlobalFragmentMapParameterName, new CloneMapType()));
    97 
    98       int i = 0;
     65      /* The following block needs to be explained in more detail;
     66       * If the tree was already affected by crossover (before mutation), then:
     67       * - it will already be contained in the GlobalTraceMap
     68       * - In order to preserve information, a clone of the tree is created
     69       * - The clone represents the intermediate stage of the tree, before mutation is applied
     70       * - The clone therefore represents the child after crossover so GlobalTraceMap[clone] will get tree's parents
     71       *   and GlobalFragmentMap[clone] will get the subtree from clone that represents the cloned fragment
     72       * - After tree is mutated, we set GlobalTraceMap[tree] = clone and GlobalFragmentMap[tree] = modified node from tree
     73       */
     74      ISymbolicExpressionTreeNode fragment;
    9975      if (GlobalTraceMap.ContainsKey(tree)) {
    100         // tree was affected by crossover before mutation
    101         // if the tree to be manipulated is already a product of crossover (in the current reproduction phase),
    102         // then there exists no relationship with the original "parent".
    103         // In order to preserve information, a tree clone is created before mutation and added to the trace map.
    104         var clone = (IItem)tree.Clone();
     76        var clone = (IItem)tree.Clone(); // create clone of tree
    10577        GlobalTraceMap[clone] = GlobalTraceMap[tree]; // clone gets parents of tree
    10678        GlobalTraceMap[tree] = new ItemList<IItem> { clone }; // tree gets clone as parent
    107         var nodes = tree.IterateNodesBreadth().ToList();
    108         for (i = 0; i != nodes.Count; ++i) {
    109           if ((GlobalFragmentMap[tree] as GenericWrapper<SymbolicExpressionTreeNode>).Content == nodes[i]) break;
     79        fragment = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[tree]).Content;
     80        int index = tree.IterateNodesBreadth().ToList().IndexOf(fragment); // returns -1 if fragment is not present in tree
     81        GlobalFragmentMap[clone] = new GenericWrapper<ISymbolicExpressionTreeNode>(index == -1 ? null : ((ISymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(index));
     82      } else {
     83        GlobalTraceMap[tree] = new ItemList<IItem> { GlobalCloneMap[tree] };
     84      }
     85
     86      var original = GlobalCloneMap[tree];
     87      var nodes0 = ((ISymbolicExpressionTree)original).IterateNodesBreadth().ToList();
     88
     89      // perform mutation
     90      Manipulate(RandomParameter.ActualValue, tree);
     91
     92      var nodes1 = tree.IterateNodesBreadth().ToList();
     93
     94      int min = Math.Min(nodes0.Count, nodes1.Count);
     95      // some tree manipulators only change local parameters while the actual node stays the same
     96      // consequently, we need a stronger comparison than ReferenceEquals
     97      var comp = SymbolicExpressionTreeNodeComparer;
     98      if (comp == null)
     99        throw new Exception(Name + ": Could not get SymbolicExpressionTreeNodeComparerParameter!");
     100      var mismatches = new List<int>();
     101      for (int i = 0; i != min; ++i) {
     102        if (!comp.Equals(nodes0[i], nodes1[i])) {
     103          mismatches.Add(i);
    110104        }
    111         var fragment = (SymbolicExpressionTreeNode)(((SymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(i));
    112         GlobalFragmentMap[clone] = new GenericWrapper<SymbolicExpressionTreeNode>(fragment);
    113       } else {
    114         var original = GlobalCloneMap[tree];
    115         GlobalTraceMap[tree] = new ItemList<IItem> { original };
    116105      }
    117       var nodes0 = tree.IterateNodesBreadth().ToList();
    118       Manipulate(RandomParameter.ActualValue, tree);
    119       var nodes1 = tree.IterateNodesBreadth().ToList();
    120       int min = Math.Min(nodes0.Count, nodes1.Count);
    121       for (i = 0; i != min; ++i)
    122         if (nodes0[i] != nodes1[i]) break;
    123       GlobalFragmentMap[tree] = new GenericWrapper<SymbolicExpressionTreeNode>(i == min ? null : (SymbolicExpressionTreeNode)nodes1[i]);
     106      if (mismatches.Count == 0) // should never happen
     107        fragment = null;
     108      else
     109        fragment = mismatches.Count > 1 ? nodes1[mismatches[0]].Parent : nodes1[mismatches[0]];
     110      GlobalFragmentMap[tree] = new GenericWrapper<ISymbolicExpressionTreeNode>(fragment);
    124111      return base.Apply();
    125112    }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeFragmentsAnalyzer.cs

    r8213 r8557  
    3333using HeuristicLab.Problems.DataAnalysis;
    3434using HeuristicLab.Problems.DataAnalysis.Symbolic;
     35// type definitions for convenience
    3536using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
    36 // type definitions for convenience
    3737using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
    38 using SymbolicExpressionTreeNodeItem = HeuristicLab.EvolutionaryTracking.GenericWrapper<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode>;
     38using SymbolicExpressionTreeNodeItem = HeuristicLab.EvolutionaryTracking.GenericWrapper<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
    3939using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
    4040
     
    4747  [StorableClass]
    4848  public sealed class SymbolicExpressionTreeFragmentsAnalyzer : SingleSuccessorOperator, IAnalyzer {
     49    #region Parameter names
    4950    private const string UpdateIntervalParameterName = "UpdateInterval";
    5051    private const string UpdateCounterParameterName = "UpdateCounter";
     
    6263    private const string FragmentLengthsDistributionParametersName = "FragmentLengths";
    6364    private const string FragmentFrequenciesParameterName = "FragmentFrequencies";
     65    private const string ParentsDiversityParameterName = "ParentsDiversity";
     66    #endregion
    6467
    6568    // impact values calculator
    66     private SymbolicRegressionSolutionValuesCalculator _calculator = new SymbolicRegressionSolutionValuesCalculator();
     69    private readonly SymbolicRegressionSolutionValuesCalculator calculator = new SymbolicRegressionSolutionValuesCalculator();
    6770
    6871    #region Parameter properties
     
    97100    public LookupParameter<DataTable> FragmentLengthsParameter {
    98101      get { return (LookupParameter<DataTable>)Parameters[FragmentLengthsDistributionParametersName]; }
     102    }
     103    public LookupParameter<DataTable> ParentsDiversityParameter {
     104      get { return (LookupParameter<DataTable>)Parameters[ParentsDiversityParameterName]; }
    99105    }
    100106    // auxiliary structures for tracking fragments and individuals from the previous generation
     
    165171      get { return FragmentFrequenciesParameter.ActualValue; }
    166172    }
     173    public DataTable ParentsDiversity {
     174      get { return ParentsDiversityParameter.ActualValue; }
     175    }
    167176    public SymbolicDataAnalysisExpressionTreeInterpreter SymbolicExpressionInterpreter {
    168177      get { return SymbolicExpressionInterpreterParameter.ActualValue; }
     
    174183
    175184    [StorableConstructor]
    176     private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing)
    177       : base() {
    178     }
    179     private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner)
    180       : base(original, cloner) {
    181     }
     185    private SymbolicExpressionTreeFragmentsAnalyzer(bool deserializing) : base(deserializing) { }
     186    private SymbolicExpressionTreeFragmentsAnalyzer(SymbolicExpressionTreeFragmentsAnalyzer original, Cloner cloner) : base(original, cloner) { }
    182187    public override IDeepCloneable Clone(Cloner cloner) {
    183188      return new SymbolicExpressionTreeFragmentsAnalyzer(this, cloner);
     
    185190    public SymbolicExpressionTreeFragmentsAnalyzer()
    186191      : base() {
     192      #region Add parameters
    187193      // analyzer update counter and update interval
    188194      Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
     
    196202      Parameters.Add(new LookupParameter<CloneMapType>(SecondaryCloneMapParameterName, "Parameter to store the clone map from the previous generation"));
    197203      Parameters.Add(new LookupParameter<CloneMapType>(SecondaryFragmentMapParameterName, "Parameter to store the fragment map from the previous generation"));
    198       // other params
     204      // fragment statistics parameters
    199205      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
    200206      Parameters.Add(new LookupParameter<IntValue>(GenerationsParameterName, "The number of generations so far."));
     
    202208      Parameters.Add(new LookupParameter<DataTable>(FragmentLengthsDistributionParametersName, "The data table to store the distribution of fragment lengths."));
    203209      Parameters.Add(new LookupParameter<DataTable>(FragmentFrequenciesParameterName, "A data structure for fragment frequencies"));
     210      Parameters.Add(new LookupParameter<DataTable>(ParentsDiversityParameterName, "A data structure to store the diversity of the parents per generation."));
    204211      // impact calculation
    205212      Parameters.Add(new LookupParameter<SymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicExpressionInterpreterParameterName, "Interpreter for symbolic expression trees"));
    206213      Parameters.Add(new LookupParameter<RegressionProblemData>(SymbolicRegressionProblemDataParameterName, "The symbolic data analysis problem."));
     214      #endregion
     215
    207216      UpdateCounterParameter.Hidden = true;
    208217      UpdateIntervalParameter.Hidden = true;
    209 
    210       //_calculator = new SymbolicRegressionSolutionValuesCalculator();
    211218    }
    212219    #region After deserialization code
     
    230237        Parameters.Add(new LookupParameter<ItemList<ItemList<IItem>>>(FragmentFrequenciesParameterName, "A data structure for fragment frequencies"));
    231238      }
     239      if (!Parameters.ContainsKey(ParentsDiversityParameterName)) {
     240        Parameters.Add(new LookupParameter<DataTable>(ParentsDiversityParameterName, "A data table to store the diversity of the parents per generation."));
     241      }
    232242    }
    233243    #endregion
     
    244254    #endregion
    245255
     256    /* A small description of the way this analyzer works
     257     *
     258     * We keep 3 maps in the global scope: the GlobalTraceMap, the GlobalFragmentMap and the GlobalCloneMap that are updated on each step: selection, crossover, mutation
     259     * These maps provide information about the children, parents and transferred fragments as follows:
     260     *
     261     * 1) GlobalCloneMap
     262     *    This data structure provides the basis for tracking. In the selection step, every selected individual gets cloned and transferred into the recombination pool.
     263     *    The GlobalCloneMap keeps track of clones by mapping them to the original individuals. This is an essential step for building the genealogy graph. Using this
     264     *    structure we can find out how many times each individual was selected.
     265     *    The GlobalCloneMap consists of Key-Value pairs Clone->Original
     266     *
     267     * 2) GlobalTraceMap
     268     *    Keeps information in the form of key-value pairs Child->{Parents}, where {Parents} is a set consisting of
     269     *      - one parent individual (in the case of mutation), by language abuse we say that the individual that mutation acted on is the parent,
     270     *        and the resulting individual is the child
     271     *      - two parent individuals (in the case of crossover), named Parent0 and Parent1. Parent0 is the individual that crossover acts on by replacing
     272     *        one of its subtrees with a compatible subtree, randomly selected from Parent1
     273     *
     274     *    CROSSOVER
     275     *        Parent0     Parent1                                                                    {Parents}
     276     *           \           /                                                                           ^
     277     *            \       fragment (inserted from Parent1 into Parent0 to create the Child)              ^    [Mapping provided by the GlobalTraceMap]
     278     *             \       /                                                                             ^
     279     *              \     /                                                                              ^
     280     *               Child                                                                             Child
     281     *               
     282     *    MUTATION
     283     *        Parent0
     284     *           |
     285     *           |    [mutation acts on a random node/subtree in the 'parent' individual
     286     *           |
     287     *         Child
     288     *         
     289     *    Since crossover and mutation act on individuals in the recombination pool (which in fact are clones of individuals from the previous generation), the GlobalTraceMap
     290     *    is populated with values given by the mappings in the GlobalCloneMap, so that the original parent for each child is known.
     291     *   
     292     *  3) GlobalFragmentMap
     293     *     Keeps information in the form of Key-Value pairs about an individual and its respective fragment
     294     *     (ie., the subtree received via crossover or created/altered by mutation)
     295     * */
    246296    public override IOperation Apply() {
    247       if (Generations.Value == 0) return base.Apply();
    248297      UpdateCounter.Value++;
    249298      if (UpdateCounter.Value == UpdateInterval.Value) {
    250         ResultCollection results = ResultsParameter.ActualValue;
    251         if (FragmentStatistics == null) {
    252           FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
    253           FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
    254           results.Add(new Result("Fragment Statistics", FragmentStatistics));
     299        UpdateCounter.Value = 0; // reset counter
     300        if (Generations.Value > 0) {
     301          InitializeParameters();
     302
     303          CalculateFragmentStatistics();
     304
     305          // save the current generation so it can be compared to the following one, next time the analyzer is applied
     306          SecondaryTraceMap = (TraceMapType)GlobalTraceMap.Clone();
     307          SecondaryTraceMap.Clear();
     308          foreach (var m in GlobalTraceMap)
     309            SecondaryTraceMap.Add(m.Key, m.Value);
     310
     311          SecondaryCloneMap.Clear();
     312          foreach (var m in GlobalCloneMap)
     313            SecondaryCloneMap.Add(m.Key, m.Value);
     314
     315          SecondaryFragmentMap.Clear();
     316          foreach (var m in GlobalFragmentMap)
     317            SecondaryFragmentMap.Add(m.Key, m.Value);
    255318        }
    256         if (FragmentLengths == null) {
    257           FragmentLengthsParameter.ActualValue = new DataTable("Fragment Lengths", "Histograms for the distribution of fragment and individual lengths");
    258           FragmentLengths.VisualProperties.YAxisTitle = "Frequency";
    259           results.Add(new Result("Fragment Lengths", FragmentLengths));
    260         }
    261         if (FragmentFrequencies == null) {
    262           FragmentFrequenciesParameter.ActualValue = new DataTable("Fragment Frequencies", "Frequencies of good and high impact fragments");
    263           FragmentFrequencies.VisualProperties.YAxisTitle = "Frequency";
    264           results.Add(new Result("Fragment Frequencies", FragmentFrequencies));
    265         }
    266         if (SecondaryTraceMap == null) {
    267           SecondaryTraceMap = new TraceMapType();
    268         }
    269         if (SecondaryCloneMap == null) {
    270           SecondaryCloneMap = new CloneMapType();
    271         }
    272         if (SecondaryFragmentMap == null) {
    273           SecondaryFragmentMap = new CloneMapType();
    274         }
    275 
    276         UpdateCounter.Value = 0; // reset counter
    277         var gScope = ExecutionContext.Scope;
    278         while (gScope.Parent != null) gScope = gScope.Parent;
    279 
    280         // for this kind of tracking/analysis, we need at least 2 successive generations of crossover
    281         if (Generations.Value > 1) {
    282           #region Fragment Statistics
    283           InitializeRows();
    284           // create a dictionary for fast lookup of parents (to see which children from the previous generation become parents, and count their fragments)
    285           var parentsLookup = new Dictionary<ISymbolicExpressionTree, bool>();
    286           foreach (var parent in GlobalTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>())) {
    287             if (!parentsLookup.ContainsKey(parent)) {
    288               parentsLookup.Add(parent, true);
    289             }
    290           }
    291           // the same, for fast lookup of clones (might not be needed after all)
    292           var clonesLookup = new Dictionary<ISymbolicExpressionTree, bool>();
    293           foreach (var original in GlobalCloneMap.Values.Cast<ISymbolicExpressionTree>()) {
    294             if (!clonesLookup.ContainsKey(original)) {
    295               clonesLookup.Add(original, true);
    296             }
    297           }
    298           var goodFragments = new List<ISymbolicExpressionTreeNode>();
    299           var goodParents = new List<ISymbolicExpressionTree>();
    300           var goodChildren = new List<ISymbolicExpressionTree>();
    301           // take all individuals that have received a fragment in the previous generation
    302           foreach (var m in SecondaryFragmentMap) {
    303             var individual = m.Key as ISymbolicExpressionTree;
    304             // check if the individual became a parent in the current generation,
    305             // by checking if it appears among the parents from the current generation trace map
    306             if (parentsLookup.ContainsKey(individual)) {
    307               var fragmentItem = m.Value as SymbolicExpressionTreeNodeItem;
    308               var fragment = fragmentItem.Content;
    309               if (fragment != null) {
    310                 goodFragments.Add(fragmentItem.Content);
    311                 goodParents.AddRange(SecondaryTraceMap[individual].Cast<ISymbolicExpressionTree>());
    312                 goodChildren.Add(individual);
    313               }
    314             }
    315           }
    316           var allFragments = SecondaryFragmentMap.Values.Where(x => ((SymbolicExpressionTreeNodeItem)x).Content != null).Select(x => ((SymbolicExpressionTreeNodeItem)x).Content as ISymbolicExpressionTreeNode).ToList();
    317           var highImpactFragments = new List<ISymbolicExpressionTreeNode>();
    318           var allParents = SecondaryTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>()).ToList();
    319           var allChildren = SecondaryFragmentMap.Keys.Select(x => x as ISymbolicExpressionTree).ToList();
    320           // high impact fragments
    321           //foreach (var c in goodChildren) {
    322           //  var impactValues = _calculator.CalculateImpactValues(c, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
    323           //  var fragmentItem = SecondaryFragmentMap[c] as SymbolicExpressionTreeNodeItem;
    324           //  var fragment = fragmentItem.Content;
    325           //  if (fragment != null && impactValues[fragment] > 0.1)
    326           //    highImpactFragments.Add(fragment);
    327           //}
    328           FragmentFrequencies.Rows["Frequency of useful fragments"].Values.Add(goodFragments.Count);
    329           FragmentFrequencies.Rows["Frequency of high impact fragments"].Values.Add(highImpactFragments.Count);
    330           FragmentStatistics.Rows["Fragment lengths (good)"].Values.Add(goodFragments.Average(x => x.GetLength()));
    331           FragmentStatistics.Rows["Fragment lengths (all)"].Values.Add(allFragments.Average(x => x.GetLength()));
    332           //double avg = highImpactFragments.Count > 0 ? highImpactFragments.Average(x => x.GetLength()) : 0;
    333           //FragmentStatistics.Rows["Fragment lengths (high impact)"].Values.Add(avg);
    334           FragmentStatistics.Rows["Parent lengths (good)"].Values.Add(goodParents.Average(x => x.Length));
    335           FragmentStatistics.Rows["Parent lengths (all)"].Values.Add(allParents.Average(x => x.Length));
    336           FragmentStatistics.Rows["Child lengths (good)"].Values.Add(goodChildren.Average(x => x.Length));
    337           FragmentStatistics.Rows["Child lengths (all)"].Values.Add(allChildren.Average(x => x.Length));
    338           FragmentStatistics.Rows["Avg visitation length (all children)"].Values.Add(allChildren.Average(x => VisitationLength(x)));
    339           FragmentStatistics.Rows["Avg visitation length (good children)"].Values.Add(goodChildren.Average(x => VisitationLength(x)));
    340           //FragmentStatistics.Rows["Exact similarity (good fragments)"].Values.Add(CalculateSimilarity(allFragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact));
    341           //foreach (var f in allFragments) f.SortSubtrees();
    342           //FragmentStatistics.Rows["Exact similarity (all fragments)"].Values.Add(CalculateSimilarity(allFragments, (int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact));
    343 
    344           FragmentLengths.Rows["All fragments length distribution"].Values.Replace(allFragments.Select(x => (double)x.GetLength()));
    345           FragmentLengths.Rows["Useful fragments length distribution"].Values.Replace(goodFragments.Select(x => (double)x.GetLength()));
    346           FragmentLengths.Rows["All children length distribution"].Values.Replace(allChildren.Select(x => (double)x.Length));
    347           FragmentLengths.Rows["Useful children length distribution"].Values.Replace(goodChildren.Select(x => (double)x.Length));
    348           #endregion
    349         }
    350         // save the current generation so it can be compared to the following one, next time the analyzer is applied
    351         SecondaryTraceMap.Clear();
    352         foreach (var m in GlobalTraceMap)
    353           SecondaryTraceMap.Add(m.Key, m.Value);
    354 
    355         SecondaryCloneMap.Clear();
    356         foreach (var m in GlobalCloneMap)
    357           SecondaryCloneMap.Add(m.Key, m.Value);
    358 
    359         SecondaryFragmentMap.Clear();
    360         foreach (var m in GlobalFragmentMap)
    361           SecondaryFragmentMap.Add(m.Key, m.Value);
    362 
    363         // clear the global maps to save memory
     319      }
     320      if (Generations.Value > 0)
    364321        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeGenealogyAnalyzer)) {
     322          // clear the global maps to save memory
    365323          GlobalCloneMap.Clear();
    366324          GlobalTraceMap.Clear();
    367325          GlobalFragmentMap.Clear();
    368326        }
    369       }
    370327      return base.Apply();
     328    }
     329
     330    private void InitializeParameters() {
     331      #region Init parameters
     332      var results = ResultsParameter.ActualValue;
     333
     334      if (FragmentStatistics == null) {
     335        FragmentStatisticsParameter.ActualValue = new DataTable("Fragment Statistics", "Statistical measurements of fragments aggregated over the whole population");
     336        FragmentStatistics.VisualProperties.YAxisTitle = "Fragment length/Similarities";
     337        results.Add(new Result("Fragment Statistics", FragmentStatistics));
     338      }
     339      if (FragmentLengths == null) {
     340        FragmentLengthsParameter.ActualValue = new DataTable("Fragment Lengths", "Histograms for the distribution of fragment and individual lengths");
     341        FragmentLengths.VisualProperties.YAxisTitle = "Frequency";
     342        results.Add(new Result("Fragment Lengths", FragmentLengths));
     343      }
     344      if (FragmentFrequencies == null) {
     345        FragmentFrequenciesParameter.ActualValue = new DataTable("Fragment Frequencies", "Frequencies of good and high impact fragments");
     346        FragmentFrequencies.VisualProperties.YAxisTitle = "Frequency";
     347        results.Add(new Result("Fragment Frequencies", FragmentFrequencies));
     348      }
     349      if (ParentsDiversity == null) {
     350        ParentsDiversityParameter.ActualValue = new DataTable("Parents Diversity", "Number of unique parents per generation");
     351        ParentsDiversity.VisualProperties.YAxisTitle = "Unique parents";
     352        results.Add(new Result("Parents Diversity", ParentsDiversity));
     353      }
     354      if (SecondaryTraceMap == null) {
     355        SecondaryTraceMap = new TraceMapType();
     356      }
     357      if (SecondaryCloneMap == null) {
     358        SecondaryCloneMap = new CloneMapType();
     359      }
     360      if (SecondaryFragmentMap == null) {
     361        SecondaryFragmentMap = new CloneMapType();
     362      }
     363      #endregion
    371364    }
    372365
     
    435428      if (!FragmentFrequencies.Rows.ContainsKey("Frequency of high impact fragments")) {
    436429        FragmentFrequencies.Rows.Add(new DataRow("Frequency of high impact fragments") {
     430          VisualProperties = { StartIndexZero = true }
     431        });
     432      }
     433      if (!ParentsDiversity.Rows.ContainsKey("Unique parents")) {
     434        ParentsDiversity.Rows.Add(new DataRow("Unique parents") {
    437435          VisualProperties = { StartIndexZero = true }
    438436        });
     
    473471    }
    474472
     473    private void CalculateFragmentStatistics() {
     474      // for this kind of tracking/analysis, we need at least 2 successive generations of crossover
     475      if (Generations.Value > 1) {
     476        InitializeRows();
     477
     478        #region Fragment Statistics
     479        // create a hashset for fast lookup of parents (to see which children from the previous generation become parents, and count their fragments)
     480        var parentsLookup = new HashSet<ISymbolicExpressionTree>(GlobalTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>()));
     481        var allParents = SecondaryTraceMap.Values.SelectMany(x => x.Cast<ISymbolicExpressionTree>()).ToList();
     482        var allChildren = SecondaryFragmentMap.Keys.Cast<ISymbolicExpressionTree>().ToList(); /* SecondaryTraceMap.Keys should be the same with SecondaryFragmentMap.Keys */
     483        var allFragments = SecondaryFragmentMap.Values.Cast<SymbolicExpressionTreeNodeItem>().Select(x => x.Content).Where(x => x != null).ToList();
     484        // "good" fragments are fragments contained in a surviving offspring (that became a parent)
     485        // "good" parents are those that produced a surviving offspring
     486        // "good" children are the surviving offspring
     487        var goodFragments = new List<ISymbolicExpressionTreeNode>();
     488        var goodParents = new List<ISymbolicExpressionTree>();
     489        var goodChildren = new List<ISymbolicExpressionTree>();
     490
     491        // take all individuals that have received a fragment in the previous generation
     492        foreach (var m in SecondaryFragmentMap) {
     493          var individual = m.Key as ISymbolicExpressionTree;
     494          // check if the individual became a parent in the current generation,
     495          // by checking if it appears among the parents from the current generation trace map
     496          if (parentsLookup.Contains(individual)) {
     497            var symbExprTreeNodeItem = m.Value as SymbolicExpressionTreeNodeItem;
     498            var fragment = symbExprTreeNodeItem.Content;
     499            if (fragment != null) {
     500              goodFragments.Add(fragment);
     501              goodParents.AddRange(SecondaryTraceMap[individual].Cast<ISymbolicExpressionTree>());
     502              goodChildren.Add(individual);
     503            }
     504          }
     505        }
     506
     507        if (false) {
     508          var highImpactFragments = new List<ISymbolicExpressionTreeNode>();
     509          foreach (var child in goodChildren) {
     510            var impactValues = calculator.CalculateImpactValues(child, SymbolicExpressionInterpreter, SymbolicRegressionProblemData, 0, 0);
     511            var fragmentItem = SecondaryFragmentMap[child] as SymbolicExpressionTreeNodeItem;
     512            var fragment = fragmentItem.Content;
     513            if (fragment != null && impactValues[fragment] > 0.1) {
     514              if (highImpactFragments.Contains(fragment, new SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel.Exact)))
     515                continue;
     516              // prune fragment (remove irrelevant/low impact nodes)
     517              // this works because a child will never have an impact value greater than its parent
     518              foreach (var fnode in fragment.IterateNodesBreadth().Where(x => x.SubtreeCount > 0)) {
     519                for (int i = 0; i < fnode.SubtreeCount; ++i) {
     520                  var subtree = fnode.GetSubtree(i);
     521                  if (impactValues[subtree] < 0.1)
     522                    fnode.RemoveSubtree(i);
     523                }
     524              }
     525              highImpactFragments.Add(fragment);
     526            }
     527          }
     528        }
     529
     530        FragmentFrequencies.Rows["Frequency of useful fragments"].Values.Add(goodFragments.Count);
     531        //        FragmentFrequencies.Rows["Frequency of high impact fragments"].Values.Add(highImpactFragments.Count);
     532        FragmentStatistics.Rows["Fragment lengths (good)"].Values.Add(goodFragments.Average(x => x.GetLength()));
     533        FragmentStatistics.Rows["Fragment lengths (all)"].Values.Add(allFragments.Average(x => x.GetLength()));
     534        //        double avg = highImpactFragments.Count > 0 ? highImpactFragments.Average(x => x.GetLength()) : 0;
     535        //        FragmentStatistics.Rows["Fragment lengths (high impact)"].Values.Add(avg);
     536        FragmentStatistics.Rows["Parent lengths (good)"].Values.Add(goodParents.Average(x => x.Length));
     537        FragmentStatistics.Rows["Parent lengths (all)"].Values.Add(allParents.Average(x => x.Length));
     538        FragmentStatistics.Rows["Child lengths (good)"].Values.Add(goodChildren.Average(x => x.Length));
     539        FragmentStatistics.Rows["Child lengths (all)"].Values.Add(allChildren.Average(x => x.Length));
     540        //        FragmentStatistics.Rows["Avg visitation length (all children)"].Values.Add(allChildren.Average(x => VisitationLength(x)));
     541        //        FragmentStatistics.Rows["Avg visitation length (good children)"].Values.Add(goodChildren.Average(x => VisitationLength(x)));
     542        FragmentLengths.Rows["All fragments length distribution"].Values.Replace(allFragments.Select(x => (double)x.GetLength()));
     543        FragmentLengths.Rows["Useful fragments length distribution"].Values.Replace(goodFragments.Select(x => (double)x.GetLength()));
     544        FragmentLengths.Rows["All children length distribution"].Values.Replace(allChildren.Select(x => (double)x.Length));
     545        FragmentLengths.Rows["Useful children length distribution"].Values.Replace(goodChildren.Select(x => (double)x.Length));
     546        ParentsDiversity.Rows["Unique parents"].Values.Add(SecondaryCloneMap.Values.GroupBy(x => x).Count());
     547        #endregion
     548      }
     549    }
     550
    475551    private static int VisitationLength(ISymbolicExpressionTree tree) {
    476552      return VisitationLength(tree.Root);
     
    478554
    479555    private static int VisitationLength(ISymbolicExpressionTreeNode node) {
    480       int sum = 0;
    481       foreach (var n in node.IterateNodesBreadth())
    482         sum += n.GetLength();
    483       return sum;
     556      return node.IterateNodesBreadth().Sum(n => n.GetLength());
    484557    }
    485558
     
    491564    /// <param name="mode">The similarity mode (0 - exact, 1 - high, 2 - relaxed)</param>
    492565    /// <returns>The average number of similar fragments</returns>
    493     private static double CalculateSimilarity(IList<ISymbolicExpressionTreeNode> fragments, int mode) {
     566    private static double CalculateSimilarity(IList<ISymbolicExpressionTreeNode> fragments, SimilarityLevel similarity) {
    494567      var visited = new bool[fragments.Count];
    495568      int groups = 0;
     
    498571        for (int j = i + 1; j != fragments.Count; ++j) {
    499572          if (visited[j]) continue;
    500           if (fragments[i].IsSimilarTo(fragments[j], mode)) visited[j] = true;
     573          if (fragments[i].IsSimilarTo(fragments[j], similarity))
     574            visited[j] = true;
    501575        }
    502576        ++groups;
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

    r8249 r8557  
    2020#endregion
    2121
    22 using System;
    23 using System.Drawing;
    2422using System.Globalization;
    2523using System.Linq;
    26 using System.Text;
    2724using System.Threading;
    2825using HeuristicLab.Common;
     
    4441  /// An operator that tracks the genealogy of every individual
    4542  /// </summary>
    46   [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks tree lengths of Symbolic Expression Trees")]
     43  [Item("SymbolicExpressionTreeGenealogyAnalyzer", "An operator that tracks the genealogy of tree individuals")]
    4744  [StorableClass]
    4845  public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
     46    #region Parameter names
    4947    private const string UpdateIntervalParameterName = "UpdateInterval";
    5048    private const string UpdateCounterParameterName = "UpdateCounter";
     
    6361    private const string SymbolicRegressionProblemDataParameterName = "ProblemData";
    6462    private const string SymbolicDataAnalysisProblemEvaluatorParameterName = "Evaluator";
     63    #endregion
    6564
    6665    #region Parameter properties
     
    159158
    160159    [StorableConstructor]
    161     private SymbolicExpressionTreeGenealogyAnalyzer(bool deserializing)
    162       : base() {
    163     }
    164     private SymbolicExpressionTreeGenealogyAnalyzer(SymbolicExpressionTreeGenealogyAnalyzer original, Cloner cloner)
    165       : base(original, cloner) {
    166     }
     160    private SymbolicExpressionTreeGenealogyAnalyzer(bool deserializing) : base(deserializing) { }
     161    private SymbolicExpressionTreeGenealogyAnalyzer(SymbolicExpressionTreeGenealogyAnalyzer original, Cloner cloner) : base(original, cloner) { }
    167162    public override IDeepCloneable Clone(Cloner cloner) {
    168163      return new SymbolicExpressionTreeGenealogyAnalyzer(this, cloner);
     
    218213        UpdateCounter.Value = 0; // reset counter
    219214
    220         var gScope = ExecutionContext.Scope;
    221         while (gScope.Parent != null) gScope = gScope.Parent;
    222215        SymbolicExpressionTreeGenealogyGraph graph;
    223216        if (!Results.ContainsKey(PopulationGraphResultParameterName)) {
     
    227220          graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphResultParameterName].Value);
    228221        }
    229         // get tree quality values (Key => Individual, Value => Quality)
     222
     223        var gScope = ExecutionContext.Scope;
     224        while (gScope.Parent != null) gScope = gScope.Parent;
    230225        var scopes = (from s in gScope.SubScopes
    231226                      let individual = s.Variables.First().Value
     
    240235          var indiv = scopes[i].Tree;
    241236          var label = (generation * scopes.Count + i + 1).ToString(CultureInfo.InvariantCulture);
    242           if (!graph.HasNode(indiv)) {
    243             var node = new GenealogyGraphNode(indiv) { Label = label };
    244             graph.AddNode(node);
    245             // node metadata
    246             graph[node].Ranks.Add(generation);
    247             graph[node].Quality = scopes[i].Quality;
    248             graph[node].IsElite = i < Elites.Value;
    249           } else {
    250             var node = graph.GetNode(indiv);
    251             graph[node].Ranks.Add(generation);
    252           }
     237          var childGraphNode = new SymbolicExpressionGenealogyGraphNode {
     238            SymbolicExpressionTree = indiv,
     239            Quality = scopes[i].Quality,
     240            IsElite = i < Elites.Value,
     241            Label = label
     242          };
     243          graph.AddNode(childGraphNode);
     244          childGraphNode.Ranks.Add(generation);
    253245          if (generation == 0) continue;
    254246          if (!GlobalTraceMap.ContainsKey(indiv)) continue;
     
    256248          var parents = GlobalTraceMap[indiv].Cast<ISymbolicExpressionTree>();
    257249          foreach (var parent in parents) {
    258             object data = ((GenericWrapper<SymbolicExpressionTreeNode>)GlobalFragmentMap[indiv]).Content;
     250            var fragmentFromParent = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[indiv]).Content;
     251            SymbolicExpressionGenealogyGraphNode parentGraphNode;
    259252            if (GlobalTraceMap.ContainsKey(parent)) {
    260               var node = new GenealogyGraphNode(parent) { Label = "X" };
    261               graph.AddNode(node);
    262               graph[node].Quality = Evaluate(parent);
    263               graph[node].Ranks.Add(generation - 0.5);
    264               var pp = GlobalTraceMap[parent].Cast<SymbolicExpressionTree>();
    265               foreach (var p in pp) {
    266                 data = ((GenericWrapper<SymbolicExpressionTreeNode>)GlobalFragmentMap[parent]).Content;
    267                 graph.AddArc(p, parent, null, data);
     253              parentGraphNode = new SymbolicExpressionGenealogyGraphNode {
     254                SymbolicExpressionTree = parent,
     255                Quality = Evaluate(parent)
     256              };
     257              graph.AddNode(parentGraphNode);
     258              parentGraphNode.Ranks.Add(generation - 0.5);
     259              var parentParents = GlobalTraceMap[parent].Cast<SymbolicExpressionTree>();
     260              foreach (var parentParent in parentParents) {
     261                var fragmentFromParentParent = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[parent]).Content;
     262                // we store the fragment in the arc
     263                var parentParentGraphNode = graph.GetGraphNodes(parentParent).Last();
     264                graph.AddArc(parentParentGraphNode, parentGraphNode, null, fragmentFromParentParent);
    268265              }
     266            } else { // individual is an elite
     267              parentGraphNode = graph.GetGraphNodes(parent).Last();
    269268            }
    270             graph.AddArc(parent, indiv, null, data);
     269            graph.AddArc(parentGraphNode, childGraphNode, null, fragmentFromParent);
    271270          }
    272271        }
    273272        // clear trace and clone maps in preparation for the next generation
    274         if (generation == 0) return base.Apply();
     273
     274      }
     275      if (Generations.Value > 0)
    275276        if (this.Successor == null || !(this.Successor is SymbolicExpressionTreeFragmentsAnalyzer)) {
    276277          GlobalTraceMap.Clear();
     
    278279          GlobalFragmentMap.Clear();
    279280        }
    280       }
    281281      return base.Apply();
    282282    }
     
    296296      return quality;
    297297    }
    298 
    299     #region Export to dot file
    300     private static void WriteDot(string path, SymbolicExpressionTreeGenealogyGraph graph) {
    301       using (var file = new System.IO.StreamWriter(path)) {
    302         string nl = Environment.NewLine;
    303         file.WriteLine("digraph \"lineage " + graph.AverageDegree.ToString(CultureInfo.InvariantCulture) + "\" {" + nl + "ratio=auto;" + nl + "mincross=2.0");
    304         file.WriteLine("\tnode [shape=circle,label=\"\",style=filled]");
    305 
    306         foreach (var node in graph.Values) {
    307           var color = Color.FromArgb((int)((1 - graph[node].Quality) * 255), (int)(graph[node].Quality * 255), 0);
    308           string fillColor = String.Format("#{0:x2}{1:x2}{2:x2}", color.R, color.G, color.B);
    309           string shape = "circle";
    310           if (graph[node].IsElite)
    311             shape = "doublecircle";
    312           file.WriteLine("\t\"" + node.Id + "\" [shape=" + shape + ",fillcolor=\"" + fillColor + "\",label=\"" + node.Label + "\"];");
    313           if (node.InEdges == null)
    314             continue;
    315           foreach (var edge in node.InEdges) {
    316             //var edgeStyle = node.InEdges.Count == 1 ? "dashed" : String.Empty;
    317             var edgeStyle = String.Empty;
    318             file.WriteLine("\t\"" + edge.Target.Id + "\" -> \"" + node.Id + "\" [arrowsize=.5, color=\"" + fillColor + "\", style=\"" + edgeStyle + "\"];");
    319           }
    320         }
    321         foreach (var g in graph.Values.GroupBy(x => graph[x].Ranks[0])) {
    322           var sb = new StringBuilder();
    323           sb.Append("\t{rank=same;");
    324           foreach (var node in g)
    325             sb.Append("\"" + node.Id + "\" ");
    326           sb.Append("}\n");
    327           file.Write(sb.ToString());
    328         }
    329         file.WriteLine("}");
    330       }
    331     }
    332     #endregion
    333298  }
    334299}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj

    r8213 r8557  
    8989    <Compile Include="Analyzers\SymbolicExpressionTreeFragmentsAnalyzer.cs" />
    9090    <Compile Include="Analyzers\SymbolicExpressionTreeGenealogyAnalyzer.cs" />
     91    <Compile Include="Analyzers\SymbolicExpressionTreeLineagesAnalyzer.cs" />
    9192    <Compile Include="Analyzers\SymbolicExpressionTreeRelativeLengthAnalyzer.cs" />
    9293    <Compile Include="GenealogyGraph.cs" />
     94    <Compile Include="GenealogyGraphArc.cs" />
     95    <Compile Include="GenealogyGraphNode.cs" />
    9396    <Compile Include="Interfaces\IGenealogyGraph.cs" />
     97    <Compile Include="Interfaces\IGenealogyGraphNode.cs" />
     98    <Compile Include="Interfaces\ISymbolicExpressionTreeGenealogyGraph.cs" />
    9499    <Compile Include="Plugin.cs" />
    95100    <Compile Include="Properties\AssemblyInfo.cs" />
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Plugin.cs

    r8213 r8557  
    3030  [PluginDependency("HeuristicLab.Common.Resources", "3.3")]
    3131  [PluginDependency("HeuristicLab.Core", "3.3")]
    32   [PluginDependency("HeuristicLab.Data", "3.3")]
    3332  [PluginDependency("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.4")]
    3433  [PluginDependency("HeuristicLab.Operators", "3.3")]
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r8213 r8557  
    169169  </ItemGroup>
    170170  <ItemGroup>
     171    <Compile Include="Analyzers\SymbolicDataAnalysisComplexityAnalyzer.cs" />
    171172    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
    172173    <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveTrainingParetoBestSolutionAnalyzer.cs" />
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisExpressionTreeMatching.cs

    r8213 r8557  
    1 using System.Collections.Generic;
     1using System;
     2using System.Collections.Generic;
     3using System.IO;
    24using System.Linq;
     5using HeuristicLab.Common;
     6using HeuristicLab.Core;
    37using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     8using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    49
    510namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    6   public class SymbolicExpressionTreeNodeSimilarityComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {
    7 
    8     public SymbolicExpressionTreeNodeSimilarityComparer(int similarityLevel) {
    9       _similarityLevel = similarityLevel;
     11  public enum SimilarityLevel {
     12    Exact,   // everything is matched bit by bit (functions and terminals)
     13    High,    // symbols are matched. leaf node types are matched
     14    Relaxed  // only symbols are matched, leafs count as wildcards
     15  }
     16  [Item("SymbolicExpressionTreeNodeSimilarityComparer", "A comparison operator that checks node equality based on different similarity measures.")]
     17  [StorableClass]
     18  public class SymbolicExpressionTreeNodeSimilarityComparer : Item, ISymbolicExpressionTreeNodeComparer {
     19    [StorableConstructor]
     20    private SymbolicExpressionTreeNodeSimilarityComparer(bool deserializing) : base(deserializing) { }
     21    private SymbolicExpressionTreeNodeSimilarityComparer(SymbolicExpressionTreeNodeSimilarityComparer original, Cloner cloner) : base(original, cloner) { }
     22    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicExpressionTreeNodeSimilarityComparer(this, cloner); }
     23
     24    private SimilarityLevel similarityLevel;
     25    public SimilarityLevel SimilarityLevel {
     26      get { return similarityLevel; }
     27      set { similarityLevel = value; }
     28    }
     29
     30    public SymbolicExpressionTreeNodeSimilarityComparer() {
     31      this.similarityLevel = SimilarityLevel.Exact;
     32    }
     33
     34    public SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel similarityLevel) {
     35      this.similarityLevel = similarityLevel;
    1036    }
    1137
     
    1541
    1642    public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    17       if (a.SubtreeCount != b.SubtreeCount) { return false; }
    18       if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
    19       // compare leaf nodes according to desired similarity level
    20       switch (_similarityLevel) {
    21         case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact):
    22           if (a is ConstantTreeNode && b is ConstantTreeNode) {
    23             return ((ConstantTreeNode)a).Value.Equals(((ConstantTreeNode)b).Value);
    24           }
    25           if (a is VariableTreeNode && b is VariableTreeNode) {
    26             return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight);
    27           }
     43      var ca = a as ConstantTreeNode;
     44      var cb = b as ConstantTreeNode;
     45      var va = a as VariableTreeNode;
     46      var vb = b as VariableTreeNode;
     47
     48      var aIsConstant = ca != null;
     49      var aIsVariable = va != null;
     50      var bIsConstant = cb != null;
     51      var bIsVariable = vb != null;
     52      var aIsFunction = (!(aIsConstant | aIsVariable));
     53      var bIsFunction = (!(bIsConstant | bIsVariable));
     54
     55      if (aIsFunction)
     56        return bIsFunction && a.Symbol.Name.Equals(b.Symbol.Name);
     57      if (bIsFunction) // one is function and the other is not, return false
     58        return false;
     59
     60      switch (similarityLevel) {
     61        case (SimilarityLevel.Exact):
     62          if (aIsConstant & bIsConstant)
     63            return ca.Value.Equals(cb.Value);
     64          if (aIsVariable & bIsVariable)
     65            return va.Weight.Equals(vb.Weight);
    2866          return false;
    29 
    30         case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.High):
    31           return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
    32 
    33         case ((int)SymbolicExpressionTreeMatching.SimilarityLevel.Relaxed):
     67        case (SimilarityLevel.High):
     68          return ((aIsConstant & bIsConstant) || (aIsVariable & bIsVariable));
     69        case (SimilarityLevel.Relaxed):
    3470          return true;
    35 
    3671        default:
    3772          return false;
     
    3974    }
    4075
    41     private readonly int _similarityLevel;
     76    public static bool ExactlySimilar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
     77      return Similar(a, b, SimilarityLevel.Exact);
     78    }
     79
     80    public static bool Similar(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SimilarityLevel level) {
     81      var comp = new SymbolicExpressionTreeNodeSimilarityComparer(level);
     82      return comp.Equals(a, b);
     83    }
    4284  }
    4385
    4486  public class SymbolicExpressionTreeNodeOrderingComparer : IComparer<ISymbolicExpressionTreeNode> {
    4587    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    46       if (a is ConstantTreeNode) {
    47         if (b is ConstantTreeNode)
    48           return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
    49             (a as ConstantTreeNode).Value.CompareTo((b as ConstantTreeNode).Value) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
    50         return -1; // if b is not constant then we consider a < b because by convention Constant < Variable < Function
    51       }
    52       if (a is VariableTreeNode) {
    53         if (b is ConstantTreeNode)
    54           return 1;
    55         if (b is VariableTreeNode)
    56           return a.Symbol.ToString().Equals(b.Symbol.ToString()) ?
    57             (a as VariableTreeNode).Weight.CompareTo((b as VariableTreeNode).Weight) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
    58         return -1;
    59       }
    60       if (b is ConstantTreeNode || b is VariableTreeNode)
    61         return 1; // a is a Function node and is greater than Constants or Variables
    62 
    63       return a.Symbol.ToString().Equals(b.Symbol.ToString()) ? a.SubtreeCount.CompareTo(b.SubtreeCount) : System.String.Compare(a.Symbol.ToString(), b.Symbol.ToString());
     88      var ca = a as ConstantTreeNode;
     89      var cb = b as ConstantTreeNode;
     90      var va = a as VariableTreeNode;
     91      var vb = b as VariableTreeNode;
     92
     93      var aIsConstant = ca != null;
     94      var aIsVariable = va != null;
     95      var bIsConstant = cb != null;
     96      var bIsVariable = vb != null;
     97      var aIsFunction = (!(aIsConstant | aIsVariable));
     98      var bIsFunction = (!(bIsConstant | bIsVariable));
     99
     100      if (aIsFunction)
     101        return bIsFunction ? a.Symbol.Name.CompareTo(b.Symbol.Name) : -1;
     102      if (bIsFunction) // a is Constant or Variables
     103        return 1;
     104      if (aIsVariable)
     105        return bIsVariable ? va.Weight.CompareTo(vb.Weight) : -1;
     106      return
     107        bIsVariable ? 1 : ca.Value.CompareTo(cb.Value);
    64108    }
    65109  }
     
    68112  public class SymbolicExpressionTreeEqualityComparer : IEqualityComparer<ISymbolicExpressionTree> {
    69113    public bool Equals(ISymbolicExpressionTree a, ISymbolicExpressionTree b) {
    70       return SymbolicExpressionTreeMatching.FindMatch(a, b, _mode) == 0;
     114      return SymbolicExpressionTreeMatching.FindMatch(a, b, similarityLevel) == 0;
    71115    }
    72116
    73117    public int GetHashCode(ISymbolicExpressionTree tree) {
    74       return tree.Length;
    75     }
    76 
    77     private int _mode;
    78     public void SetComparisonMode(int mode) {
    79       _mode = mode;
     118      return (tree.Length << 8) % 12345;
     119    }
     120
     121    private SimilarityLevel similarityLevel;
     122    public void SetComparisonMode(SimilarityLevel simLevel) {
     123      similarityLevel = simLevel;
    80124    }
    81125  }
    82126
    83127  public static class SymbolicExpressionTreeMatching {
    84     public enum SimilarityLevel {
    85       Exact,   // everything is matched bit by bit (functions and terminals)
    86       High,    // symbols are matched. leaf node types are matched
    87       Relaxed  // only symbols are matched, leafs count as wildcards
    88     }
    89 
    90     public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
     128    public static bool IsSimilarTo(this ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, SimilarityLevel mode) {
    91129      return FindMatch(t1, t2, mode) == 0;
    92130    }
    93     public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, int mode) {
     131
     132    public static bool IsSimilarTo(this ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, SimilarityLevel mode) {
    94133      return FindMatch(t1, t2, mode) == 0;
    95134    }
    96135
    97     public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
    98       var nodes = tree.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
    99       var fragments = fragment.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
    100       return FindMatch(nodes, fragments, mode) != -1;
     136    public static bool ContainsFragment(this ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SimilarityLevel mode) {
     137      var matches = FindMatches(tree, fragment, mode);
     138      return matches.Count > 0;
    101139    }
    102140
     
    106144
    107145    public static void SortSubtrees(this ISymbolicExpressionTreeNode node) {
    108       if (node.SubtreeCount > 0) {
    109         var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
    110         if (subtrees == null) return;
    111         subtrees.Sort(new SymbolicExpressionTreeNodeOrderingComparer());
    112         foreach (var subtree in subtrees)
    113           subtree.SortSubtrees();
    114       }
    115     }
    116 
    117     public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, int mode) {
     146      if (node.SubtreeCount == 0) return;
     147      var subtrees = node.Subtrees as List<ISymbolicExpressionTreeNode>;
     148      if (subtrees == null) return;
     149      var comparer = new SymbolicExpressionTreeNodeOrderingComparer();
     150      subtrees.Sort(comparer);
     151      foreach (var subtree in subtrees)
     152        subtree.SortSubtrees();
     153    }
     154
     155    // return child that is the same as node
     156    public static ISymbolicExpressionTreeNode FindChild(this ISymbolicExpressionTreeNode parent, ISymbolicExpressionTreeNode node) {
     157      var subtrees = parent.Subtrees as List<ISymbolicExpressionTreeNode>;
     158      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(SimilarityLevel.Exact);
     159      return subtrees.Find(x => comparer.Equals(x, node));
     160    }
     161
     162    public static int FindMatch(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SimilarityLevel similarityLevel) {
    118163      var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
    119164      var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
    120       return FindMatch(nodesA, nodesB, mode);
    121     }
    122     public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, int mode) {
     165      return FindMatch(nodesA, nodesB, similarityLevel);
     166    }
     167
     168    public static int FindMatch(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SimilarityLevel similarityLevel) {
    123169      var nodesA = a.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
    124170      var nodesB = b.IterateNodesPostfix() as List<ISymbolicExpressionTreeNode>;
    125       return FindMatch(nodesA, nodesB, mode);
    126     }
     171      return FindMatch(nodesA, nodesB, similarityLevel);
     172    }
     173
    127174    // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
    128175    // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
    129     public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, int mode) {
     176    public static int FindMatch(List<ISymbolicExpressionTreeNode> seq, List<ISymbolicExpressionTreeNode> pat, SimilarityLevel similarityLevel) {
    130177      int patlen = pat.Count;
    131178      int seqlen = seq.Count;
    132179      if (patlen == 0 || seqlen == 0) return -1;
    133       var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(mode);
     180      var comparer = new SymbolicExpressionTreeNodeSimilarityComparer(similarityLevel);
    134181      if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
    135182      for (int i = patlen; i <= seqlen; ++i) {
     
    140187      return -1;
    141188    }
     189
     190    public static List<ISymbolicExpressionTreeNode> FindMatches(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, SimilarityLevel similarityLevel) {
     191      var comp = new SymbolicExpressionTreeNodeSimilarityComparer(similarityLevel);
     192      return FindMatches(tree.Root, fragment, comp);
     193    }
     194
     195    public static List<ISymbolicExpressionTreeNode>
     196    FindMatches(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode fragment, SymbolicExpressionTreeNodeSimilarityComparer comp) {
     197      var matches = new List<ISymbolicExpressionTreeNode>();
     198      root.ForEachNodePostfix(node => {
     199        if (Match(node, fragment, comp) == fragment.GetLength()) matches.Add(node);
     200      });
     201      return matches;
     202    }
     203
     204    ///<summary>
     205    /// Finds the longest common subsequence in quadratic time and linear space
     206    /// Variant of:
     207    /// D . S. Hirschberg. A linear space algorithm for or computing maximal common subsequences. 1975.
     208    /// http://dl.acm.org/citation.cfm?id=360861
     209    /// </summary>
     210    /// <returns>Number of pairs that were matched</returns>
     211    public static int
     212    Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
     213      if (!comp.Equals(a, b))
     214        return 0;
     215
     216      int m = a.SubtreeCount;
     217      int n = b.SubtreeCount;
     218      if (m == 0 || n == 0) return 1;
     219
     220      var matrix = new int[m + 1, n + 1];
     221      for (int i = 1; i <= m; ++i)
     222        for (int j = 1; j <= n; ++j) {
     223          var ai = a.GetSubtree(i - 1);
     224          var bj = b.GetSubtree(j - 1);
     225          int match = Match(ai, bj, comp);
     226          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
     227        }
     228      return matrix[m, n] + 1;
     229    }
     230
     231    public static int
     232    LCS(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
     233      var nodesA = a.IterateNodesPrefix().ToList();
     234      var nodesB = b.IterateNodesPrefix().ToList();
     235      int m = nodesA.Count;
     236      int n = nodesB.Count;
     237      var matrix = new int[m + 1, n + 1];
     238      for (int i = 1; i <= m; ++i) {
     239        for (int j = 1; j <= n; ++j) {
     240          int w = comp.Equals(a, b) ? 1 : 0;
     241          matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + w);
     242        }
     243      }
     244      return matrix[m, n];
     245    }
     246
     247    public static void RenderTree(TextWriter writer, ISymbolicExpressionTree tree) {
     248      RenderNode(writer, tree.Root, string.Empty);
     249    }
     250
     251    public static void RenderNode(TextWriter writer, ISymbolicExpressionTreeNode node, string prefix) {
     252      string label;
     253      if (node is VariableTreeNode) {
     254        var variable = node as VariableTreeNode;
     255        label = string.Concat(string.Format("{0:0.000}", variable.Weight), '·', variable.VariableName);
     256      } else if (node is ConstantTreeNode) {
     257        var constant = node as ConstantTreeNode;
     258        label = string.Format("{0:0.000}", constant.Value);
     259      } else {
     260        label = node.Symbol.ToString();
     261      }
     262
     263      writer.Write(label);
     264      if (node.SubtreeCount > 0) {
     265        char connector, extender = ' ';
     266        var padding = prefix + new string(' ', label.Length);
     267        for (int i = 0; i != node.SubtreeCount; ++i) {
     268          if (i == 0) {
     269            if (node.SubtreeCount > 1) {
     270              connector = RenderChars.JunctionDown;
     271              extender = RenderChars.VerticalLine;
     272            } else {
     273              connector = RenderChars.HorizontalLine;
     274              extender = ' ';
     275            }
     276          } else {
     277            writer.Write(padding);
     278            if (i == node.SubtreeCount - 1) {
     279              connector = RenderChars.CornerRight;
     280              extender = ' ';
     281            } else {
     282              connector = RenderChars.JunctionRight;
     283              extender = RenderChars.VerticalLine;
     284            }
     285          }
     286          writer.Write(string.Concat(connector, RenderChars.HorizontalLine));
     287          var newPrefix = string.Concat(padding, extender, ' ');
     288          RenderNode(writer, node.GetSubtree(i), newPrefix);
     289        }
     290      } else
     291        writer.WriteLine();
     292    }
     293  }
     294
     295  // helper class providing characters for displaying a tree in the console
     296  public static class RenderChars {
     297    public const char JunctionDown = '┬';
     298    public const char HorizontalLine = '─';
     299    public const char VerticalLine = '│';
     300    public const char JunctionRight = '├';
     301    public const char CornerRight = '└';
    142302  }
    143303}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

    r8213 r8557  
    319319        op.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
    320320      }
     321      var comparers = ApplicationManager.Manager.GetInstances<ISymbolicExpressionTreeNodeComparer>().ToList();
     322      if (comparers.Count > 0)
     323        foreach (var op in operators.OfType<ITracingSymbolicExpressionTreeOperator>()) {
     324          op.SymbolicExpressionTreeNodeComparerParameter.ActualValue = comparers.First();
     325        }
    321326    }
    322327
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Selection/3.3/Plugin.cs

    r8248 r8557  
    2626  /// Plugin class for HeuristicLab.Selection plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Selection", "3.3.6.8236")]
     28  [Plugin("HeuristicLab.Selection", "3.3.6.8248")]
    2929  [PluginFile("HeuristicLab.Selection-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Collections", "3.3")]
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Tracking.sln

    r8213 r8557  
    77  ProjectSection(SolutionItems) = preProject
    88    Build.cmd = Build.cmd
     9    HeuristicLab.Tracking.vsmdi = HeuristicLab.Tracking.vsmdi
     10    Local.testsettings = Local.testsettings
    911    PreBuildEvent.cmd = PreBuildEvent.cmd
     12    TraceAndTestImpact.testsettings = TraceAndTestImpact.testsettings
    1013  EndProjectSection
    1114EndProject
     
    1922EndProject
    2023Global
     24  GlobalSection(TestCaseManagementSettings) = postSolution
     25    CategoryFile = HeuristicLab.Tracking.vsmdi
     26  EndGlobalSection
    2127  GlobalSection(SolutionConfigurationPlatforms) = preSolution
    2228    Debug|Any CPU = Debug|Any CPU
Note: See TracChangeset for help on using the changeset viewer.