Index: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionStructuralSimilarityCrossover.cs
===================================================================
--- branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionStructuralSimilarityCrossover.cs	(revision 9963)
+++ branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionStructuralSimilarityCrossover.cs	(revision 9963)
@@ -0,0 +1,150 @@
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
+  [Item("SemanticSimilarityCrossover",
+    "An operator which performs subtree swapping based on the notion of structural similarity between subtrees\n" +
+    "(criteria: structural similarity coefficient between the subtrees must be lower than given threshold.)\n" +
+    "- Take two parent individuals P0 and P1\n" +
+    "- Randomly choose a node N from the P0\n" +
+    "- Find the first node M that satisfies the structural similarity criteria\n" +
+    "- Swap N for M and return P0")]
+  public sealed class SymbolicDataAnalysisExpressionStructuralSimilarityCrossover<T> :
+    SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
+    private const string StructuralSimilarityThresholdParameterName = "StructuralSimilarityThresholdParameterName";
+    private const string MatchVariablesParameterName = "MatchVariableNames";
+    private const string MatchVariableWeightsParameterName = "MatchVariableWeights";
+    private const string MatchConstantValuesParameterName = "MatchConstantValues";
+    private const string ResultsParameterName = "Results";
+
+    private readonly SymbolicExpressionTreeNodeSimilarityComparer comparer;
+
+    #region Parameter properties
+    private ValueParameter<DoubleValue> StructuralSimilarityThresholdParameter {
+      get { return (ValueParameter<DoubleValue>)Parameters[StructuralSimilarityThresholdParameterName]; }
+    }
+    public ValueParameter<BoolValue> MatchVariableNamesParameter {
+      get { return (ValueParameter<BoolValue>)Parameters[MatchVariablesParameterName]; }
+    }
+    public ValueParameter<BoolValue> MatchVariableWeightsParameter {
+      get { return (ValueParameter<BoolValue>)Parameters[MatchVariableWeightsParameterName]; }
+    }
+    public ValueParameter<BoolValue> MatchConstantValuesParameter {
+      get { return (ValueParameter<BoolValue>)Parameters[MatchConstantValuesParameterName]; }
+    }
+    public LookupParameter<ResultCollection> ResultsParameter {
+      get { return (LookupParameter<ResultCollection>)Parameters[ResultsParameterName]; }
+    }
+    #endregion
+    #region Properties
+    private DoubleValue StructuralSimilarityThreshold { get { return StructuralSimilarityThresholdParameter.Value; } }
+    public ResultCollection Results { get { return ResultsParameter.ActualValue; } }
+    #endregion
+
+    [StorableConstructor]
+    private SymbolicDataAnalysisExpressionStructuralSimilarityCrossover(bool deserializing)
+      : base(deserializing) {
+      if (comparer == null) comparer = new SymbolicExpressionTreeNodeSimilarityComparer();
+    }
+
+    private SymbolicDataAnalysisExpressionStructuralSimilarityCrossover(
+      SymbolicDataAnalysisExpressionCrossover<T> original, Cloner cloner)
+      : base(original, cloner) {
+      if (comparer == null) comparer = new SymbolicExpressionTreeNodeSimilarityComparer();
+    }
+
+    public SymbolicDataAnalysisExpressionStructuralSimilarityCrossover()
+      : base() {
+      Parameters.Add(new ValueParameter<DoubleValue>(StructuralSimilarityThresholdParameterName, new DoubleValue(0.8)));
+      Parameters.Add(new ValueParameter<BoolValue>(MatchVariablesParameterName, "Specify if the symbolic expression tree comparer should match variable names.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<BoolValue>(MatchVariableWeightsParameterName, "Specify if the symbolic expression tree comparer should match variable weights.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<BoolValue>(MatchConstantValuesParameterName, "Specify if the symbolic expression tree comparer should match constant values.", new BoolValue(true)));
+      Parameters.Add(new ValueLookupParameter<ResultCollection>(ResultsParameterName, "The results collection where the analysis values should be stored."));
+
+      name = "StructuralSimilarityCrossover";
+
+      comparer = new SymbolicExpressionTreeNodeSimilarityComparer { MatchConstantValues = true, MatchVariableNames = true, MatchVariableWeights = true };
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new SymbolicDataAnalysisExpressionStructuralSimilarityCrossover<T>(this, cloner);
+    }
+
+    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
+      comparer.MatchConstantValues = MatchConstantValuesParameter.Value.Value;
+      comparer.MatchVariableNames = MatchVariableNamesParameter.Value.Value;
+      comparer.MatchVariableWeights = MatchVariableWeightsParameter.Value.Value;
+
+      if (CalculateSimilarity(parent0.Root, parent1.Root, comparer) > StructuralSimilarityThreshold.Value)
+        return parent0;
+      return Cross(random, parent0, parent1, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value, StructuralSimilarityThreshold, comparer);
+    }
+
+    /// <summary>
+    /// Takes two parent individuals P0 and P1. 
+    /// Randomly choose a node i from the first parent, then get a node j from the second parent that matches the semantic similarity criteria.
+    /// </summary>
+    public ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, int maxDepth, int maxLength,
+                                                DoubleValue structuralSimilarityThreshold, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+      var crossoverPoints0 = new List<CutPoint>();
+      parent0.Root.ForEachNodePostfix(n => {
+        if (n.Parent != null && n.Parent != parent0.Root)
+          crossoverPoints0.Add(new CutPoint(n.Parent, n));
+      });
+      var crossoverPoint0 = crossoverPoints0.SelectRandom(random);
+      int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
+      int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
+
+      var allowedBranches = new List<ISymbolicExpressionTreeNode>();
+      parent1.Root.ForEachNodePostfix(n => {
+        if (n.Parent != null && n.Parent != parent1.Root) {
+          if (n.GetDepth() + level <= maxDepth && n.GetLength() + length <= maxLength &&
+              crossoverPoint0.IsMatchingPointType(n))
+            allowedBranches.Add(n);
+        }
+      });
+      ISymbolicExpressionTreeNode selectedBranch = null;
+      if (allowedBranches.Count == 0) return parent0;
+      var b = allowedBranches.SelectRandom(random);
+      if (CalculateSimilarity(crossoverPoint0.Child, b, comparer) < structuralSimilarityThreshold.Value)
+        selectedBranch = b;
+      // perform the actual swap
+      if (selectedBranch != null) {
+        Swap(crossoverPoint0, selectedBranch);
+      }
+
+      return parent0;
+    }
+
+    private static double CalculateSimilarity(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b, SymbolicExpressionTreeNodeSimilarityComparer comparer) {
+      return SymbolicDataAnalysisExpressionTreeSimilarity.CalculateSimilarity(a, b, comparer);
+    }
+  }
+}
