Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/09/12 09:56:56 (13 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.