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

#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);
    }
  }
}