source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs @ 11458

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2014 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.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Crossovers {
  [Item("SymbolicDataAnalysisExpressionDiversityPreservingCrossover", "A crossover operator which tries to preserve diversity by favoring duplicate nodes as crossover points in the tree")]
  [StorableClass]
  public sealed class SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
    private const string SimilarityCalculatorParameterName = "SimilarityCalculator";
    private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";

    #region Parameter Properties
    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
      get { return (IValueLookupParameter<PercentValue>)Parameters[InternalCrossoverPointProbabilityParameterName]; }
    }
    public IValueParameter<ISymbolicDataAnalysisExpressionSimilarityCalculator> SimilarityCalculatorParameter {
      get { return (IValueParameter<ISymbolicDataAnalysisExpressionSimilarityCalculator>)Parameters[SimilarityCalculatorParameterName]; }
    }
    #endregion

    public ISymbolicDataAnalysisExpressionSimilarityCalculator SimilarityCalculator {
      get { return SimilarityCalculatorParameter.Value; }
    }

    private SymbolicDataAnalysisExpressionDiversityPreservingCrossover(SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> original, Cloner cloner)
      : base(original, cloner) {
    }

    public SymbolicDataAnalysisExpressionDiversityPreservingCrossover() {
      Parameters.Add(new ValueLookupParameter<PercentValue>(InternalCrossoverPointProbabilityParameterName, "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
      Parameters.Add(new ValueParameter<ISymbolicDataAnalysisExpressionSimilarityCalculator>(SimilarityCalculatorParameterName, "The similarity calculator", new BottomUpSimilarityCalculator()));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T>(this, cloner);
    }

    [StorableConstructor]
    private SymbolicDataAnalysisExpressionDiversityPreservingCrossover(bool deserializing) : base(deserializing) { }

    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
      int maximumTreeLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
      int maximumTreeDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
      double internalCrossoverPointProbability = InternalCrossoverPointProbabilityParameter.ActualValue.Value;

      return Cross(random, parent0, parent1, SimilarityCalculator, maximumTreeDepth, maximumTreeLength);
    }

    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, ISymbolicDataAnalysisExpressionSimilarityCalculator similarityCalculator, int maxDepth, int maxLength) {
      var actualRoot = parent0.Root.GetSubtree(0).GetSubtree(0);
      while (actualRoot.SubtreeCount > 0 && actualRoot.SubtreeCount < 2) actualRoot = actualRoot.GetSubtree(0);
      if (actualRoot.SubtreeCount == 0) return parent0;
      var left = actualRoot.GetSubtree(0);
      var right = actualRoot.GetSubtree(1);
      var bus = (BottomUpSimilarityCalculator)similarityCalculator;
      var map = bus.ComputeBottomUpMapping(left, right);

      var crossoverPoints = parent0.IterateNodesPostfix().Where(x => x.Parent != null && x.Parent != parent0.Root).Select(x => new CutPoint(x.Parent, x)).ToList();
      var weights = crossoverPoints.Select(x => map.ContainsKey(x.Child) ? 3D : x.Child.SubtreeCount > 0 ? 2D : 1D);

      var cutpoint = crossoverPoints.SelectRandom(weights, random);
      int level = parent0.Root.GetBranchLevel(cutpoint.Child);
      int length = parent0.Root.GetLength() - cutpoint.Child.GetLength();

      var allowedBranches = parent1.IterateNodesPostfix().Where(x => x.Parent != null &&
                                                                x.Parent != parent1.Root &&
                                                                x.GetDepth() + level <= maxDepth &&
                                                                x.GetLength() + length <= maxLength &&
                                                                cutpoint.IsMatchingPointType(x)).ToList();
      if (!allowedBranches.Any())
        return parent0;

      var selectedBranch = allowedBranches.SelectRandom(random);

      // swap the node that would create the best offspring
      Swap(cutpoint, selectedBranch);
      return parent0;
    }
  }
}