Changeset 13561 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem

Timestamp:

01/21/16 11:15:23 (9 years ago)

Author:

abeham

Message:

#2457:

• added two types of problem instance mappings: PCA and MDS

File:

• branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/ExpertSystem.cs (modified) (4 diffs)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/ExpertSystem.cs

@@ -116 +116 @@
     private BidirectionalDictionary<long, IAlgorithm> algorithmId2AlgorithmInstanceMapping;
 
+    [Storable]
+    private Run currentInstance;
+
     private bool Maximization {
       get {
@@ -140 +143 @@
         algorithmId2AlgorithmInstanceMapping.Add(kvp.Key, cloner.Clone(kvp.Value));
       }
+      currentInstance = cloner.Clone(original.currentInstance);
       RegisterEventHandlers();
     }
@@ -188 +192 @@
     }
 
-    public void UpdateInstanceMap() {
-      var flaValues = ProblemInstances.ResultNames
-                      .Where(x => x.StartsWith("Characteristic.")
-                        && ProblemInstances.All(y => y.Results.ContainsKey(x) && y.Results[x] is DoubleValue))
-                      .Select(x => x).ToList();
-      var ds = new double[ProblemInstances.Count, flaValues.Count];
-      var instanceCounter = 0;
-      foreach (var instance in ProblemInstances) {
-        for (var feature = 0; feature < flaValues.Count; feature++)
-          ds[instanceCounter, feature] = ((DoubleValue)instance.Results[flaValues[feature]]).Value;
-        instanceCounter++;
+    public void UpdateInstanceProjection() {
+      currentInstance = null;
+      var filter = new HashSet<string>();
+
+      if (Problem.ProblemId != -1) {
+        currentInstance = new Run { Name = Problem.Name };
+        Problem.Problem.CollectParameterValues(currentInstance.Parameters);
+        foreach (var c in RunCreationClient.GetCharacteristicValues(Problem.ProblemId)) {
+          var key = "Characteristic." + c.Name;
+          currentInstance.Results.Add(key, RunCreationClient.Instance.ConvertToItem(c));
+          filter.Add(key);
+        }
+      }
+      // TODO: There is a problem with missing values that has to be solved
+      // The common set of characteristics among all problems may be too small to be useful
+      // It has to be decided somehow which problem instances to include in order to obtain the set of features that is expressive and available
+      var allCharacteristics = ProblemInstances.Select(x => new HashSet<string>(x.Results.Where(y => y.Key.StartsWith("Characteristic.", StringComparison.Ordinal)).Select(y => y.Key))).ToList();
+      var commonCharacteristics = filter.Count > 0 ? filter : allCharacteristics[0];
+      for (var i = 0; i < allCharacteristics.Count; i++)
+        commonCharacteristics.IntersectWith(allCharacteristics[i]);
+
+      if (commonCharacteristics.Count == 0) return;
+
+      var instances = new Dictionary<string, double[]>();
+      foreach (var i in ProblemInstances)
+        instances[i.Name] = i.Results.Where(x => commonCharacteristics.Contains(x.Key)).OrderBy(x => x.Key).Select(x => (double)((dynamic)x.Value).Value).ToArray();
+      if (currentInstance != null)
+        instances[currentInstance.Name] = currentInstance.Results.Where(x => commonCharacteristics.Contains(x.Key)).OrderBy(x => x.Key).Select(x => (double)((dynamic)x.Value).Value).ToArray();
+
+      var allValues = instances.SelectMany(x => x.Value).ToList();
+      var avg = allValues.Average();
+      var stdev = allValues.StandardDeviation();
+
+      // normalize characteristic values by transforming them to their z-score
+      foreach (var key in instances.Keys.ToList()) {
+        var arr = instances[key];
+        for (var i = 0; i < arr.Length; i++) {
+          arr[i] = (arr[i] - avg) / stdev;
+        }
+      }
+
+      var key2Idx = new BidirectionalDictionary<string, 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, commonCharacteristics.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];
       }
 
@@ -204 +260 @@
       double[] s2;
       double[,] v;
-      alglib.pcabuildbasis(ds, instanceCounter, flaValues.Count, out info, out s2, out v);
+      alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
+      #endregion
 
       ProblemInstances.UpdateOfRunsInProgress = true;
       try {
-        instanceCounter = 0;
         foreach (var instance in ProblemInstances) {
           double x = 0, y = 0;
-          for (var feature = 0; feature < flaValues.Count; feature++) {
-            x += ds[instanceCounter, feature] * v[feature, 0];
-            y += ds[instanceCounter, feature] * v[feature, 1];
+          for (var feature = 0; feature < ds.GetLength(1); feature++) {
+            x += ds[key2Idx.GetByFirst(instance.Name), feature] * v[feature, 0];
+            y += ds[key2Idx.GetByFirst(instance.Name), feature] * v[feature, 1];
           }
+
           IItem item;
-          if (instance.Results.TryGetValue("Projection.PCA1", out item)) {
+          if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
             ((DoubleValue)item).Value = x;
-          } else instance.Results.Add("Projection.PCA1", new DoubleValue(x));
-          if (instance.Results.TryGetValue("Projection.PCA2", out item)) {
+          } 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.PCA2", new DoubleValue(y));
-
-          instanceCounter++;
+          } 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.Name), 0];
+          } else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance.Name), 0]));
+          if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
+            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance.Name), 1];
+          } else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance.Name), 1]));
         }
       } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
+
+      if (currentInstance != null) {
+        double x = 0, y = 0;
+        for (var feature = 0; feature < ds.GetLength(1); feature++) {
+          x += ds[key2Idx.GetByFirst(currentInstance.Name), feature] * v[feature, 0];
+          y += ds[key2Idx.GetByFirst(currentInstance.Name), feature] * v[feature, 1];
+        }
+
+        IItem item;
+        if (currentInstance.Results.TryGetValue("Projection.PCA.X", out item)) {
+          ((DoubleValue)item).Value = x;
+        } else currentInstance.Results.Add("Projection.PCA.X", new DoubleValue(x));
+        if (currentInstance.Results.TryGetValue("Projection.PCA.Y", out item)) {
+          ((DoubleValue)item).Value = y;
+        } else currentInstance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
+
+        if (currentInstance.Results.TryGetValue("Projection.MDS.X", out item)) {
+          ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(currentInstance.Name), 0];
+        } else currentInstance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(currentInstance.Name), 0]));
+        if (currentInstance.Results.TryGetValue("Projection.MDS.Y", out item)) {
+          ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(currentInstance.Name), 1];
+        } else currentInstance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(currentInstance.Name), 1]));
+      }
+    }
+
+    public Tuple<double, double> ProjectCurrentInstance(string projection) {
+      if (currentInstance == null) return null;
+      var xKey = "Projection." + projection + ".X";
+      var yKey = "Projection." + projection + ".Y";
+      if (!currentInstance.Results.ContainsKey(xKey) || !currentInstance.Results.ContainsKey(yKey))
+        return null;
+      var x = ((DoubleValue)currentInstance.Results[xKey]).Value;
+      var y = ((DoubleValue)currentInstance.Results[yKey]).Value;
+      return Tuple.Create(x, y);
     }