Changeset 13757

Timestamp:

04/13/16 16:25:12 (9 years ago)

Author:

abeham

Message:

#2547:

• worked on problem instance mapping
• started working on improved suggestion algorithm

Location:

branches/PerformanceComparison

Files:

• HeuristicLab.Analysis/3.3/QualityAnalysis/ExpectedRuntimeHelper.cs (modified) (3 diffs)
• HeuristicLab.OptimizationExpertSystem.Common/3.3/Enums.cs (moved) (moved from branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/SeedingStrategyTypes.cs) (1 diff)
• HeuristicLab.OptimizationExpertSystem.Common/3.3/HeuristicLab.OptimizationExpertSystem.Common-3.3.csproj (modified) (1 diff)
• HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs (modified) (15 diffs)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingProblemInstanceView.Designer.cs (modified) (15 diffs)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingProblemInstanceView.cs (modified) (9 diffs)

branches/PerformanceComparison/HeuristicLab.Analysis/3.3/QualityAnalysis/ExpectedRuntimeHelper.cs

@@ -1 @@
-using System.Collections.Generic;
+using HeuristicLab.Optimization;
+using System;
+using System.Collections.Generic;
 using System.Globalization;
 using System.Linq;
-using HeuristicLab.Optimization;
 
 namespace HeuristicLab.Analysis {
   public static class ExpectedRuntimeHelper {
-    public static ErtCalculationResult CalculateErt(List<IRun> runs, string indexedDataTableName, double target, bool maximization) {
+    public static ErtCalculationResult CalculateErt(IEnumerable<IEnumerable<Tuple<double, double>>> convGraphs, double target, bool maximization) {
       var successful = new List<double>();
       var unsuccessful = new List<double>();
-      foreach (var r in runs) {
+      foreach (var graph in convGraphs) {
         var targetAchieved = false;
-        var row = ((IndexedDataTable<double>)r.Results[indexedDataTableName]).Rows.First();
-        foreach (var v in row.Values) {
+        var lastEffort = double.MaxValue;
+        foreach (var v in graph) {
           if (maximization && v.Item2 >= target || !maximization && v.Item2 <= target) {
             successful.Add(v.Item1);
@@ -18 +19 @@
             break;
           }
+          lastEffort = v.Item1;
         }
-        if (!targetAchieved) unsuccessful.Add(row.Values.Last().Item1);
+        if (!targetAchieved) unsuccessful.Add(lastEffort);
       }
 
@@ -32 +34 @@
       }
       return new ErtCalculationResult(successful.Count, (successful.Count + unsuccessful.Count), ert);
+    }
+
+    public static ErtCalculationResult CalculateErt(List<IRun> runs, string indexedDataTableName, double target, bool maximization) {
+      return CalculateErt(runs.Select(r => ((IndexedDataTable<double>)r.Results[indexedDataTableName]).Rows.First().Values), target, maximization);
     }
   }

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

@@ -26 +26 @@
     SeedByCloning
   }
+
+  public enum ProblemInstanceProximityType {
+    FeatureSpace,
+    PCA,
+    MDS,
+    SOM
+  }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/HeuristicLab.OptimizationExpertSystem.Common-3.3.csproj

@@ -150 +150 @@
     <Compile Include="KnowledgeCenter.cs" />
     <Compile Include="Plugin.cs" />
-    <Compile Include="SeedingStrategyTypes.cs" />
+    <Compile Include="Enums.cs" />
     <None Include="Properties\AssemblyInfo.cs.frame" />
     <Compile Include="ProblemCharacteristicAnalysis\CharacteristicCalculator.cs" />

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

@@ -59 +59 @@
     }
 
+    private readonly DoubleValue minimumTarget;
+    public DoubleValue MinimumTarget {
+      get { return minimumTarget; }
+    }
+    
     private readonly RunCollection instanceRuns;
     public RunCollection InstanceRuns {
@@ -94 +99 @@
     public ReadOnlyCheckedItemList<StringValue> ProblemCharacteristics {
       get { return readonlyProblemCharacteristics; }
-    } 
+    }
+
+    private readonly EnumValue<ProblemInstanceProximityType> problemInstanceProximity;
+    public EnumValue<ProblemInstanceProximityType> ProblemInstanceProximity {
+      get { return problemInstanceProximity; }
+    }
+
+    private readonly DoubleValue problemInstanceNeighborhoodFactor;
+    public DoubleValue ProblemInstanceNeighborhoodFactor {
+      get { return problemInstanceNeighborhoodFactor; }
+    }
 
     private readonly CheckedItemList<IScope> solutionSeedingPool;
@@ -116 +131 @@
     public KnowledgeCenter() {
       maximumEvaluations = new IntValue(10000);
+      minimumTarget = new DoubleValue(1.05);
       instanceRuns = new RunCollection();
       seededRuns = new RunCollection();
@@ -123 +139 @@
       problemInstances = new RunCollection();
       problemCharacteristics = new CheckedItemList<StringValue>();
+      problemInstanceProximity = new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace);
+      problemInstanceNeighborhoodFactor = new DoubleValue(1);
       readonlyProblemCharacteristics = problemCharacteristics.AsReadOnly();
       problem = new SingleObjectiveOKBProblem();
@@ -139 +157 @@
     private void RegisterEventHandlers() {
       maximumEvaluations.ValueChanged += MaximumEvaluationsOnValueChanged;
+      minimumTarget.ValueChanged += MinimumTargetOnValueChanged;
       problem.ProblemChanged += ProblemOnProblemChanged;
       problem.Solutions.ItemsAdded += ProblemSolutionsChanged;
@@ -157 +176 @@
       problemCharacteristics.CollectionReset += CharacteristicChanged;
       problemCharacteristics.CheckedItemsChanged += CharacteristicChanged;
+      problemInstanceProximity.ValueChanged += ProblemInstanceProximityChanged;
+      problemInstanceNeighborhoodFactor.ValueChanged += ProblemInstanceProximityChanged;
     }
 
     private void MaximumEvaluationsOnValueChanged(object sender, EventArgs eventArgs) {
+      UpdateSuggestions();
+    }
+
+    private void MinimumTargetOnValueChanged(object sender, EventArgs e) {
       UpdateSuggestions();
     }
@@ -181 +206 @@
     }
 
+    private void ProblemInstanceProximityChanged(object sender, EventArgs e) {
+      UpdateSuggestions();
+    }
+
     public bool IsCurrentInstance(IRun run) {
       if (!problemId2ProblemInstanceMapping.ContainsSecond(run)) return false;
@@ -189 +218 @@
       if (ProblemCharacteristics.Count == 0) return;
 
+      var instances = GetProblemCharacteristics();
+
+      var key2Idx = new BidirectionalDictionary<IRun, int>();
+      foreach (var kvp in instances.Select((k, i) => new { Index = i, Key = k.Key }))
+        key2Idx.Add(kvp.Key, kvp.Index);
+
+      #region MDS
+      Func<double[], double[], double> euclid = (a, b) => Math.Sqrt(a.Zip(b, (x, y) => (x - y)).Sum(x => x * x));
+      var num = instances.Count;
+      var matrix = new DoubleMatrix(num, num);
+      for (var i = 0; i < num - 1; i++) {
+        for (var j = i + 1; j < num; j++) {
+          matrix[i, j] = matrix[j, i] = euclid(instances[key2Idx.GetBySecond(i)], instances[key2Idx.GetBySecond(j)]);
+        }
+      }
+
+      var coords = MultidimensionalScaling.KruskalShepard(matrix);
+      #endregion
+      #region PCA
+      var ds = new double[instances.Count, ProblemCharacteristics.CheckedItems.Count()];
+      foreach (var instance in instances) {
+        var arr = instance.Value;
+        for (var feature = 0; feature < arr.Length; feature++)
+          ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
+      }
+
+      int info;
+      double[] s2;
+      double[,] v;
+      alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
+      #endregion
+      #region SOM
+      var features = new DoubleMatrix(ProblemCharacteristics.CheckedItems.Count(), instances.Count);
+      foreach (var instance in instances) {
+        var arr = instance.Value;
+        for (var feature = 0; feature < arr.Length; feature++)
+          features[feature, key2Idx.GetByFirst(instance.Key)] = arr[feature];
+      }
+      var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 20, learningRadius: 20, iterations: 200, jittering: true);
+      #endregion
+
+      ProblemInstances.UpdateOfRunsInProgress = true;
+      try {
+        foreach (var instance in ProblemInstances) {
+          double x = 0, y = 0;
+          for (var feature = 0; feature < ds.GetLength(1); feature++) {
+            x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
+            y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
+          }
+
+          IItem item;
+          if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
+            ((DoubleValue)item).Value = x;
+          } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
+          if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
+            ((DoubleValue)item).Value = y;
+          } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
+
+          if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
+            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 0];
+          } else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance), 0]));
+          if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
+            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 1];
+          } else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance), 1]));
+
+          if (instance.Results.TryGetValue("Projection.SOM.X", out item)) {
+            ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 0];
+          } else instance.Results.Add("Projection.SOM.X", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 0]));
+          if (instance.Results.TryGetValue("Projection.SOM.Y", out item)) {
+            ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 1];
+          } else instance.Results.Add("Projection.SOM.Y", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 1]));
+        }
+      } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
+    }
+
+    private Dictionary<IRun, double[]> GetProblemCharacteristics() {
       var instances = new Dictionary<IRun, double[]>();
       var values = new List<double>[ProblemCharacteristics.CheckedItems.Count()];
@@ -207 +312 @@
       var median = values.Select(x => x.Count == 0 ? 0.0 : x.Median()).ToList();
 
-      var allValues = instances.Values.Select(x => x.Select((f, i) => new { Idx = i, Val = double.IsNaN(f) ? median[i] : f }).ToList())
-                                      .SelectMany(x => x)
-                                      .GroupBy(x => x.Idx, x => x.Val)
-                                      .OrderBy(x => x.Key).ToList();
+      var allValues = instances.Values.Select(x => x.Select((f, i) => new {Idx = i, Val = double.IsNaN(f) ? median[i] : f}).ToList())
+        .SelectMany(x => x)
+        .GroupBy(x => x.Idx, x => x.Val)
+        .OrderBy(x => x.Key).ToList();
       var avg = allValues.Select(x => x.Average()).ToList();
       var stdev = allValues.Select(x => x.StandardDeviation()).ToList();
@@ -222 +327 @@
         }
       }
-
-      var key2Idx = new BidirectionalDictionary<IRun, int>();
-      foreach (var kvp in instances.Select((k, i) => new { Index = i, Key = k.Key }))
-        key2Idx.Add(kvp.Key, kvp.Index);
-
-      #region MDS
-      Func<double[], double[], double> euclid = (a, b) => Math.Sqrt(a.Zip(b, (x, y) => (x - y)).Sum(x => x * x));
-      var num = instances.Count;
-      var matrix = new DoubleMatrix(num, num);
-      for (var i = 0; i < num - 1; i++) {
-        for (var j = i + 1; j < num; j++) {
-          matrix[i, j] = matrix[j, i] = euclid(instances[key2Idx.GetBySecond(i)], instances[key2Idx.GetBySecond(j)]);
-        }
-      }
-
-      var coords = MultidimensionalScaling.KruskalShepard(matrix);
-      #endregion
-      #region PCA
-      var ds = new double[instances.Count, ProblemCharacteristics.CheckedItems.Count()];
-      foreach (var instance in instances) {
-        var arr = instance.Value;
-        for (var feature = 0; feature < arr.Length; feature++)
-          ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
-      }
-
-      int info;
-      double[] s2;
-      double[,] v;
-      alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
-      #endregion
-      #region SOM
-      var features = new DoubleMatrix(ProblemCharacteristics.CheckedItems.Count(), instances.Count);
-      foreach (var instance in instances) {
-        var arr = instance.Value;
-        for (var feature = 0; feature < arr.Length; feature++)
-          features[feature, key2Idx.GetByFirst(instance.Key)] = arr[feature];
-      }
-      var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 20, learningRadius: 20, iterations: 200, jittering: true);
-      #endregion
-
-      ProblemInstances.UpdateOfRunsInProgress = true;
-      try {
-        foreach (var instance in ProblemInstances) {
-          double x = 0, y = 0;
-          for (var feature = 0; feature < ds.GetLength(1); feature++) {
-            x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
-            y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
-          }
-
-          IItem item;
-          if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
-            ((DoubleValue)item).Value = x;
-          } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
-          if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
-            ((DoubleValue)item).Value = y;
-          } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
-
-          if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
-            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 0];
-          } else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance), 0]));
-          if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
-            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 1];
-          } else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance), 1]));
-
-          if (instance.Results.TryGetValue("Projection.SOM.X", out item)) {
-            ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 0];
-          } else instance.Results.Add("Projection.SOM.X", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 0]));
-          if (instance.Results.TryGetValue("Projection.SOM.Y", out item)) {
-            ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 1];
-          } else instance.Results.Add("Projection.SOM.Y", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 1]));
-        }
-      } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
+      return instances;
     }
 
@@ -434 +468 @@
         problemClassFilter.Value = adminClient.ProblemClasses.Single(x => x.Id == probClassId).Name;
 
+        problemId2ProblemInstanceMapping.Clear();
         progress.Status = "Downloading problem instances...";
         progress.ProgressValue = 0;
@@ -550 +585 @@
 
           if (!algInstRunDict.ContainsKey(probInstanceName)) continue;
-          foreach (var kvp in algInstRunDict[probInstanceName]) {
-            // TODO: Things needs to be configurable here (table name, targets)
-            foreach (var target in new[] { 1, 1.01, 1.05, 1.1, 1.2, 1.5 }) {
+          // TODO: Things needs to be configurable here (table name, targets)
+          foreach (var target in new[] { 1, 1.01, 1.05, 1.1, 1.2, 1.5 }) {
+            var indexMap = new BidirectionalDictionary<string, int>();
+            var dict = new Dictionary<string, double>();
+            var idx = 0;
+            foreach (var kvp in algInstRunDict[probInstanceName]) {
               var result = ExpectedRuntimeHelper.CalculateErt(kvp.Value, "QualityPerEvaluations", bkQuality * target, maximization);
-              var resultName = kvp.Key + "@" + ((target - 1) * 100) + "%";
-              characteristics.Add(resultName);
-              IItem item;
-              if (instance.Results.TryGetValue(resultName, out item)) {
-                ((DoubleValue)item).Value = Math.Log10(result.ExpectedRuntime);
-              } else instance.Results.Add(resultName, new DoubleValue(Math.Log10(result.ExpectedRuntime)));
+              indexMap.Add(kvp.Key, idx);
+              dict[kvp.Key] = !double.IsNaN(result.ExpectedRuntime) ? result.ExpectedRuntime : int.MaxValue;
+              idx++;
+            }
+            var points = dict.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value > 0 ? Math.Log10(x.Value) : 0).ToArray();
+            int[] clusters;
+            Ckmeans1dClusters(points, 5, out clusters);
+            var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = dict[indexMap.GetBySecond(i)] })
+                                .GroupBy(x => x.Cluster, x => x.Perf)
+                                .Select(x => new { Cluster = x.Key, AvgPerf = x.Average() })
+                                .OrderBy(x => x.AvgPerf)
+                                .Select((c, i) => new { Cluster = c.Cluster, Rank = i })
+                                .ToDictionary(x => x.Cluster, x => x.Rank);
+            for (var i = 0; i < clusters.Length; i++) {
+              var resultName = "Rank." + indexMap.GetBySecond(i) + "@" + ((target - 1) * 100) + "%";
+              instance.Results[resultName] = new IntValue(dict[indexMap.GetBySecond(i)] < int.MaxValue ? ranks[clusters[i]] : 6);
             }
           }
@@ -576 +624 @@
       } finally { progress.Finish(); ProblemInstances.UpdateOfRunsInProgress = false; }
       UpdateInstanceProjection();
+      UpdateSuggestions();
     }
 
     private void UpdateSuggestions() {
       if (Problem == null) return;
+      var piDistances = GetProblemDistances();
+      var maxDistance = piDistances.Max();
+      // Weighted combination of algorithm performances using distance-based exponentially falling weights
+      // Scale distances by maxDistance
+      // Parameter to influence dampening factor
+      // Algorithm performances are given in expected run time
+      // Using convergence graphs up to maximum evaluations effort
+      // Care has to be taken if not every algorithm has been executed on every problem instance
       var instances = new SortedList<double, IAlgorithm>();
       foreach (var relevantRuns in knowledgeBase.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
@@ -608 +665 @@
     }
 
+    private DoubleMatrix GetProblemDistances() {
+      var matrix = new DoubleMatrix(ProblemInstances.Count, ProblemInstances.Count);
+      switch (ProblemInstanceProximity.Value) {
+        case ProblemInstanceProximityType.MDS:
+        case ProblemInstanceProximityType.PCA:
+        case ProblemInstanceProximityType.SOM:
+          int i = 0, j = 0;
+          foreach (var a in ProblemInstances) {
+            double xa, ya;
+            GetProjectionCoordinates(a, out xa, out ya);
+            j = 0;
+            foreach (var b in ProblemInstances) {
+              double xb, yb;
+              GetProjectionCoordinates(b, out xb, out yb);
+              matrix[i, j] = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
+              j++;
+            }
+            i++;
+          }
+          break;
+        case ProblemInstanceProximityType.FeatureSpace:
+          int k = 0, l = 0;
+          var features = GetProblemCharacteristics();
+          foreach (var a in ProblemInstances) {
+            l = 0;
+            var fa = features[a];
+            foreach (var b in ProblemInstances) {
+              var sum = features[b].Select((t, f) => (fa[f] - t) * (fa[f] - t)).Sum();
+              matrix[k, l] = Math.Sqrt(sum);
+              l++;
+            }
+            k++;
+          }
+          break;
+        default: throw new InvalidOperationException(string.Format("Unkonwn proximity type {0}", ProblemInstanceProximity.Value));
+      }
+      return matrix;
+    }
+
+    private void GetProjectionCoordinates(IRun problemInstance, out double x, out double y) {
+      x = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".X"]).Value;
+      y = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".Y"]).Value;
+    }
+
     public event EventHandler<EventArgs<IProgress>> DownloadStarted;
     private void OnDownloadStarted(IProgress progress) {
@@ -619 +720 @@
       if (handler != null) handler(this, new EventArgs<IAlgorithm>(instance));
     }
+
+    // implement further classes and methods
+    private static SortedList<double, int> Ckmeans1dClusters(double[] estimations, int k, out int[] clusterValues) {
+      int nPoints = estimations.Length;
+      var distinct = estimations.Distinct().OrderBy(x => x).ToArray();
+      var max = distinct.Max();
+      if (distinct.Length <= k) {
+        var dict = distinct.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Value, y => y.Index);
+        for (int i = distinct.Length; i < k; i++)
+          dict.Add(max + i - distinct.Length + 1, i);
+
+        clusterValues = new int[nPoints];
+        for (int i = 0; i < nPoints; i++)
+          if (!dict.ContainsKey(estimations[i])) clusterValues[i] = 0;
+          else clusterValues[i] = dict[estimations[i]];
+
+        return new SortedList<double, int>(dict);
+      }
+
+      var n = distinct.Length;
+      var D = new double[n, k];
+      var B = new int[n, k];
+
+      for (int m = 0; m < k; m++) {
+        for (int j = m; j <= n - k + m; j++) {
+          if (m == 0)
+            D[j, m] = SumOfSquaredDistances(distinct, 0, j + 1);
+          else {
+            var minD = double.MaxValue;
+            var minI = 0;
+            for (int i = 1; i <= j; i++) {
+              var d = D[i - 1, m - 1] + SumOfSquaredDistances(distinct, i, j + 1);
+              if (d < minD) {
+                minD = d;
+                minI = i;
+              }
+            }
+            D[j, m] = minD;
+            B[j, m] = minI;
+          }
+        }
+      }
+
+      var centers = new SortedList<double, int>();
+      var upper = B[n - 1, k - 1];
+      var c = Mean(distinct, upper, n);
+      centers.Add(c, k - 1);
+      for (int i = k - 2; i >= 0; i--) {
+        var lower = B[upper - 1, i];
+        var c2 = Mean(distinct, lower, upper);
+        centers.Add(c2, i);
+        upper = lower;
+      }
+
+      clusterValues = new int[nPoints];
+      for (int i = 0; i < estimations.Length; i++) {
+        clusterValues[i] = centers.MinItems(x => Math.Abs(estimations[i] - x.Key)).First().Value;
+      }
+
+      return centers;
+    }
+
+    private static double SumOfSquaredDistances(double[] x, int start, int end) {
+      if (start == end) throw new InvalidOperationException();
+      if (start + 1 == end) return 0.0;
+      double mean = 0.0;
+      for (int i = start; i < end; i++) {
+        mean += x[i];
+      }
+      mean /= (end - start);
+      var sum = 0.0;
+      for (int i = start; i < end; i++) {
+        sum += (x[i] - mean) * (x[i] - mean);
+      }
+      return sum;
+    }
+
+    private static double Mean(double[] x, int start, int end) {
+      if (start == end) throw new InvalidOperationException();
+      double mean = 0.0;
+      for (int i = start; i < end; i++) {
+        mean += x[i];
+      }
+      mean /= (end - start);
+      return mean;
+    }
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingProblemInstanceView.Designer.cs

@@ -54 +54 @@
       this.mapSplitContainer = new System.Windows.Forms.SplitContainer();
       this.showCharacteristicsCheckBox = new System.Windows.Forms.CheckBox();
+      this.fromZeroCheckBox = new System.Windows.Forms.CheckBox();
       this.invPropCheckBox = new System.Windows.Forms.CheckBox();
       this.sizeLabel = new System.Windows.Forms.Label();
@@ -62 +63 @@
       this.instancesTabPage = new System.Windows.Forms.TabPage();
       this.problemInstancesView = new HeuristicLab.MainForm.WindowsForms.ViewHost();
+      this.colorComboBox = new System.Windows.Forms.ComboBox();
+      this.colorLabel = new System.Windows.Forms.Label();
       this.problemInstancesTabControl.SuspendLayout();
       this.mapTabPage.SuspendLayout();
@@ -82 +85 @@
       this.problemInstancesTabControl.Name = "problemInstancesTabControl";
       this.problemInstancesTabControl.SelectedIndex = 0;
-      this.problemInstancesTabControl.Size = new System.Drawing.Size(1000, 760);
+      this.problemInstancesTabControl.Size = new System.Drawing.Size(1108, 760);
       this.problemInstancesTabControl.TabIndex = 8;
       // 
@@ -91 +94 @@
       this.mapTabPage.Name = "mapTabPage";
       this.mapTabPage.Padding = new System.Windows.Forms.Padding(3);
-      this.mapTabPage.Size = new System.Drawing.Size(992, 734);
+      this.mapTabPage.Size = new System.Drawing.Size(1100, 734);
       this.mapTabPage.TabIndex = 1;
       this.mapTabPage.Text = "Map";
@@ -106 +109 @@
       // 
       this.mapSplitContainer.Panel1.Controls.Add(this.showCharacteristicsCheckBox);
+      this.mapSplitContainer.Panel1.Controls.Add(this.fromZeroCheckBox);
       this.mapSplitContainer.Panel1.Controls.Add(this.invPropCheckBox);
+      this.mapSplitContainer.Panel1.Controls.Add(this.colorLabel);
       this.mapSplitContainer.Panel1.Controls.Add(this.sizeLabel);
       this.mapSplitContainer.Panel1.Controls.Add(this.projectionLabel);
       this.mapSplitContainer.Panel1.Controls.Add(this.instanceMapChart);
+      this.mapSplitContainer.Panel1.Controls.Add(this.colorComboBox);
       this.mapSplitContainer.Panel1.Controls.Add(this.sizeComboBox);
       this.mapSplitContainer.Panel1.Controls.Add(this.projectionComboBox);
       this.mapSplitContainer.Panel1.Padding = new System.Windows.Forms.Padding(0, 3, 0, 0);
       this.mapSplitContainer.Panel2Collapsed = true;
-      this.mapSplitContainer.Size = new System.Drawing.Size(986, 728);
+      this.mapSplitContainer.Size = new System.Drawing.Size(1094, 728);
       this.mapSplitContainer.SplitterDistance = 847;
       this.mapSplitContainer.TabIndex = 12;
@@ -122 +128 @@
       this.showCharacteristicsCheckBox.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
       this.showCharacteristicsCheckBox.Appearance = System.Windows.Forms.Appearance.Button;
-      this.showCharacteristicsCheckBox.Location = new System.Drawing.Point(957, 4);
+      this.showCharacteristicsCheckBox.Location = new System.Drawing.Point(1065, 5);
       this.showCharacteristicsCheckBox.Name = "showCharacteristicsCheckBox";
       this.showCharacteristicsCheckBox.Size = new System.Drawing.Size(26, 23);
@@ -130 +136 @@
       this.showCharacteristicsCheckBox.CheckedChanged += new System.EventHandler(this.showCharacteristicsCheckBox_CheckedChanged);
       // 
+      // fromZeroCheckBox
+      // 
+      this.fromZeroCheckBox.AutoSize = true;
+      this.fromZeroCheckBox.Checked = true;
+      this.fromZeroCheckBox.CheckState = System.Windows.Forms.CheckState.Checked;
+      this.fromZeroCheckBox.Location = new System.Drawing.Point(639, 8);
+      this.fromZeroCheckBox.Name = "fromZeroCheckBox";
+      this.fromZeroCheckBox.Size = new System.Drawing.Size(69, 17);
+      this.fromZeroCheckBox.TabIndex = 17;
+      this.fromZeroCheckBox.Text = "from zero";
+      this.fromZeroCheckBox.UseVisualStyleBackColor = true;
+      this.fromZeroCheckBox.CheckedChanged += new System.EventHandler(this.fromZeroCheckBox_CheckedChanged);
+      // 
       // invPropCheckBox
       // 
@@ -135 +154 @@
       this.invPropCheckBox.Checked = true;
       this.invPropCheckBox.CheckState = System.Windows.Forms.CheckState.Checked;
-      this.invPropCheckBox.Location = new System.Drawing.Point(579, 12);
+      this.invPropCheckBox.Location = new System.Drawing.Point(515, 8);
       this.invPropCheckBox.Name = "invPropCheckBox";
       this.invPropCheckBox.Size = new System.Drawing.Size(118, 17);
@@ -146 +165 @@
       // 
       this.sizeLabel.AutoSize = true;
-      this.sizeLabel.Location = new System.Drawing.Point(264, 12);
+      this.sizeLabel.Location = new System.Drawing.Point(251, 12);
       this.sizeLabel.Name = "sizeLabel";
       this.sizeLabel.Size = new System.Drawing.Size(30, 13);
@@ -192 +211 @@
       this.instanceMapChart.Series.Add(series1);
       this.instanceMapChart.Series.Add(series2);
-      this.instanceMapChart.Size = new System.Drawing.Size(980, 692);
+      this.instanceMapChart.Size = new System.Drawing.Size(974, 692);
       this.instanceMapChart.TabIndex = 12;
       // 
@@ -199 +218 @@
       this.sizeComboBox.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
       this.sizeComboBox.FormattingEnabled = true;
-      this.sizeComboBox.Location = new System.Drawing.Point(300, 6);
+      this.sizeComboBox.Location = new System.Drawing.Point(287, 6);
       this.sizeComboBox.Name = "sizeComboBox";
-      this.sizeComboBox.Size = new System.Drawing.Size(273, 21);
+      this.sizeComboBox.Size = new System.Drawing.Size(222, 21);
       this.sizeComboBox.TabIndex = 13;
       this.sizeComboBox.SelectedIndexChanged += new System.EventHandler(this.SizeComboBoxOnSelectedIndexChanged);
@@ -221 +240 @@
       this.instancesTabPage.Name = "instancesTabPage";
       this.instancesTabPage.Padding = new System.Windows.Forms.Padding(3);
-      this.instancesTabPage.Size = new System.Drawing.Size(992, 734);
+      this.instancesTabPage.Size = new System.Drawing.Size(1106, 734);
       this.instancesTabPage.TabIndex = 0;
       this.instancesTabPage.Text = "Instances";
@@ -235 +254 @@
       this.problemInstancesView.Name = "problemInstancesView";
       this.problemInstancesView.ReadOnly = false;
-      this.problemInstancesView.Size = new System.Drawing.Size(986, 728);
+      this.problemInstancesView.Size = new System.Drawing.Size(1100, 728);
       this.problemInstancesView.TabIndex = 0;
       this.problemInstancesView.ViewsLabelVisible = true;
       this.problemInstancesView.ViewType = null;
+      // 
+      // colorComboBox
+      // 
+      this.colorComboBox.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
+      this.colorComboBox.FormattingEnabled = true;
+      this.colorComboBox.Location = new System.Drawing.Point(768, 6);
+      this.colorComboBox.Name = "colorComboBox";
+      this.colorComboBox.Size = new System.Drawing.Size(222, 21);
+      this.colorComboBox.TabIndex = 13;
+      this.colorComboBox.SelectedIndexChanged += new System.EventHandler(this.colorComboBox_SelectedIndexChanged);
+      // 
+      // colorLabel
+      // 
+      this.colorLabel.AutoSize = true;
+      this.colorLabel.Location = new System.Drawing.Point(728, 9);
+      this.colorLabel.Name = "colorLabel";
+      this.colorLabel.Size = new System.Drawing.Size(34, 13);
+      this.colorLabel.TabIndex = 15;
+      this.colorLabel.Text = "Color:";
       // 
       // UnderstandingProblemInstanceView
@@ -246 +284 @@
       this.Controls.Add(this.problemInstancesTabControl);
       this.Name = "UnderstandingProblemInstanceView";
-      this.Size = new System.Drawing.Size(1000, 760);
+      this.Size = new System.Drawing.Size(1108, 760);
       this.problemInstancesTabControl.ResumeLayout(false);
       this.mapTabPage.ResumeLayout(false);
@@ -273 +311 @@
     private System.Windows.Forms.ComboBox sizeComboBox;
     private System.Windows.Forms.ComboBox projectionComboBox;
+    private System.Windows.Forms.CheckBox fromZeroCheckBox;
+    private System.Windows.Forms.Label colorLabel;
+    private System.Windows.Forms.ComboBox colorComboBox;
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/UnderstandingProblemInstanceView.cs

@@ -28 +28 @@
 using System;
 using System.Collections.Generic;
+using System.Drawing;
 using System.Linq;
 using System.Text.RegularExpressions;
@@ -62 +63 @@
         UpdateProjectionComboBox();
         UpdateSizeComboBox();
+        UpdateColorComboBox();
       }
     }
@@ -76 +78 @@
       UpdateProjectionComboBox();
       UpdateSizeComboBox();
+      UpdateColorComboBox();
       UpdateProjection();
     }
@@ -108 +111 @@
       } finally { SuppressEvents = false; }
     }
+
+    private void UpdateColorComboBox() {
+      try {
+        SuppressEvents = true;
+        var selected = colorComboBox.SelectedIndex >= 0 ? (string)colorComboBox.SelectedItem : null;
+        colorComboBox.Items.Clear();
+        colorComboBox.Items.Add(string.Empty);
+        foreach (var str in Content.ProblemInstances.ResultNames.Where(x => x.StartsWith("Rank."))) {
+          colorComboBox.Items.Add(str);
+          if (selected == str) colorComboBox.SelectedItem = str;
+        }
+        if (selected == null && colorComboBox.Items.Count > 0)
+          colorComboBox.SelectedIndex = 0;
+      } finally { SuppressEvents = false; }
+    }
     
     private IEnumerable<string> GetProjections() {
@@ -130 +148 @@
       var projection = (string)projectionComboBox.SelectedItem;
       var size = sizeComboBox.SelectedIndex >= 0 ? (string)sizeComboBox.SelectedItem : string.Empty;
-
-      DoProjectProblemInstances(instancesSeries, currentInstanceSeries, projection, size, invPropCheckBox.Checked);
-    }
-
-    private void DoProjectProblemInstances(Series instancesSeries, Series currentInstanceSeries, string projection, string size, bool invProp) {
+      var color = colorComboBox.SelectedIndex >= 0 ? (string)colorComboBox.SelectedItem : string.Empty;
+
+      DoProjectProblemInstances(instancesSeries, currentInstanceSeries, projection,
+        size, color, invPropCheckBox.Checked, fromZeroCheckBox.Checked);
+    }
+
+    private void DoProjectProblemInstances(Series instancesSeries, Series currentInstanceSeries, string projection, string size, string color, bool invProp, bool fromZero) {
       instancesSeries.Points.Clear();
       currentInstanceSeries.Points.Clear();
@@ -143 +163 @@
         if (sizes.Count > 0) {
           maxSize = sizes.Max(x => x.Value);
-          minSize = sizes.Min(x => x.Value);
+          if (maxSize < 0 && fromZero) {
+            maxSize = 0;
+            minSize = sizes.Min(x => x.Value);
+          } else if (fromZero) {
+            minSize = 0;
+          } else {
+            minSize = sizes.Min(x => x.Value);
+          }
         }
       }
@@ -159 +186 @@
         if (maxSize > minSize && run.Results.TryGetValue(size, out item)) {
           var dItem = item as Data.DoubleValue;
+          if (dItem == null && item is IntValue) dItem = new DoubleValue(((IntValue)item).Value);
           if (dItem != null) {
             if (double.IsNaN(dItem.Value))
@@ -171 +199 @@
         } else dataPoint.MarkerSize = 1;
 
+        if (!string.IsNullOrEmpty(color)) {
+          if (run.Results.TryGetValue(color, out item)) {
+            var v = (int)(item is DoubleValue ? ((DoubleValue)item).Value : (item is IntValue ? ((IntValue)item).Value : int.MaxValue));
+            switch (v) {
+              case 0: dataPoint.MarkerColor = Color.Green; break;
+              case 1: dataPoint.MarkerColor = Color.LightSeaGreen; break;
+              case 2: dataPoint.MarkerColor = Color.CornflowerBlue; break;
+              case 3: dataPoint.MarkerColor = Color.PaleVioletRed; break;
+              case 4: dataPoint.MarkerColor = Color.IndianRed; break;
+              default: dataPoint.MarkerColor = Color.LightGray; break;
+            }
+          }
+        }
         if (Content.IsCurrentInstance(run)) currentInstanceSeries.Points.Add(dataPoint);
         else instancesSeries.Points.Add(dataPoint);
@@ -185 +226 @@
     }
 
+    private void colorComboBox_SelectedIndexChanged(object sender, EventArgs e) {
+      UpdateProjection();
+    }
+
     private void InvPropCheckBoxOnCheckedChanged(object sender, EventArgs e) {
+      UpdateProjection();
+    }
+
+    private void fromZeroCheckBox_CheckedChanged(object sender, EventArgs e) {
       UpdateProjection();
     }