Changeset 7785


Ignore:
Timestamp:
05/09/12 09:56:56 (8 years ago)
Author:
bburlacu
Message:

#1772: Moved tree matching functionality in separate class, implemented new tree fragments analyzer. Fixed bug in GetCutIndex method.

Location:
branches/HeuristicLab.EvolutionaryTracking
Files:
2 added
2 deleted
13 edited

Legend:

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

    r7522 r7785  
    6464      }
    6565    }
     66
     67    public static CutPoint GetCutPoint(ISymbolicExpressionTree parent, ISymbolicExpressionTree child) {
     68      return GetCutPoint(parent.Root, child.Root);
     69    }
     70
     71    public static CutPoint GetCutPoint(ISymbolicExpressionTree parent, ISymbolicExpressionTreeNode child) {
     72      return GetCutPoint(parent.Root, child);
     73    }
     74
     75    public static CutPoint GetCutPoint(ISymbolicExpressionTreeNode parent, ISymbolicExpressionTree child) {
     76      return GetCutPoint(parent, child.Root);
     77    }
     78
     79    // child is the result of a genetic operation on parent
     80    // this method returns the index on which the two individuals start to differ
     81    public static CutPoint GetCutPoint(ISymbolicExpressionTreeNode parent, ISymbolicExpressionTreeNode child) {
     82      var e1 = parent.IterateNodesPostfix().GetEnumerator();
     83      var e2 = child.IterateNodesPostfix().GetEnumerator();
     84      int pos = -1;
     85      var comparer = new SymbolicExpressionTreeNodeComparer((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
     86      while (e1.MoveNext() && e2.MoveNext())
     87        if (comparer.Equals(e1.Current, e2.Current))
     88          ++pos;
     89      return pos == -1 ? null : new CutPoint(parent, pos);
     90    }
    6691  }
    6792}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r7479 r7785  
    133133      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
    134134    </Reference>
     135    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     136      <SpecificVersion>False</SpecificVersion>
     137      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.dll</HintPath>
     138    </Reference>
    135139    <Reference Include="HeuristicLab.Random-3.3">
    136140      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     
    174178    </Compile>
    175179    <Compile Include="Creators\RampedHalfAndHalfTreeCreator.cs" />
     180    <Compile Include="Crossovers\AssortativeSymbolicExpressionTreeCrossover.cs" />
    176181    <Compile Include="Crossovers\TracingSymbolicExpressionTreeCrossover.cs" />
    177182    <Compile Include="Interfaces\IReadOnlySymbol.cs" />
     
    206211    <Compile Include="SymbolicExpressionGrammar.cs" />
    207212    <Compile Include="SymbolicExpressionTreeGrammar.cs" />
     213    <Compile Include="SymbolicExpressionTreeMatching.cs" />
    208214    <Compile Include="SymbolicExpressionTreeTopLevelNode.cs" />
    209215    <Compile Include="Crossovers\SubtreeCrossover.cs">
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj.user

    r7514 r7785  
    77  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|AnyCPU'">
    88    <StartAction>Program</StartAction>
    9     <StartProgram>C:\Users\bburlacu\Desktop\HL-Core\trunk\sources\bin\HeuristicLab 3.3.exe</StartProgram>
     9    <StartProgram>C:\Users\Bogdan\Desktop\Trunk\sources\bin\HeuristicLab 3.3.exe</StartProgram>
    1010  </PropertyGroup>
    1111  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x86'">
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Plugin.cs

    r7779 r7785  
    2626
    2727namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    28   [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7522")]
     28  [Plugin("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding","Provides operators and related classes for the symbolic expression tree encoding.", "3.4.2.7779")]
    2929  [PluginFile("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Analysis", "3.3")]
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/GenealogyGraphChart.cs

    r7779 r7785  
    177177          foreach (var node in ancestors.SelectMany(n => _visualNodeMap[n])) {
    178178            node.Brush = new SolidBrush(node.ToColor());
    179             if (node.IncomingArcs != null && node == _visualNodeMap[node.Data].First())
     179            if (node.IncomingArcs != null && node == _visualNodeMap[node.Data].First()) {
    180180              foreach (var arc in node.IncomingArcs) {
    181181                if (arc.Source.Data == node.Data) continue;
     
    183183                var end = new Point((int)arc.End.X, (int)arc.End.Y);
    184184                arc.Pen.Brush = new LinearGradientBrush(start, end, arc.Source.ToColor(), arc.Target.ToColor());
    185                 if (node.Data.CutpointIndex == -1) { // if the cut index wasn't computed yet
     185                if (node.Data.CutpointIndex == -1) {
     186                  // if the cut index wasn't computed yet
    186187                  var parent = arc.Source.Data.Data as ISymbolicExpressionTree;
    187188                  var child = node.Data.Data as ISymbolicExpressionTree;
     
    189190                }
    190191              }
     192            }
    191193          }
    192194          // highlight the descendants
     
    208210        Chart.UpdateEnabled = true;
    209211        Chart.EnforceUpdate();
    210         if (_selectedGenealogyGraphNode != null) /* emit clicked event */ OnGenealogyGraphNodeClicked(_selectedGenealogyGraphNode, e);
     212        if (_selectedGenealogyGraphNode != null)
     213          /* emit clicked event */
     214          OnGenealogyGraphNodeClicked(_selectedGenealogyGraphNode, e);
    211215      }
    212216    }
     
    238242      var e1 = parent.IterateNodesPostfix().GetEnumerator();
    239243      var e2 = child.IterateNodesPostfix().GetEnumerator();
    240       int pos = -1;
    241       var comparer = new SymbolicExpressionTreeGenealogyGraph.SymbolicExpressionTreeNodeComparer(0);
     244      int pos = 0;
     245      var comparer = new SymbolicExpressionTreeNodeComparer((int)SymbolicExpressionTreeMatching.SimilarityLevel.Exact);
    242246      while (e1.MoveNext() && e2.MoveNext() && comparer.Equals(e1.Current, e2.Current)) ++pos;
     247      if (pos == 0) return -1;
     248      if (pos == child.Length) return 0;
    243249      return pos;
     250      //return pos == 0 ? -1 : pos;
    244251    }
    245252  }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking.Views/3.4/GenealogyGraphView.cs

    r7779 r7785  
    9494        var nodes = symbolicExpressionTreeChart.Tree.IterateNodesPostfix().ToArray();
    9595        var fragments = _selectedVisualSymbolicExpressionTreeNode.SymbolicExpressionTreeNode.IterateNodesPostfix().ToArray();
    96         int index = SymbolicExpressionTreeGenealogyGraph.FindMatch(nodes, fragments, similarityModeSelector.SelectedIndex);
     96        int index = SymbolicExpressionTreeMatching.FindMatch(nodes, fragments, similarityModeSelector.SelectedIndex);
    9797        if (index != -1) {
    9898          _selectedVisualSymbolicExpressionTreeNode = symbolicExpressionTreeChart.GetVisualSymbolicExpressionTreeNode(nodes[index + fragments.Count() - 1]);
     
    143143      genealogyGraphChart.ClearAllNodes(); // clear node colors
    144144      // color each graph node according to the degree to which it matches the selected tree fragment
    145       foreach (var i in Enum.GetValues(typeof(SymbolicExpressionTreeGenealogyGraph.SimilarityLevel)).Cast<int>().Reverse()) {
     145      foreach (var i in Enum.GetValues(typeof(SymbolicExpressionTreeMatching.SimilarityLevel)).Cast<int>().Reverse()) {
    146146        var owners = genealogyGraphChart.Graph.TraceFragment(treeNode, i).ToList();
    147147        if (owners.Any()) genealogyGraphChart.HighlightNodes(owners, colors[i]); // highlight matching individuals from the genealogy
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/Analyzers/SymbolicExpressionTreeGenealogyAnalyzer.cs

    r7779 r7785  
    3737using HeuristicLab.Problems.DataAnalysis;
    3838using HeuristicLab.Problems.DataAnalysis.Symbolic;
     39// type definitions for ease of use
    3940using CloneMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItem>;
    4041using TraceMapType = HeuristicLab.Core.ItemDictionary<HeuristicLab.Core.IItem, HeuristicLab.Core.IItemList<HeuristicLab.Core.IItem>>;
     
    4748  [StorableClass]
    4849  public sealed class SymbolicExpressionTreeGenealogyAnalyzer : SingleSuccessorOperator, IAnalyzer {
    49     public enum GeneticOperator { Crossover, Mutation }
    50 
    5150    private const string UpdateIntervalParameterName = "UpdateInterval";
    5251    private const string UpdateCounterParameterName = "UpdateCounter";
     
    220219          Results.Add(new Result(PopulationGraphResultParameterName, PopulationGraphResultParameterDescription, graph));
    221220        } else {
    222           graph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphResultParameterName].Value;
    223         }
    224         // get tree quality values
     221          //graph = (SymbolicExpressionTreeGenealogyGraph)Results[PopulationGraphResultParameterName].Value;
     222          graph = (SymbolicExpressionTreeGenealogyGraph)(Results[PopulationGraphResultParameterName].Value);
     223        }
     224        // get tree quality values (Key => Individual, Value => Quality)
    225225        var qualities = (from s in gScope.SubScopes
    226226                         let individual = s.Variables.First().Value
     
    232232        int generation = Generations.Value;
    233233        string label;
    234 
    235234        if (generation == 0) {
    236235          // at generation 0 no trace map is present (since no reproduction has taken place yet), so we only add the initial trees as nodes in the genealogy graph
     
    252251
    253252          foreach (var parent in parents) {
    254             int opType;
    255253            if (GlobalTraceMap.ContainsKey(parent)) {
    256254              double quality = Evaluate((ISymbolicExpressionTree)parent);
     
    258256              var pp = GlobalTraceMap[parent];
    259257              foreach (var p in pp) {
    260                 opType = pp.Count == 2 ? (int)GeneticOperator.Crossover : (int)GeneticOperator.Mutation;
    261                 graph.AddArc((ISymbolicExpressionTree)p, (ISymbolicExpressionTree)parent, opType);
     258                graph.AddArc((ISymbolicExpressionTree)p, (ISymbolicExpressionTree)parent);
    262259              }
    263260            }
    264             opType = parents.Count == 2 ? (int)GeneticOperator.Crossover : (int)GeneticOperator.Mutation;
    265             graph.AddArc((ISymbolicExpressionTree)parent, child, opType);
     261            graph.AddArc((ISymbolicExpressionTree)parent, child);
    266262          }
    267263        }
     
    319315    }
    320316
     317 
     318
    321319    private double Evaluate(ISymbolicExpressionTree tree) {
    322320      // we perform evaluation by adding a temporary subscope with the tree in it, and calling evaluator.Apply()
     
    368366    }
    369367    #endregion
    370 
    371     #region Extra / not really needed
    372     // method of iterating tree nodes in a breadth-wise manner
    373     private IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTree tree) {
    374       return IterateNodes(tree.Root);
    375     }
    376 
    377     private static IEnumerable<ISymbolicExpressionTreeNode> IterateNodes(ISymbolicExpressionTreeNode root) {
    378       var list = new List<ISymbolicExpressionTreeNode> { root };
    379       int offset = 0, count = 1;
    380       while (offset != count) {
    381         var c = count;
    382         for (int i = offset; i != count; ++i) {
    383           yield return list[i];
    384           if (!list[i].Subtrees.Any()) continue;
    385           list.AddRange(list[i].Subtrees);
    386         }
    387         offset = c;
    388         count = list.Count;
    389       }
    390     }
    391     #endregion
    392368  }
    393369}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/GenealogyGraph.cs

    r7779 r7785  
    5050
    5151    [StorableConstructor]
    52     private GenealogyGraph(bool serializing)
     52    protected GenealogyGraph(bool serializing)
    5353      : base(serializing) {
    5454    }
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/HeuristicLab.EvolutionaryTracking-3.4.csproj

    r7779 r7785  
    3838  </PropertyGroup>
    3939  <ItemGroup>
     40    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL" />
    4041    <Reference Include="HeuristicLab.Collections-3.3">
    4142      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath>
     
    8384  </ItemGroup>
    8485  <ItemGroup>
     86    <Compile Include="Analyzers\SymbolicExpressionTreeFragmentsAnalyzer.cs" />
    8587    <Compile Include="Analyzers\SymbolicExpressionTreeGenealogyAnalyzer.cs" />
    8688    <Compile Include="GenealogyGraph.cs" />
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.EvolutionaryTracking/3.4/SymbolicExpressionTreeGenealogyGraph.cs

    r7779 r7785  
    1 using System;
    2 using System.Collections.Generic;
    3 using System.Globalization;
     1using System.Collections.Generic;
    42using System.Linq;
    53using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    6 using HeuristicLab.Problems.DataAnalysis.Symbolic;
     4using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    75
    86namespace HeuristicLab.EvolutionaryTracking {
    97  public class SymbolicExpressionTreeGenealogyGraph : GenealogyGraph<ISymbolicExpressionTree> {
    10     public enum SimilarityLevel { Exact, High, Relaxed }
     8    public SymbolicExpressionTreeGenealogyGraph() {
     9    }
    1110
    12     private readonly Dictionary<int, Func<ISymbolicExpressionTreeNode, string>> _dispatcher;
    13 
    14     public delegate string HashFunction(ISymbolicExpressionTreeNode node);
    15 
    16     public SymbolicExpressionTreeGenealogyGraph() {
    17       _dispatcher = new Dictionary<int, Func<ISymbolicExpressionTreeNode, string>>();
    18       _dispatcher[(int)SimilarityLevel.Exact] = GetExactString;
    19       _dispatcher[(int)SimilarityLevel.High] = GetHighLevelString;
    20       _dispatcher[(int)SimilarityLevel.Relaxed] = GetRelaxedString;
     11    [StorableConstructor]
     12    public SymbolicExpressionTreeGenealogyGraph(bool serializing)
     13      : base(serializing) {
    2114    }
    2215
    2316    #region Fragment tracing
    2417    public IEnumerable<ISymbolicExpressionTree> TraceFragment(ISymbolicExpressionTreeNode fragment, int mode = 0) {
    25       return Keys.Where(tree => ContainsFragment(tree, fragment, mode) != -1);
     18      //return Keys.Where(tree => ContainsFragment(tree, fragment, mode) != -1);
     19      return Keys.Where(tree => tree.ContainsFragment(fragment, mode));
    2620    }
    27 
    28     public static bool CheckSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, int mode) {
    29       return FindMatch(t1, t2, mode) == 0;
    30     }
    31 
    32     public static int ContainsFragment(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode fragment, int mode) {
    33       var nodes = tree.IterateNodesPostfix().ToArray();
    34       var fragments = fragment.IterateNodesPostfix().ToArray();
    35       return FindMatch(nodes, fragments, mode);
    36     }
    37 
    38     // Build a string hash out of all node symbols and parameter values (trimmed to 4 decimal places)
    39     private static string GetExactString(ISymbolicExpressionTreeNode node) {
    40       if (node is ConstantTreeNode) {
    41         var constant = node as ConstantTreeNode;
    42         return (constant.Symbol + string.Format("{0:0.0000}", constant.Value));
    43       }
    44       if (node is VariableTreeNode) {
    45         var variable = node as VariableTreeNode;
    46         return (variable.Symbol + variable.VariableName + variable.Weight);
    47       }
    48       return (node.Symbol.ToString());
    49     }
    50 
    51     // Build a string hash out of all node symbols in their respective order
    52     private static string GetHighLevelString(ISymbolicExpressionTreeNode node) {
    53       return (node.Symbol.ToString());
    54     }
    55 
    56     // Build a string hash which only considers function symbols and function arities. leaf nodes are taken as "wildcards"
    57     private static string GetRelaxedString(ISymbolicExpressionTreeNode node) {
    58       if (node.SubtreeCount != 0) /* function node */ {
    59         return (node.Symbol + node.SubtreeCount.ToString(CultureInfo.InvariantCulture));
    60       }
    61       return string.Empty;
    62     }
    63 
    6421    #endregion
    65     public class SymbolicExpressionTreeNodeComparer : IEqualityComparer<ISymbolicExpressionTreeNode> {
    66       public SymbolicExpressionTreeNodeComparer(int similarityLevel) { _similarityLevel = similarityLevel; }
    67 
    68       public int GetHashCode(ISymbolicExpressionTreeNode n) { return n.ToString().ToLower().GetHashCode(); }
    69 
    70       public bool Equals(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    71         if (a.SubtreeCount != b.SubtreeCount) { return false; }
    72         if (a.SubtreeCount > 0) { return a.Symbol.ToString().Equals(b.Symbol.ToString()); }
    73         switch (_similarityLevel) {
    74           case ((int)SimilarityLevel.Exact):
    75             if (a is ConstantTreeNode && b is ConstantTreeNode) { return (a as ConstantTreeNode).Value.Equals((b as ConstantTreeNode).Value); }
    76             if (a is VariableTreeNode && b is VariableTreeNode) { return (a as VariableTreeNode).Weight.Equals((b as VariableTreeNode).Weight); }
    77             return false;
    78           case ((int)SimilarityLevel.High):
    79             return (a is ConstantTreeNode && b is ConstantTreeNode) || (a is VariableTreeNode && b is VariableTreeNode);
    80           case ((int)SimilarityLevel.Relaxed):
    81             return true;
    82           default:
    83             return false;
    84         }
    85       }
    86       private readonly int _similarityLevel;
    87     }
    88 
    89     private static int FindMatch(ISymbolicExpressionTree t0, ISymbolicExpressionTree t1, int mode) {
    90       return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
    91     }
    92 
    93     private static int FindMatch(ISymbolicExpressionTreeNode t0, ISymbolicExpressionTreeNode t1, int mode) {
    94       return FindMatch(t0.IterateNodesPostfix().ToArray(), t1.IterateNodesPostfix().ToArray(), mode);
    95     }
    96 
    97     // returns the index in the sequence 'seq', where pattern 'pat' is matched, or -1 for no match
    98     // -1 means no match, 0 means perfect match (the sequences overlap, hence the match index is 0)
    99     public static int FindMatch(ISymbolicExpressionTreeNode[] seq, ISymbolicExpressionTreeNode[] pat, int mode) {
    100       int patlen = pat.Length;
    101       int seqlen = seq.Length;
    102       if (patlen == 0 || seqlen == 0) return -1;
    103       var comparer = new SymbolicExpressionTreeNodeComparer(mode);
    104       if (patlen == seqlen) return seq.SequenceEqual(pat, comparer) ? 0 : -1;
    105       int i = patlen;
    106       while (i <= seqlen) {
    107         var ch = seq[i - 1];
    108         if (comparer.Equals(ch, pat.Last())) {
    109           if (seq.Skip(i - patlen).Take(patlen).SequenceEqual(pat, comparer)) {
    110             return i - patlen;
    111           }
    112         }
    113         ++i;
    114       }
    115       return -1;
    116     }
    11722  }
    11823}
  • branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Selection/3.3/Plugin.cs

    r7779 r7785  
    2626  /// Plugin class for HeuristicLab.Selection plugin.
    2727  /// </summary>
    28   [Plugin("HeuristicLab.Selection", "3.3.6.0")]
     28  [Plugin("HeuristicLab.Selection", "3.3.6.7779")]
    2929  [PluginFile("HeuristicLab.Selection-3.3.dll", PluginFileType.Assembly)]
    3030  [PluginDependency("HeuristicLab.Collections", "3.3")]
Note: See TracChangeset for help on using the changeset viewer.