Changeset 15031

Timestamp:

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

Author:

abeham

Message:

#2457: worked on code for eurocast paper

Location:

branches/PerformanceComparison

Files:

• HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/UpDownWalkCalculator.cs (modified) (1 diff)
• HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs (modified) (4 diffs)
• HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs (modified) (4 diffs)
• ProblemInstanceIdentifier/InstanceDescriptor.cs (modified) (2 diffs)
• ProblemInstanceIdentifier/InstanceExplorer.cs (modified) (6 diffs)
• ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj (modified) (1 diff)
• ProblemInstanceIdentifier/Program.cs (modified) (4 diffs)

branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/UpDownWalkCalculator.cs

@@ -58 +58 @@
       characteristics = cloner.Clone(original.characteristics);
     }
-    public UpDownWalkCalculator() {
+    public UpDownWalkCalculator() : this(new UpDownWalk()) { }
+    public UpDownWalkCalculator(UpDownWalk walker) {
       Name = ItemName;
       Description = ItemDescription;
-      walker = new UpDownWalk();
+      this.walker = walker;
       characteristics = new CheckedItemList<StringValue>(
         new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent",

branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

@@ -79 +79 @@
     private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
     public QAPDirectedWalk() {
-      characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness", /*"Swap2.Steadiness"*/ }
+      characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }
         .Select(x => new StringValue(x)).ToList());
       Parameters.Add(new FixedValueParameter<IntValue>("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50)));
@@ -98 +98 @@
       IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
       var qap = (QuadraticAssignmentProblem)Problem;
-      var pathCount = Paths;
-
+      List<Permutation> permutations = CalculateRelinkingPoints(random, qap, Paths, LocalOptima);
+
+      var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
+      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
+
+      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
+        if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
+        if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
+        if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
+      }
+    }
+
+    public static List<Permutation> CalculateRelinkingPoints(IRandom random, QuadraticAssignmentProblem qap, int pathCount, bool localOptima) {
       var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
-      if (LocalOptima) {
+      if (localOptima) {
         var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
         QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
@@ -109 +120 @@
         perm = (Permutation)permutations.Last().Clone();
         BiasedShuffle(perm, random);
-        if (LocalOptima) {
+        if (localOptima) {
           var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
           QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
@@ -117 +128 @@
       }
 
-      var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
-      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
-      
-      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
-        if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
-        if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
-        if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
-      }
+      return permutations;
     }
 

branches/PerformanceComparison/HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs

@@ -2 +2 @@
 using System.Collections.Generic;
 using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
+using System.Text.RegularExpressions;
 
 namespace HeuristicLab.Problems.Instances.QAPLIB {
@@ -9 +8 @@
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
       var drezner = new DreznerQAPInstanceProvider();
-      foreach (var desc in drezner.GetDataDescriptors())
-        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, drezner, desc);
+      foreach (var desc in drezner.GetDataDescriptors()) {
+        var dim = int.Parse(Regex.Match(desc.Name, "dre(?<g>\\d+)").Groups["g"].Value);
+        if (dim < 25) continue;
+        yield return new OneSizeDataDescriptor(desc.Name + (dim == 25 ? "" : "-25"), desc.Description, drezner, desc);
+      }
+      // Microarray instances are all greater than 25 dimensions
       var microarray = new MicroarrayQAPInstanceProvider();
-      foreach (var desc in microarray.GetDataDescriptors())
+      foreach (var desc in microarray.GetDataDescriptors()) {
         yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, microarray, desc);
+      }
       var qaplib = new QAPLIBInstanceProvider();
-      foreach (var desc in qaplib.GetDataDescriptors())
-        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, qaplib, desc);
+      foreach (var desc in qaplib.GetDataDescriptors()) {
+        var instance = qaplib.LoadData(desc);
+        if (instance.Dimension < 25) continue;
+        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == 25 ? "" : "-25"), desc.Description, qaplib, desc);
+      }
+      // Taillard's instances are basically from the same distribution
+      // to avoid over-representation in the set only the tai27e are taken and reduced to 25 dimension
       var taillard = new TaillardQAPInstanceProvider();
-      foreach (var desc in taillard.GetDataDescriptors())
+      foreach (var desc in taillard.GetDataDescriptors()) {
+        if (!desc.Name.StartsWith("tai27e")) continue;
         yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, taillard, desc);
+      }
     }
 
@@ -59 +70 @@
       data.Dimension = 25;
       data.Name += "-25";
-      data.Description += " (reduced or enlarged to 25 dimensions)";
+      data.Description += " (reduced to 25 dimensions)";
 
       return data;
@@ -68 +79 @@
     public override Uri WebLink { get { return null; } }
     public override string ReferencePublication { get { return string.Empty; } }
-
-    // permutation must be strictly different in every position
+    
     private static void Shuffle(int[] p, Random random) {
       for (var i = p.Length - 1; i > 0; i--) {
-        // Swap element "i" with a random earlier element (excluding itself)
         var swapIndex = random.Next(i + 1);
         var h = p[swapIndex];

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>>>();