Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11458


Ignore:
Timestamp:
10/13/14 13:03:24 (10 years ago)
Author:
bburlacu
Message:

#1772: HeuristicLab.Problems.DataAnalysis.Symbolic:

  • Merged trunk changes (SymbolicExpressionImporter)
  • Added Passthrough symbol (does not perform an operation, just transfers the input), adjusted interpreter and opcodes accordingly
  • Added diversity preserving crossover
  • Replaced IDistanceCalculator interface with ISymbolicDataAnalysisExpressionSimilarityCalculator and adjusted similarity calculators
  • Refactored tracing, moved functionality to the TraceCalculator (when this is complete the old code will be removed)
Location:
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4
Files:
5 added
1 deleted
11 edited
1 copied
1 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

    • Property svn:ignore
      •  

        old new  
        55TreeDistance
        66SymbolicDataAnalysisExpressionTreeMatching.cs
         7Importer
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers

    • Property svn:ignore set to
      SymbolicDataAnalysisExpressionSizefairCrossover.cs
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/TypeCoherentExpressionGrammar.cs

    r11208 r11458  
    2626using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
     29
    2830namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2931  [StorableClass]
     
    8688      var psi = new Psi();
    8789      var sineIntegral = new SineIntegral();
     90      var passthrough = new Passthrough();
    8891
    8992      var @if = new IfThenElse();
     
    113116      var exponentialAndLogarithmicSymbols = new GroupSymbol(ExponentialFunctionsName, new List<ISymbol> { exp, log });
    114117      var specialFunctions = new GroupSymbol(SpecialFunctionsName, new List<ISymbol> { airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi,
    115         fresnelCosineIntegral,fresnelSineIntegral,gamma,hypCosineIntegral,hypSineIntegral,norm, psi, sineIntegral});
     118        fresnelCosineIntegral,fresnelSineIntegral,gamma,hypCosineIntegral,hypSineIntegral,norm, psi, sineIntegral, passthrough});
    116119      var terminalSymbols = new GroupSymbol(TerminalsName, new List<ISymbol> { constant, variableSymbol });
    117120      var realValuedSymbols = new GroupSymbol(RealValuedSymbolsName, new List<ISymbol>() { arithmeticSymbols, trigonometricSymbols, exponentialAndLogarithmicSymbols, specialFunctions, terminalSymbols });
     
    156159      SetSubtreeCount(laggedVariable, 0, 0);
    157160      SetSubtreeCount(autoregressiveVariable, 0, 0);
     161      SetSubtreeCount(passthrough, 1, 1);
    158162      #endregion
    159163
     
    224228      AddAllowedChildSymbol(derivative, powerSymbols);
    225229      AddAllowedChildSymbol(derivative, conditionSymbols);
     230
     231      AddAllowedChildSymbol(passthrough, realValuedSymbols);
     232      AddAllowedChildSymbol(passthrough, powerSymbols);
     233      AddAllowedChildSymbol(passthrough, conditionSymbols);
     234      AddAllowedChildSymbol(passthrough, timeSeriesSymbols);
     235      AddAllowedChildSymbol(passthrough, specialFunctions);
    226236      #endregion
    227237    }
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11318 r11458  
    105105      <Private>False</Private>
    106106    </Reference>
    107     <Reference Include="HeuristicLab.Common-3.3">
     107    <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     108      <SpecificVersion>False</SpecificVersion>
    108109      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
    109110      <Private>False</Private>
     
    190191      <SubType>Code</SubType>
    191192    </Compile>
     193    <Compile Include="Crossovers\SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs" />
     194    <Compile Include="Importer\SymbolicExpressionImporter.cs" />
     195    <Compile Include="Importer\Token.cs" />
    192196    <Compile Include="Interfaces\IModelBacktransformator.cs" />
    193     <Compile Include="Interfaces\IDistanceCalculator.cs" />
     197    <Compile Include="Interfaces\ISymbolicDataAnalysisExpressionSimilarityCalculator.cs" />
    194198    <Compile Include="Matching\SymbolicExpressionTreeCanonicalSorter.cs" />
    195199    <Compile Include="Matching\SymbolicExpressionTreeEqualityComparer.cs" />
     
    263267    <Compile Include="Symbols\AiryB.cs" />
    264268    <Compile Include="Symbols\Bessel.cs" />
     269    <Compile Include="Symbols\Passthrough.cs" />
    265270    <Compile Include="Symbols\Xor.cs" />
    266271    <Compile Include="Symbols\Erf.cs" />
     
    305310    <Compile Include="Symbols\VariableConditionTreeNode.cs" />
    306311    <Compile Include="Symbols\VariableTreeNode.cs" />
     312    <Compile Include="Tracking\TraceCalculator.cs" />
    307313    <Compile Include="TransformationToSymbolicTreeMapper.cs" />
    308314    <Compile Include="Tracking\FragmentGraph\FragmentGraph.cs" />
     
    349355      <Project>{423bd94f-963a-438e-ba45-3bb3d61cd03b}</Project>
    350356      <Name>HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views-3.4</Name>
     357      <Private>False</Private>
    351358    </ProjectReference>
    352359    <ProjectReference Include="..\..\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding\3.4\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj">
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/ISymbolicDataAnalysisExpressionSimilarityCalculator.cs

    r11350 r11458  
    1 using HeuristicLab.Core;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using HeuristicLab.Core;
    223using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    324
    425namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    5   public interface IDistanceCalculator : IItem {
    6     double CalculateDistance(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2);
     26  public interface ISymbolicDataAnalysisExpressionSimilarityCalculator : IItem {
     27    double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2);
    728  }
    829}
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/OpCodes.cs

    r11208 r11458  
    2323using System.Collections.Generic;
    2424using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     25using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
    2526
    2627namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
     
    8384    public const byte Erf = 43;
    8485    public const byte Bessel = 44;
     86    public const byte Passthrough = 45;
    8587
    8688    private static Dictionary<Type, byte> symbolToOpcode = new Dictionary<Type, byte>() {
     
    130132      { typeof(Norm), OpCodes.Norm},
    131133      { typeof(Erf), OpCodes.Erf},
    132       { typeof(Bessel), OpCodes.Bessel}   
     134      { typeof(Bessel), OpCodes.Bessel},
     135      { typeof(Passthrough), OpCodes.Passthrough}
    133136    };
    134137
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeLinearInterpreter.cs

    r11232 r11458  
    111111
    112112      var code = SymbolicExpressionTreeLinearCompiler.Compile(tree, OpCodes.MapSymbolToOpCode);
     113      PrepareInstructions(code, dataset);
     114      return rows.Select(row => Evaluate(dataset, row, code));
     115    }
     116
     117    // NOTE: do not use this method when evaluating trees. this method is provided as a shortcut for evaluating subtrees ad-hoc
     118    public IEnumerable<double> GetValues(ISymbolicExpressionTreeNode node, Dataset dataset, IEnumerable<int> rows) {
     119      var code = SymbolicExpressionTreeLinearCompiler.Compile(node, OpCodes.MapSymbolToOpCode);
    113120      PrepareInstructions(code, dataset);
    114121      return rows.Select(row => Evaluate(dataset, row, code));
     
    329336          state.Reset();
    330337          instr.value = interpreter.Evaluate(dataset, ref row, state);
     338        } else if (instr.opCode == OpCodes.Passthrough) {
     339          instr.value = code[instr.childIndex].value;
    331340        } else {
    332341          var errorText = string.Format("The {0} symbol is not supported by the linear interpreter. To support this symbol, please use the SymbolicDataAnalysisExpressionTreeInterpreter.", instr.dynamicNode.Symbol.Name);
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs

    r11385 r11458  
    7777
    7878    public static ISymbolicExpressionTreeNode Difference(this ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNode other) {
    79       var these = node.IterateNodesPrefix().ToList();
    80       var others = other.IterateNodesPrefix().ToList();
    81 
    82       var minCount = Math.Min(these.Count, others.Count);
     79      var a = node.IterateNodesPrefix().ToList();
     80      var b = other.IterateNodesPrefix().ToList();
    8381      var list = new List<ISymbolicExpressionTreeNode>();
    84 
    85       for (int i = 0; i < minCount; ++i) {
    86         if (these[i].ToString() != others[i].ToString())
    87           list.Add(these[i]);
     82      for (int i = 0, j = 0; i < a.Count && j < b.Count; ++i, ++j) {
     83        var s1 = a[i].ToString();
     84        var s2 = b[j].ToString();
     85        if (s1 == s2) continue;
     86        list.Add(a[i]);
     87        // skip subtrees since the parents are already different
     88        i += a[i].SubtreeCount;
     89        j += b[j].SubtreeCount;
    8890      }
    89 
    90       return list.Count > 0 ? LowestCommonAncestor(node, list) : null;
     91      ISymbolicExpressionTreeNode result = list.Count > 0 ? LowestCommonAncestor(node, list) : null;
     92      return result;
    9193    }
    9294
     
    98100        return nodes[0];
    99101
    100       int lowestLevel = nodes.Min(x => root.GetBranchLevel(x));
     102      int minLevel = nodes.Min(x => root.GetBranchLevel(x));
    101103
    102104      // bring the nodes in the nodes to the same level (relative to the root)
     
    104106        var node = nodes[i];
    105107        var level = root.GetBranchLevel(node);
    106         for (int j = lowestLevel; j < level; ++j)
     108        for (int j = minLevel; j < level; ++j)
    107109          node = node.Parent;
    108110        nodes[i] = node;
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    r11229 r11458  
    3232  [StorableClass]
    3333  [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
    34   public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     34  public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator, ISymbolicDataAnalysisExpressionSimilarityCalculator {
    3535    private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
    3636
     
    3939    public override IDeepCloneable Clone(Cloner cloner) {
    4040      return new BottomUpSimilarityCalculator(this, cloner);
     41    }
     42
     43    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     44      if (t1 == t2)
     45        return 1;
     46
     47      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
     48      return 2.0 * map.Count / (t1.Length + t2.Length);
    4149    }
    4250
     
    5260        throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
    5361
    54       var similarity = CalculateSolutionSimilarity(t1, t2);
     62      var similarity = CalculateSimilarity(t1, t2);
    5563      if (similarity > 1.0)
    5664        throw new Exception("Similarity value cannot be greater than 1");
    5765
    5866      return similarity;
    59     }
    60 
    61     public double CalculateSolutionSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
    62       if (t1 == t2)
    63         return 1;
    64 
    65       var map = ComputeBottomUpMapping(t1.Root, t2.Root);
    66       return 2.0 * map.Count / (t1.Length + t2.Length);
    6767    }
    6868
     
    174174        }
    175175
     176        if (n == n1 || n == n2)
     177          continue;
     178
    176179        var p = n.Parent;
    177180        if (p == null)
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/MaxCommonSubtreeSimilarityCalculator.cs

    r11230 r11458  
    3030  [StorableClass]
    3131  [Item("MaxCommonSubtreeSimilarityCalculator", "A similarity calculator based on the size of the maximum common subtree between two trees")]
    32   public class MaxCommonSubtreeSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
    33     public MaxCommonSubtreeSimilarityCalculator() { }
     32  public class MaxCommonSubtreeSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator, ISymbolicDataAnalysisExpressionSimilarityCalculator {
     33    private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
     34    public bool MatchVariableNames {
     35      get { return comparer.MatchVariableNames; }
     36      set { comparer.MatchVariableNames = value; }
     37    }
     38
     39    public bool MatchVariableWeights {
     40      get { return comparer.MatchVariableWeights; }
     41      set { comparer.MatchVariableWeights = value; }
     42    }
     43
     44    public bool MatchConstantValues {
     45      get { return comparer.MatchConstantValues; }
     46      set { comparer.MatchConstantValues = value; }
     47    }
     48
     49    [StorableConstructor]
     50    protected MaxCommonSubtreeSimilarityCalculator(bool deserializing) : base(deserializing) { }
     51
     52    public override IDeepCloneable Clone(Cloner cloner) {
     53      return new MaxCommonSubtreeSimilarityCalculator(this, cloner);
     54    }
    3455
    3556    protected MaxCommonSubtreeSimilarityCalculator(MaxCommonSubtreeSimilarityCalculator original, Cloner cloner)
     
    3758    }
    3859
    39     public override IDeepCloneable Clone(Cloner cloner) {
    40       return new MaxCommonSubtreeSimilarityCalculator(this, cloner);
     60    public MaxCommonSubtreeSimilarityCalculator() {
     61      comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
     62        MatchConstantValues = true,
     63        MatchVariableNames = true,
     64        MatchVariableWeights = true
     65      };
     66    }
     67
     68    public MaxCommonSubtreeSimilarityCalculator(bool matchVariableNames, bool matchVariableWeights, bool matchConstantValues) {
     69      comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
     70        MatchConstantValues = matchConstantValues,
     71        MatchVariableNames = matchVariableNames,
     72        MatchVariableWeights = matchVariableWeights
     73      };
     74    }
     75
     76    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     77      return MaxCommonSubtreeSimilarity(t1, t2, comparer);
    4178    }
    4279
     
    4784      if (t1 == null || t2 == null)
    4885        throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
    49       var comparer = new SymbolicExpressionTreeNodeSimilarityComparer {
    50         MatchConstantValues = true,
    51         MatchVariableNames = true,
    52         MatchVariableWeights = true
    53       };
    5486
    5587      return MaxCommonSubtreeSimilarity(t1, t2, comparer);
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/PhenotypicSimilarityCalculator.cs

    r11291 r11458  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Data;
     25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2526using HeuristicLab.Optimization.Operators;
    2627using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    2930  [Item("PhenotypicSimilarityCalculator", "An operator that calculates the similarity betweeon two trees based on the correlation of their outputs.")]
    3031  [StorableClass]
    31   public class PhenotypicSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     32  public class PhenotypicSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator, ISymbolicDataAnalysisExpressionSimilarityCalculator {
    3233    public PhenotypicSimilarityCalculator(PhenotypicSimilarityCalculator original, Cloner cloner)
    3334      : base(original, cloner) {
     
    4142    public override IDeepCloneable Clone(Cloner cloner) {
    4243      return new PhenotypicSimilarityCalculator(this, cloner);
     44    }
     45
     46    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     47      throw new System.NotImplementedException();
    4348    }
    4449
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionTracing.cs

    r11388 r11458  
    4848      var parent = parentNode; // current parent
    4949
     50      IGenealogyGraphNode<ISymbolicExpressionTree> n1 = null;
     51      int i1 = -1;
     52
    5053      while (true) {
     54        if (node == n1 && index == i1)
     55          throw new InvalidOperationException("Infinite loop detected");
     56
     57        n1 = node;
     58        i1 = index;
     59
    5160        if (!node.Parents.Any()) {
    5261          // no tracing if there are no parents, return a fragment node representing the current trace
    53           var fragmentNode = new FragmentNode(node) { SubtreeIndex = index };
     62          var fragmentNode = new FragmentNode(node.Data) { SubtreeIndex = index };
    5463          if (parent != null) {
    55             var arc = new Arc(parent, fragmentNode);
     64            var arc = new GenealogyGraphArc(parent, fragmentNode);
    5665            parent.AddArc(arc);
    5766            fragmentNode.AddArc(arc);
     
    8291        if (parents.Count == 1) {
    8392          // we are tracing a mutation operation
    84           var fragmentNode = new FragmentNode(node) {
     93          var fragmentNode = new FragmentNode(node.Data) {
    8594            SubtreeIndex = index,
    8695            FragmentIndex = fragment.Index1
     
    91100            fragmentNode.AddArc(arc);
    92101          }
     102          if (node == parents[0])
     103            throw new InvalidOperationException("Node == parents[0]");
     104
    93105          node = parents[0];
    94           if (subtreeIndex == fragment.Index1) {
     106
     107          if (index == fragment.Index1) {
    95108            // index stays the same
    96           } else if (fragment.Index1 < subtreeIndex) {
    97             if (subtreeIndex < fragment.Index1 + fragmentLength) {
     109          } else if (fragment.Index1 < index) {
     110            if (index < fragment.Index1 + fragmentLength) {
    98111              // in the case of mutation, the fragment could have been introduced via a node replacement
    99112              // there is no guarantee the subtree exists above this level, therefore the index is set to the fragment index
     
    103116              index += node.Data.NodeAt(fragment.Index1).GetLength() - fragmentLength;
    104117            }
    105           } else if (subtreeIndex < fragment.Index1) {
    106             if (fragment.Index1 < subtreeIndex + subtreeLength) {
     118          } else if (index < fragment.Index1) {
     119            if (fragment.Index1 < index + subtreeLength) {
    107120              // subtree contains fragment
    108121              index = fragment.Index1;
     
    111124            }
    112125          }
    113 
    114126          yield return fragmentNode;
    115           var up = Trace(node, index, fragmentNode); // force immediate query execution
     127          if (node == graphNode && index == subtreeIndex)
     128            throw new ArgumentException("Infinite recursion detected");
     129          var up = Trace(node, index, fragmentNode).ToList(); // force immediate query execution
    116130          foreach (var v in up) { yield return v; }
    117131          break;
     
    121135        #region crossover tracing
    122136        if (parents.Count == 2) {
     137          if (node == parents[0])
     138            throw new InvalidOperationException("Node == parents[0]");
     139          if (node == parents[1])
     140            throw new InvalidOperationException("Node == parents[1]");
    123141          // we are tracing a crossover operation
    124142          if (fragment.Index1 == index) {
     
    143161            if (fragment.Index1 < index + subtreeLength) {
    144162              // subtree contains fragment => branching point in the fragment graph
    145               var fragmentNode = new FragmentNode(node) {
     163              var fragmentNode = new FragmentNode(node.Data) {
    146164                SubtreeIndex = index,
    147165                FragmentIndex = fragment.Index1
    148166              };
    149167              if (parent != null) {
    150                 var arc = new Arc(parent, fragmentNode);
     168                var arc = new GenealogyGraphArc(parent, fragmentNode);
    151169                parent.AddArc(arc);
    152170                fragmentNode.AddArc(arc);
     
    176194      return writer.ToString();
    177195    }
    178     #region some helper methods for shortening the tracing code
    179     private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int position) {
    180       return NodeAt(tree.Root, position);
    181     }
    182     private static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int position) {
    183       return root.IterateNodesPrefix().ElementAt(position);
    184     }
    185     #endregion
    186196  }
    187197}
Note: See TracChangeset for help on using the changeset viewer.