Changeset 15031


Ignore:
Timestamp:
06/10/17 23:19:11 (4 months ago)
Author:
abeham
Message:

#2457: worked on code for eurocast paper

Location:
branches/PerformanceComparison
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/UpDownWalkCalculator.cs

    r13920 r15031  
    5858      characteristics = cloner.Clone(original.characteristics);
    5959    }
    60     public UpDownWalkCalculator() {
     60    public UpDownWalkCalculator() : this(new UpDownWalk()) { }
     61    public UpDownWalkCalculator(UpDownWalk walker) {
    6162      Name = ItemName;
    6263      Description = ItemDescription;
    63       walker = new UpDownWalk();
     64      this.walker = walker;
    6465      characteristics = new CheckedItemList<StringValue>(
    6566        new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent",
  • branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

    r14691 r15031  
    7979    private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
    8080    public QAPDirectedWalk() {
    81       characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness", /*"Swap2.Steadiness"*/ }
     81      characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }
    8282        .Select(x => new StringValue(x)).ToList());
    8383      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)));
     
    9898      IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
    9999      var qap = (QuadraticAssignmentProblem)Problem;
    100       var pathCount = Paths;
    101 
     100      List<Permutation> permutations = CalculateRelinkingPoints(random, qap, Paths, LocalOptima);
     101
     102      var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
     103      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
     104
     105      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
     106        if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
     107        if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
     108        if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
     109      }
     110    }
     111
     112    public static List<Permutation> CalculateRelinkingPoints(IRandom random, QuadraticAssignmentProblem qap, int pathCount, bool localOptima) {
    102113      var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
    103       if (LocalOptima) {
     114      if (localOptima) {
    104115        var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
    105116        QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     
    109120        perm = (Permutation)permutations.Last().Clone();
    110121        BiasedShuffle(perm, random);
    111         if (LocalOptima) {
     122        if (localOptima) {
    112123          var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
    113124          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
     
    117128      }
    118129
    119       var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
    120       var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
    121      
    122       foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
    123         if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
    124         if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
    125         if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
    126       }
     130      return permutations;
    127131    }
    128132
  • branches/PerformanceComparison/HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs

    r14691 r15031  
    22using System.Collections.Generic;
    33using System.Linq;
    4 using System.Text;
    5 using System.Threading.Tasks;
     4using System.Text.RegularExpressions;
    65
    76namespace HeuristicLab.Problems.Instances.QAPLIB {
     
    98    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    109      var drezner = new DreznerQAPInstanceProvider();
    11       foreach (var desc in drezner.GetDataDescriptors())
    12         yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, drezner, desc);
     10      foreach (var desc in drezner.GetDataDescriptors()) {
     11        var dim = int.Parse(Regex.Match(desc.Name, "dre(?<g>\\d+)").Groups["g"].Value);
     12        if (dim < 25) continue;
     13        yield return new OneSizeDataDescriptor(desc.Name + (dim == 25 ? "" : "-25"), desc.Description, drezner, desc);
     14      }
     15      // Microarray instances are all greater than 25 dimensions
    1316      var microarray = new MicroarrayQAPInstanceProvider();
    14       foreach (var desc in microarray.GetDataDescriptors())
     17      foreach (var desc in microarray.GetDataDescriptors()) {
    1518        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, microarray, desc);
     19      }
    1620      var qaplib = new QAPLIBInstanceProvider();
    17       foreach (var desc in qaplib.GetDataDescriptors())
    18         yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, qaplib, desc);
     21      foreach (var desc in qaplib.GetDataDescriptors()) {
     22        var instance = qaplib.LoadData(desc);
     23        if (instance.Dimension < 25) continue;
     24        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == 25 ? "" : "-25"), desc.Description, qaplib, desc);
     25      }
     26      // Taillard's instances are basically from the same distribution
     27      // to avoid over-representation in the set only the tai27e are taken and reduced to 25 dimension
    1928      var taillard = new TaillardQAPInstanceProvider();
    20       foreach (var desc in taillard.GetDataDescriptors())
     29      foreach (var desc in taillard.GetDataDescriptors()) {
     30        if (!desc.Name.StartsWith("tai27e")) continue;
    2131        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, taillard, desc);
     32      }
    2233    }
    2334
     
    5970      data.Dimension = 25;
    6071      data.Name += "-25";
    61       data.Description += " (reduced or enlarged to 25 dimensions)";
     72      data.Description += " (reduced to 25 dimensions)";
    6273
    6374      return data;
     
    6879    public override Uri WebLink { get { return null; } }
    6980    public override string ReferencePublication { get { return string.Empty; } }
    70 
    71     // permutation must be strictly different in every position
     81   
    7282    private static void Shuffle(int[] p, Random random) {
    7383      for (var i = p.Length - 1; i > 0; i--) {
    74         // Swap element "i" with a random earlier element (excluding itself)
    7584        var swapIndex = random.Next(i + 1);
    7685        var h = p[swapIndex];
  • branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs

    r14691 r15031  
    22using System.Collections.Generic;
    33using System.Linq;
     4using System.Text.RegularExpressions;
    45using HeuristicLab.Analysis.FitnessLandscape;
    56using HeuristicLab.Common;
    6 using HeuristicLab.Data;
    77using HeuristicLab.Encodings.PermutationEncoding;
    88using HeuristicLab.Problems.QuadraticAssignment;
     
    6868          break;
    6969        case "tai":
    70           if (char.IsLetter(subCls)) cls += "-" + subCls;
     70          if (Regex.IsMatch(name, "tai\\d+e\\d+")) cls += "-e";
     71          else if (char.IsLetter(subCls)) cls += "-" + subCls;
    7172          break;
    7273      }
  • branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs

    r14776 r15031  
    11using System;
    22using System.Linq;
    3 using System.Threading;
    43using HeuristicLab.Algorithms.MemPR.Permutation;
    54using HeuristicLab.Analysis.FitnessLandscape;
     
    76using HeuristicLab.Encodings.PermutationEncoding;
    87using HeuristicLab.Problems.QuadraticAssignment;
     8using HeuristicLab.Random;
    99using HeuristicLab.SequentialEngine;
    1010
     
    4545  }
    4646
     47  public class PathRelinkingOldFeaturedExplorer : InstanceExplorer {
     48    public int Paths { get; set; }
     49    public bool LocalOptima { get; set; }
     50
     51    public override string Name { get { return "Path-Relinking Explorer"; } }
     52    public override int Effort { get { return Paths; } }
     53
     54    public PathRelinkingOldFeaturedExplorer() {
     55
     56    }
     57
     58    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
     59      var random = new MersenneTwister();
     60      var samples = QAPDirectedWalk.CalculateRelinkingPoints(random, problem, Paths, LocalOptima);
     61      var trajectories = QAPDirectedWalk.Run(random, problem, samples);
     62
     63      double avgAc1 = 0, avgCorLen = 0, avgIc = 0, avgDbi = 0, avgPic = 0, avgIs = 0, avgDiv = 0,
     64        avgReg = 0, avgEnt = 0, avgPkIc = 0, avgPkDbi = 0;
     65      int count = 0;
     66      foreach (var t in trajectories) {
     67        var trail = t.Select(x => x.Item2).ToArray();
     68        if (trail.Length < 4) continue;
     69        count++;
     70        double[] acf;
     71        var len = RuggednessCalculator.CalculateCorrelationLength(trail, out acf);
     72        avgAc1 += acf[0];
     73        avgCorLen += len;
     74        var analysis = new InformationAnalysis(trail, 20, 2);
     75        avgIc += analysis.InformationContent[0];
     76        avgDbi += analysis.DensityBasinInformation[0];
     77        avgPic += analysis.PartialInformationContent[0];
     78        avgIs += analysis.InformationStability;
     79        avgDiv += analysis.Diversity;
     80        avgReg += analysis.Regularity;
     81        avgEnt += analysis.TotalEntropy[0];
     82        avgPkIc += analysis.PeakInformationContent.Value;
     83        avgPkDbi += analysis.PeakDensityBasinInformation.Value;
     84      }
     85      avgAc1 /= count;
     86      avgCorLen /= count;
     87      avgIc /= count;
     88      avgDbi /= count;
     89      avgPic /= count;
     90      avgIs /= count;
     91      avgDiv /= count;
     92      avgReg /= count;
     93      avgEnt /= count;
     94      avgPkIc /= count;
     95      avgPkDbi /= count;
     96
     97      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
     98        new[] { "Autocorrelation(1)", "CorrelationLength", "InformationContent", "DensityBasinInformation",
     99          "PartialInformationContent", "InformationStability", "Diversity", "Regularity", "TotalEntropy",
     100          "PeakInformationContent", "PeakDensityBasinInformation" },
     101        new[] { avgAc1, avgCorLen, avgIc, avgDbi,
     102          avgPic, avgIs, avgDiv, avgReg, avgEnt,
     103          avgPkIc, avgPkDbi });
     104    }
     105  }
     106
    47107
    48108  public class RandomWalkExplorer : InstanceExplorer {
     
    76136  public class AdaptiveWalkExplorer : InstanceExplorer {
    77137    public int Iterations { get; set; }
     138    public int SampleSize { get; set; }
    78139
    79140    public override string Name { get { return "Adaptive-Walk Explorer"; } }
    80     public override int Effort { get { return Iterations; } }
     141    public override int Effort { get { return Iterations * SampleSize; } }
    81142
    82143    public AdaptiveWalkExplorer() {
     
    87148      var walk = new AdaptiveWalk() {
    88149        SeedParameter = { Value = { Value = seed ?? 0 } },
    89         SetSeedRandomlyParameter = { Value = { Value = seed.HasValue } },
     150        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
    90151        MaximumIterationsParameter = { Value = { Value = Iterations } },
    91         RepetitionsParameter = { Value = { Value = 1 } }
     152        RepetitionsParameter = { Value = { Value = 1 } },
     153        SampleSizeParameter = { Value = { Value = SampleSize } }
    92154      };
    93155      walk.Problem = problem;
     
    95157      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
    96158      var calculator = new AdaptiveWalkCalculator(walk) { Problem = problem };
     159      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
     160
     161      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
     162        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
     163    }
     164  }
     165
     166  public class UpDownWalkExplorer : InstanceExplorer {
     167    public int Iterations { get; set; }
     168    public int SampleSize { get; set; }
     169
     170    public override string Name { get { return "Up/Down-Walk Explorer"; } }
     171    public override int Effort { get { return Iterations * SampleSize; } }
     172
     173    public UpDownWalkExplorer() {
     174
     175    }
     176
     177    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
     178      var walk = new UpDownWalk() {
     179        SeedParameter = { Value = { Value = seed ?? 0 } },
     180        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
     181        MaximumIterationsParameter = { Value = { Value = Iterations } },
     182        RepetitionsParameter = { Value = { Value = 1 } },
     183        SampleSizeParameter = { Value = { Value = SampleSize } }
     184      };
     185      walk.Problem = problem;
     186      walk.Engine = new SequentialEngine();
     187      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
     188      var calculator = new UpDownWalkCalculator(walk) {  Problem = problem };
    97189      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
    98190
  • branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj

    r14690 r15031  
    5050    <Reference Include="HeuristicLab.Encodings.PermutationEncoding-3.3">
    5151      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.PermutationEncoding-3.3.dll</HintPath>
     52    </Reference>
     53    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec">
     54      <Private>True</Private>
    5255    </Reference>
    5356    <Reference Include="HeuristicLab.Persistence-3.3">
  • branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs

    r14776 r15031  
    1212namespace ProblemInstanceIdentifier {
    1313  class Program {
     14    static void Main(string[] args) {
     15      //var instances = Get20DifferentClasses();
     16      var instances = GetSomeRandomInstances(50, 13);
     17
     18      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
     19      foreach (var cls in classes.OrderBy(x => x.Key)) {
     20        Console.WriteLine("{0};{1}", cls.Key, cls.Count());
     21      }*/
     22
     23      var prExplorer = new PathRelinkingExplorer() {
     24        LocalOptima = false,
     25        Paths = 200
     26      };
     27      var prOldExplorer = new PathRelinkingOldFeaturedExplorer() {
     28        LocalOptima = false,
     29        Paths = 200
     30      };
     31
     32      var prLocalExplorer = new PathRelinkingExplorer() {
     33        LocalOptima = true,
     34        Paths = 200
     35      };
     36      var prOldLocalExplorer = new PathRelinkingOldFeaturedExplorer() {
     37        LocalOptima = true,
     38        Paths = 200
     39      };
     40
     41      var memPrExplorer = new MemPRExplorer() {
     42        IncludeLocalSearch = false,
     43        Seconds = 10
     44      };
     45
     46      //var training = GenerateData(instances, prOldExplorer, parallel: true);
     47      //var standardizer = InstancesStandardizer.CreateAndApply(training);
     48      //var test = GenerateData(instances, prOldExplorer, parallel: true);
     49      //standardizer.Apply(test);
     50      //PrintMatchResult(Compare(training, test));
     51
     52      //Console.WriteLine("=== Path Relinking Walk ===");
     53      //ExploreMatching(instances,
     54      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
     55      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
     56      //parallel: true);
     57      //Console.WriteLine("=== Random Walk ===");
     58      //ExploreMatching(instances,
     59      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
     60      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
     61      //parallel: true);
     62      //Console.WriteLine("=== Adaptive Walk ===");
     63      //ExploreMatching(instances,
     64      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
     65      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
     66      //parallel: true);
     67      Console.WriteLine("=== Up/Down Walk ===");
     68      ExploreMatching(instances,
     69      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
     70      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
     71      parallel: true);
     72    }
     73
     74    private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances, int seed) {
     75      var sync = new object();
     76      var provider = new OneSizeInstanceProvider();
     77      var instances = new List<QuadraticAssignmentProblem>();
     78      var random = new FastRandom(seed);
     79      Parallel.ForEach(provider.GetDataDescriptors().Shuffle(random), desc => {
     80        var qapData = provider.LoadData(desc);
     81        if (instances.Count >= totalInstances) return;
     82        var qap = new QuadraticAssignmentProblem();
     83        qap.Load(qapData);
     84        lock (sync) {
     85          if (instances.Count >= totalInstances) return;
     86          instances.Add(qap);
     87        }
     88      });
     89      return instances;
     90    }
     91
    1492    private static HashSet<string> selectedInstances = new HashSet<string>() {
    1593      "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
     
    1795      "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
    1896    };
    19     static void Main(string[] args) {
    20       var instances = Get20DifferentClasses();
    21       //var instances = GetSomeRandomInstances(50);
    22 
    23       /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
    24       foreach (var cls in classes.OrderBy(x => x.Key)) {
    25         Console.WriteLine("{0};{1}", cls.Key, cls.Count());
    26       }*/
    27 
    28       var prExplorer = new PathRelinkingExplorer() {
    29         LocalOptima = false,
    30         Paths = 200
    31       };
    32       var prLocalExplorer = new PathRelinkingExplorer() {
    33         LocalOptima = true,
    34         Paths = 200
    35       };
    36       var memPrExplorer = new MemPRExplorer() {
    37         IncludeLocalSearch = false,
    38         Seconds = 10
    39       };
    40 
    41       var training = GenerateData(instances, prExplorer, parallel:true);
    42       var standardizer = InstancesStandardizer.CreateAndApply(training);
    43       var test = GenerateData(instances, prExplorer, parallel: false);
    44       standardizer.Apply(test);
    45       PrintMatchResult(Compare(training, test));
    46 
    47       ExploreMatching(instances, new [] { prLocalExplorer }, new [] { memPrExplorer });
    48     }
    49 
    50     private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances) {
    51       var sync = new object();
    52       var provider = new OneSizeInstanceProvider();
    53       var instances = new List<QuadraticAssignmentProblem>();
    54       var random = new FastRandom(0);
    55       Parallel.ForEach(provider.GetDataDescriptors().Shuffle(random), desc => {
    56         var qapData = provider.LoadData(desc);
    57         if (qapData.Dimension < 25) return;
    58         if (instances.Count >= totalInstances) return;
    59         var qap = new QuadraticAssignmentProblem();
    60         qap.Load(qapData);
    61         lock (sync) {
    62           if (instances.Count >= totalInstances) return;
    63           instances.Add(qap);
    64         }
    65       });
    66       return instances;
    67     }
    68 
    6997    private static List<QuadraticAssignmentProblem> Get20DifferentClasses() {
    7098      var sync = new object();
     
    100128      };
    101129      if (parallel) {
    102         Parallel.ForEach(instances, body);
     130        Parallel.ForEach(instances.Select(x => (QuadraticAssignmentProblem)x.Clone()), body);
    103131      } else {
    104132        foreach (var qap in instances) body(qap);
     
    156184    private static void ExploreMatching(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] trainingExplorers, InstanceExplorer[] testExporers, bool parallel = false) {
    157185      var sync = new object();
    158       var rand = new Random();
    159       var first = rand.Next();
    160       var second = rand.Next();
    161       while (first == second) second = rand.Next();
    162186
    163187      var knowledgeBase = new Dictionary<InstanceExplorer, Tuple<InstancesStandardizer, List<InstanceDescriptor>>>();
Note: See TracChangeset for help on using the changeset viewer.