source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs @ 12970

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

namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
  [Item("SchemaEvaluator", "An operator that builds schemas based on the heredity relationship in the genealogy graph.")]
  [StorableClass]
  public class SchemaEvaluator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
    #region parameter names
    private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
    private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
    private const string ReplacementRatioParameterName = "ReplacementRatio";
    private const string SchemaParameterName = "Schema";
    private const string PopulationSizeParameterName = "PopulationSize";
    private const string RandomParameterName = "Random";
    private const string EvaluatorParameterName = "Evaluator";
    private const string ProblemDataParameterName = "ProblemData";
    private const string InterpreterParameterName = "SymbolicExpressionTreeInterpreter";
    private const string EstimationLimitsParameterName = "EstimationLimits";
    private const string ApplyLinearScalingParameterName = "ApplyLinearScaling";
    private const string MutatorParameterName = "Mutator";
    private const string RandomReplacementParameterName = "RandomReplacement";
    private const string ChangedTreesParameterName = "ChangedTrees";
    #endregion

    #region parameters
    public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>> EvaluatorParameter {
      get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>)Parameters[EvaluatorParameterName]; }
    }
    public ILookupParameter<IRegressionProblemData> ProblemDataParameter {
      get { return (ILookupParameter<IRegressionProblemData>)Parameters[ProblemDataParameterName]; }
    }
    public ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter> InterpreterParameter {
      get { return (ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[InterpreterParameterName]; }
    }
    public ILookupParameter<DoubleLimit> EstimationLimitsParameter {
      get { return (ILookupParameter<DoubleLimit>)Parameters[EstimationLimitsParameterName]; }
    }
    public ILookupParameter<BoolValue> ApplyLinearScalingParameter {
      get { return (ILookupParameter<BoolValue>)Parameters[ApplyLinearScalingParameterName]; }
    }
    public ILookupParameter<BoolValue> RandomReplacementParameter {
      get { return (ILookupParameter<BoolValue>)Parameters[RandomReplacementParameterName]; }
    }
    public ILookupParameter<ISymbolicExpressionTreeManipulator> MutatorParameter {
      get { return (ILookupParameter<ISymbolicExpressionTreeManipulator>)Parameters[MutatorParameterName]; }
    }
    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters[RandomParameterName]; }
    }
    public ILookupParameter<IntValue> PopulationSizeParameter {
      get { return (ILookupParameter<IntValue>)Parameters[PopulationSizeParameterName]; }
    }
    public ILookupParameter<ISymbolicExpressionTree> SchemaParameter {
      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters[SchemaParameterName]; }
    }
    public ILookupParameter<PercentValue> MinimumSchemaFrequencyParameter {
      get { return (ILookupParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
    }
    public ILookupParameter<PercentValue> ReplacementRatioParameter {
      get { return (ILookupParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
    }
    public ILookupParameter<PercentValue> MinimumPhenotypicSimilarityParameter {
      get { return (ILookupParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
    }
    public LookupParameter<IntValue> ChangedTreesParameter {
      get { return (LookupParameter<IntValue>)Parameters[ChangedTreesParameterName]; }
    }
    #endregion

    #region parameter properties
    public PercentValue MinimumSchemaFrequency {
      get { return MinimumSchemaFrequencyParameter.ActualValue; }
    }

    public PercentValue ReplacementRatio {
      get { return ReplacementRatioParameter.ActualValue; }
    }

    public PercentValue MinimumPhenotypicSimilarity {
      get { return MinimumPhenotypicSimilarityParameter.ActualValue; }
    }

    public BoolValue RandomReplacement {
      get { return RandomReplacementParameter.ActualValue; }
    }
    #endregion

    private readonly SymbolicExpressionTreePhenotypicSimilarityCalculator calculator = new SymbolicExpressionTreePhenotypicSimilarityCalculator();
    private readonly QueryMatch qm;

    private readonly ISymbolicExpressionTreeNodeEqualityComparer comp = new SymbolicExpressionTreeNodeEqualityComparer {
      MatchConstantValues = false,
      MatchVariableWeights = false,
      MatchVariableNames = true
    };


    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      if (!Parameters.ContainsKey(ChangedTreesParameterName))
        Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
    }

    public SchemaEvaluator() {
      qm = new QueryMatch(comp) { MatchParents = true };

      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
      Parameters.Add(new LookupParameter<PercentValue>(MinimumSchemaFrequencyParameterName));
      Parameters.Add(new LookupParameter<PercentValue>(ReplacementRatioParameterName));
      Parameters.Add(new LookupParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName));
      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(PopulationSizeParameterName));
      Parameters.Add(new LookupParameter<IRandom>(RandomParameterName));
      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>(EvaluatorParameterName));
      Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>(InterpreterParameterName));
      Parameters.Add(new LookupParameter<DoubleLimit>(EstimationLimitsParameterName));
      Parameters.Add(new LookupParameter<BoolValue>(ApplyLinearScalingParameterName));
      Parameters.Add(new LookupParameter<ISymbolicExpressionTreeManipulator>(MutatorParameterName));
      Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
      Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
    }


    [StorableConstructor]
    protected SchemaEvaluator(bool deserializing) : base(deserializing) { }

    protected SchemaEvaluator(SchemaEvaluator original, Cloner cloner) : base(original, cloner) {
      this.comp = (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
      this.qm = new QueryMatch(comp) { MatchParents = original.qm.MatchParents };
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new SchemaEvaluator(this, cloner);
    }

    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator) {
      double similarity = 0;
      int count = individuals.Count;
      for (int i = 0; i < count - 1; ++i) {
        for (int j = i + 1; j < count; ++j) {
          similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
        }
      }
      return similarity / (count * (count - 1) / 2.0);
    }

    public override IOperation Apply() {
      var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals

      var random = RandomParameter.ActualValue;
      var mutator = MutatorParameter.ActualValue;
      var evaluator = EvaluatorParameter.ActualValue;
      var updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();

      var s = SchemaParameter.ActualValue;
      var matchingIndividuals = new ScopeList();
      foreach (var ind in individuals) {
        var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
        if (t.Length >= s.Length && qm.Match(t, s))
          matchingIndividuals.Add(ind);
      }

      if (matchingIndividuals.Count < (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count))) {
        ChangedTreesParameter.ActualValue = new IntValue(0);
        return base.Apply();
      }

      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator);
      if (similarity < MinimumPhenotypicSimilarity.Value) {
        ChangedTreesParameter.ActualValue = new IntValue(0);
        return base.Apply();
      }

      var oc = new OperationCollection();
      int n = (int)Math.Floor(matchingIndividuals.Count * ReplacementRatio.Value);
      var individualsToReplace = RandomReplacement.Value ? matchingIndividuals.SampleRandomWithoutRepetition(random, n).ToList()
                                                         : matchingIndividuals.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n).ToList();
      foreach (var ind in individualsToReplace) {
        var mutatorOp = ExecutionContext.CreateChildOperation(mutator, ind);
        var evaluatorOp = ExecutionContext.CreateChildOperation(evaluator, ind);
        var updateEstimatedValuesOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
        oc.Add(mutatorOp);
        oc.Add(evaluatorOp);
        oc.Add(updateEstimatedValuesOp);
      }
      ChangedTreesParameter.ActualValue = new IntValue(individualsToReplace.Count);
      return new OperationCollection(oc, base.Apply());
    }
  }
}