Changeset 13803 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common

Timestamp:

04/27/16 16:21:07 (8 years ago)

Author:

abeham

Message:

#2457:

• changed expected runtime calculation
  • now outputs positive infinity instead of nan when no run was successful
  • now filters outliers in successful and unsuccessful runs by using two standard deviations of the mean of successful runs as lower bound
    • this change allows having unsuccessful runs in the database with low evaluations / runtime (e.g. due to being aborted early or from an experiment where the max budget was lower)
• worked on recommendation algorithms
  • implemented several performance measures (absolute error, absolute log error, ndcp, kendall's tau) to evaluate the ranking

Location:

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3

Files:

• KnowledgeCenter.cs (modified) (2 diffs)
• Recommenders/KNearestNeighborModel.cs (modified) (2 diffs)
• Recommenders/OverallBestRecommender.cs (modified) (1 diff)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

@@ -654 +654 @@
           var bkq = ((DoubleValue)prob.Parameters["BestKnownQuality"]).Value;
           var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime;
-          if (double.IsNaN(ert)) ert = int.MaxValue;
+          if (double.IsInfinity(ert)) ert = int.MaxValue;
           ds.AddRow(new object[] { pr.Key }.Concat(f.Cast<object>()).Concat(new object[] { ert }));
         }
@@ -720 +720 @@
         var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())
                        .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime);
-        var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsNaN(x.Value))
+        var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsInfinity(x.Value))
           .GetByCluster().ToList();
         foreach (var c in ranks) {

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs

@@ -49 +49 @@
       var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
       var nearestK = features.Select((f, i) => new { ProblemInstanceIndex = i, Feature = f })
-                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum())
-                             .Take(K);
+                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum());
       
-      var performances = new Dictionary<IAlgorithm, List<double>>();
+      var performances = new Dictionary<IAlgorithm, Performance>();
+
+      var k = 0;
       foreach (var next in nearestK) {
+        if (k >= K) break;
         var perfs = performance[problemInstanceMap.GetByFirst(next.ProblemInstanceIndex)];
         if (perfs.Count == 0) continue;
@@ -59 +61 @@
         foreach (var p in perfs) {
           var ert = p.Value;
-          if (double.IsNaN(ert)) ert = int.MaxValue;
-          List<double> erts;
-          if (!performances.TryGetValue(p.Key, out erts)) {
-            performances[p.Key] = new List<double>() { ert }; ;
-          } else erts.Add(ert);
+          Performance perf;
+          if (!performances.TryGetValue(p.Key, out perf)) {
+            perf = new Performance();
+            performances[p.Key] = perf;
+          }
+          perf.Add(ert);
         }
+
+        k++;
       }
 
-      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.Average() })
+      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.ExpectedRuntime() })
                          .OrderBy(x => x.Perf)
                          .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf));
     }
+
+    private class Performance {
+      private readonly List<double> successful;
+      private int runs;
+      public int Fails { get { return runs - successful.Count; } }
+
+      public Performance() {
+        successful = new List<double>();
+      }
+
+      public void Add(double ert) {
+        if (!double.IsInfinity(ert)) successful.Add(ert);
+        runs++;
+      }
+
+      public double ExpectedRuntime() {
+        if (successful.Count == 0) return int.MaxValue;
+        return successful.Average() / (successful.Count / (double)runs);
+      }
+    }
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/OverallBestRecommender.cs

@@ -63 +63 @@
           if (!pis.TryGetValue(problemRuns.Key, out bkq)) continue;
           var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", kc.GetTarget(bkq, kc.MinimumTarget.Value, kc.Maximization), kc.Maximization).ExpectedRuntime;
-          if (double.IsNaN(ert)) ert = int.MaxValue;
+          if (double.IsInfinity(ert)) ert = int.MaxValue;
           avgERT += ert;
           count++;