Changeset 13774 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3

Timestamp:

04/19/16 12:40:40 (8 years ago)

Author:

abeham

Message:

#2457: worked on recommendation algorithms

Location:

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3

Files:

• DistanceWeightedRecommender.cs (added)
• HeuristicLab.OptimizationExpertSystem.Common-3.3.csproj (modified) (3 diffs)
• IAlgorithmInstanceRecommender.cs (added)
• KNearestNeighborRecommender.cs (added)
• KnowledgeCenter.cs (modified) (11 diffs)
• OverallBestRecommender.cs (added)

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

@@ -78 +78 @@
       <Private>False</Private>
     </Reference>
+    <Reference Include="HeuristicLab.Algorithms.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Algorithms.DataAnalysis-3.4.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
     <Reference Include="HeuristicLab.Clients.OKB-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
       <SpecificVersion>False</SpecificVersion>
@@ -120 +125 @@
     <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
+    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis-3.4.dll</HintPath>
       <Private>False</Private>
     </Reference>
@@ -148 +158 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="OverallBestRecommender.cs" />
+    <Compile Include="DistanceWeightedRecommender.cs" />
+    <Compile Include="IAlgorithmInstanceRecommender.cs" />
+    <Compile Include="KNearestNeighborRecommender.cs" />
     <Compile Include="KnowledgeCenter.cs" />
     <Compile Include="Plugin.cs" />

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

@@ -30 +30 @@
 using HeuristicLab.Optimization;
 using HeuristicLab.Persistence.Default.Xml;
+using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Random;
 using System;
@@ -50 +51 @@
     public string Filename { get; set; }
 
-    public static new Image StaticItemImage {
+    public static Image StaticItemImage {
       get { return VSImageLibrary.Library; }
     }
@@ -84 +85 @@
     }
 
-    private readonly ItemList<IAlgorithm> suggestedInstances;
-    private readonly ReadOnlyItemList<IAlgorithm> readOnlySuggestedInstances;
-    public ReadOnlyItemList<IAlgorithm> SuggestedInstances {
-      get { return readOnlySuggestedInstances; }
+    private readonly ItemList<IAlgorithm> algorithmInstances;
+    private readonly ReadOnlyItemList<IAlgorithm> readonlyAlgorithmInstances;
+    public ReadOnlyItemList<IAlgorithm> AlgorithmInstances {
+      get { return readonlyAlgorithmInstances; }
     }
 
@@ -101 +102 @@
     }
 
-    private readonly EnumValue<ProblemInstanceProximityType> problemInstanceProximity;
-    public EnumValue<ProblemInstanceProximityType> ProblemInstanceProximity {
-      get { return problemInstanceProximity; }
-    }
-
-    private readonly DoubleValue problemInstanceNeighborhoodFactor;
-    public DoubleValue ProblemInstanceNeighborhoodFactor {
-      get { return problemInstanceNeighborhoodFactor; }
+    private IAlgorithmInstanceRecommender algorithmInstanceRecommender;
+    public IAlgorithmInstanceRecommender AlgorithmInstanceRecommender {
+      get { return algorithmInstanceRecommender; }
+      set { algorithmInstanceRecommender = value; }
     }
 
@@ -125 +122 @@
     private BidirectionalDictionary<long, IRun> problemId2ProblemInstanceMapping;
     
-    private bool Maximization {
+    public bool Maximization {
       get { return Problem != null && Problem.ProblemId >= 0 && ((IValueParameter<BoolValue>)Problem.MaximizationParameter).Value.Value; }
     }
@@ -135 +132 @@
       seededRuns = new RunCollection();
       knowledgeBase = new RunCollection();
-      suggestedInstances = new ItemList<IAlgorithm>();
-      readOnlySuggestedInstances = suggestedInstances.AsReadOnly();
+      algorithmInstances = new ItemList<IAlgorithm>();
+      readonlyAlgorithmInstances = algorithmInstances.AsReadOnly();
       problemInstances = new RunCollection();
       problemCharacteristics = new CheckedItemList<StringValue>();
-      problemInstanceProximity = new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace);
-      problemInstanceNeighborhoodFactor = new DoubleValue(5);
       readonlyProblemCharacteristics = problemCharacteristics.AsReadOnly();
+      algorithmInstanceRecommender = new OverallBestRecommender(this);
       problem = new SingleObjectiveOKBProblem();
       algorithmId2RunMapping = new BidirectionalLookup<long, IRun>();
@@ -176 +172 @@
       problemCharacteristics.CollectionReset += CharacteristicChanged;
       problemCharacteristics.CheckedItemsChanged += CharacteristicChanged;
-      problemInstanceProximity.ValueChanged += ProblemInstanceProximityChanged;
-      problemInstanceNeighborhoodFactor.ValueChanged += ProblemInstanceProximityChanged;
     }
 
@@ -205 +199 @@
       UpdateInstanceProjection();
     }
-
-    private void ProblemInstanceProximityChanged(object sender, EventArgs e) {
-      UpdateSuggestions();
-    }
-
+    
     public bool IsCurrentInstance(IRun run) {
       if (!problemId2ProblemInstanceMapping.ContainsSecond(run)) return false;
@@ -339 +329 @@
 
     public Task<ResultCollection> StartAlgorithmAsync(int index, CancellationToken cancellation) {
-      var selectedInstance = suggestedInstances[index];
+      var selectedInstance = algorithmInstances[index];
       var algorithmClone = (IAlgorithm)selectedInstance.Clone();
       var problemClone = Problem.CloneProblem() as ISingleObjectiveHeuristicOptimizationProblem;
@@ -627 +617 @@
     }
 
-    private void UpdateSuggestions() {
-      if (Problem == null) return;
-      var piDistances = GetProblemDistances();
-      var maxDist = piDistances.Max(x => x.Value);
-      var instances = new SortedList<double, IAlgorithm>();
+    public void UpdateSuggestions() {
+      // TODO: Maintain a separate list of suggested instances
+      // TODO: expose expected expected run time
+      algorithmInstances.Replace(AlgorithmInstanceRecommender.GetRanking());
+    }
+
+    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);
+      return knowledgeBase.Where(x => ((StringValue)x.Parameters["Problem Name"]).Value == ((StringValue)problemInstance.Parameters["Problem Name"]).Value)
+                          .GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
+                          .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", target, Maximization).ExpectedRuntime);
+    }
+
+    public Dictionary<IAlgorithm, List<IRun>> GetKnowledgeBaseByAlgorithm() {
+      return KnowledgeBase.GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
+                          .ToDictionary(x => x.Key, x => x.ToList());
+    }
+
+    public IEnumerable<IRegressionProblem> GetDataAnalysisProblem(double target) {
+      if (Problem == null) yield break;
+      var characteristics = GetProblemCharacteristics();
+      // TODO: knowledgebase only stores problem name as a string
+      // this doesn't work if there are two equally named problem instances
+      var problemMap = ProblemInstances.Select(x => new { Key = ((StringValue)x.Parameters["Problem Name"]).Value, Value = x })
+                                       .ToDictionary(x => x.Key, x => x.Value);
       foreach (var relevantRuns in knowledgeBase.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
-        var algorithm = algorithmId2AlgorithmInstanceMapping.GetByFirst(relevantRuns.Key);
-        Func<double, double> distFunc = (d) => Math.Exp(ProblemInstanceNeighborhoodFactor.Value * (-d / maxDist));
-        var pis = relevantRuns.Select(x => ((StringValue)x.Parameters["Problem Name"]).Value).Distinct()
-                              .Select(x => Tuple.Create(x, ProblemInstances.SingleOrDefault(y => ((StringValue)y.Parameters["Problem Name"]).Value == x)))
-                              .Where(x => x.Item2 != null)
-                              .Select(x => Tuple.Create(x.Item1, distFunc(piDistances[x.Item2]), ((DoubleValue)x.Item2.Parameters["BestKnownQuality"]).Value))
-                              .ToDictionary(x => x.Item1, x => Tuple.Create(x.Item2, x.Item3));
-        var sumPis = pis.Sum(x => x.Value.Item1);
-        var avgERT = 0.0;
-        foreach (var problemRuns in relevantRuns.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)) {
-          Tuple<double, double> info;
-          if (!pis.TryGetValue(problemRuns.Key, out info)) continue;
-          var convGraph = new List<List<Tuple<double, double>>>();
-          foreach (var run in problemRuns) {
-            var current = new List<Tuple<double, double>>();
-            var performanceGraph = ((IndexedDataTable<double>)run.Results["QualityPerEvaluations"]);
-            current.AddRange(performanceGraph.Rows.First().Values.TakeWhile(v => v.Item1 < MaximumEvaluations.Value));
-            if (current.Count > 0) {
-              current.Add(Tuple.Create((double)MaximumEvaluations.Value, current.Last().Item2));
-              convGraph.Add(current);
-            }
-          }
-          var ert = ExpectedRuntimeHelper.CalculateErt(convGraph, (Maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value)) * info.Item2, Maximization).ExpectedRuntime;
-          if (double.IsNaN(ert)) {
-            ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", (Maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value)) * info.Item2, Maximization).ExpectedRuntime;
-            if (double.IsNaN(ert)) ert = int.MaxValue;
-          }
-          avgERT += info.Item1 * ert;
-        }
-        avgERT /= sumPis;
-        if (instances.ContainsKey(avgERT)) {
-          avgERT += new System.Random().NextDouble();
-        }
-        instances.Add(avgERT, algorithm);
-      }
-
-      var instanceLadder = instances.Select(x => (IAlgorithm)x.Value.Clone()).ToList();
-      suggestedInstances.Replace(instanceLadder);
-    }
-
-    private Dictionary<IRun, double> GetProblemDistances() {
+        var problemRuns = relevantRuns.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value).ToList();
+        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>());
+        ds.AddVariable("ERT", new List<double>());
+        var max = Maximization;
+        foreach (var pr in problemRuns) {
+          var prob = problemMap[pr.Key];
+          var features = characteristics[prob];
+          var bkq = ((DoubleValue)prob.Parameters["BestKnownQuality"]).Value;
+          var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerEvaluations", GetTarget(bkq), 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");
+        var result = new RegressionProblem() {
+          Name = algorithmId2AlgorithmInstanceMapping.GetByFirst(relevantRuns.Key).Name
+        };
+        result.ProblemDataParameter.Value = datAnalysisData;
+        yield return result;
+      }
+    }
+
+    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>(); 
       var currentInstance = problemId2ProblemInstanceMapping.GetByFirst(Problem.ProblemId);
-      switch (ProblemInstanceProximity.Value) {
+      switch (proximityType) {
         case ProblemInstanceProximityType.MDS:
         case ProblemInstanceProximityType.PCA:
         case ProblemInstanceProximityType.SOM:
           double xa, ya;
-          GetProjectionCoordinates(currentInstance, out xa, out ya);
+          GetProjectionCoordinates(currentInstance, proximityType, out xa, out ya);
           foreach (var b in ProblemInstances) {
+            if (b == currentInstance) continue;
             double xb, yb;
-            GetProjectionCoordinates(b, out xb, out yb);
+            GetProjectionCoordinates(b, proximityType, out xb, out yb);
             var d = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
             result[b] = d;
@@ -693 +693 @@
           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}", ProblemInstanceProximity.Value));
+        default: throw new InvalidOperationException(string.Format("Unkonwn proximity type {0}", proximityType));
       }
       return result;
     }
 
-    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;
-      if (ProblemInstanceProximity.Value == ProblemInstanceProximityType.SOM) {
+    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);