Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/13/16 16:25:12 (8 years ago)
Author:
abeham
Message:

#2547:

  • worked on problem instance mapping
  • started working on improved suggestion algorithm
File:
1 edited

Legend:

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

    r13752 r13757  
    5959    }
    6060
     61    private readonly DoubleValue minimumTarget;
     62    public DoubleValue MinimumTarget {
     63      get { return minimumTarget; }
     64    }
     65   
    6166    private readonly RunCollection instanceRuns;
    6267    public RunCollection InstanceRuns {
     
    9499    public ReadOnlyCheckedItemList<StringValue> ProblemCharacteristics {
    95100      get { return readonlyProblemCharacteristics; }
    96     }
     101    }
     102
     103    private readonly EnumValue<ProblemInstanceProximityType> problemInstanceProximity;
     104    public EnumValue<ProblemInstanceProximityType> ProblemInstanceProximity {
     105      get { return problemInstanceProximity; }
     106    }
     107
     108    private readonly DoubleValue problemInstanceNeighborhoodFactor;
     109    public DoubleValue ProblemInstanceNeighborhoodFactor {
     110      get { return problemInstanceNeighborhoodFactor; }
     111    }
    97112
    98113    private readonly CheckedItemList<IScope> solutionSeedingPool;
     
    116131    public KnowledgeCenter() {
    117132      maximumEvaluations = new IntValue(10000);
     133      minimumTarget = new DoubleValue(1.05);
    118134      instanceRuns = new RunCollection();
    119135      seededRuns = new RunCollection();
     
    123139      problemInstances = new RunCollection();
    124140      problemCharacteristics = new CheckedItemList<StringValue>();
     141      problemInstanceProximity = new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace);
     142      problemInstanceNeighborhoodFactor = new DoubleValue(1);
    125143      readonlyProblemCharacteristics = problemCharacteristics.AsReadOnly();
    126144      problem = new SingleObjectiveOKBProblem();
     
    139157    private void RegisterEventHandlers() {
    140158      maximumEvaluations.ValueChanged += MaximumEvaluationsOnValueChanged;
     159      minimumTarget.ValueChanged += MinimumTargetOnValueChanged;
    141160      problem.ProblemChanged += ProblemOnProblemChanged;
    142161      problem.Solutions.ItemsAdded += ProblemSolutionsChanged;
     
    157176      problemCharacteristics.CollectionReset += CharacteristicChanged;
    158177      problemCharacteristics.CheckedItemsChanged += CharacteristicChanged;
     178      problemInstanceProximity.ValueChanged += ProblemInstanceProximityChanged;
     179      problemInstanceNeighborhoodFactor.ValueChanged += ProblemInstanceProximityChanged;
    159180    }
    160181
    161182    private void MaximumEvaluationsOnValueChanged(object sender, EventArgs eventArgs) {
     183      UpdateSuggestions();
     184    }
     185
     186    private void MinimumTargetOnValueChanged(object sender, EventArgs e) {
    162187      UpdateSuggestions();
    163188    }
     
    181206    }
    182207
     208    private void ProblemInstanceProximityChanged(object sender, EventArgs e) {
     209      UpdateSuggestions();
     210    }
     211
    183212    public bool IsCurrentInstance(IRun run) {
    184213      if (!problemId2ProblemInstanceMapping.ContainsSecond(run)) return false;
     
    189218      if (ProblemCharacteristics.Count == 0) return;
    190219
     220      var instances = GetProblemCharacteristics();
     221
     222      var key2Idx = new BidirectionalDictionary<IRun, int>();
     223      foreach (var kvp in instances.Select((k, i) => new { Index = i, Key = k.Key }))
     224        key2Idx.Add(kvp.Key, kvp.Index);
     225
     226      #region MDS
     227      Func<double[], double[], double> euclid = (a, b) => Math.Sqrt(a.Zip(b, (x, y) => (x - y)).Sum(x => x * x));
     228      var num = instances.Count;
     229      var matrix = new DoubleMatrix(num, num);
     230      for (var i = 0; i < num - 1; i++) {
     231        for (var j = i + 1; j < num; j++) {
     232          matrix[i, j] = matrix[j, i] = euclid(instances[key2Idx.GetBySecond(i)], instances[key2Idx.GetBySecond(j)]);
     233        }
     234      }
     235
     236      var coords = MultidimensionalScaling.KruskalShepard(matrix);
     237      #endregion
     238      #region PCA
     239      var ds = new double[instances.Count, ProblemCharacteristics.CheckedItems.Count()];
     240      foreach (var instance in instances) {
     241        var arr = instance.Value;
     242        for (var feature = 0; feature < arr.Length; feature++)
     243          ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
     244      }
     245
     246      int info;
     247      double[] s2;
     248      double[,] v;
     249      alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
     250      #endregion
     251      #region SOM
     252      var features = new DoubleMatrix(ProblemCharacteristics.CheckedItems.Count(), instances.Count);
     253      foreach (var instance in instances) {
     254        var arr = instance.Value;
     255        for (var feature = 0; feature < arr.Length; feature++)
     256          features[feature, key2Idx.GetByFirst(instance.Key)] = arr[feature];
     257      }
     258      var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 20, learningRadius: 20, iterations: 200, jittering: true);
     259      #endregion
     260
     261      ProblemInstances.UpdateOfRunsInProgress = true;
     262      try {
     263        foreach (var instance in ProblemInstances) {
     264          double x = 0, y = 0;
     265          for (var feature = 0; feature < ds.GetLength(1); feature++) {
     266            x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
     267            y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
     268          }
     269
     270          IItem item;
     271          if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
     272            ((DoubleValue)item).Value = x;
     273          } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
     274          if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
     275            ((DoubleValue)item).Value = y;
     276          } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
     277
     278          if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
     279            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 0];
     280          } else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance), 0]));
     281          if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
     282            ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 1];
     283          } else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance), 1]));
     284
     285          if (instance.Results.TryGetValue("Projection.SOM.X", out item)) {
     286            ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 0];
     287          } else instance.Results.Add("Projection.SOM.X", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 0]));
     288          if (instance.Results.TryGetValue("Projection.SOM.Y", out item)) {
     289            ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 1];
     290          } else instance.Results.Add("Projection.SOM.Y", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 1]));
     291        }
     292      } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
     293    }
     294
     295    private Dictionary<IRun, double[]> GetProblemCharacteristics() {
    191296      var instances = new Dictionary<IRun, double[]>();
    192297      var values = new List<double>[ProblemCharacteristics.CheckedItems.Count()];
     
    207312      var median = values.Select(x => x.Count == 0 ? 0.0 : x.Median()).ToList();
    208313
    209       var allValues = instances.Values.Select(x => x.Select((f, i) => new { Idx = i, Val = double.IsNaN(f) ? median[i] : f }).ToList())
    210                                       .SelectMany(x => x)
    211                                       .GroupBy(x => x.Idx, x => x.Val)
    212                                       .OrderBy(x => x.Key).ToList();
     314      var allValues = instances.Values.Select(x => x.Select((f, i) => new {Idx = i, Val = double.IsNaN(f) ? median[i] : f}).ToList())
     315        .SelectMany(x => x)
     316        .GroupBy(x => x.Idx, x => x.Val)
     317        .OrderBy(x => x.Key).ToList();
    213318      var avg = allValues.Select(x => x.Average()).ToList();
    214319      var stdev = allValues.Select(x => x.StandardDeviation()).ToList();
     
    222327        }
    223328      }
    224 
    225       var key2Idx = new BidirectionalDictionary<IRun, int>();
    226       foreach (var kvp in instances.Select((k, i) => new { Index = i, Key = k.Key }))
    227         key2Idx.Add(kvp.Key, kvp.Index);
    228 
    229       #region MDS
    230       Func<double[], double[], double> euclid = (a, b) => Math.Sqrt(a.Zip(b, (x, y) => (x - y)).Sum(x => x * x));
    231       var num = instances.Count;
    232       var matrix = new DoubleMatrix(num, num);
    233       for (var i = 0; i < num - 1; i++) {
    234         for (var j = i + 1; j < num; j++) {
    235           matrix[i, j] = matrix[j, i] = euclid(instances[key2Idx.GetBySecond(i)], instances[key2Idx.GetBySecond(j)]);
    236         }
    237       }
    238 
    239       var coords = MultidimensionalScaling.KruskalShepard(matrix);
    240       #endregion
    241       #region PCA
    242       var ds = new double[instances.Count, ProblemCharacteristics.CheckedItems.Count()];
    243       foreach (var instance in instances) {
    244         var arr = instance.Value;
    245         for (var feature = 0; feature < arr.Length; feature++)
    246           ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
    247       }
    248 
    249       int info;
    250       double[] s2;
    251       double[,] v;
    252       alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
    253       #endregion
    254       #region SOM
    255       var features = new DoubleMatrix(ProblemCharacteristics.CheckedItems.Count(), instances.Count);
    256       foreach (var instance in instances) {
    257         var arr = instance.Value;
    258         for (var feature = 0; feature < arr.Length; feature++)
    259           features[feature, key2Idx.GetByFirst(instance.Key)] = arr[feature];
    260       }
    261       var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 20, learningRadius: 20, iterations: 200, jittering: true);
    262       #endregion
    263 
    264       ProblemInstances.UpdateOfRunsInProgress = true;
    265       try {
    266         foreach (var instance in ProblemInstances) {
    267           double x = 0, y = 0;
    268           for (var feature = 0; feature < ds.GetLength(1); feature++) {
    269             x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
    270             y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
    271           }
    272 
    273           IItem item;
    274           if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
    275             ((DoubleValue)item).Value = x;
    276           } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
    277           if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
    278             ((DoubleValue)item).Value = y;
    279           } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
    280 
    281           if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
    282             ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 0];
    283           } else instance.Results.Add("Projection.MDS.X", new DoubleValue(coords[key2Idx.GetByFirst(instance), 0]));
    284           if (instance.Results.TryGetValue("Projection.MDS.Y", out item)) {
    285             ((DoubleValue)item).Value = coords[key2Idx.GetByFirst(instance), 1];
    286           } else instance.Results.Add("Projection.MDS.Y", new DoubleValue(coords[key2Idx.GetByFirst(instance), 1]));
    287 
    288           if (instance.Results.TryGetValue("Projection.SOM.X", out item)) {
    289             ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 0];
    290           } else instance.Results.Add("Projection.SOM.X", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 0]));
    291           if (instance.Results.TryGetValue("Projection.SOM.Y", out item)) {
    292             ((DoubleValue)item).Value = somCoords[key2Idx.GetByFirst(instance), 1];
    293           } else instance.Results.Add("Projection.SOM.Y", new DoubleValue(somCoords[key2Idx.GetByFirst(instance), 1]));
    294         }
    295       } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
     329      return instances;
    296330    }
    297331
     
    434468        problemClassFilter.Value = adminClient.ProblemClasses.Single(x => x.Id == probClassId).Name;
    435469
     470        problemId2ProblemInstanceMapping.Clear();
    436471        progress.Status = "Downloading problem instances...";
    437472        progress.ProgressValue = 0;
     
    550585
    551586          if (!algInstRunDict.ContainsKey(probInstanceName)) continue;
    552           foreach (var kvp in algInstRunDict[probInstanceName]) {
    553             // TODO: Things needs to be configurable here (table name, targets)
    554             foreach (var target in new[] { 1, 1.01, 1.05, 1.1, 1.2, 1.5 }) {
     587          // TODO: Things needs to be configurable here (table name, targets)
     588          foreach (var target in new[] { 1, 1.01, 1.05, 1.1, 1.2, 1.5 }) {
     589            var indexMap = new BidirectionalDictionary<string, int>();
     590            var dict = new Dictionary<string, double>();
     591            var idx = 0;
     592            foreach (var kvp in algInstRunDict[probInstanceName]) {
    555593              var result = ExpectedRuntimeHelper.CalculateErt(kvp.Value, "QualityPerEvaluations", bkQuality * target, maximization);
    556               var resultName = kvp.Key + "@" + ((target - 1) * 100) + "%";
    557               characteristics.Add(resultName);
    558               IItem item;
    559               if (instance.Results.TryGetValue(resultName, out item)) {
    560                 ((DoubleValue)item).Value = Math.Log10(result.ExpectedRuntime);
    561               } else instance.Results.Add(resultName, new DoubleValue(Math.Log10(result.ExpectedRuntime)));
     594              indexMap.Add(kvp.Key, idx);
     595              dict[kvp.Key] = !double.IsNaN(result.ExpectedRuntime) ? result.ExpectedRuntime : int.MaxValue;
     596              idx++;
     597            }
     598            var points = dict.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value > 0 ? Math.Log10(x.Value) : 0).ToArray();
     599            int[] clusters;
     600            Ckmeans1dClusters(points, 5, out clusters);
     601            var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = dict[indexMap.GetBySecond(i)] })
     602                                .GroupBy(x => x.Cluster, x => x.Perf)
     603                                .Select(x => new { Cluster = x.Key, AvgPerf = x.Average() })
     604                                .OrderBy(x => x.AvgPerf)
     605                                .Select((c, i) => new { Cluster = c.Cluster, Rank = i })
     606                                .ToDictionary(x => x.Cluster, x => x.Rank);
     607            for (var i = 0; i < clusters.Length; i++) {
     608              var resultName = "Rank." + indexMap.GetBySecond(i) + "@" + ((target - 1) * 100) + "%";
     609              instance.Results[resultName] = new IntValue(dict[indexMap.GetBySecond(i)] < int.MaxValue ? ranks[clusters[i]] : 6);
    562610            }
    563611          }
     
    576624      } finally { progress.Finish(); ProblemInstances.UpdateOfRunsInProgress = false; }
    577625      UpdateInstanceProjection();
     626      UpdateSuggestions();
    578627    }
    579628
    580629    private void UpdateSuggestions() {
    581630      if (Problem == null) return;
     631      var piDistances = GetProblemDistances();
     632      var maxDistance = piDistances.Max();
     633      // Weighted combination of algorithm performances using distance-based exponentially falling weights
     634      // Scale distances by maxDistance
     635      // Parameter to influence dampening factor
     636      // Algorithm performances are given in expected run time
     637      // Using convergence graphs up to maximum evaluations effort
     638      // Care has to be taken if not every algorithm has been executed on every problem instance
    582639      var instances = new SortedList<double, IAlgorithm>();
    583640      foreach (var relevantRuns in knowledgeBase.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
     
    608665    }
    609666
     667    private DoubleMatrix GetProblemDistances() {
     668      var matrix = new DoubleMatrix(ProblemInstances.Count, ProblemInstances.Count);
     669      switch (ProblemInstanceProximity.Value) {
     670        case ProblemInstanceProximityType.MDS:
     671        case ProblemInstanceProximityType.PCA:
     672        case ProblemInstanceProximityType.SOM:
     673          int i = 0, j = 0;
     674          foreach (var a in ProblemInstances) {
     675            double xa, ya;
     676            GetProjectionCoordinates(a, out xa, out ya);
     677            j = 0;
     678            foreach (var b in ProblemInstances) {
     679              double xb, yb;
     680              GetProjectionCoordinates(b, out xb, out yb);
     681              matrix[i, j] = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
     682              j++;
     683            }
     684            i++;
     685          }
     686          break;
     687        case ProblemInstanceProximityType.FeatureSpace:
     688          int k = 0, l = 0;
     689          var features = GetProblemCharacteristics();
     690          foreach (var a in ProblemInstances) {
     691            l = 0;
     692            var fa = features[a];
     693            foreach (var b in ProblemInstances) {
     694              var sum = features[b].Select((t, f) => (fa[f] - t) * (fa[f] - t)).Sum();
     695              matrix[k, l] = Math.Sqrt(sum);
     696              l++;
     697            }
     698            k++;
     699          }
     700          break;
     701        default: throw new InvalidOperationException(string.Format("Unkonwn proximity type {0}", ProblemInstanceProximity.Value));
     702      }
     703      return matrix;
     704    }
     705
     706    private void GetProjectionCoordinates(IRun problemInstance, out double x, out double y) {
     707      x = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".X"]).Value;
     708      y = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".Y"]).Value;
     709    }
     710
    610711    public event EventHandler<EventArgs<IProgress>> DownloadStarted;
    611712    private void OnDownloadStarted(IProgress progress) {
     
    619720      if (handler != null) handler(this, new EventArgs<IAlgorithm>(instance));
    620721    }
     722
     723    // implement further classes and methods
     724    private static SortedList<double, int> Ckmeans1dClusters(double[] estimations, int k, out int[] clusterValues) {
     725      int nPoints = estimations.Length;
     726      var distinct = estimations.Distinct().OrderBy(x => x).ToArray();
     727      var max = distinct.Max();
     728      if (distinct.Length <= k) {
     729        var dict = distinct.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Value, y => y.Index);
     730        for (int i = distinct.Length; i < k; i++)
     731          dict.Add(max + i - distinct.Length + 1, i);
     732
     733        clusterValues = new int[nPoints];
     734        for (int i = 0; i < nPoints; i++)
     735          if (!dict.ContainsKey(estimations[i])) clusterValues[i] = 0;
     736          else clusterValues[i] = dict[estimations[i]];
     737
     738        return new SortedList<double, int>(dict);
     739      }
     740
     741      var n = distinct.Length;
     742      var D = new double[n, k];
     743      var B = new int[n, k];
     744
     745      for (int m = 0; m < k; m++) {
     746        for (int j = m; j <= n - k + m; j++) {
     747          if (m == 0)
     748            D[j, m] = SumOfSquaredDistances(distinct, 0, j + 1);
     749          else {
     750            var minD = double.MaxValue;
     751            var minI = 0;
     752            for (int i = 1; i <= j; i++) {
     753              var d = D[i - 1, m - 1] + SumOfSquaredDistances(distinct, i, j + 1);
     754              if (d < minD) {
     755                minD = d;
     756                minI = i;
     757              }
     758            }
     759            D[j, m] = minD;
     760            B[j, m] = minI;
     761          }
     762        }
     763      }
     764
     765      var centers = new SortedList<double, int>();
     766      var upper = B[n - 1, k - 1];
     767      var c = Mean(distinct, upper, n);
     768      centers.Add(c, k - 1);
     769      for (int i = k - 2; i >= 0; i--) {
     770        var lower = B[upper - 1, i];
     771        var c2 = Mean(distinct, lower, upper);
     772        centers.Add(c2, i);
     773        upper = lower;
     774      }
     775
     776      clusterValues = new int[nPoints];
     777      for (int i = 0; i < estimations.Length; i++) {
     778        clusterValues[i] = centers.MinItems(x => Math.Abs(estimations[i] - x.Key)).First().Value;
     779      }
     780
     781      return centers;
     782    }
     783
     784    private static double SumOfSquaredDistances(double[] x, int start, int end) {
     785      if (start == end) throw new InvalidOperationException();
     786      if (start + 1 == end) return 0.0;
     787      double mean = 0.0;
     788      for (int i = start; i < end; i++) {
     789        mean += x[i];
     790      }
     791      mean /= (end - start);
     792      var sum = 0.0;
     793      for (int i = start; i < end; i++) {
     794        sum += (x[i] - mean) * (x[i] - mean);
     795      }
     796      return sum;
     797    }
     798
     799    private static double Mean(double[] x, int start, int end) {
     800      if (start == end) throw new InvalidOperationException();
     801      double mean = 0.0;
     802      for (int i = start; i < end; i++) {
     803        mean += x[i];
     804      }
     805      mean /= (end - start);
     806      return mean;
     807    }
    621808  }
    622809}
Note: See TracChangeset for help on using the changeset viewer.