source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/BenchmarkSuite/PushBenchmarkSuiteEvaluator.cs @ 15189

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Problem.BenchmarkSuite {
  using System;
  using System.Collections.Generic;
  using System.Globalization;
  using System.Linq;

  using Common;
  using Core;
  using Expressions;

  using HeuristicLab.BenchmarkSuite;
  using HeuristicLab.Parameters;
  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Constants;

  using Interpreter;
  using Problem;
  using Stack;

  [StorableClass]
  public class PushBenchmarkSuiteEvaluator : ParameterizedNamedItem, IPushEvaluator {

    private const string DataBoundsParameterName = "DataBounds";
    private const string DataParameterName = "Data";
    private const string DataParameterDescription = "Program Synthesis";

    public PushBenchmarkSuiteEvaluator() {
      Parameters.Add(new FixedValueParameter<DataBounds>(DataBoundsParameterName));

      Parameters.Add(new ValueParameter<ProblemData>(
        DataParameterName,
        DataParameterDescription));
    }

    public PushBenchmarkSuiteEvaluator(ProblemData data) : this() {
      LoadData(data);
    }

    [StorableConstructor]
    public PushBenchmarkSuiteEvaluator(bool deserializing) : base(deserializing) { }

    public PushBenchmarkSuiteEvaluator(PushBenchmarkSuiteEvaluator origin, Cloner cloner) : base(origin, cloner) {
      Data = cloner.Clone(origin.Data);
    }

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

    public IValueParameter<ProblemData> DataParameter
    {
      get { return (IValueParameter<ProblemData>)Parameters[DataParameterName]; }
    }

    public ProblemData Data
    {
      get { return DataParameter.Value; }
      set { DataParameter.Value = value; }
    }

    public IValueParameter<DataBounds> DataBoundsParameter
    {
      get { return (IValueParameter<DataBounds>)Parameters[DataBoundsParameterName]; }
    }

    public DataBounds DataBounds
    {
      get { return DataBoundsParameter.Value; }
      set { DataBoundsParameter.Value = value; }
    }

    public void LoadData(ProblemData data) {
      Data = data;

      DataBounds.TrainingRange.Start = 0;
      DataBounds.TrainingRange.End = Data.TrainingCount;
      DataBounds.TestRange.Start = Data.TrainingCount;
      DataBounds.TestRange.End = Data.TrainingCount + Data.TestCount;
    }

    public EvaluationResult Evaluate(IPushInterpreter interpreter, PushProgram program, int start, int end) {
      var length = end - start;
      if (length <= 0) return null;

      var evaluationResult = new EvaluationResult(length);

      for (var i = start; i < end; i++) {
        var result = Evaluate(interpreter, program, i);
        evaluationResult.ExampleQualities[i - start] = result;
        evaluationResult.AvgQuality += result;
        interpreter.Reset();
      }

      evaluationResult.AvgQuality /= length;

      return evaluationResult;
    }

    public EvaluationResult EvaluateTest(IPushInterpreter interpreter, PushProgram program) {
      return Evaluate(interpreter, program, DataBounds.TestRange.Start, DataBounds.TestRange.End);
    }

    public EvaluationResult EvaluateTest(IReadOnlyPushConfiguration config, PushProgram program, IRandom random) {
      var interpreter = new PushInterpreter(config, random);
      return EvaluateTest(interpreter, program);
    }

    public EvaluationResult EvaluateTest(PushInterpreterPool pool, PushProgram program, IRandom random) {
      using (var interpreter = pool.Create(random)) {
        return EvaluateTest(interpreter, program);
      }
    }

    public EvaluationResult EvaluateTraining(IPushInterpreter interpreter, PushProgram program) {
      return Evaluate(interpreter, program, DataBounds.TrainingRange.Start, DataBounds.TrainingRange.End);
    }

    public EvaluationResult EvaluateTraining(IReadOnlyPushConfiguration config, PushProgram program, IRandom random) {
      var interpreter = new PushInterpreter(config, random);
      return EvaluateTraining(interpreter, program);
    }

    public EvaluationResult EvaluateTraining(PushInterpreterPool pool, PushProgram program, IRandom random) {
      using (var interpreter = pool.Create(random)) {
        return EvaluateTraining(interpreter, program);
      }
    }

    public double Evaluate(IPushInterpreter interpreter, PushProgram program, int exampleIndex) {
      var example = Data.Examples[exampleIndex];

      //interpreter.BooleanStack.Push(example.InputBoolean);
      //interpreter.IntegerStack.Push(example.InputInteger);
      //interpreter.FloatStack.Push(example.InputFloat);
      //interpreter.CharStack.Push(example.InputChar);
      //interpreter.StringStack.Push(example.InputString);
      //interpreter.StringVectorStack.Push(example.InputStringVector);
      //interpreter.IntegerVectorStack.Push(example.InputIntegerVector);
      //interpreter.FloatVectorStack.Push(example.InputFloatVector);

      interpreter.SetInput(
        integers: example.InputInteger,
        floats: example.InputFloat,
        booleans: example.InputBoolean,
        chars: example.InputChar,
        strings: example.InputString,
        integerVectors: example.InputIntegerVector,
        floatVectors: example.InputFloatVector,
        stringVectors: example.InputStringVector);

      interpreter.Run(program);

      switch (Data.ProblemType) {
        case ProblemType.NumberIO: return NumberIo(interpreter, example);
        case ProblemType.Median: return Median(interpreter, example);
      }

      return Default(interpreter, example);
    }

    private double Default(IPushInterpreter interpreter, Example example) {
      var result = GetDiff(example.OutputInteger, interpreter.IntegerStack, Data.WorstResult, IntegerDiffer)
             + GetDiff(example.OutputFloat, interpreter.FloatStack, Data.WorstResult, (a, b) => FloatDiffer(a, b, example.OutputFloatPrecision))
             + GetDiff(example.OutputBoolean, interpreter.BooleanStack, Data.WorstResult, BooleanDiffer)
             + GetDiff(example.OutputString, interpreter.StringStack, Data.WorstResult, StringDiffer)
             + GetDiff(example.OutputChar, interpreter.CharStack, Data.WorstResult, CharDiffer)
             + GetPrintDiffer(example.OutputPrint, interpreter.PrintStack, example.OutputPrintLineCount, Data.WorstResult)
             + GetVectorDiff(example.OutputIntegerVector, interpreter.IntegerVectorStack, Data.WorstResult, (a, b) => VectorDiffer(a, b, IntegerDiffer))
             + GetVectorDiff(example.OutputFloatVector, interpreter.FloatVectorStack, Data.WorstResult, (a, b) => VectorDiffer(a, b, (x, y) => FloatDiffer(x, y, example.OutputFloatVectorPrecision)))
             + GetVectorDiff(example.OutputStringVector, interpreter.StringVectorStack, Data.WorstResult, (a, b) => VectorDiffer(a, b, StringDiffer));

      return result;
    }

    private double Median(IPushInterpreter interpreter, Example example) {
      return interpreter.PrintStack.IsEmpty || !interpreter.PrintStack.Top.Equals(example.OutputPrint) ? 1 : 0;
    }

    private double NumberIo(IPushInterpreter interpreter, Example example) {
      if (interpreter.PrintStack.IsEmpty)
        return Data.WorstResult;

      double value;
      if (double.TryParse(interpreter.PrintStack.Top, NumberStyles.Number | NumberStyles.AllowDecimalPoint, CultureInfo.InvariantCulture, out value)) {
        var diff = Math.Abs(example.OutputFloat[0] - value);
        var result = Math.Min(diff, Data.WorstResult);

        return result;
      }

      var penaltyError = Data.WorstResult / 4.0d;
      var levenshteinDistance = GetPrintDiffer(
        example.OutputPrint,
        interpreter.PrintStack.Top,
        Data.WorstResult);

      return levenshteinDistance + penaltyError;
    }

    private static double FloatDiffer(double a, double b, int digits) {
      var result = Math.Round(a, digits) - Math.Round(b, digits);

      // ReSharper disable once CompareOfFloatsByEqualityOperator
      if (result == double.MinValue || double.IsPositiveInfinity(result) || double.IsNaN(result))
        return double.MaxValue;

      // ReSharper disable once CompareOfFloatsByEqualityOperator
      if (result == double.MaxValue || double.IsNegativeInfinity(result))
        return double.MinValue;

      return Math.Abs(result);
    }

    private static double IntegerDiffer(long a, long b) {
      var result = a - b;

      return result == long.MinValue ? long.MaxValue : Math.Abs(result);
    }

    private static double BooleanDiffer(bool a, bool b) {
      return a == b ? 0 : 1;
    }

    private static double StringDiffer(string a, string b) {
      return LevenshteinDistance(a, b);
    }

    private static double CharDiffer(char a, char b) {
      return IntegerDiffer(a, b);
    }

    private static double VectorDiffer<T>(IReadOnlyList<T> estimated, IReadOnlyList<T> outcome, Func<T, T, double> differ) {
      var length = Math.Min(estimated.Count, outcome.Count);
      var result = 0d;

      for (var i = 0; i < length; i++) {
        result += differ(estimated[i], outcome[i]);
      }

      if (estimated.Count > outcome.Count) {
        var remainingLength = estimated.Count - length;
        for (var i = 0; i < remainingLength; i++)
          result += differ(estimated[i], default(T));
      }

      return result;
    }

    private static double GetPrintDiffer(string estimated, string printResult, double worstResult) {
      var distance = LevenshteinDistance(estimated, printResult);

      return Math.Min(distance, worstResult);
    }

    private static double GetPrintDiffer(string estimated, IPushStack<string> printStack, int estimatedCount, double worstResult) {
      var printResult = string.Join(PushEnvironment.NewLine, printStack.AsStrings().Take(estimatedCount));
      var distance = LevenshteinDistance(estimated, printResult);

      return Math.Min(distance, worstResult);
    }

    private static double GetVectorDiff<T>(IReadOnlyList<IReadOnlyList<T>> estimated, IPushStack<IReadOnlyList<T>> resultStack, double worstResult, Func<IReadOnlyList<T>, IReadOnlyList<T>, double> differ)
      where T : IComparable {
      if (estimated.Count == 0) return 0d;

      var diff = 0d;
      var comparableLength = 0;

      if (!resultStack.IsEmpty) {
        var count = Math.Min(estimated.Count, resultStack.Count);
        var result = resultStack.Peek(count);
        comparableLength = Math.Min(estimated.Count, result.Count);

        for (var i = 0; i < comparableLength; i++) {
          diff += Math.Min(differ(estimated[i], result[i]), worstResult);
        }
      }

      var emptyTArray = new T[0];
      for (var i = comparableLength; i < estimated.Count - comparableLength; i++) {
        diff += differ(estimated[i], emptyTArray);
      }

      return diff;
    }

    private static double GetDiff<T>(IReadOnlyList<T> estimated, IPushStack<T> resultStack, double worstResult, Func<T, T, double> differ)
      where T : IComparable {
      if (estimated.Count == 0) return 0d;

      var diff = 0d;
      var comparableLength = 0;

      if (!resultStack.IsEmpty) {
        var count = Math.Min(estimated.Count, resultStack.Count);
        var result = resultStack.Peek(count);
        comparableLength = Math.Min(estimated.Count, result.Count);

        for (var i = 0; i < comparableLength; i++) {
          diff += Math.Min(differ(estimated[i], result[i]), worstResult);
        }
      }

      for (var i = comparableLength; i < estimated.Count - comparableLength; i++) {
        diff += differ(estimated[i], default(T));
      }

      return diff;
    }

    /// <summary>
    /// https://www.dotnetperls.com/levenshtein
    /// </summary>
    private static int LevenshteinDistance(string source, string target) {
      if (source == null && target == null) return 0;
      if (source == null) return target.Length;
      if (target == null) return source.Length;

      int n = source.Length;
      int m = target.Length;
      int[,] d = new int[n + 1, m + 1];

      // Step 1
      if (n == 0) {
        return m;
      }

      if (m == 0) {
        return n;
      }

      // Step 2
      for (int i = 0; i <= n; d[i, 0] = i++) {
      }

      for (int j = 0; j <= m; d[0, j] = j++) {
      }

      // Step 3
      for (int i = 1; i <= n; i++) {
        //Step 4
        for (int j = 1; j <= m; j++) {
          // Step 5
          int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

          // Step 6
          d[i, j] = Math.Min(
              Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
              d[i - 1, j - 1] + cost);
        }
      }
      // Step 7
      return d[n, m];
    }
  }
}