Changeset 14690 for branches/PerformanceComparison/ProblemInstanceIdentifier

Timestamp:

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

Author:

abeham

Message:

#2457: working on identification of problem instances

Location:

branches/PerformanceComparison/ProblemInstanceIdentifier

Files:

• InstanceDescriptor.cs (modified) (5 diffs)
• InstanceExplorer.cs (added)
• ProblemInstanceIdentifier.csproj (modified) (5 diffs)
• Program.cs (modified) (5 diffs)

branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs

@@ -1 @@
-using System.Linq;
+using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Analysis.FitnessLandscape;
+using HeuristicLab.Common;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Problems.QuadraticAssignment;
 
@@ -9 +13 @@
     public string Cls { get; private set; }
     public int Dimension { get; set; }
-    public double Sharpness { get; set; }
-    public double SharpnessSdev { get; set; }
-    public double Bumpiness { get; set; }
-    public double BumpinessSdev { get; set; }
-    public double Flatness { get; set; }
-    public double FlatnessSdev { get; set; }
-    public double Steadiness { get; set; }
-    public double SteadinessSdev { get; set; }
+
+    public string[] FeatureNames { get; set; }
+    public double[] FeatureValues { get; set; }
     
     private InstanceDescriptor() { }
 
-    public static InstanceDescriptor FromPathRelinkingAnalysis(QuadraticAssignmentProblem qap, int paths, int? seed) {
-      var walk = new QAPDirectedWalk {
-        Problem = qap,
-        BestImprovement = true,
-        Paths = paths,
-        Seed = seed
+    public InstanceDescriptor(string name, string cls, int dimension, string[] names, double[] values) {
+      Name = name;
+      Cls = cls;
+      Dimension = dimension;
+      FeatureNames = names;
+      FeatureValues = values;
+    }
+
+    public InstanceDescriptor(InstanceDescriptor other) {
+      Name = other.Name;
+      Cls = other.Cls;
+      Dimension = other.Dimension;
+      FeatureNames = (string[])other.FeatureNames.Clone();
+      FeatureValues = (double[]) other.FeatureValues.Clone();
+    }
+
+    public static InstanceDescriptor FromProblemOnly(QuadraticAssignmentProblem qap) {
+      return new InstanceDescriptor() {
+        Name = qap.Name,
+        Cls = GetClass(qap.Name),
+        Dimension = qap.Weights.Rows,
+        FeatureNames = new string[0],
+        FeatureValues = new double[0]
       };
-      var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value);
+    }
+
+    public static InstanceDescriptor FromPaths(QuadraticAssignmentProblem qap, List<List<Tuple<Permutation, double>>> trajectories) {
+      var features = QAPDirectedWalk.Calculate(trajectories).ToDictionary(x => x.Name, x => x.Value);
       
       return new InstanceDescriptor() {
@@ -33 +52 @@
         Cls = GetClass(qap.Name),
         Dimension = qap.Weights.Rows,
-        Sharpness = ((DoubleValue)features["Swap2.Sharpness"]).Value,
-        Bumpiness = ((DoubleValue)features["Swap2.Bumpiness"]).Value,
-        Flatness = ((DoubleValue)features["Swap2.Flatness"]).Value,
-        Steadiness = ((DoubleValue)features["Swap2.Steadiness"]).Value,
+        FeatureNames = features.Keys.ToArray(),
+        FeatureValues = features.Values.Select(x => ((DoubleValue)x).Value).ToArray()
       };
     }
 
-    private static string GetClass(string name) {
+    public static string GetClass(string name) {
       var cls = name.Substring(0, 3);
       var subCls = name.Last();
@@ -58 +75 @@
 
     public double CalculateSimilarity(InstanceDescriptor other) {
-      var sa = (Sharpness - other.Sharpness);
-      var bu = (Bumpiness - other.Bumpiness);
-      var fl = (Flatness - other.Flatness);
-      var se = (Steadiness - other.Steadiness);
-      return sa * sa + bu * bu + fl * fl + se * se;
+      return FeatureValues.Select((v, i) => (v - other.FeatureValues[i]) * (v - other.FeatureValues[i])).Sum();
     }
 
@@ -69 +82 @@
     }
   }
+
+  public class InstancesStandardizer {
+    private double[] featureMeans;
+    private double[] featureStdevs;
+
+    private InstancesStandardizer() { }
+
+    public static InstancesStandardizer Create(IList<InstanceDescriptor> instances) {
+      var standardizer = new InstancesStandardizer();
+      var featureLength = instances.First().FeatureValues.Length;
+      standardizer.featureMeans =
+        Enumerable.Range(0, featureLength)
+        .Select(x => instances.Select(y => y.FeatureValues[x]).Average()).ToArray();
+      standardizer.featureStdevs =
+        Enumerable.Range(0, featureLength)
+        .Select(x => instances.Select(y => y.FeatureValues[x]).StandardDeviation()).ToArray();
+
+      return standardizer;
+    }
+
+    public void Apply(IList<InstanceDescriptor> instances) {
+      for (var i = 0; i < instances.Count; i++) {
+        var inst = instances[i];
+        for (var x = 0; x < featureMeans.Length; x++)
+          inst.FeatureValues[x] = (inst.FeatureValues[x] - featureMeans[x]) / featureStdevs[x];
+      }
+    }
+  }
 }

branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj

@@ -23 +23 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
@@ -32 +33 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
   </PropertyGroup>
   <ItemGroup>
@@ -67 +69 @@
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Selection-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Selection-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.SequentialEngine-3.3">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.SequentialEngine-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -78 +87 @@
   <ItemGroup>
     <Compile Include="InstanceDescriptor.cs" />
+    <Compile Include="InstanceExplorer.cs" />
     <Compile Include="Program.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
@@ -85 +95 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.MemPR\3.3\HeuristicLab.Algorithms.MemPR-3.3.csproj">
+      <Project>{9d274421-6332-4fbc-aae4-467ace27c368}</Project>
+      <Name>HeuristicLab.Algorithms.MemPR-3.3</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Analysis.FitnessLandscape\3.3\HeuristicLab.Analysis.FitnessLandscape-3.3.csproj">
       <Project>{5fbdcd4a-3c2a-4ec6-83ce-34b29f43621a}</Project>

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