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

Timestamp:

04/24/16 10:03:52 (8 years ago)

Author:

abeham

Message:

#2457: worked on performance modeling

Location:

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3

Files:

• Enums.cs (modified) (1 diff)
• HeuristicLab.OptimizationExpertSystem.Common-3.3.csproj (modified) (1 diff)
• Interfaces (added)
• Interfaces/IAlgorithmInstanceRecommender.cs (moved) (moved from branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/IAlgorithmInstanceRecommender.cs) (1 diff)
• Interfaces/IRecommendationModel.cs (added)
• KnowledgeCenter.cs (modified) (16 diffs)
• Recommenders (added)
• Recommenders/DistanceWeightedRecommender.cs (moved) (moved from branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/DistanceWeightedRecommender.cs) (4 diffs)
• Recommenders/FixedRankModel.cs (added)
• Recommenders/KNearestNeighborModel.cs (added)
• Recommenders/KNearestNeighborRecommender.cs (moved) (moved from branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KNearestNeighborRecommender.cs) (4 diffs)
• Recommenders/OverallBestRecommender.cs (moved) (moved from branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/OverallBestRecommender.cs) (5 diffs)

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

@@ -158 +158 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="OverallBestRecommender.cs" />
-    <Compile Include="DistanceWeightedRecommender.cs" />
-    <Compile Include="IAlgorithmInstanceRecommender.cs" />
-    <Compile Include="KNearestNeighborRecommender.cs" />
+    <Compile Include="Interfaces\IRecommendationModel.cs" />
+    <Compile Include="Recommenders\KNearestNeighborModel.cs" />
+    <Compile Include="Recommenders\OverallBestRecommender.cs" />
+    <Compile Include="Recommenders\DistanceWeightedRecommender.cs" />
+    <Compile Include="Interfaces\IAlgorithmInstanceRecommender.cs" />
+    <Compile Include="Recommenders\KNearestNeighborRecommender.cs" />
     <Compile Include="KnowledgeCenter.cs" />
     <Compile Include="Plugin.cs" />
     <Compile Include="Enums.cs" />
+    <Compile Include="Recommenders\FixedRankModel.cs" />
     <None Include="Properties\AssemblyInfo.cs.frame" />
     <Compile Include="ProblemCharacteristicAnalysis\CharacteristicCalculator.cs" />

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Interfaces/IAlgorithmInstanceRecommender.cs

@@ -20 +20 @@
 #endregion
 
-using HeuristicLab.Common;
-using HeuristicLab.Optimization;
-using System.Collections.Generic;
+using HeuristicLab.Core;
 
 namespace HeuristicLab.OptimizationExpertSystem.Common {
-  public interface IAlgorithmInstanceRecommender : IContent {
-    IEnumerable<IAlgorithm> GetRanking();
+  public interface IAlgorithmInstanceRecommender : IParameterizedItem {
+    IRecommendationModel TrainModel(KnowledgeCenter kc, string[] characteristics);
   }
 }

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

@@ -96 +96 @@
     }
 
-    private readonly CheckedItemList<StringValue> problemCharacteristics;
-    private readonly ReadOnlyCheckedItemList<StringValue> readonlyProblemCharacteristics; 
-    public ReadOnlyCheckedItemList<StringValue> ProblemCharacteristics {
-      get { return readonlyProblemCharacteristics; }
-    }
-
-    private IAlgorithmInstanceRecommender algorithmInstanceRecommender;
-    public IAlgorithmInstanceRecommender AlgorithmInstanceRecommender {
-      get { return algorithmInstanceRecommender; }
-      set { algorithmInstanceRecommender = value; }
+    private IRecommendationModel recommendationModel;
+    public IRecommendationModel RecommendationModel {
+      get { return recommendationModel; }
+      set {
+        if (recommendationModel == value) return;
+        recommendationModel = value;
+        OnRecommenderModelChanged();
+      }
     }
 
@@ -135 +133 @@
       readonlyAlgorithmInstances = algorithmInstances.AsReadOnly();
       problemInstances = new RunCollection();
-      problemCharacteristics = new CheckedItemList<StringValue>();
-      readonlyProblemCharacteristics = problemCharacteristics.AsReadOnly();
-      algorithmInstanceRecommender = new OverallBestRecommender(this);
+      recommendationModel = FixedRankModel.GetEmpty();
       problem = new SingleObjectiveOKBProblem();
       algorithmId2RunMapping = new BidirectionalLookup<long, IRun>();
@@ -167 +163 @@
       knowledgeBase.ItemsAdded += InformationChanged;
       knowledgeBase.ItemsRemoved += InformationChanged;
-      problemCharacteristics.ItemsAdded += CharacteristicChanged;
-      problemCharacteristics.ItemsReplaced += CharacteristicChanged;
-      problemCharacteristics.ItemsRemoved += CharacteristicChanged;
-      problemCharacteristics.CollectionReset += CharacteristicChanged;
-      problemCharacteristics.CheckedItemsChanged += CharacteristicChanged;
     }
 
     private void MaximumEvaluationsOnValueChanged(object sender, EventArgs eventArgs) {
-      UpdateSuggestions();
+
     }
 
     private void MinimumTargetOnValueChanged(object sender, EventArgs e) {
-      UpdateSuggestions();
+
     }
 
@@ -192 +183 @@
       var runCollection = sender as RunCollection;
       if (runCollection != null && runCollection.UpdateOfRunsInProgress) return;
-      UpdateSuggestions();
-    }
-
-    private void CharacteristicChanged(object sender, EventArgs e) {
-      if (SuppressEvents) return;
-      UpdateInstanceProjection();
     }
     
@@ -205 +190 @@
     }
 
-    public void UpdateInstanceProjection() {
-      if (ProblemCharacteristics.Count == 0) return;
-
-      var instances = GetProblemCharacteristics();
+    public void UpdateInstanceProjection(string[] characteristics) {
+      if (characteristics.Length == 0) return;
+
+      var instances = GetProblemCharacteristics(characteristics);
 
       var key2Idx = new BidirectionalDictionary<IRun, int>();
@@ -227 +212 @@
       #endregion
       #region PCA
-      var ds = new double[instances.Count, ProblemCharacteristics.CheckedItems.Count()];
+      var ds = new double[instances.Count, characteristics.Length];
       foreach (var instance in instances) {
         var arr = instance.Value;
@@ -240 +225 @@
       #endregion
       #region SOM
-      var features = new DoubleMatrix(ProblemCharacteristics.CheckedItems.Count(), instances.Count);
+      var features = new DoubleMatrix(characteristics.Length, instances.Count);
       foreach (var instance in instances) {
         var arr = instance.Value;
@@ -283 +268 @@
     }
 
-    private Dictionary<IRun, double[]> GetProblemCharacteristics() {
+    public Dictionary<IRun, double[]> GetProblemCharacteristics(string[] characteristics) {
       var instances = new Dictionary<IRun, double[]>();
-      var values = new List<double>[ProblemCharacteristics.CheckedItems.Count()];
+      var values = new List<double>[characteristics.Length];
       foreach (var run in ProblemInstances) {
         var f = 0;
-        instances[run] = new double[ProblemCharacteristics.CheckedItems.Count()];
-        foreach (var c in ProblemCharacteristics.CheckedItems.Select(x => x.Value.Value)) {
+        instances[run] = new double[characteristics.Length];
+        foreach (var c in characteristics) {
           if (values[f] == null) values[f] = new List<double>(ProblemInstances.Count);
           IItem item;
@@ -514 +499 @@
             if (alg != null) {
               lock (algorithmId2AlgorithmInstanceMapping) {
+                algorithmInstances.Add(alg);
                 algorithmId2AlgorithmInstanceMapping.Add(algInst.Id, alg);
                 progress.Status = string.Format("Downloaded algorithm {0} (okb-id: {1})...", algInst.Name, algInst.Id);
@@ -549 +535 @@
 
         progress.Status = "Finishing...";
-        var algInstRunDict = runList.Where(x => x.Parameters.ContainsKey("Problem Name") && x.Parameters["Problem Name"] is StringValue)
-                                          .GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)
-                                          .ToDictionary(x => x.Key, x => x.GroupBy(y => ((StringValue)y.Parameters["Algorithm Name"]).Value)
-                                                                                  .ToDictionary(y => y.Key, y => y.ToList()));
-
-        foreach (var instance in ProblemInstances) {
-          IItem probNameParam;
-          if (!instance.Parameters.TryGetValue("Problem Name", out probNameParam)) continue;
-
-          var probInstanceName = ((StringValue)probNameParam).Value;
-          var maximization = ((BoolValue)instance.Parameters["Maximization"]).Value;
-          
-          IItem bkParam;
-          if (!instance.Parameters.TryGetValue("BestKnownQuality", out bkParam) || !(bkParam is DoubleValue)) {
-            Dictionary<string, List<IRun>> algRuns;
-            if (!algInstRunDict.TryGetValue(probInstanceName, out algRuns)) continue;
-            var list = algRuns.SelectMany(x => x.Value)
-                              .Where(x => x.Results.ContainsKey("QualityPerEvaluations"))
-                              .Select(x => ((IndexedDataTable<double>)x.Results["QualityPerEvaluations"]).Rows.First().Values.Last().Item2);
-            bkParam = new DoubleValue(maximization ? list.Max() : list.Min());
-            instance.Parameters["BestKnownQuality"] = bkParam;
-          } else bkParam = instance.Parameters["BestKnownQuality"];
-
-          var bkQuality = ((DoubleValue)bkParam).Value;
-
-          if (!algInstRunDict.ContainsKey(probInstanceName)) continue;
-          // 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);
-              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);
-            }
-          }
-        }
-        try {
-          SuppressEvents = true;
-          problemCharacteristics.Replace(characteristics.Select(x => new StringValue(x)));
-          foreach (var pc in problemCharacteristics.Where(x => !x.Value.StartsWith("Characteristic.")))
-            problemCharacteristics.SetItemCheckedState(pc, false);
-        } finally { SuppressEvents = false; }
+        
         try {
           KnowledgeBase.UpdateOfRunsInProgress = true;
@@ -612 +541 @@
           KnowledgeBase.AddRange(runList);
         } finally { KnowledgeBase.UpdateOfRunsInProgress = false; }
+
+        var algInstRunDict = runList.Where(x => x.Parameters.ContainsKey("Problem Name") && x.Parameters["Problem Name"] is StringValue)
+                                          .GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)
+                                          .ToDictionary(x => x.Key, x => x.GroupBy(y => ((StringValue)y.Parameters["Algorithm Name"]).Value)
+                                                                                  .ToDictionary(y => y.Key, y => y.ToList()));
+
+        // set best-known quality to best-found in case it is not known
+        foreach (var kvp in algInstRunDict) {
+          var prob = ProblemInstances.SingleOrDefault(x => ((StringValue)x.Parameters["Problem Name"]).Value == kvp.Key);
+          if (prob == null) continue;
+          var maximization = ((BoolValue)prob.Parameters["Maximization"]).Value;
+
+          IItem bkParam;
+          if (!prob.Parameters.TryGetValue("BestKnownQuality", out bkParam) || !(bkParam is DoubleValue)) {
+            var list = kvp.Value.SelectMany(x => x.Value)
+              .Where(x => x.Results.ContainsKey("QualityPerEvaluations"))
+              .Select(x => ((IndexedDataTable<double>)x.Results["QualityPerEvaluations"]).Rows.First().Values.Last().Item2);
+            if (!list.Any()) continue;
+            bkParam = new DoubleValue(maximization ? list.Max() : list.Min());
+            prob.Parameters["BestKnownQuality"] = bkParam;
+          }
+        }
+
+        // add algorithm instance ranks as features to the problem instances for a range of targets
+        foreach (var target in new[] {1, 1.01, 1.05, 1.1, 1.2, 1.5}) {
+          var cls = GetPerformanceClasses(target, 5);
+          foreach (var kvp in cls) {
+            var prob = kvp.Key;
+            foreach (var kvp2 in kvp.Value) {
+              var resultName = "Rank." + algorithmId2AlgorithmInstanceMapping.GetByFirst(kvp2.Key) + "@" + ((target - 1) * 100) + "%";
+              prob.Results[resultName] = new IntValue(kvp2.Value);
+            }
+          }
+        }
       } finally { progress.Finish(); ProblemInstances.UpdateOfRunsInProgress = false; }
-      UpdateInstanceProjection();
-      UpdateSuggestions();
-    }
-
-    public void UpdateSuggestions() {
-      // TODO: Maintain a separate list of suggested instances
-      // TODO: expose expected expected run time
-      algorithmInstances.Replace(AlgorithmInstanceRecommender.GetRanking());
+      UpdateInstanceProjection(ProblemInstances.ResultNames.Where(x => x.StartsWith("Characteristic.")).ToArray());
     }
 
     public Dictionary<IAlgorithm, double> GetAlgorithmPerformance(IRun problemInstance) {
       if (!problemInstance.Parameters.ContainsKey("BestKnownQuality")) return new Dictionary<IAlgorithm, double>();
-      var target = GetTarget(((DoubleValue)problemInstance.Parameters["BestKnownQuality"]).Value);
+      var target = GetTarget(((DoubleValue)problemInstance.Parameters["BestKnownQuality"]).Value, Maximization);
       return knowledgeBase.Where(x => ((StringValue)x.Parameters["Problem Name"]).Value == ((StringValue)problemInstance.Parameters["Problem Name"]).Value)
                           .GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
@@ -636 +592 @@
     }
 
-    public IEnumerable<IRegressionProblem> GetDataAnalysisProblem(double target) {
+    public IEnumerable<IRegressionProblem> GetRegressionProblemPerAlgorithmInstance(double target, string[] characteristics) {
       if (Problem == null) yield break;
-      var characteristics = GetProblemCharacteristics();
+      var features = GetProblemCharacteristics(characteristics);
       // TODO: knowledgebase only stores problem name as a string
       // this doesn't work if there are two equally named problem instances
@@ -647 +603 @@
         var ds = new ModifiableDataset();
         ds.AddVariable("Problem Name", new List<string>());
-        foreach (var pc in ProblemCharacteristics.CheckedItems)
-          ds.AddVariable(pc.Value.Value, new List<double>());
+        foreach (var pc in characteristics)
+          ds.AddVariable(pc, new List<double>());
         ds.AddVariable("ERT", new List<double>());
-        var max = Maximization;
         foreach (var pr in problemRuns) {
           var prob = problemMap[pr.Key];
-          var features = characteristics[prob];
+          var f = features[prob];
+          var max = ((BoolValue)prob.Parameters["Maximization"]).Value;
           var bkq = ((DoubleValue)prob.Parameters["BestKnownQuality"]).Value;
-          var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerEvaluations", GetTarget(bkq), max).ExpectedRuntime;
+          var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime;
           if (double.IsNaN(ert)) ert = int.MaxValue;
-          ds.AddRow(new object[] { pr.Key }.Concat(features.Cast<object>()).Concat(new object[] { ert }));
-        }
-        var datAnalysisData = new RegressionProblemData(ds, ProblemCharacteristics.CheckedItems.Select(x => x.Value.Value), "ERT");
+          ds.AddRow(new object[] { pr.Key }.Concat(f.Cast<object>()).Concat(new object[] { ert }));
+        }
+        var datAnalysisData = new RegressionProblemData(ds, characteristics, "ERT");
         var result = new RegressionProblem() {
           Name = algorithmId2AlgorithmInstanceMapping.GetByFirst(relevantRuns.Key).Name
@@ -668 +624 @@
     }
 
-    private double GetTarget(double bestKnownQuality) {
-      return bestKnownQuality * (Maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value));
-    }
-
-    public Dictionary<IRun, double> GetProblemDistances(ProblemInstanceProximityType proximityType) {
-      var result = new Dictionary<IRun, double>(); 
+    public IEnumerable<IClassificationProblem> GetClassificationProblemPerAlgorithmInstance(double target, string[] characteristics) {
+      if (Problem == null) yield break;
+
+      var classes = GetPerformanceClasses(target, 5);
+      var features = GetProblemCharacteristics(characteristics);
+
+      foreach (var alg in AlgorithmInstances) {
+        var ds = new ModifiableDataset();
+        ds.AddVariable("Problem Name", new List<string>());
+        foreach (var pc in characteristics)
+          ds.AddVariable(pc, new List<double>());
+        ds.AddVariable("Class", new List<double>());
+
+        foreach (var c in classes) {
+          int cls;
+          if (c.Value.TryGetValue(algorithmId2AlgorithmInstanceMapping.GetBySecond(alg), out cls)) {
+            ds.AddRow(new object[] { ((StringValue)c.Key.Parameters["Problem Name"]).Value }
+              .Concat(features[c.Key].Cast<object>()).Concat(new object[] { cls }));
+          }
+        }
+        var datAnalysisData = new ClassificationProblemData(ds, characteristics, "Class");
+        var result = new ClassificationProblem() {
+          Name = alg.Name
+        };
+        result.ProblemDataParameter.Value = datAnalysisData;
+        yield return result;
+      }
+    }
+
+    public Dictionary<IRun, double> GetProblemDistances(string[] characteristics) {
+      var result = new Dictionary<IRun, double>();
       var currentInstance = problemId2ProblemInstanceMapping.GetByFirst(Problem.ProblemId);
-      switch (proximityType) {
-        case ProblemInstanceProximityType.MDS:
-        case ProblemInstanceProximityType.PCA:
-        case ProblemInstanceProximityType.SOM:
-          double xa, ya;
-          GetProjectionCoordinates(currentInstance, proximityType, out xa, out ya);
-          foreach (var b in ProblemInstances) {
-            if (b == currentInstance) continue;
-            double xb, yb;
-            GetProjectionCoordinates(b, proximityType, out xb, out yb);
-            var d = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
-            result[b] = d;
-          }
-          break;
-        case ProblemInstanceProximityType.FeatureSpace:
-          var features = GetProblemCharacteristics();
-          var cF = features[currentInstance];
-          foreach (var b in ProblemInstances) {
-            if (b == currentInstance) continue;
-            var sum = features[b].Select((t, f) => (cF[f] - t) * (cF[f] - t)).Sum();
-            result[b] = Math.Sqrt(sum);
-          }
-          break;
-        default: throw new InvalidOperationException(string.Format("Unkonwn proximity type {0}", proximityType));
+      var features = GetProblemCharacteristics(characteristics);
+      var cF = features[currentInstance];
+      foreach (var b in ProblemInstances) {
+        if (b == currentInstance) continue;
+        var sum = features[b].Select((t, f) => (cF[f] - t) * (cF[f] - t)).Sum();
+        result[b] = Math.Sqrt(sum);
       }
       return result;
     }
 
-    private void GetProjectionCoordinates(IRun problemInstance, ProblemInstanceProximityType proximityType, out double x, out double y) {
-      x = ((DoubleValue)problemInstance.Results["Projection." + proximityType + ".X"]).Value;
-      y = ((DoubleValue)problemInstance.Results["Projection." + proximityType + ".Y"]).Value;
-      if (proximityType == ProblemInstanceProximityType.SOM) {
-        x = Math.Floor(x);
-        y = Math.Floor(y);
-      }
+    public Dictionary<IRun, Dictionary<long, int>> GetPerformanceClasses(double target, int nClasses) {
+      var result = new Dictionary<IRun, Dictionary<long, int>>();
+      var problemMap = ProblemInstances.Select(x => new { Key = ((StringValue)x.Parameters["Problem Name"]).Value, Value = x })
+                                       .ToDictionary(x => x.Key, x => x.Value);
+      foreach (var pr in KnowledgeBase.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value).ToList()) {
+        var bkq = ((DoubleValue)problemMap[pr.Key].Parameters["BestKnownQuality"]).Value;
+        var max = ((BoolValue)problemMap[pr.Key].Parameters["Maximization"]).Value;
+
+        result[problemMap[pr.Key]] = new Dictionary<long, int>();
+
+        var indexMap = new BidirectionalDictionary<long, int>();
+        var perf = new Dictionary<long, double>();
+        var idx = 0;
+        foreach (var kvp in pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
+          var ert = ExpectedRuntimeHelper.CalculateErt(kvp.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime;
+          if (double.IsNaN(ert)) {
+            // algorithm can't solve that instance with the given target
+            // these are put into their own additional class
+            result[problemMap[pr.Key]][kvp.Key] = nClasses;
+            continue;
+          }
+          indexMap.Add(kvp.Key, idx);
+          perf[kvp.Key] = Math.Log10(ert);
+          idx++;
+        }
+        if (perf.Count == 0) continue;
+        
+        var points = perf.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value).ToArray();
+        int[] clusters;
+        Ckmeans1dClusters(points, nClasses, out clusters);
+        var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = perf[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++)
+          result[problemMap[pr.Key]][indexMap.GetBySecond(i)] = ranks[clusters[i]];
+      }
+      return result;
+    }
+
+    private double GetTarget(double bestKnownQuality, bool maximization) {
+      return bestKnownQuality * (maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value));
     }
 
@@ -722 +722 @@
       var handler = AlgorithmInstanceStarted;
       if (handler != null) handler(this, new EventArgs<IAlgorithm>(instance));
+    }
+
+    public event EventHandler RecommendationModelChanged;
+    private void OnRecommenderModelChanged() {
+      var handler = RecommendationModelChanged;
+      if (handler != null) handler(this, EventArgs.Empty);
     }
 
@@ -809 +815 @@
       return mean;
     }
+
+    public IEnumerable<Tuple<IAlgorithm, double>> GetAlgorithmInstanceRanking() {
+      return RecommendationModel.GetRanking(this);
+    }
   }
 }

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

@@ -35 +35 @@
   [StorableClass]
   public class DistanceWeightedRecommender : ParameterizedNamedItem, IAlgorithmInstanceRecommender {
-    private KnowledgeCenter okc;
-
-    private IFixedValueParameter<EnumValue<ProblemInstanceProximityType>> ProximityTypeParameter {
-      get { return (IFixedValueParameter<EnumValue<ProblemInstanceProximityType>>)Parameters["ProximityType"]; }
-    }
 
     private IFixedValueParameter<DoubleValue> NeighborhoodFactorParameter {
       get { return (IFixedValueParameter<DoubleValue>)Parameters["NeighborhoodFactor"]; }
-    }
-
-    public ProblemInstanceProximityType ProximityType {
-      get { return ProximityTypeParameter.Value.Value; }
-      set { ProximityTypeParameter.Value.Value = value; }
     }
 
@@ -59 +49 @@
     private DistanceWeightedRecommender(DistanceWeightedRecommender original, Cloner cloner)
       : base(original, cloner) { }
-    public DistanceWeightedRecommender(KnowledgeCenter okc) {
-      this.okc = okc;
-      Parameters.Add(new FixedValueParameter<EnumValue<ProblemInstanceProximityType>>("ProximityType", "The type of neighbor proximity.", new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace)));
+    public DistanceWeightedRecommender() {
       Parameters.Add(new FixedValueParameter<DoubleValue>("NeighborhoodFactor", "Penalize neighbors that are far away.", new DoubleValue(5)));
     }
@@ -69 +57 @@
     }
 
-    public IEnumerable<IAlgorithm> GetRanking() {
-      if (okc.Problem.ProblemId == -1) yield break;
-
-      var piDistances = okc.GetProblemDistances(ProximityType);
+    public IRecommendationModel TrainModel(KnowledgeCenter okc, string[] characteristics) {
+      var piDistances = okc.GetProblemDistances(characteristics);
       var maxDist = piDistances.Max(x => x.Value);
       var instances = new SortedList<double, IAlgorithm>();
@@ -109 +95 @@
           avgERT += new System.Random().NextDouble();
         }
-        instances.Add(avgERT, algorithm);
+        instances.Add(avgERT, (IAlgorithm)algorithm.Clone());
       }
 
-      foreach (var alg in instances.Select(x => (IAlgorithm)x.Value.Clone()))
-        yield return alg;
+      return new FixedRankModel(instances.Select(x => Tuple.Create(x.Value, x.Key)));
     }
   }

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

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
-using System.Linq;
 
 namespace HeuristicLab.OptimizationExpertSystem.Common {
@@ -33 +30 @@
   [StorableClass]
   public sealed class KNearestNeighborRecommender : ParameterizedNamedItem, IAlgorithmInstanceRecommender {
-    private KnowledgeCenter okc;
-
-    private IFixedValueParameter<EnumValue<ProblemInstanceProximityType>> ProximityTypeParameter {
-      get { return (IFixedValueParameter<EnumValue<ProblemInstanceProximityType>>)Parameters["ProximityType"]; }
-    }
-
-    public ProblemInstanceProximityType ProximityType {
-      get { return ProximityTypeParameter.Value.Value; }
-      set { ProximityTypeParameter.Value.Value = value; }
-    }
-
+    
     private IFixedValueParameter<IntValue> KParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters["K"]; }
@@ -52 +39 @@
     private KNearestNeighborRecommender(KNearestNeighborRecommender original, Cloner cloner)
       : base(original, cloner) { }
-    public KNearestNeighborRecommender(KnowledgeCenter okc) {
-      this.okc = okc;
-      Parameters.Add(new FixedValueParameter<EnumValue<ProblemInstanceProximityType>>("ProximityType", "The type of neighbor proximity.", new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace)));
+    public KNearestNeighborRecommender() {
       Parameters.Add(new FixedValueParameter<IntValue>("K", "The number of nearest neighbors to consider.", new IntValue(5)));
     }
@@ -62 +47 @@
     }
 
-    public IEnumerable<IAlgorithm> GetRanking() {
-      if (okc.Problem.ProblemId == -1) yield break;
-
-      var distances = okc.GetProblemDistances(ProximityType);
-      var K = KParameter.Value.Value;
-      var performances = new Dictionary<IAlgorithm, List<double>>();
-      for (var k = 0; k < K; k++) {
-        if (distances.Count == 0) break;
-        var min = distances.MinItems(x => x.Value).First();
-        // lookup algorithm performances in min
-        var perfs = okc.GetAlgorithmPerformance(min.Key);
-        if (perfs.Count == 0) {
-          k--;
-          continue;
-        }
-        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);
-        }
-        distances.Remove(min.Key);
-      }
-      foreach (var alg in performances.Select(x => new { Alg = x.Key, Perf = x.Value.Average() })
-                         .OrderBy(x => x.Perf)
-                         .Select(x => x.Alg))
-        yield return alg;
+    public IRecommendationModel TrainModel(KnowledgeCenter kc, string[] characteristics) {
+      return new KNearestNeighborModel(KParameter.Value.Value, characteristics);
     }
   }

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

@@ -35 +35 @@
   [StorableClass]
   public class OverallBestRecommender : ParameterizedNamedItem, IAlgorithmInstanceRecommender {
-    private KnowledgeCenter okc;
-
-    private IFixedValueParameter<EnumValue<ProblemInstanceProximityType>> ProximityTypeParameter {
-      get { return (IFixedValueParameter<EnumValue<ProblemInstanceProximityType>>)Parameters["ProximityType"]; }
-    }
 
     private IFixedValueParameter<DoubleValue> NeighborhoodFactorParameter {
       get { return (IFixedValueParameter<DoubleValue>)Parameters["NeighborhoodFactor"]; }
-    }
-
-    public ProblemInstanceProximityType ProximityType {
-      get { return ProximityTypeParameter.Value.Value; }
-      set { ProximityTypeParameter.Value.Value = value; }
     }
 
@@ -59 +49 @@
     private OverallBestRecommender(OverallBestRecommender original, Cloner cloner)
       : base(original, cloner) { }
-    public OverallBestRecommender(KnowledgeCenter okc) {
-      this.okc = okc;
-      Parameters.Add(new FixedValueParameter<EnumValue<ProblemInstanceProximityType>>("ProximityType", "The type of neighbor proximity.", new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace)));
+    public OverallBestRecommender() {
       Parameters.Add(new FixedValueParameter<DoubleValue>("NeighborhoodFactor", "Penalize neighbors that are far away.", new DoubleValue(5)));
     }
@@ -69 +57 @@
     }
 
-    public IEnumerable<IAlgorithm> GetRanking() {
-      if (okc.Problem.ProblemId == -1) yield break;
-
+    public IRecommendationModel TrainModel(KnowledgeCenter kc, string[] characteristics) {
       var instances = new List<Tuple<IAlgorithm, double>>();
-      foreach (var relevantRuns in okc.GetKnowledgeBaseByAlgorithm()) {
+      foreach (var relevantRuns in kc.GetKnowledgeBaseByAlgorithm()) {
         var algorithm = relevantRuns.Key;
         var pis = relevantRuns.Value.Select(x => ((StringValue)x.Parameters["Problem Name"]).Value).Distinct()
-                              .Select(x => Tuple.Create(x, okc.ProblemInstances.SingleOrDefault(y => ((StringValue)y.Parameters["Problem Name"]).Value == x)))
+                              .Select(x => Tuple.Create(x, kc.ProblemInstances.SingleOrDefault(y => ((StringValue)y.Parameters["Problem Name"]).Value == x)))
                               .Where(x => x.Item2 != null)
                               .Select(x => Tuple.Create(x.Item1, ((DoubleValue)x.Item2.Parameters["BestKnownQuality"]).Value))
@@ -84 +70 @@
         foreach (var problemRuns in relevantRuns.Value.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)) {
           var bkq = pis[problemRuns.Key];
-          var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", (okc.Maximization ? (1 - okc.MinimumTarget.Value) : (1 + okc.MinimumTarget.Value)) * bkq, okc.Maximization).ExpectedRuntime;
+          var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", (kc.Maximization ? (1 - kc.MinimumTarget.Value) : (1 + kc.MinimumTarget.Value)) * bkq, kc.Maximization).ExpectedRuntime;
           if (double.IsNaN(ert)) ert = int.MaxValue;
           avgERT += ert;
@@ -90 +76 @@
         }
         avgERT /= count;
-        instances.Add(Tuple.Create(algorithm, avgERT));
+        instances.Add(Tuple.Create((IAlgorithm)algorithm.Clone(), avgERT));
       }
 
-      foreach (var alg in instances.OrderBy(x => x.Item2).Select(x => (IAlgorithm)x.Item1.Clone()))
-        yield return alg;
+      return new FixedRankModel(instances.OrderBy(x => x.Item2));
     }
   }