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

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Problem.BenchmarkSuite {
  using System;
  using System.Collections.Generic;
  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 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, IRandom random, 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.TotalQuality += result;
        interpreter.Reset();
      }

      evaluationResult.TotalQuality /= length;

      return evaluationResult;
    }

    public EvaluationResult EvaluateTest(IPushInterpreter interpreter, PushProgram program, IRandom random) {
      return Evaluate(interpreter, program, random, 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, random);
    }

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

    public EvaluationResult EvaluateTraining(IPushInterpreter interpreter, PushProgram program, IRandom random) {
      return Evaluate(interpreter, program, random, 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, random);
    }

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

    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.Select(v => new List<string>(v)));
      interpreter.IntegerVectorStack.Push(example.InputIntegerVector.Select(v => new List<long>(v)));
      interpreter.FloatVectorStack.Push(example.InputFloatVector.Select(v => new List<double>(v)));

      interpreter.Run(program);

      var result = GetDiff(example.OutputInteger, interpreter.IntegerStack, Data.WorstResult, IntegerDiffer)
                 + GetDiff(example.OutputFloat, interpreter.FloatStack, Data.WorstResult, FloatDiffer)
                 + 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)
                 + 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, FloatDiffer))
                 + GetVectorDiff(example.OutputStringVector, interpreter.StringVectorStack, Data.WorstResult, (a, b) => VectorDiffer(a, b, StringDiffer));

      return result;
    }

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

      if (result.IsAlmost(double.MinValue) || double.IsPositiveInfinity(result) || double.IsNaN(result))
        return double.MaxValue;

      if (result.IsAlmost(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 readonly string[] separator = { "\n" };
    private static double GetPrintDiffer(string estimated, IPushStack<string> printStack) {
      var estimatedCount = estimated.Split(separator, StringSplitOptions.None).Length;
      var printResult = string.Join(separator[0], printStack.Take(estimatedCount));

      return LevenshteinDistance(estimated, printResult);
    }

    private static double GetVectorDiff<T>(IReadOnlyList<IReadOnlyList<T>> estimated, IPushStack<List<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.Length);

        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.Length);

        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];
    }
  }
}