Ignore:
Timestamp:
01/21/16 11:15:23 (5 years ago)
Author:
abeham
Message:

#2457:

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

Legend:

Unmodified
Added
Removed
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/ExpertSystem.cs

    r13551 r13561  
    116116    private BidirectionalDictionary<long, IAlgorithm> algorithmId2AlgorithmInstanceMapping;
    117117
     118    [Storable]
     119    private Run currentInstance;
     120
    118121    private bool Maximization {
    119122      get {
     
    140143        algorithmId2AlgorithmInstanceMapping.Add(kvp.Key, cloner.Clone(kvp.Value));
    141144      }
     145      currentInstance = cloner.Clone(original.currentInstance);
    142146      RegisterEventHandlers();
    143147    }
     
    188192    }
    189193
    190     public void UpdateInstanceMap() {
    191       var flaValues = ProblemInstances.ResultNames
    192                       .Where(x => x.StartsWith("Characteristic.")
    193                         && ProblemInstances.All(y => y.Results.ContainsKey(x) && y.Results[x] is DoubleValue))
    194                       .Select(x => x).ToList();
    195       var ds = new double[ProblemInstances.Count, flaValues.Count];
    196       var instanceCounter = 0;
    197       foreach (var instance in ProblemInstances) {
    198         for (var feature = 0; feature < flaValues.Count; feature++)
    199           ds[instanceCounter, feature] = ((DoubleValue)instance.Results[flaValues[feature]]).Value;
    200         instanceCounter++;
     194    public void UpdateInstanceProjection() {
     195      currentInstance = null;
     196      var filter = new HashSet<string>();
     197
     198      if (Problem.ProblemId != -1) {
     199        currentInstance = new Run { Name = Problem.Name };
     200        Problem.Problem.CollectParameterValues(currentInstance.Parameters);
     201        foreach (var c in RunCreationClient.GetCharacteristicValues(Problem.ProblemId)) {
     202          var key = "Characteristic." + c.Name;
     203          currentInstance.Results.Add(key, RunCreationClient.Instance.ConvertToItem(c));
     204          filter.Add(key);
     205        }
     206      }
     207      // TODO: There is a problem with missing values that has to be solved
     208      // The common set of characteristics among all problems may be too small to be useful
     209      // It has to be decided somehow which problem instances to include in order to obtain the set of features that is expressive and available
     210      var allCharacteristics = ProblemInstances.Select(x => new HashSet<string>(x.Results.Where(y => y.Key.StartsWith("Characteristic.", StringComparison.Ordinal)).Select(y => y.Key))).ToList();
     211      var commonCharacteristics = filter.Count > 0 ? filter : allCharacteristics[0];
     212      for (var i = 0; i < allCharacteristics.Count; i++)
     213        commonCharacteristics.IntersectWith(allCharacteristics[i]);
     214
     215      if (commonCharacteristics.Count == 0) return;
     216
     217      var instances = new Dictionary<string, double[]>();
     218      foreach (var i in ProblemInstances)
     219        instances[i.Name] = i.Results.Where(x => commonCharacteristics.Contains(x.Key)).OrderBy(x => x.Key).Select(x => (double)((dynamic)x.Value).Value).ToArray();
     220      if (currentInstance != null)
     221        instances[currentInstance.Name] = currentInstance.Results.Where(x => commonCharacteristics.Contains(x.Key)).OrderBy(x => x.Key).Select(x => (double)((dynamic)x.Value).Value).ToArray();
     222
     223      var allValues = instances.SelectMany(x => x.Value).ToList();
     224      var avg = allValues.Average();
     225      var stdev = allValues.StandardDeviation();
     226
     227      // normalize characteristic values by transforming them to their z-score
     228      foreach (var key in instances.Keys.ToList()) {
     229        var arr = instances[key];
     230        for (var i = 0; i < arr.Length; i++) {
     231          arr[i] = (arr[i] - avg) / stdev;
     232        }
     233      }
     234
     235      var key2Idx = new BidirectionalDictionary<string, int>();
     236      foreach (var kvp in instances.Select((k, i) => new { Index = i, Key = k.Key }))
     237        key2Idx.Add(kvp.Key, kvp.Index);
     238
     239      #region MDS
     240      Func<double[], double[], double> euclid = (a, b) => Math.Sqrt(a.Zip(b, (x, y) => (x - y)).Sum(x => x * x));
     241      var num = instances.Count;
     242      var matrix = new DoubleMatrix(num, num);
     243      for (var i = 0; i < num - 1; i++) {
     244        for (var j = i + 1; j < num; j++) {
     245          matrix[i, j] = matrix[j, i] = euclid(instances[key2Idx.GetBySecond(i)], instances[key2Idx.GetBySecond(j)]);
     246        }
     247      }
     248
     249      var coords = MultidimensionalScaling.KruskalShepard(matrix);
     250      #endregion
     251      #region PCA
     252      var ds = new double[instances.Count, commonCharacteristics.Count];
     253      foreach (var instance in instances) {
     254        var arr = instance.Value;
     255        for (var feature = 0; feature < arr.Length; feature++)
     256          ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
    201257      }
    202258
     
    204260      double[] s2;
    205261      double[,] v;
    206       alglib.pcabuildbasis(ds, instanceCounter, flaValues.Count, out info, out s2, out v);
     262      alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
     263      #endregion
    207264
    208265      ProblemInstances.UpdateOfRunsInProgress = true;
    209266      try {
    210         instanceCounter = 0;
    211267        foreach (var instance in ProblemInstances) {
    212268          double x = 0, y = 0;
    213           for (var feature = 0; feature < flaValues.Count; feature++) {
    214             x += ds[instanceCounter, feature] * v[feature, 0];
    215             y += ds[instanceCounter, feature] * v[feature, 1];
     269          for (var feature = 0; feature < ds.GetLength(1); feature++) {
     270            x += ds[key2Idx.GetByFirst(instance.Name), feature] * v[feature, 0];
     271            y += ds[key2Idx.GetByFirst(instance.Name), feature] * v[feature, 1];
    216272          }
     273
    217274          IItem item;
    218           if (instance.Results.TryGetValue("Projection.PCA1", out item)) {
     275          if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
    219276            ((DoubleValue)item).Value = x;
    220           } else instance.Results.Add("Projection.PCA1", new DoubleValue(x));
    221           if (instance.Results.TryGetValue("Projection.PCA2", out item)) {
     277          } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
     278          if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
    222279            ((DoubleValue)item).Value = y;
    223           } else instance.Results.Add("Projection.PCA2", new DoubleValue(y));
    224 
    225           instanceCounter++;
     280          } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
     281
     282          if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
     283            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance.Name), 0];
     284          } else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance.Name), 0]));
     285          if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
     286            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance.Name), 1];
     287          } else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance.Name), 1]));
    226288        }
    227289      } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
     290
     291      if (currentInstance != null) {
     292        double x = 0, y = 0;
     293        for (var feature = 0; feature < ds.GetLength(1); feature++) {
     294          x += ds[key2Idx.GetByFirst(currentInstance.Name), feature] * v[feature, 0];
     295          y += ds[key2Idx.GetByFirst(currentInstance.Name), feature] * v[feature, 1];
     296        }
     297
     298        IItem item;
     299        if (currentInstance.Results.TryGetValue("Projection.PCA.X", out item)) {
     300          ((DoubleValue)item).Value = x;
     301        } else currentInstance.Results.Add("Projection.PCA.X", new DoubleValue(x));
     302        if (currentInstance.Results.TryGetValue("Projection.PCA.Y", out item)) {
     303          ((DoubleValue)item).Value = y;
     304        } else currentInstance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
     305
     306        if (currentInstance.Results.TryGetValue("Projection.MDS.X", out item)) {
     307          ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(currentInstance.Name), 0];
     308        } else currentInstance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(currentInstance.Name), 0]));
     309        if (currentInstance.Results.TryGetValue("Projection.MDS.Y", out item)) {
     310          ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(currentInstance.Name), 1];
     311        } else currentInstance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(currentInstance.Name), 1]));
     312      }
     313    }
     314
     315    public Tuple<double, double> ProjectCurrentInstance(string projection) {
     316      if (currentInstance == null) return null;
     317      var xKey = "Projection." + projection + ".X";
     318      var yKey = "Projection." + projection + ".Y";
     319      if (!currentInstance.Results.ContainsKey(xKey) || !currentInstance.Results.ContainsKey(yKey))
     320        return null;
     321      var x = ((DoubleValue)currentInstance.Results[xKey]).Value;
     322      var y = ((DoubleValue)currentInstance.Results[yKey]).Value;
     323      return Tuple.Create(x, y);
    228324    }
    229325
Note: See TracChangeset for help on using the changeset viewer.