Changeset 15031 for branches/PerformanceComparison/ProblemInstanceIdentifier

Timestamp:

06/10/17 23:19:11 (8 years ago)

Author:

abeham

Message:

#2457: worked on code for eurocast paper

Location:

branches/PerformanceComparison/ProblemInstanceIdentifier

Files:

• InstanceDescriptor.cs (modified) (2 diffs)
• InstanceExplorer.cs (modified) (6 diffs)
• ProblemInstanceIdentifier.csproj (modified) (1 diff)
• Program.cs (modified) (4 diffs)

branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs

@@ -2 +2 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Text.RegularExpressions;
 using HeuristicLab.Analysis.FitnessLandscape;
 using HeuristicLab.Common;
-using HeuristicLab.Data;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Problems.QuadraticAssignment;
@@ -68 +68 @@
           break;
         case "tai":
-          if (char.IsLetter(subCls)) cls += "-" + subCls;
+          if (Regex.IsMatch(name, "tai\\d+e\\d+")) cls += "-e";
+          else if (char.IsLetter(subCls)) cls += "-" + subCls;
           break;
       }

branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs

@@ -1 +1 @@
 using System;
 using System.Linq;
-using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Permutation;
 using HeuristicLab.Analysis.FitnessLandscape;
@@ -7 +6 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Problems.QuadraticAssignment;
+using HeuristicLab.Random;
 using HeuristicLab.SequentialEngine;
 
@@ -45 +45 @@
   }
 
+  public class PathRelinkingOldFeaturedExplorer : InstanceExplorer {
+    public int Paths { get; set; }
+    public bool LocalOptima { get; set; }
+
+    public override string Name { get { return "Path-Relinking Explorer"; } }
+    public override int Effort { get { return Paths; } }
+
+    public PathRelinkingOldFeaturedExplorer() {
+
+    }
+
+    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
+      var random = new MersenneTwister();
+      var samples = QAPDirectedWalk.CalculateRelinkingPoints(random, problem, Paths, LocalOptima);
+      var trajectories = QAPDirectedWalk.Run(random, problem, samples);
+
+      double avgAc1 = 0, avgCorLen = 0, avgIc = 0, avgDbi = 0, avgPic = 0, avgIs = 0, avgDiv = 0,
+        avgReg = 0, avgEnt = 0, avgPkIc = 0, avgPkDbi = 0;
+      int count = 0;
+      foreach (var t in trajectories) {
+        var trail = t.Select(x => x.Item2).ToArray();
+        if (trail.Length < 4) continue;
+        count++;
+        double[] acf;
+        var len = RuggednessCalculator.CalculateCorrelationLength(trail, out acf);
+        avgAc1 += acf[0];
+        avgCorLen += len;
+        var analysis = new InformationAnalysis(trail, 20, 2);
+        avgIc += analysis.InformationContent[0];
+        avgDbi += analysis.DensityBasinInformation[0];
+        avgPic += analysis.PartialInformationContent[0];
+        avgIs += analysis.InformationStability;
+        avgDiv += analysis.Diversity;
+        avgReg += analysis.Regularity;
+        avgEnt += analysis.TotalEntropy[0];
+        avgPkIc += analysis.PeakInformationContent.Value;
+        avgPkDbi += analysis.PeakDensityBasinInformation.Value;
+      }
+      avgAc1 /= count;
+      avgCorLen /= count;
+      avgIc /= count;
+      avgDbi /= count;
+      avgPic /= count;
+      avgIs /= count;
+      avgDiv /= count;
+      avgReg /= count;
+      avgEnt /= count;
+      avgPkIc /= count;
+      avgPkDbi /= count;
+
+      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
+        new[] { "Autocorrelation(1)", "CorrelationLength", "InformationContent", "DensityBasinInformation",
+          "PartialInformationContent", "InformationStability", "Diversity", "Regularity", "TotalEntropy",
+          "PeakInformationContent", "PeakDensityBasinInformation" },
+        new[] { avgAc1, avgCorLen, avgIc, avgDbi,
+          avgPic, avgIs, avgDiv, avgReg, avgEnt,
+          avgPkIc, avgPkDbi });
+    }
+  }
+
 
   public class RandomWalkExplorer : InstanceExplorer {
@@ -76 +136 @@
   public class AdaptiveWalkExplorer : InstanceExplorer {
     public int Iterations { get; set; }
+    public int SampleSize { get; set; }
 
     public override string Name { get { return "Adaptive-Walk Explorer"; } }
-    public override int Effort { get { return Iterations; } }
+    public override int Effort { get { return Iterations * SampleSize; } }
 
     public AdaptiveWalkExplorer() {
@@ -87 +148 @@
       var walk = new AdaptiveWalk() {
         SeedParameter = { Value = { Value = seed ?? 0 } },
-        SetSeedRandomlyParameter = { Value = { Value = seed.HasValue } },
+        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
         MaximumIterationsParameter = { Value = { Value = Iterations } },
-        RepetitionsParameter = { Value = { Value = 1 } }
+        RepetitionsParameter = { Value = { Value = 1 } },
+        SampleSizeParameter = { Value = { Value = SampleSize } }
       };
       walk.Problem = problem;
@@ -95 +157 @@
       walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
       var calculator = new AdaptiveWalkCalculator(walk) { Problem = problem };
+      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
+
+      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
+        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
+    }
+  }
+
+  public class UpDownWalkExplorer : InstanceExplorer {
+    public int Iterations { get; set; }
+    public int SampleSize { get; set; }
+
+    public override string Name { get { return "Up/Down-Walk Explorer"; } }
+    public override int Effort { get { return Iterations * SampleSize; } }
+
+    public UpDownWalkExplorer() {
+
+    }
+
+    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
+      var walk = new UpDownWalk() {
+        SeedParameter = { Value = { Value = seed ?? 0 } },
+        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
+        MaximumIterationsParameter = { Value = { Value = Iterations } },
+        RepetitionsParameter = { Value = { Value = 1 } },
+        SampleSizeParameter = { Value = { Value = SampleSize } }
+      };
+      walk.Problem = problem;
+      walk.Engine = new SequentialEngine();
+      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
+      var calculator = new UpDownWalkCalculator(walk) {  Problem = problem };
       var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
 

branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj

@@ -50 +50 @@
     <Reference Include="HeuristicLab.Encodings.PermutationEncoding-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.PermutationEncoding-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec">
+      <Private>True</Private>
     </Reference>
     <Reference Include="HeuristicLab.Persistence-3.3">

branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs

@@ -12 +12 @@
 namespace ProblemInstanceIdentifier {
   class Program {
+    static void Main(string[] args) {
+      //var instances = Get20DifferentClasses();
+      var instances = GetSomeRandomInstances(50, 13);
+
+      /*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 prExplorer = new PathRelinkingExplorer() {
+        LocalOptima = false,
+        Paths = 200
+      };
+      var prOldExplorer = new PathRelinkingOldFeaturedExplorer() {
+        LocalOptima = false,
+        Paths = 200
+      };
+
+      var prLocalExplorer = new PathRelinkingExplorer() {
+        LocalOptima = true,
+        Paths = 200
+      };
+      var prOldLocalExplorer = new PathRelinkingOldFeaturedExplorer() {
+        LocalOptima = true,
+        Paths = 200
+      };
+
+      var memPrExplorer = new MemPRExplorer() {
+        IncludeLocalSearch = false,
+        Seconds = 10
+      };
+
+      //var training = GenerateData(instances, prOldExplorer, parallel: true);
+      //var standardizer = InstancesStandardizer.CreateAndApply(training);
+      //var test = GenerateData(instances, prOldExplorer, parallel: true);
+      //standardizer.Apply(test);
+      //PrintMatchResult(Compare(training, test));
+
+      //Console.WriteLine("=== Path Relinking Walk ===");
+      //ExploreMatching(instances,
+      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
+      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
+      //parallel: true);
+      //Console.WriteLine("=== Random Walk ===");
+      //ExploreMatching(instances,
+      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
+      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
+      //parallel: true);
+      //Console.WriteLine("=== Adaptive Walk ===");
+      //ExploreMatching(instances,
+      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
+      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
+      //parallel: true);
+      Console.WriteLine("=== Up/Down Walk ===");
+      ExploreMatching(instances,
+      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
+      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
+      parallel: true);
+    }
+
+    private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances, int seed) {
+      var sync = new object();
+      var provider = new OneSizeInstanceProvider();
+      var instances = new List<QuadraticAssignmentProblem>();
+      var random = new FastRandom(seed);
+      Parallel.ForEach(provider.GetDataDescriptors().Shuffle(random), desc => {
+        var qapData = provider.LoadData(desc);
+        if (instances.Count >= totalInstances) return;
+        var qap = new QuadraticAssignmentProblem();
+        qap.Load(qapData);
+        lock (sync) {
+          if (instances.Count >= totalInstances) return;
+          instances.Add(qap);
+        }
+      });
+      return instances;
+    }
+
     private static HashSet<string> selectedInstances = new HashSet<string>() {
       "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
@@ -17 +95 @@
       "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 instances = Get20DifferentClasses();
-      //var instances = GetSomeRandomInstances(50);
-
-      /*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 prExplorer = new PathRelinkingExplorer() {
-        LocalOptima = false,
-        Paths = 200
-      };
-      var prLocalExplorer = new PathRelinkingExplorer() {
-        LocalOptima = true,
-        Paths = 200
-      };
-      var memPrExplorer = new MemPRExplorer() {
-        IncludeLocalSearch = false,
-        Seconds = 10
-      };
-
-      var training = GenerateData(instances, prExplorer, parallel:true);
-      var standardizer = InstancesStandardizer.CreateAndApply(training);
-      var test = GenerateData(instances, prExplorer, parallel: false);
-      standardizer.Apply(test);
-      PrintMatchResult(Compare(training, test));
-
-      ExploreMatching(instances, new [] { prLocalExplorer }, new [] { memPrExplorer });
-    }
-
-    private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances) {
-      var sync = new object();
-      var provider = new OneSizeInstanceProvider();
-      var instances = new List<QuadraticAssignmentProblem>();
-      var random = new FastRandom(0);
-      Parallel.ForEach(provider.GetDataDescriptors().Shuffle(random), desc => {
-        var qapData = provider.LoadData(desc);
-        if (qapData.Dimension < 25) return;
-        if (instances.Count >= totalInstances) return;
-        var qap = new QuadraticAssignmentProblem();
-        qap.Load(qapData);
-        lock (sync) {
-          if (instances.Count >= totalInstances) return;
-          instances.Add(qap);
-        }
-      });
-      return instances;
-    }
-
     private static List<QuadraticAssignmentProblem> Get20DifferentClasses() {
       var sync = new object();
@@ -100 +128 @@
       };
       if (parallel) {
-        Parallel.ForEach(instances, body);
+        Parallel.ForEach(instances.Select(x => (QuadraticAssignmentProblem)x.Clone()), body);
       } else {
         foreach (var qap in instances) body(qap);
@@ -156 +184 @@
     private static void ExploreMatching(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] trainingExplorers, InstanceExplorer[] testExporers, bool parallel = false) {
       var sync = new object();
-      var rand = new Random();
-      var first = rand.Next();
-      var second = rand.Next();
-      while (first == second) second = rand.Next();
 
       var knowledgeBase = new Dictionary<InstanceExplorer, Tuple<InstancesStandardizer, List<InstanceDescriptor>>>();