source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionStructuralSimilarityCrossover.cs @ 9963

Last change on this file since 9963 was 9963, checked in by bburlacu, 8 years ago

#1772: Merged changes from the trunk and other branches. Added new ExtendedSymbolicExpressionTreeCanvas control for the visual exploration of tree genealogies. Reorganized some files and folders.

File size: 8.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
32  [Item("SemanticSimilarityCrossover",
33    "An operator which performs subtree swapping based on the notion of structural similarity between subtrees\n" +
34    "(criteria: structural similarity coefficient between the subtrees must be lower than given threshold.)\n" +
35    "- Take two parent individuals P0 and P1\n" +
36    "- Randomly choose a node N from the P0\n" +
37    "- Find the first node M that satisfies the structural similarity criteria\n" +
38    "- Swap N for M and return P0")]
39  public sealed class SymbolicDataAnalysisExpressionStructuralSimilarityCrossover<T> :
40    SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
41    private const string StructuralSimilarityThresholdParameterName = "StructuralSimilarityThresholdParameterName";
42    private const string MatchVariablesParameterName = "MatchVariableNames";
43    private const string MatchVariableWeightsParameterName = "MatchVariableWeights";
44    private const string MatchConstantValuesParameterName = "MatchConstantValues";
45    private const string ResultsParameterName = "Results";
46
47    private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
48
49    #region Parameter properties
50    private ValueParameter<DoubleValue> StructuralSimilarityThresholdParameter {
51      get { return (ValueParameter<DoubleValue>)Parameters[StructuralSimilarityThresholdParameterName]; }
52    }
53    public ValueParameter<BoolValue> MatchVariableNamesParameter {
54      get { return (ValueParameter<BoolValue>)Parameters[MatchVariablesParameterName]; }
55    }
56    public ValueParameter<BoolValue> MatchVariableWeightsParameter {
57      get { return (ValueParameter<BoolValue>)Parameters[MatchVariableWeightsParameterName]; }
58    }
59    public ValueParameter<BoolValue> MatchConstantValuesParameter {
60      get { return (ValueParameter<BoolValue>)Parameters[MatchConstantValuesParameterName]; }
61    }
62    public LookupParameter<ResultCollection> ResultsParameter {
63      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
64    }
65    #endregion
66    #region Properties
67    private DoubleValue StructuralSimilarityThreshold { get { return StructuralSimilarityThresholdParameter.Value; } }
68    public ResultCollection Results { get { return ResultsParameter.ActualValue; } }
69    #endregion
70
71    [StorableConstructor]
72    private SymbolicDataAnalysisExpressionStructuralSimilarityCrossover(bool deserializing)
73      : base(deserializing) {
74      if (comparer == null) comparer = new SymbolicExpressionTreeNodeSimilarityComparer();
75    }
76
77    private SymbolicDataAnalysisExpressionStructuralSimilarityCrossover(
78      SymbolicDataAnalysisExpressionCrossover<T> original, Cloner cloner)
79      : base(original, cloner) {
80      if (comparer == null) comparer = new SymbolicExpressionTreeNodeSimilarityComparer();
81    }
82
83    public SymbolicDataAnalysisExpressionStructuralSimilarityCrossover()
84      : base() {
85      Parameters.Add(new ValueParameter<DoubleValue>(StructuralSimilarityThresholdParameterName, new DoubleValue(0.8)));
86      Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names.", new BoolValue(true)));
87      Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights.", new BoolValue(true)));
88      Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values.", new BoolValue(true)));
89      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
90
91      name = "StructuralSimilarityCrossover";
92
93      comparer = new SymbolicExpressionTreeNodeSimilarityComparer { MatchConstantValues = true, MatchVariableNames = true, MatchVariableWeights = true };
94    }
95
96    public override IDeepCloneable Clone(Cloner cloner) {
97      return new SymbolicDataAnalysisExpressionStructuralSimilarityCrossover<T>(this, cloner);
98    }
99
100    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
101      comparer.MatchConstantValues = MatchConstantValuesParameter.Value.Value;
102      comparer.MatchVariableNames = MatchVariableNamesParameter.Value.Value;
103      comparer.MatchVariableWeights = MatchVariableWeightsParameter.Value.Value;
104
105      if (CalculateSimilarity(parent0.Root, parent1.Root, comparer) > StructuralSimilarityThreshold.Value)
106        return parent0;
107      return Cross(random, parent0, parent1, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value, StructuralSimilarityThreshold, comparer);
108    }
109
110    /// <summary>
111    /// Takes two parent individuals P0 and P1.
112    /// Randomly choose a node i from the first parent, then get a node j from the second parent that matches the semantic similarity criteria.
113    /// </summary>
114    public ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, int maxDepth, int maxLength,
115                                                DoubleValue structuralSimilarityThreshold, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
116      var crossoverPoints0 = new List<CutPoint>();
117      parent0.Root.ForEachNodePostfix(n => {
118        if (n.Parent != null && n.Parent != parent0.Root)
119          crossoverPoints0.Add(new CutPoint(n.Parent, n));
120      });
121      var crossoverPoint0 = crossoverPoints0.SelectRandom(random);
122      int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
123      int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
124
125      var allowedBranches = new List<ISymbolicExpressionTreeNode>();
126      parent1.Root.ForEachNodePostfix(n => {
127        if (n.Parent != null && n.Parent != parent1.Root) {
128          if (n.GetDepth() + level <= maxDepth && n.GetLength() + length <= maxLength &&
129              crossoverPoint0.IsMatchingPointType(n))
130            allowedBranches.Add(n);
131        }
132      });
133      ISymbolicExpressionTreeNode selectedBranch = null;
134      if (allowedBranches.Count == 0) return parent0;
135      var b = allowedBranches.SelectRandom(random);
136      if (CalculateSimilarity(crossoverPoint0.Child, b, comparer) < structuralSimilarityThreshold.Value)
137        selectedBranch = b;
138      // perform the actual swap
139      if (selectedBranch != null) {
140        Swap(crossoverPoint0, selectedBranch);
141      }
142
143      return parent0;
144    }
145
146    private static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
147      return SymbolicDataAnalysisExpressionTreeSimilarity.CalculateSimilarity(a, b, comparer);
148    }
149  }
150}
Note: See TracBrowser for help on using the repository browser.