Changeset 14875 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushEvaluator.cs

Timestamp:

04/18/17 01:15:25 (7 years ago)

Author:

pkimmesw

Message:

#2665 BenchmarkSuite, all examples, partially tested, VectorExpressions added

File:

• branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushEvaluator.cs (modified) (6 diffs)

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushEvaluator.cs

@@ -3 +3 @@
 
 namespace HeuristicLab.Problems.ProgramSynthesis.Push.Problem {
+
   using HeuristicLab.BenchmarkSuite;
   using HeuristicLab.BenchmarkSuite.Problems;
+  using HeuristicLab.Common;
   using HeuristicLab.Core;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
@@ -13 +15 @@
     public static double Evaluate(IPushInterpreter interpreter, PushProgram program, Example example, double worstResult) {
       interpreter.BooleanStack.Push(example.InputBoolean);
-      interpreter.IntegerStack.Push(example.InputInt);
+      interpreter.IntegerStack.Push(example.InputInteger);
       interpreter.FloatStack.Push(example.InputFloat);
 
       interpreter.Run(program);
 
-      var result = GetDiff(example.OutputInt, interpreter.IntegerStack, worstResult, LongDiffer)
-                 + GetDiff(example.OutputFloat, interpreter.FloatStack, worstResult, DoubleDiffer)
-                 + GetDiff(example.OutputBoolean, interpreter.BooleanStack, worstResult, BooleanDiffer);
+      var result = GetDiff(example.OutputInteger, interpreter.IntegerStack, worstResult, IntegerDiffer)
+                 + GetDiff(example.OutputFloat, interpreter.FloatStack, worstResult, FloatDiffer)
+                 + GetDiff(example.OutputBoolean, interpreter.BooleanStack, worstResult, BooleanDiffer)
+                 + GetDiff(example.OutputString, interpreter.StringStack, worstResult, StringDiffer)
+                 + GetDiff(example.OutputChar, interpreter.CharStack, worstResult, CharDiffer)
+                 + GetVectorDiff(example.OutputIntegerVector, interpreter.IntegerVectorStack, worstResult, (a, b) => VectorDiffer(a, b, IntegerDiffer))
+                 + GetVectorDiff(example.OutputFloatVector, interpreter.FloatVectorStack, worstResult, (a, b) => VectorDiffer(a, b, FloatDiffer))
+                 + GetVectorDiff(example.OutputStringVector, interpreter.StringVectorStack, worstResult, (a, b) => VectorDiffer(a, b, StringDiffer));
 
       return result;
     }
 
-    public static EvaluationResult Evaluate(PushProgram program, PushInterpreterPool pool, IRandom random, Data data, int startIndex, int endIndex) {
+    public static EvaluationResult Evaluate(PushProgram program, PushInterpreterPool pool, IRandom random, ProblemData data, int startIndex, int endIndex) {
       var length = endIndex - startIndex;
       if (length <= 0) return null;
@@ -45 +52 @@
     }
 
-    //public static EvaluationResult Evaluate(Individual individual, PushInterpreterPool pool, IRandom random, Data data, int startIndex, int endIndex) {
-    //  var program = individual.ToPushProgram(pool.PushGpConfiguration);
-    //  return Evaluate(program, pool, random, data, startIndex, endIndex);
-    //}
-
-    private static double DoubleDiffer(double a, double b) {
+    private static double FloatDiffer(double a, double b) {
       var result = a - b;
 
-      if (result == double.MinValue || double.IsPositiveInfinity(result) || double.IsNaN(result))
+      if (result.IsAlmost(double.MinValue) || double.IsPositiveInfinity(result) || double.IsNaN(result))
         return double.MaxValue;
 
-      if (result == double.MaxValue || double.IsNegativeInfinity(result))
+      if (result.IsAlmost(double.MaxValue) || double.IsNegativeInfinity(result))
         return double.MinValue;
 
@@ -62 +64 @@
     }
 
-    private static double LongDiffer(long a, long b) {
+    private static double IntegerDiffer(long a, long b) {
       var result = a - b;
 
@@ -70 +72 @@
     private static double BooleanDiffer(bool a, bool b) {
       return a && b ? 0 : a || b ? 1 : 2;
+    }
+
+    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> a, IReadOnlyList<T> b, Func<T, T, double> differ) {
+      var length = Math.Min(a.Count, b.Count);
+      var result = 0d;
+
+      for (var i = 0; i < length; i++) {
+        result += differ(a[i], b[i]);
+      }
+
+      if (a.Count > b.Count) {
+        var remainingLength = a.Count - length;
+        for (var i = 0; i < remainingLength; i++)
+          result += differ(a[i], default(T));
+      }
+
+      return result;
+    }
+
+    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;
     }
 
@@ -95 +147 @@
       return diff;
     }
+
+    /// <summary>
+    /// https://www.dotnetperls.com/levenshtein
+    /// </summary>
+    /// <param name="s"></param>
+    /// <param name="t"></param>
+    /// <returns></returns>
+    private static int LevenshteinDistance(string s, string t) {
+      if (s == null && t == null) return 0;
+      if (s == null) return t.Length;
+      if (t == null) return s.Length;
+
+      int n = s.Length;
+      int m = t.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 = (t[j - 1] == s[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];
+    }
   }
 }