Changeset 11239


Ignore:
Timestamp:
07/30/14 13:44:14 (7 years ago)
Author:
bburlacu
Message:

#2215:

  • Renamed BottomUpSimilarityCalculator to BottomUpTreeSimilarityCalculator.
  • Refactored the BottomUpTreeSimilarityCalculator to accept a configurable list of commutative symbols (the children of commutative symbols need to be sorted according to their label).
  • Added MaxCommonSubtreeSimilarityCalculator performance test
  • Updated BottomUpTreeSimilarityCalculatorTest
Location:
branches/HeuristicLab.BottomUpTreeDistance
Files:
1 added
6 edited
2 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs

    r11224 r11239  
    4242
    4343    private const string ResultCollectionParameterName = "Results";
    44     private readonly BottomUpSimilarityCalculator busCalculator;
     44    private readonly BottomUpTreeSimilarityCalculator busCalculator;
    4545
    4646    public SymbolicDataAnalysisInternalDiversityAnalyzer() {
    47       busCalculator = new BottomUpSimilarityCalculator();
     47      busCalculator = new BottomUpTreeSimilarityCalculator();
    4848
    4949      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName));
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11221 r11239  
    225225    <Compile Include="Matching\SymbolicExpressionTreeNodeComparer.cs" />
    226226    <Compile Include="Matching\SymbolicExpressionTreeNodeSimilarityComparer.cs" />
    227     <Compile Include="SimilarityCalculators\BottomUpSimilarityCalculator.cs" />
     227    <Compile Include="SimilarityCalculators\BottomUpTreeSimilarityCalculator.cs" />
    228228    <Compile Include="SimilarityCalculators\MaxCommonSubtreeSimilarityCalculator.cs" />
    229229    <Compile Include="SymbolicExpressionTreeBacktransformator.cs" />
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeMatching.cs

    r10562 r11239  
    1 using System;
     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 System;
    223using System.Collections.Generic;
    324using System.Linq;
     
    2950    /// </summary>
    3051    /// <returns>Number of pairs that were matched</returns>
    31     public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comp) {
     52    public static int Match(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, ISymbolicExpressionTreeNodeSimilarityComparer comp) {
    3253      if (!comp.Equals(a, b)) return 0;
    3354      int m = a.SubtreeCount;
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpTreeSimilarityCalculator.cs

    r11236 r11239  
    3131namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3232  [StorableClass]
    33   [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
    34   public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
    35     private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
    36 
    37     public BottomUpSimilarityCalculator() { }
     33  [Item("BottomUpTreeSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
     34  public class BottomUpTreeSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     35    private readonly HashSet<string> commutativeSymbols;
     36
     37    public BottomUpTreeSimilarityCalculator() {
     38      commutativeSymbols = new HashSet<string>();
     39    }
     40
     41    public BottomUpTreeSimilarityCalculator(IEnumerable<string> commutativeSymbols) {
     42      this.commutativeSymbols = new HashSet<string>(commutativeSymbols);
     43    }
    3844
    3945    public override IDeepCloneable Clone(Cloner cloner) {
    40       return new BottomUpSimilarityCalculator(this, cloner);
    41     }
    42 
    43     protected BottomUpSimilarityCalculator(BottomUpSimilarityCalculator original, Cloner cloner)
     46      return new BottomUpTreeSimilarityCalculator(this, cloner);
     47    }
     48
     49    protected BottomUpTreeSimilarityCalculator(BottomUpTreeSimilarityCalculator original, Cloner cloner)
    4450      : base(original, cloner) {
    4551    }
     
    5763
    5864      return similarity;
     65    }
     66
     67    public bool AddCommutativeSymbol(string symbolName) {
     68      return commutativeSymbols.Add(symbolName);
     69    }
     70
     71    public bool RemoveCommutativeSymbol(string symbolName) {
     72      return commutativeSymbols.Remove(symbolName);
    5973    }
    6074
     
    187201    }
    188202
     203    /// <summary>
     204    /// This method iterates the nodes of a subtree in breadth order while also sorting the subtrees of commutative symbols based on their label.
     205    /// This is necessary in order for the mapping to be realized correctly.
     206    /// </summary>
     207    /// <param name="node">The root of the subtree</param>
     208    /// <returns>A list of nodes in breadth order (with children of commutative symbols sorted by label)</returns>
    189209    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
    190210      var list = new List<ISymbolicExpressionTreeNode> { node };
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/MaxCommonSubtreeSimilarityCalculator.cs

    r11230 r11239  
    5656    }
    5757
    58     public static double MaxCommonSubtreeSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
     58    public static double MaxCommonSubtreeSimilarity(ISymbolicExpressionTree a, ISymbolicExpressionTree b, ISymbolicExpressionTreeNodeSimilarityComparer comparer) {
    5959      int max = 0;
    6060      var rootA = a.Root.GetSubtree(0).GetSubtree(0);
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

    r11221 r11239  
    234234      Operators.Add(new SymbolicExpressionTreeLengthAnalyzer());
    235235      Operators.Add(new SingleObjectivePopulationDiversityAnalyzer());
    236       Operators.Add(new BottomUpSimilarityCalculator());
     236      Operators.Add(new BottomUpTreeSimilarityCalculator());
    237237      ParameterizeOperators();
    238238    }
     
    359359      }
    360360      foreach (var op in operators.OfType<SingleObjectivePopulationDiversityAnalyzer>()) {
    361         op.SimilarityCalculator = operators.OfType<BottomUpSimilarityCalculator>().SingleOrDefault();
     361        op.SimilarityCalculator = operators.OfType<BottomUpTreeSimilarityCalculator>().SingleOrDefault();
    362362      }
    363363    }
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpTreeSimilarityCalculatorTest.cs

    r11236 r11239  
    1414  [TestClass]
    1515  public class BottomUpSimilarityCalculatorTest {
    16     private readonly BottomUpSimilarityCalculator busCalculator;
     16    private readonly BottomUpTreeSimilarityCalculator busCalculator;
    1717    private readonly SymbolicExpressionImporter importer;
    1818
     
    2222
    2323    public BottomUpSimilarityCalculatorTest() {
    24       busCalculator = new BottomUpSimilarityCalculator();
     24      busCalculator = new BottomUpTreeSimilarityCalculator(new List<string> { "Addition", "Multiplication", "And", "Or", "Xor" });
    2525      importer = new SymbolicExpressionImporter();
    2626    }
     
    8585        }
    8686      }
     87
    8788      sw.Stop();
    88       Console.WriteLine("Elapsed time: " + sw.ElapsedMilliseconds / 1000.0 + ", Avg. similarity: " + s);
     89      Console.WriteLine("Elapsed time: " + sw.ElapsedMilliseconds / 1000.0 + ", Avg. similarity: " + s / (N * (N - 1) / 2));
    8990      Console.WriteLine(N * (N + 1) / (2 * sw.ElapsedMilliseconds / 1000.0) + " similarity calculations per second.");
    9091    }
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r11234 r11239  
    9797  </Choose>
    9898  <ItemGroup>
     99    <Compile Include="BottomUpTreeSimilarityCalculatorTest.cs" />
    99100    <Compile Include="MaxCommonSubtreeSimilarityCalculatorTest.cs" />
    100     <Compile Include="BottomUpSimilarityCalculatorTest.cs" />
    101101    <Compile Include="Properties\AssemblyInfo.cs" />
    102102    <Compile Include="SymbolicExpressionImporter.cs" />
Note: See TracChangeset for help on using the changeset viewer.