Changeset 13759 for branches/PerformanceComparison

Timestamp:

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

Author:

abeham

Message:

#2457: worked on suggestion algorithm

Location:

branches/PerformanceComparison

Files:

• HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs (modified) (8 diffs)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/SolverView.Designer.cs (modified) (10 diffs)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/SolverView.cs (modified) (2 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);
+      }
     }
 

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/SolverView.Designer.cs

@@ -60 +60 @@
       WeifenLuo.WinFormsUI.Docking.TabGradient tabGradient6 = new WeifenLuo.WinFormsUI.Docking.TabGradient();
       WeifenLuo.WinFormsUI.Docking.TabGradient tabGradient7 = new WeifenLuo.WinFormsUI.Docking.TabGradient();
+      this.minTargetView = new HeuristicLab.Data.Views.StringConvertibleValueView();
+      this.maxEvaluationsView = new HeuristicLab.Data.Views.StringConvertibleValueView();
+      this.algorithmCloneButton = new System.Windows.Forms.Button();
       this.seedingStrategyPanel = new System.Windows.Forms.Panel();
       this.solverTabControl = new HeuristicLab.MainForm.WindowsForms.DragOverTabControl();
@@ -67 +70 @@
       this.runsTabPage = new System.Windows.Forms.TabPage();
       this.runsView = new HeuristicLab.Optimization.Views.RunCollectionView();
+      this.seededRunsTabPage = new System.Windows.Forms.TabPage();
+      this.seededRunsView = new HeuristicLab.Optimization.Views.RunCollectionView();
       this.solutionSeedingTabPage = new System.Windows.Forms.TabPage();
       this.parametersTabPage = new System.Windows.Forms.TabPage();
@@ -73 +78 @@
       this.operatorGraphViewHost = new HeuristicLab.MainForm.WindowsForms.ViewHost();
       this.algorithmStartButton = new System.Windows.Forms.Button();
-      this.label1 = new System.Windows.Forms.Label();
+      this.minimumTargetLabel = new System.Windows.Forms.Label();
+      this.seedingStrategyLabel = new System.Windows.Forms.Label();
       this.evaluationsLimitabel = new System.Windows.Forms.Label();
       this.algorithmSuggestionLabel = new System.Windows.Forms.Label();
       this.suggestedInstancesComboBox = new System.Windows.Forms.ComboBox();
-      this.algorithmCloneButton = new System.Windows.Forms.Button();
-      this.maxEvaluationsView = new HeuristicLab.Data.Views.StringConvertibleValueView();
-      this.seededRunsTabPage = new System.Windows.Forms.TabPage();
-      this.seededRunsView = new HeuristicLab.Optimization.Views.RunCollectionView();
       this.solverTabControl.SuspendLayout();
       this.resultsTabPage.SuspendLayout();
       this.runsTabPage.SuspendLayout();
+      this.seededRunsTabPage.SuspendLayout();
       this.parametersTabPage.SuspendLayout();
       this.operatorGraphTabPage.SuspendLayout();
-      this.seededRunsTabPage.SuspendLayout();
       this.SuspendLayout();
+      // 
+      // minTargetView
+      // 
+      this.minTargetView.Caption = "StringConvertibleValue View";
+      this.minTargetView.Content = null;
+      this.minTargetView.LabelVisible = false;
+      this.minTargetView.Location = new System.Drawing.Point(431, 3);
+      this.minTargetView.Name = "minTargetView";
+      this.minTargetView.ReadOnly = false;
+      this.minTargetView.Size = new System.Drawing.Size(255, 21);
+      this.minTargetView.TabIndex = 16;
+      // 
+      // maxEvaluationsView
+      // 
+      this.maxEvaluationsView.Caption = "StringConvertibleValue View";
+      this.maxEvaluationsView.Content = null;
+      this.maxEvaluationsView.LabelVisible = false;
+      this.maxEvaluationsView.Location = new System.Drawing.Point(91, 3);
+      this.maxEvaluationsView.Name = "maxEvaluationsView";
+      this.maxEvaluationsView.ReadOnly = false;
+      this.maxEvaluationsView.Size = new System.Drawing.Size(255, 21);
+      this.maxEvaluationsView.TabIndex = 16;
+      // 
+      // algorithmCloneButton
+      // 
+      this.algorithmCloneButton.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
+      this.algorithmCloneButton.Location = new System.Drawing.Point(823, 56);
+      this.algorithmCloneButton.Name = "algorithmCloneButton";
+      this.algorithmCloneButton.Size = new System.Drawing.Size(26, 23);
+      this.algorithmCloneButton.TabIndex = 15;
+      this.algorithmCloneButton.Text = "Clone";
+      this.algorithmCloneButton.UseVisualStyleBackColor = true;
+      this.algorithmCloneButton.Click += new System.EventHandler(this.AlgorithmCloneButtonOnClick);
       // 
       // seedingStrategyPanel
@@ -217 +252 @@
       this.runsView.TabIndex = 0;
       // 
+      // seededRunsTabPage
+      // 
+      this.seededRunsTabPage.Controls.Add(this.seededRunsView);
+      this.seededRunsTabPage.Location = new System.Drawing.Point(4, 22);
+      this.seededRunsTabPage.Name = "seededRunsTabPage";
+      this.seededRunsTabPage.Padding = new System.Windows.Forms.Padding(3);
+      this.seededRunsTabPage.Size = new System.Drawing.Size(841, 454);
+      this.seededRunsTabPage.TabIndex = 5;
+      this.seededRunsTabPage.Text = "Seeded Runs";
+      this.seededRunsTabPage.UseVisualStyleBackColor = true;
+      // 
+      // seededRunsView
+      // 
+      this.seededRunsView.Caption = "RunCollection View";
+      this.seededRunsView.Content = null;
+      this.seededRunsView.Dock = System.Windows.Forms.DockStyle.Fill;
+      this.seededRunsView.Location = new System.Drawing.Point(3, 3);
+      this.seededRunsView.Name = "seededRunsView";
+      this.seededRunsView.ReadOnly = false;
+      this.seededRunsView.Size = new System.Drawing.Size(835, 448);
+      this.seededRunsView.TabIndex = 1;
+      // 
       // solutionSeedingTabPage
       // 
@@ -287 +344 @@
       this.algorithmStartButton.Click += new System.EventHandler(this.AlgorithmStartButtonOnClick);
       // 
-      // label1
-      // 
-      this.label1.AutoSize = true;
-      this.label1.Location = new System.Drawing.Point(3, 33);
-      this.label1.Name = "label1";
-      this.label1.Size = new System.Drawing.Size(91, 13);
-      this.label1.TabIndex = 8;
-      this.label1.Text = "Seeding Strategy:";
+      // minimumTargetLabel
+      // 
+      this.minimumTargetLabel.AutoSize = true;
+      this.minimumTargetLabel.Location = new System.Drawing.Point(384, 6);
+      this.minimumTargetLabel.Name = "minimumTargetLabel";
+      this.minimumTargetLabel.Size = new System.Drawing.Size(41, 13);
+      this.minimumTargetLabel.TabIndex = 13;
+      this.minimumTargetLabel.Text = "Target:";
+      // 
+      // seedingStrategyLabel
+      // 
+      this.seedingStrategyLabel.AutoSize = true;
+      this.seedingStrategyLabel.Location = new System.Drawing.Point(3, 33);
+      this.seedingStrategyLabel.Name = "seedingStrategyLabel";
+      this.seedingStrategyLabel.Size = new System.Drawing.Size(91, 13);
+      this.seedingStrategyLabel.TabIndex = 8;
+      this.seedingStrategyLabel.Text = "Seeding Strategy:";
       // 
       // evaluationsLimitabel
@@ -326 +392 @@
       this.suggestedInstancesComboBox.SelectedIndexChanged += new System.EventHandler(this.SuggestedInstancesComboBoxOnSelectedIndexChanged);
       // 
-      // algorithmCloneButton
-      // 
-      this.algorithmCloneButton.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
-      this.algorithmCloneButton.Location = new System.Drawing.Point(823, 56);
-      this.algorithmCloneButton.Name = "algorithmCloneButton";
-      this.algorithmCloneButton.Size = new System.Drawing.Size(26, 23);
-      this.algorithmCloneButton.TabIndex = 15;
-      this.algorithmCloneButton.Text = "Clone";
-      this.algorithmCloneButton.UseVisualStyleBackColor = true;
-      this.algorithmCloneButton.Click += new System.EventHandler(this.AlgorithmCloneButtonOnClick);
-      // 
-      // maxEvaluationsView
-      // 
-      this.maxEvaluationsView.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left) 
-            | System.Windows.Forms.AnchorStyles.Right)));
-      this.maxEvaluationsView.Caption = "StringConvertibleValue View";
-      this.maxEvaluationsView.Content = null;
-      this.maxEvaluationsView.LabelVisible = false;
-      this.maxEvaluationsView.Location = new System.Drawing.Point(91, 3);
-      this.maxEvaluationsView.Name = "maxEvaluationsView";
-      this.maxEvaluationsView.ReadOnly = false;
-      this.maxEvaluationsView.Size = new System.Drawing.Size(758, 21);
-      this.maxEvaluationsView.TabIndex = 16;
-      // 
-      // seededRunsTabPage
-      // 
-      this.seededRunsTabPage.Controls.Add(this.seededRunsView);
-      this.seededRunsTabPage.Location = new System.Drawing.Point(4, 22);
-      this.seededRunsTabPage.Name = "seededRunsTabPage";
-      this.seededRunsTabPage.Padding = new System.Windows.Forms.Padding(3);
-      this.seededRunsTabPage.Size = new System.Drawing.Size(841, 454);
-      this.seededRunsTabPage.TabIndex = 5;
-      this.seededRunsTabPage.Text = "Seeded Runs";
-      this.seededRunsTabPage.UseVisualStyleBackColor = true;
-      // 
-      // seededRunsView
-      // 
-      this.seededRunsView.Caption = "RunCollection View";
-      this.seededRunsView.Content = null;
-      this.seededRunsView.Dock = System.Windows.Forms.DockStyle.Fill;
-      this.seededRunsView.Location = new System.Drawing.Point(3, 3);
-      this.seededRunsView.Name = "seededRunsView";
-      this.seededRunsView.ReadOnly = false;
-      this.seededRunsView.Size = new System.Drawing.Size(835, 448);
-      this.seededRunsView.TabIndex = 1;
-      // 
       // SolverView
       // 
       this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
       this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
+      this.Controls.Add(this.minTargetView);
       this.Controls.Add(this.maxEvaluationsView);
       this.Controls.Add(this.algorithmCloneButton);
@@ -381 +402 @@
       this.Controls.Add(this.solverTabControl);
       this.Controls.Add(this.algorithmStartButton);
-      this.Controls.Add(this.label1);
+      this.Controls.Add(this.minimumTargetLabel);
+      this.Controls.Add(this.seedingStrategyLabel);
       this.Controls.Add(this.evaluationsLimitabel);
       this.Controls.Add(this.algorithmSuggestionLabel);
@@ -391 +413 @@
       this.resultsTabPage.PerformLayout();
       this.runsTabPage.ResumeLayout(false);
+      this.seededRunsTabPage.ResumeLayout(false);
       this.parametersTabPage.ResumeLayout(false);
       this.operatorGraphTabPage.ResumeLayout(false);
-      this.seededRunsTabPage.ResumeLayout(false);
       this.ResumeLayout(false);
       this.PerformLayout();
@@ -410 +432 @@
     private MainForm.WindowsForms.ViewHost operatorGraphViewHost;
     private System.Windows.Forms.Button algorithmStartButton;
-    private System.Windows.Forms.Label label1;
+    private System.Windows.Forms.Label seedingStrategyLabel;
     private System.Windows.Forms.Label evaluationsLimitabel;
     private System.Windows.Forms.Label algorithmSuggestionLabel;
@@ -422 +444 @@
     private System.Windows.Forms.TabPage seededRunsTabPage;
     private Optimization.Views.RunCollectionView seededRunsView;
+    private System.Windows.Forms.Label minimumTargetLabel;
+    private Data.Views.StringConvertibleValueView minTargetView;
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/SolverView.cs

@@ -60 +60 @@
         if (Content == null) {
           maxEvaluationsView.Content = null;
+          minTargetView.Content = null;
           solverParametersView.Content = null;
           runsView.Content = null;
@@ -67 +68 @@
         } else {
           maxEvaluationsView.Content = Content.MaximumEvaluations;
+          minTargetView.Content = Content.MinimumTarget;
           runsView.Content = Content.InstanceRuns;
           seededRunsView.Content = Content.SeededRuns;