Changeset 14690 for branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs

Timestamp:

02/20/17 20:41:33 (8 years ago)

Author:

abeham

Message:

#2457: working on identification of problem instances

File:

• branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs (modified) (5 diffs)

branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Globalization;
 using System.Linq;
 using System.Threading.Tasks;
+using HeuristicLab.Algorithms.MemPR.Permutation;
 using HeuristicLab.PluginInfrastructure;
 using HeuristicLab.Problems.Instances;
@@ -10 +12 @@
 namespace ProblemInstanceIdentifier {
   class Program {
+    private static HashSet<string> selectedInstances = new HashSet<string>() {
+      "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
+      "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50",
+      "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
+    };
     static void Main(string[] args) {
       var sync = new object();
@@ -18 +25 @@
         if (provider is TaillardQAPInstanceProvider) continue;
         Parallel.ForEach(provider.GetDataDescriptors(), desc => {
-          if (desc.Name == "esc16f") return;
+          if (!selectedInstances.Contains(desc.Name)) return;
+          //if (desc.Name == "esc16f") return;
           var qapData = provider.LoadData(desc);
-          if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
+          //if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
           var qap = new QuadraticAssignmentProblem();
           qap.Load(qapData);
@@ -29 +37 @@
       }
 
-      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", "Repetition", "KB-Paths", "Exp-Paths", "Cls-Hits", "Exact-Hits", "No-Hits", "Cls-Rank", "Exact-Rank");
-      var paths = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50 };
-      for (var r = 0; r < 20; r++) {
-        Parallel.ForEach(paths, kbPaths => {
-          foreach (var expPaths in paths) {
-            if (expPaths > kbPaths) continue;
+      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
+      foreach (var cls in classes.OrderBy(x => x.Key)) {
+        Console.WriteLine("{0};{1}", cls.Key, cls.Count());
+      }*/
+
+      //var kb = GenerateKnowledgeBase(instances, 200, localOptima: false);
+
+
+      //var paths = new[] { 1, 2, 3, 5, 10, 20, 30, 50, 100, 200 };
+      //var kbExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray();
+      //var expExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray();
+      //ExploreSelfIdentification(instances, kbExplorers, expExplorers);
+
+      var iterations = new[] { 100, 1000, 10000, 100000 };
+      var kbExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray();
+      var expExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray();
+      ExploreSelfIdentification(instances, kbExplorers, expExplorers);
+
+      //ExploreMemPrIdentification(instances);
+    }
+
+    private static List<InstanceDescriptor> GenerateKnowledgeBase(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer) {
+      var headerPrinted = false;
+      var sync = new object();
+      var kb = new List<InstanceDescriptor>();
+      Parallel.ForEach(instances.OrderBy(x => x.Weights.Rows), qap => {
+        var instance = explorer.Explore(qap);
+        lock (sync) {
+          if (!headerPrinted) {
+            headerPrinted = true;
+            Console.WriteLine(string.Join(";",
+              new [] { "Name", "Cls", "Dimension" }
+              .Concat(instance.FeatureNames)));
+          }
+          PrintInstanceLine(instance);
+          kb.Add(instance);
+        }
+      });
+      var standardizer = InstancesStandardizer.Create(kb);
+      var normalizedKb = kb.Select(x => new InstanceDescriptor(x)).ToList();
+      standardizer.Apply(normalizedKb);
+      Console.WriteLine();
+      foreach (var instance in kb) {
+        PrintInstanceLine(instance);
+      }
+      //return normalizedKb;
+      return kb;
+    }
+
+    private static void PrintInstanceLine(InstanceDescriptor instance) {
+      Console.WriteLine(string.Join(";",
+        new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)}
+          .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture)))));
+    }
+
+    private static void ExploreSelfIdentification(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] kbExplorer, InstanceExplorer[] expExporer) {
+      var sync = new object();
+      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Effort", "Exp-Effort",
+        "Exact-Hits", "No-Hits", "Exact-Rank");
+      var kbSeeds = Enumerable.Range(0, 20).ToList();
+      var expSeeds = Enumerable.Range(20, 20).ToList();
+      for (var r = 0; r < 10; r++) {
+        var rlokal = r;
+        Parallel.ForEach(kbExplorer, kbPaths => {
+        //foreach (var kbPaths in kbExplorer) {
+          foreach (var expPaths in expExporer) {
+            //if (expPaths > kbPaths) continue;
             var kb = new List<InstanceDescriptor>();
             var exp = new List<InstanceDescriptor>();
             foreach (var qap in instances) {
-              kb.Add(InstanceDescriptor.FromPathRelinkingAnalysis(qap, kbPaths, null));
-              exp.Add(InstanceDescriptor.FromPathRelinkingAnalysis(qap, expPaths, null));
+              kb.Add(kbPaths.Explore(qap, kbSeeds[rlokal]));
+              exp.Add(expPaths.Explore(qap, expSeeds[rlokal]));
             }
+            var standardizer = InstancesStandardizer.Create(kb);
+            standardizer.Apply(kb);
+            standardizer.Apply(exp);
+            int exactCount = 0, clsCount = 0, missedCount = 0;
+            int exactRank = 0, clsRank = 0;
+            foreach (var e in exp) {
+              var ordered = kb.OrderBy(x => x.CalculateSimilarity(e)).ToList();
+              var bestMatch = ordered.First();
+              if (bestMatch.Cls == e.Cls) {
+                clsCount++;
+                if (bestMatch.Name == e.Name) exactCount++;
+              }
+              else missedCount++;
+              clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1;
+              exactRank += ordered.FindIndex((id) => id.Name == e.Name) + 1;
+            }
+            lock (sync) {
+              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths.Effort, expPaths.Effort, exactCount,
+                missedCount, exactRank / (double) exp.Count);
+            }
+          }
+        });
+        //}
+      }
+    }
+    
+    private static void ExploreMemPrIdentification(List<QuadraticAssignmentProblem> instances) {
+      var sync = new object();
+      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Runtime", "Exp-Runtime",
+        "Exact-Hits", "No-Hits", "Average-Rank");
+      var paths = new[] { 10 };
+      var repetitions = 10;
+      var kbSeeds = Enumerable.Range(0, repetitions).ToList();
+      var expSeeds = Enumerable.Range(repetitions, repetitions).ToList();
+      for (var r = 0; r < repetitions; r++) {
+        var rlokal = r;
+        Parallel.ForEach(paths, kbPaths => {
+          var memPr = new PermutationMemPR();
+          foreach (var expPaths in paths) {
+            //if (expPaths > kbPaths) continue;
+            var kb = new List<InstanceDescriptor>();
+            var exp = new List<InstanceDescriptor>();
+            foreach (var qap in instances.Select(x => (QuadraticAssignmentProblem)x.Clone())) {
+              memPr.Problem = qap;
+              memPr.Prepare(true);
+              memPr.Seed = kbSeeds[rlokal];
+              memPr.MaximumExecutionTime = TimeSpan.FromSeconds(kbPaths);
+              memPr.StartSync();
+              if (memPr.Context.RelinkedPaths.IsEmpty) continue;
+              kb.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList()));
+              memPr.Prepare(true);
+              memPr.Seed = expSeeds[rlokal];
+              memPr.MaximumExecutionTime = TimeSpan.FromSeconds(expPaths);
+              memPr.StartSync();
+              if (memPr.Context.RelinkedPaths.IsEmpty) continue;
+              exp.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList()));
+            }
+            var standardizer = InstancesStandardizer.Create(kb);
+            standardizer.Apply(kb);
+            standardizer.Apply(exp);
             int exactCount = 0, clsCount = 0, missedCount = 0;
             int exactRank = 0, clsRank = 0;
@@ -54 +183 @@
             }
             lock (sync) {
-              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", r, kbPaths, expPaths, clsCount, exactCount, missedCount, clsRank / (double)exp.Count, exactRank / (double)exp.Count);
+              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths, expPaths, exactCount,
+                missedCount, exactRank / (double)exp.Count);
             }
           }