Changeset 13759 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

Timestamp:

04/14/16 01:20:10 (8 years ago)

Author:

abeham

Message:

#2457: worked on suggestion algorithm

File:

• branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs (modified) (8 diffs)

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

@@ -131 +131 @@
     public KnowledgeCenter() {
       maximumEvaluations = new IntValue(10000);
-      minimumTarget = new DoubleValue(1.05);
+      minimumTarget = new DoubleValue(0.05);
       instanceRuns = new RunCollection();
       seededRuns = new RunCollection();
@@ -140 +140 @@
       problemCharacteristics = new CheckedItemList<StringValue>();
       problemInstanceProximity = new EnumValue<ProblemInstanceProximityType>(ProblemInstanceProximityType.FeatureSpace);
-      problemInstanceNeighborhoodFactor = new DoubleValue(1);
+      problemInstanceNeighborhoodFactor = new DoubleValue(5);
       readonlyProblemCharacteristics = problemCharacteristics.AsReadOnly();
       problem = new SingleObjectiveOKBProblem();
@@ -455 +455 @@
         progress.ProgressValue = 0;
         // FIXME: How to tell if refresh is necessary?
-        queryClient.Refresh();
-        progress.ProgressValue = 0.5;
-        progress.Status = "Downloading algorithm and problem instance information...";
-        // FIXME: How to tell if refresh is necessary?
-        adminClient.Refresh();
+        var refreshTasks = new[] {
+          Task.Factory.StartNew(() => queryClient.Refresh()),
+          Task.Factory.StartNew(() => adminClient.Refresh())
+        };
+        Task.WaitAll(refreshTasks);
 
         var probInstance = adminClient.Problems.SingleOrDefault(x => x.Id == Problem.ProblemId);
@@ -476 +476 @@
         var characteristics = new HashSet<string>();
         var totalProblems = adminClient.Problems.Count(x => x.ProblemClassId == probClassId);
-        Parallel.ForEach(adminClient.Problems.Where(x => x.ProblemClassId == probClassId), (pInst) => { 
+        Parallel.ForEach(adminClient.Problems.Where(x => x.ProblemClassId == probClassId), new ParallelOptions { MaxDegreeOfParallelism = 3 }, (pInst) => { 
           var charas = new List<string>();
           IRun probRun = null;
@@ -512 +512 @@
         progress.ProgressValue = 0;
         p[0] = 0;
-        Parallel.ForEach(adminClient.Algorithms, (algInst) => {
+        Parallel.ForEach(adminClient.Algorithms, new ParallelOptions { MaxDegreeOfParallelism = 3 }, (algInst) => {
           IAlgorithm alg = null;
           var data = Clients.OKB.Administration.AdministrationClient.GetAlgorithmData(algInst.Id);
@@ -544 +544 @@
         var runIds = queryClient.GetRunIds(problemClassFilter).ToList();
         var batches = runIds.Select((v, i) => new { Idx = i, Val = v }).GroupBy(x => x.Idx / 500, x => x.Val);
-        Parallel.ForEach(batches.Select(x => x.ToList()), (batch) => {
+        Parallel.ForEach(batches.Select(x => x.ToList()), new ParallelOptions { MaxDegreeOfParallelism = 3 }, (batch) => {
           var okbRuns = queryClient.GetRunsWithValues(batch, true, interestingValues);
           var hlRuns = okbRuns.AsParallel().Select(x => new { AlgorithmId = x.Algorithm.Id, Run = queryClient.ConvertToOptimizationRun(x) }).ToList();
@@ -630 +630 @@
       if (Problem == null) return;
       var piDistances = GetProblemDistances();
-      var maxDistance = piDistances.Max();
-      // Weighted combination of algorithm performances using distance-based exponentially falling weights
-      // Scale distances by maxDistance
-      // Parameter to influence dampening factor
-      // Algorithm performances are given in expected run time
-      // Using convergence graphs up to maximum evaluations effort
-      // Care has to be taken if not every algorithm has been executed on every problem instance
+      var maxDist = piDistances.Max(x => x.Value);
       var instances = new SortedList<double, IAlgorithm>();
       foreach (var relevantRuns in knowledgeBase.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
         var algorithm = algorithmId2AlgorithmInstanceMapping.GetByFirst(relevantRuns.Key);
-        var avgQuality = 0.0;
-        var counter = 0;
+        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)) {
-          var probInstance = ProblemInstances.SingleOrDefault(x => x.Name == problemRuns.Key);
-          if (probInstance == null) continue;
-          var bkQuality = ((DoubleValue)probInstance.Parameters["BestKnownQuality"]).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"]);
-            try {
-              avgQuality += performanceGraph.Rows.First().Values.TakeWhile(x => x.Item1 < MaximumEvaluations.Value).Last().Item2 / bkQuality;
-              counter++;
-            } catch {
-              continue;
-            }
-          }
-        }
-        avgQuality /= counter;
-        instances.Add(avgQuality, algorithm);
+            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();
-      if (Maximization) instanceLadder.Reverse();
       suggestedInstances.Replace(instanceLadder);
     }
 
-    private DoubleMatrix GetProblemDistances() {
-      var matrix = new DoubleMatrix(ProblemInstances.Count, ProblemInstances.Count);
+    private Dictionary<IRun, double> GetProblemDistances() {
+      var result = new Dictionary<IRun, double>(); 
+      var currentInstance = problemId2ProblemInstanceMapping.GetByFirst(Problem.ProblemId);
       switch (ProblemInstanceProximity.Value) {
         case ProblemInstanceProximityType.MDS:
         case ProblemInstanceProximityType.PCA:
         case ProblemInstanceProximityType.SOM:
-          int i = 0, j = 0;
-          foreach (var a in ProblemInstances) {
-            double xa, ya;
-            GetProjectionCoordinates(a, out xa, out ya);
-            j = 0;
-            foreach (var b in ProblemInstances) {
-              double xb, yb;
-              GetProjectionCoordinates(b, out xb, out yb);
-              matrix[i, j] = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
-              j++;
-            }
-            i++;
+          double xa, ya;
+          GetProjectionCoordinates(currentInstance, out xa, out ya);
+          foreach (var b in ProblemInstances) {
+            double xb, yb;
+            GetProjectionCoordinates(b, out xb, out yb);
+            var d = Math.Sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
+            result[b] = d;
           }
           break;
         case ProblemInstanceProximityType.FeatureSpace:
-          int k = 0, l = 0;
           var features = GetProblemCharacteristics();
-          foreach (var a in ProblemInstances) {
-            l = 0;
-            var fa = features[a];
-            foreach (var b in ProblemInstances) {
-              var sum = features[b].Select((t, f) => (fa[f] - t) * (fa[f] - t)).Sum();
-              matrix[k, l] = Math.Sqrt(sum);
-              l++;
-            }
-            k++;
+          var cF = features[currentInstance];
+          foreach (var b in ProblemInstances) {
+            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));
       }
-      return matrix;
+      return result;
     }
 
@@ -707 +705 @@
       x = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".X"]).Value;
       y = ((DoubleValue)problemInstance.Results["Projection." + ProblemInstanceProximity.Value + ".Y"]).Value;
+      if (ProblemInstanceProximity.Value == ProblemInstanceProximityType.SOM) {
+        x = Math.Floor(x);
+        y = Math.Floor(y);
+      }
     }