Changeset 15718 for branches/1614_GeneralizedQAP

Timestamp:

02/04/18 21:06:14 (7 years ago)

Author:

abeham

Message:

#1614:

• Scale directed walk fitness values
• Performance improvements to RLD view
• Changed CPLEX to use a single thread only
• Set the context to null when algorithm is stopped

Location:

branches/1614_GeneralizedQAP

Files:

• HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/DoubleMatrixCharacteristicCalculator.cs (modified) (2 diffs)
• HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPCharacteristicCalculator.cs (modified) (1 diff)
• HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs (modified) (1 diff)
• HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs (modified) (32 diffs)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/CPLEX/CplexSolver.cs (modified) (1 diff)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/ContextAlgorithm.cs (modified) (1 diff)

branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/DoubleMatrixCharacteristicCalculator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Data;
-using System;
-using System.Linq;
 
 namespace HeuristicLab.Analysis.FitnessLandscape {
@@ -30 +30 @@
       var avg = m.Average();
       var stdDev = m.StandardDeviation();
+      return stdDev / avg;
+    }
+
+    public static double CoeffVariationNonZeroes(DoubleMatrix m) {
+      var nonzeroes = m.Where(x => !x.IsAlmost(0));
+      var avg = nonzeroes.Average();
+      var stdDev = nonzeroes.StandardDeviation();
       return stdDev / avg;
     }

branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPCharacteristicCalculator.cs

@@ -66 +66 @@
           yield return new Result(chara, new DoubleValue(inst.Capacities.Length / (double)inst.Demands.Length));
         if (chara == "FlowDominance")
-          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Weights)));
+          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariationNonZeroes(inst.Weights)));
         if (chara == "DistanceDominance")
-          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Distances)));
+          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariationNonZeroes(inst.Distances)));
         if (chara == "FlowSparsity")
           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(inst.Weights)));

branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs

@@ -134 +134 @@
     public static IEnumerable<List<Tuple<IntegerVector, double>>> Run(IRandom random, GQAP gqap, IEnumerable<IntegerVector> points, bool bestImprovement = true) {
       var iter = points.GetEnumerator();
-      if (!iter.MoveNext()) yield break;
+      if (!iter.MoveNext()) return new List<Tuple<IntegerVector, double>>[0];
 
       var start = iter.Current;
+      var walks = new List<List<Tuple<IntegerVector, double>>>();
       while (iter.MoveNext()) {
         var end = iter.Current;
 
         var walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList();
-        yield return walk.ToList();
+        walks.Add(walk);
         start = end;
       } // end paths
+
+      var min = walks.SelectMany(x => x.Select(y => y.Item2)).Min();
+      var max = walks.SelectMany(x => x.Select(y => y.Item2)).Max();
+
+      if (min == max) max = min + 1;
+      return walks.Select(w => w.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList());
     }
 

branches/1614_GeneralizedQAP/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs

@@ -31 +31 @@
 using HeuristicLab.Analysis;
 using HeuristicLab.Collections;
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Core.Views;
@@ -146 +147 @@
         return;
       }
+      if (updateInProgress) return;
       try {
         updateInProgress = true;
-        UpdateGroupAndProblemComboBox();
-        UpdateDataTableComboBox();
+        UpdateComboBoxes();
         GroupRuns();
       } finally { updateInProgress = false; }
@@ -160 +161 @@
         return;
       }
+      if (updateInProgress) return;
       try {
         updateInProgress = true;
-        UpdateGroupAndProblemComboBox();
-        UpdateDataTableComboBox();
+        UpdateComboBoxes();
         GroupRuns();
       } finally { updateInProgress = false; }
@@ -175 +176 @@
         return;
       }
+      if (updateInProgress) return;
       try {
         updateInProgress = true;
-        UpdateGroupAndProblemComboBox();
-        UpdateDataTableComboBox();
+        UpdateComboBoxes();
         GroupRuns();
       } finally { updateInProgress = false; }
@@ -194 +195 @@
       suppressContentEvents = Content.UpdateOfRunsInProgress;
       if (!suppressContentEvents) {
+        if (updateInProgress) return;
         try {
           updateInProgress = true;
-          UpdateGroupAndProblemComboBox();
-          UpdateDataTableComboBox();
+          UpdateComboBoxes();
           GroupRuns();
         } finally { updateInProgress = false; }
@@ -215 +216 @@
       } else {
         if (e.PropertyName == "Visible") {
+          if (updateInProgress) return;
           try {
             updateInProgress = true;
@@ -238 +240 @@
         try {
           updateInProgress = true;
-          UpdateGroupAndProblemComboBox();
-          UpdateDataTableComboBox();
+          UpdateComboBoxes();
           UpdateRuns();
         } finally { updateInProgress = false; }
@@ -246 +247 @@
 
 
-    private void UpdateGroupAndProblemComboBox() {
+    private void UpdateComboBoxes() {
       var selectedGroupItem = (string)groupComboBox.SelectedItem;
 
@@ -259 +260 @@
       }
 
+      string selectedDataTable = (string)dataTableComboBox.SelectedItem;
+
+      dataTableComboBox.Items.Clear();
+      var dataTables = (from run in Content
+                        from result in run.Results
+                        where result.Value is IndexedDataTable<double>
+                        select result.Key).Distinct().ToArray();
+
+      dataTableComboBox.Items.AddRange(dataTables);
+      if (selectedDataTable != null && dataTableComboBox.Items.Contains(selectedDataTable)) {
+        dataTableComboBox.SelectedItem = selectedDataTable;
+      } else if (dataTableComboBox.Items.Count > 0) {
+        dataTableComboBox.SelectedItem = dataTableComboBox.Items[0];
+      }
+
       var selectedProblemItem = (ProblemInstance)problemComboBox.SelectedItem;
       
@@ -271 +287 @@
 
       SetEnabledStateOfControls();
-    }
-
-    private void UpdateDataTableComboBox() {
-      string selectedItem = (string)dataTableComboBox.SelectedItem;
-
-      dataTableComboBox.Items.Clear();
-      var dataTables = (from run in Content
-                        from result in run.Results
-                        where result.Value is IndexedDataTable<double>
-                        select result.Key).Distinct().ToArray();
-
-      dataTableComboBox.Items.AddRange(dataTables);
-      if (selectedItem != null && dataTableComboBox.Items.Contains(selectedItem)) {
-        dataTableComboBox.SelectedItem = selectedItem;
-      } else if (dataTableComboBox.Items.Count > 0) {
-        dataTableComboBox.SelectedItem = dataTableComboBox.Items[0];
-      }
-
-      UpdateProblemInstances();
     }
 
@@ -318 +315 @@
                             && r.Visible
                             && selectedProblem.Match(r)
-                            && r.Results.ContainsKey(table)
-                            && r.Results[table] is IndexedDataTable<double>
-                          let key = selectedGroup == AllInstances ? AllInstances : r.Parameters[selectedGroup].ToString()
+                          let key = selectedGroup == AllInstances
+                            ? AllInstances : r.Parameters[selectedGroup].ToString()
                           group r by key into g
                           select g) {
-        var trials = from run in alg
-                     from pd in problems
-                     where pd.Equals(new ProblemInstance(run))
-                     let cgraph = ((IndexedDataTable<double>)run.Results[table])
-                     where cgraph.Rows.Count > 0 && cgraph.Rows.First().Values.Count > 0
+        var trials = (from run in alg
+                     from pd in problems.Skip(1) // exclude artificial match all
+                     where pd.Match(run) && run.Results.ContainsKey(table)
+                     let cgraph = run.Results[table] as IndexedDataTable<double>
+                     where cgraph != null && cgraph.Rows.Count > 0
+                        && cgraph.Rows.First().Values.Count > 0
                      group cgraph by pd into g
-                     select g;
-
+                     select g).ToList();
+
+        if (trials.Count == 0) continue;
         groups.Add(new AlgorithmInstance(alg.Key, trials));
       }
@@ -339 +337 @@
         problems.Clear();
         var table = (string)dataTableComboBox.SelectedItem;
-        if (string.IsNullOrEmpty(table)) return;
-
+        
         var problemDict = CalculateBestTargetPerProblemInstance(table);
 
@@ -350 +347 @@
 
         problems.Add(ProblemInstance.MatchAll);
-        foreach (var p in problemDict.ToList()) {
+        foreach (var p in problemDict.OrderBy(x => x.Key.ProblemName, new NaturalStringComparer()).ToList()) {
           p.Key.BestKnownQuality = p.Value;
           p.Key.DisplayProblemType = problemTypesDifferent;
@@ -394 +391 @@
           misses[alg.Name] = epdfMisses = new SortedList<double, int>();
         }
-        foreach (var problem in alg.GetCases()) {
-          var max = problem.IsMaximization();
+        foreach (var problem in alg.GetCases().Where(x => x.Maximization.HasValue)) {
+          var max = problem.Maximization.Value;
           var absTargets = GetAbsoluteTargets(problem).ToArray();
           foreach (var run in alg.GetTrials(problem)) {
@@ -450 +447 @@
       foreach (var list in hits) {
         var row = new Series(list.Key) {
-          ChartType = SeriesChartType.StepLine,
+          ChartType = list.Value.Count > 1000 ? SeriesChartType.FastLine : SeriesChartType.StepLine,
           BorderWidth = 3,
           Color = colors[colorCount],
@@ -603 +600 @@
     private IEnumerable<double> GetAbsoluteTargets(ProblemInstance pInstance) {
       if (!targetsAreRelative) return targets;
-
-      var maximization = pInstance.IsMaximization();
+      if (!pInstance.Maximization.HasValue) throw new ArgumentException("Problem doesn't specify if it is to be maximized or minimized.");
+
+      var maximization = pInstance.Maximization.Value;
       var bestKnown = pInstance.BestKnownQuality;
       if (double.IsNaN(bestKnown)) throw new ArgumentException("Problem instance does not have a defined best - known quality.");
@@ -621 +619 @@
     private double[] GetAbsoluteTargetsWorstToBest(ProblemInstance pInstance) {
       if (targetsAreRelative && double.IsNaN(pInstance.BestKnownQuality)) throw new ArgumentException("Problem instance does not have a defined best-known quality.");
+      if (!pInstance.Maximization.HasValue) throw new ArgumentException("Problem doesn't specify if it is to be maximized or minimized.");
       var absTargets = GetAbsoluteTargets(pInstance);
-      return (pInstance.IsMaximization()
+      return (pInstance.Maximization.Value
         ? absTargets.OrderBy(x => x) : absTargets.OrderByDescending(x => x)).ToArray();
     }
@@ -663 +662 @@
       var problems = groups.SelectMany(x => x.GetCases()).Distinct().ToList();
 
-      foreach (var problem in problems) {
-        if (double.IsNaN(problem.BestKnownQuality)) continue;
+      foreach (var problem in problems.OrderBy(x => x.ProblemName, new NaturalStringComparer())) {
+        if (double.IsNaN(problem.BestKnownQuality) || !problem.Maximization.HasValue) continue;
         rowNames.Add(problem.ToString());
-        var max = problem.IsMaximization();
+        var max = problem.Maximization.Value;
         var absTargets = GetAbsoluteTargetsWorstToBest(problem);
         if (targetsAreRelative) {
@@ -776 +775 @@
 
     private void CalculateHitsForEachBudget(Dictionary<string, SortedList<double, double>> hits, ConvergenceGraph cgraph, ProblemInstance problem, string groupName) {
-      var max = problem.IsMaximization();
+      var max = problem.Maximization.Value;
       var prevIndex = 0;
       foreach (var b in budgets) {
@@ -897 +896 @@
         updateInProgress = true;
         var pd = (ProblemInstance)problemComboBox.SelectedItem;
-        if (!double.IsNaN(pd.BestKnownQuality)) {
-          var max = pd.IsMaximization();
+        if (!double.IsNaN(pd.BestKnownQuality) && pd.Maximization.HasValue) {
+          var max = pd.Maximization.Value;
           if (targetsAreRelative) targets = GetAbsoluteTargets(pd).ToArray();
           else {
@@ -957 +956 @@
         var values = resultsTable.Rows.First().Values;
         var pd = new ProblemInstance(run);
+        if (!pd.Maximization.HasValue) continue;
         pd = problems.Single(x => x.Equals(pd));
         if (targetsAreRelative && double.IsNaN(pd.BestKnownQuality)) continue;
 
-        var max = pd.IsMaximization();
+        var max = pd.Maximization.Value;
         var absTargets = GetAbsoluteTargetsWorstToBest(pd);
         var cgraph = new ConvergenceGraph(resultsTable, max);
@@ -1071 +1071 @@
         var values = resultsTable.Rows.First().Values;
         var pd = new ProblemInstance(run);
+        if (!pd.Maximization.HasValue) continue;
         pd = problems.Single(x => x.Equals(pd));
-        var max = pd.IsMaximization();
+        var max = pd.Maximization.Value;
         var cgraph = new ConvergenceGraph(resultsTable, max);
         var prevIndex = 0;
@@ -1082 +1083 @@
           }
           var v = values[index];
-          var tgt = targetsAreRelative ? CalculateRelativeDifference(pd.IsMaximization(), pd.BestKnownQuality, v.Item2) : v.Item2;
+          var tgt = targetsAreRelative ? CalculateRelativeDifference(max, pd.BestKnownQuality, v.Item2) : v.Item2;
           run.Results[table + (targetsAreRelative ? ".CostForRelTarget " : ".CostForAbsTarget ") + b] = new DoubleValue(tgt);
           prevIndex = index;
@@ -1109 +1110 @@
       var dict = new Dictionary<ProblemInstance, double>();
       foreach (var k in from r in Content where r.Visible let pd = new ProblemInstance(r) group r by pd into g select new { Problem = g.Key, Runs = g.ToList() }) {
-        var pd = new ProblemInstance(k.Runs[0]);
+        var pd = k.Problem;
+        if (!pd.Maximization.HasValue) continue;
         var values = GetQualityValues(k.Runs, table).ToList();
         var target = double.NaN;
         if (values.Count > 0) {
-          target = pd.IsMaximization() ? values.Max() : values.Min();
+          target = pd.Maximization.Value ? values.Max() : values.Min();
         }
         dict[pd] = target;
@@ -1133 +1135 @@
             var last = dt.Rows.First().Values.Last().Item2;
             if (!double.IsNaN(last))
-              yield return last;
+              yield return Math.Round(last, 10);
           }
         }
@@ -1296 +1298 @@
         performanceData = new Dictionary<ProblemInstance, List<ConvergenceGraph>>();
         foreach (var t in trials) {
-          if (double.IsNaN(t.Key.BestKnownQuality)) continue;
-          var max = t.Key.IsMaximization();
-          performanceData[t.Key] = t.Select(c => new ConvergenceGraph(c, max)).ToList();
+          if (double.IsNaN(t.Key.BestKnownQuality) || !t.Key.Maximization.HasValue) continue;
+          performanceData[t.Key] = t.Select(c => new ConvergenceGraph(c, t.Key.Maximization.Value)).ToList();
         }
       }
@@ -1329 +1330 @@
         ProblemName = string.Empty;
         Evaluator = string.Empty;
-        Maximization = string.Empty;
+        Maximization = null;
         DisplayProblemType = false;
         DisplayProblemName = false;
@@ -1342 +1343 @@
         ProblemName = GetStringValueOrEmpty(run, "Problem Name");
         Evaluator = GetStringValueOrEmpty(run, "Evaluator");
-        Maximization = GetMaximizationValueOrEmpty(run, "Maximization");
+        Maximization = GetBoolValueOrEmpty(run, "Maximization");
         DisplayProblemType = !string.IsNullOrEmpty(ProblemType);
         DisplayProblemName = !string.IsNullOrEmpty(ProblemName);
         DisplayEvaluator = !string.IsNullOrEmpty(Evaluator);
-        DisplayMaximization = !string.IsNullOrEmpty(Maximization);
+        DisplayMaximization = Maximization.HasValue;
         matchAll = false;
         BestKnownQuality = GetDoubleValueOrNaN(run, "BestKnownQuality");
@@ -1414 +1415 @@
         }
       }
-      private string maximization;
-      public string Maximization {
+      private bool? maximization;
+      public bool? Maximization {
         get { return maximization; }
         set {
@@ -1433 +1434 @@
       }
 
-      public bool IsMaximization() {
-        return Maximization == "MAX";
-      }
-
       public bool Match(IRun run) {
         return matchAll ||
-               GetStringValueOrEmpty(run, "Problem Type") == ProblemType
+               (GetStringValueOrEmpty(run, "Problem Type") == ProblemType
                && GetStringValueOrEmpty(run, "Problem Name") == ProblemName
                && GetStringValueOrEmpty(run, "Evaluator") == Evaluator
-               && GetMaximizationValueOrEmpty(run, "Maximization") == Maximization;
+               && GetBoolValueOrEmpty(run, "Maximization") == Maximization);
       }
 
@@ -1463 +1460 @@
       }
 
-      private string GetMaximizationValueOrEmpty(IRun run, string key) {
+      private bool? GetBoolValueOrEmpty(IRun run, string key) {
         IItem param;
         if (run.Parameters.TryGetValue(key, out param)) {
           var bv = param as BoolValue;
-          return bv != null ? (bv.Value ? "MAX" : "MIN") : string.Empty;
-        }
-        return string.Empty;
+          if (bv != null) return bv.Value;
+        }
+        return null;
       }
 
@@ -1490 +1487 @@
           (DisplayProblemName ? ProblemName : string.Empty),
           (DisplayEvaluator ? Evaluator : string.Empty),
-          (DisplayMaximization ? Maximization : string.Empty),
+          (DisplayMaximization && Maximization.HasValue ? (Maximization.Value ? "MAX" : "MIN") : string.Empty),
           !double.IsNaN(BestKnownQuality) ? BestKnownQuality.ToString(CultureInfo.CurrentCulture.NumberFormat) : string.Empty }.Where(x => !string.IsNullOrEmpty(x)));
       }

branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/CPLEX/CplexSolver.cs

@@ -63 +63 @@
       cplex.Use(new LogCallback(this, cancellationToken));
       cplex.SetParam(Cplex.DoubleParam.TiLim, MaximumRuntime.TotalSeconds);
+      cplex.SetParam(Cplex.IntParam.Threads, 1);
       var dataSource = new GQAPDataSource(factory, Problem.ProblemInstance);
       using (var settings = factory.CreateOplSettings(factory.CreateOplErrorHandler()))

branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/ContextAlgorithm.cs

@@ -205 +205 @@
           firstHitGraph.Values[firstHitGraph.Values.Count - 1] = Tuple.Create(elapsed.TotalSeconds, Context.BestQuality);
       }
+      context = null;
       // base call must be done last as the results will be cloned and a run is created
       base.OnStopped();