Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/15/15 16:38:08 (8 years ago)
Author:
abeham
Message:

#2221:

  • implemented review comments
    • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
    • added missing probabilities
    • base class for instance providers
    • prebuild event events
    • build platforms
    • unit test will be removed on trunk integration
    • corrected assembly file version
    • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
    • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
  • added moves (full evaluation) for analytical tsp
  • added local improvement operators for analytical ptsp
  • added recalculation of distance matrix when parameters change
  • still lots of other changes
Location:
branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3
Files:
1 deleted
3 edited
1 copied

Legend:

Unmodified
Added
Removed

  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj

    r13412 r13470  
    123123  </ItemGroup>
    124124  <ItemGroup>
    125     <Compile Include="MarsagliaRandom.cs" />
    126125    <Compile Include="TSPLIBHeterogeneousPTSPDataDescriptor.cs" />
    127126    <Compile Include="TSPLIBHomogeneousPTSPDataDescriptor.cs" />
    128127    <Compile Include="TSPLIBHeterogeneousPTSPInstanceProvider.cs" />
     128    <Compile Include="TSPLIBPTSPInstanceProvider.cs" />
    129129    <Compile Include="TSPLIBInstanceProvider.cs" />
    130130    <Compile Include="TSPLIBATSPInstanceProvider.cs" />

  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHeterogeneousPTSPInstanceProvider.cs

    r13412 r13470  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.IO;
    2524using System.Linq;
    2625
    2726namespace HeuristicLab.Problems.Instances.TSPLIB {
    28   public class TSPLIBHeterogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
     27  public class TSPLIBHeterogeneousPTSPInstanceProvider : TSPLIBPTSPInstanceProvider {
    2928
    3029    public override string Name {
    … …  
    3231    }
    3332
    34     public override string Description {
    35       get { return "Traveling Salesman Problem Library"; }
    36     }
    37 
    38     protected override string FileExtension { get { return "tsp"; } }
    39 
    4033    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    4134      foreach (var desc in base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>()) {
    42         desc.Name += " [0.1;0.9]";
    4335        desc.SolutionIdentifier = null;
    4436        yield return desc;
    … …  
    4638    }
    4739
    48     protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    49       parser.Parse();
    50       if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
    51       var instance = new PTSPData();
    52       instance.Dimension = parser.Dimension;
    53       instance.Coordinates = parser.Vertices != null ? parser.Vertices : parser.DisplayVertices;
    54       instance.Distances = parser.Distances;
    55       switch (parser.EdgeWeightType) {
    56         case TSPLIBEdgeWeightTypes.ATT:
    57           instance.DistanceMeasure = DistanceMeasure.Att; break;
    58         case TSPLIBEdgeWeightTypes.CEIL_2D:
    59           instance.DistanceMeasure = DistanceMeasure.UpperEuclidean; break;
    60         case TSPLIBEdgeWeightTypes.EUC_2D:
    61           instance.DistanceMeasure = DistanceMeasure.RoundedEuclidean; break;
    62         case TSPLIBEdgeWeightTypes.EUC_3D:
    63           throw new InvalidDataException("3D coordinates are not supported.");
    64         case TSPLIBEdgeWeightTypes.EXPLICIT:
    65           instance.DistanceMeasure = DistanceMeasure.Direct; break;
    66         case TSPLIBEdgeWeightTypes.GEO:
    67           instance.DistanceMeasure = DistanceMeasure.Geo; break;
    68         case TSPLIBEdgeWeightTypes.MAN_2D:
    69           instance.DistanceMeasure = DistanceMeasure.Manhattan; break;
    70         case TSPLIBEdgeWeightTypes.MAN_3D:
    71           throw new InvalidDataException("3D coordinates are not supported.");
    72         case TSPLIBEdgeWeightTypes.MAX_2D:
    73           instance.DistanceMeasure = DistanceMeasure.Maximum; break;
    74         case TSPLIBEdgeWeightTypes.MAX_3D:
    75           throw new InvalidDataException("3D coordinates are not supported.");
    76         default:
    77           throw new InvalidDataException("The given edge weight is not supported by HeuristicLab.");
     40    protected override double[] GetProbabilities(IDataDescriptor descriptor, PTSPData instance) {
     41      var random = new MarsagliaRandom(GetInstanceHash(instance.Name));
     42      return Enumerable.Range(0, instance.Dimension).Select(_ => (int)Math.Round((0.1 + 0.9 * random.NextDouble()) * 100) / 100.0).ToArray();
     43    }
     44
     45    // Bernstein's hash function
     46    private uint GetInstanceHash(string name) {
     47      uint hash = 5381;
     48      var len = name.Length;
     49      for (var i = 0; i < len; i++)
     50        unchecked { hash = ((hash * 33) + name[i]); }
     51      return hash;
     52    }
     53
     54    /// <summary>
     55    /// This class is used to randomly generate PTSP instances given the TSPLIB instances.
     56    /// An own implementation of a RNG was used in order to avoid possible implementation changes
     57    /// in future .NET versions which would result in entirely different instances.
     58    /// </summary>
     59    /// <remarks>
     60    /// RNG is implemented according to George Marsaglia https://en.wikipedia.org/wiki/Multiply-with-carry
     61    /// </remarks>
     62    private class MarsagliaRandom {
     63      /*
     64       * S = 2111111111*X[n-4] + 1492*X[n-3] + 1776*X[n-2] + 5115*X[n-1] + C
     65       * X[n] = S modulo 2^32
     66       * C = floor(S / 2^32)
     67       *
     68       */
     69      private readonly uint[] mem = new uint[4];
     70      private uint c;
     71
     72      public MarsagliaRandom(uint s) {
     73        int i;
     74        for (i = 0; i < mem.Length; i++) {
     75          unchecked { s = s * 31294061 + 1; }
     76          mem[i] = s;
     77        }
     78        unchecked { c = s * 31294061 + 1; }
    7879      }
    7980
    80       instance.Name = parser.Name;
    81       instance.Description = parser.Comment
    82         + Environment.NewLine + Environment.NewLine
    83         + GetInstanceDescription();
     81      private uint Next() {
     82        unchecked {
     83          ulong wsum = 2111111111 * mem[0]
     84                      + 1492 * mem[1]
     85                      + 1776 * mem[2]
     86                      + 5115 * mem[3]
     87                      + c;
    8488
    85       var random = new MarsagliaRandom((uint)(descriptor != null ? descriptor.Name : instance.Name).GetHashCode());
    86       instance.Probabilities = Enumerable.Range(0, instance.Dimension).Select(_ => 0.1 + 0.9 * random.NextDouble()).ToArray();
     89          mem[0] = mem[1];
     90          mem[1] = mem[2];
     91          mem[2] = mem[3];
     92          mem[3] = (uint)wsum;
     93          c = (uint)(wsum >> 32);
     94          return mem[3];
     95        }
     96      }
    8797
    88       return instance;
     98      public double NextDouble() {
     99        return (double)Next() / uint.MaxValue;
     100      }
    89101    }
    90 
    91     protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
    92       parser.Parse();
    93       instance.BestKnownTour = parser.Tour.FirstOrDefault();
    94     }
    95 
    96     public PTSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
    97       var data = LoadInstance(new TSPLIBParser(tspFile));
    98       if (!String.IsNullOrEmpty(tourFile)) {
    99         var tourParser = new TSPLIBParser(tourFile);
    100         LoadSolution(tourParser, data);
    101       }
    102       if (bestQuality.HasValue)
    103         data.BestKnownQuality = bestQuality.Value;
    104       return data;
    105     }
    106 
    107102  }
    108103}

  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHomogeneousPTSPInstanceProvider.cs

    r13412 r13470  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    2423using System.Globalization;
    25 using System.IO;
    2624using System.Linq;
    2725
    2826namespace HeuristicLab.Problems.Instances.TSPLIB {
    29   public class TSPLIBHomogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
    30     private static readonly double[] probabilities = new[] { 0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0 };
     27  public class TSPLIBHomogeneousPTSPInstanceProvider : TSPLIBPTSPInstanceProvider {
     28    private static readonly double[] Probabilities = new[] { 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0 };
    3129
    3230    public override string Name {
    … …  
    3432    }
    3533
    36     public override string Description {
    37       get { return "Traveling Salesman Problem Library"; }
    38     }
    39 
    40     protected override string FileExtension { get { return "tsp"; } }
    41 
    4234    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    4335      var tspDescriptors = base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>();
    4436      foreach (var desc in tspDescriptors) {
    45         foreach (var p in probabilities) {
     37        foreach (var p in Probabilities) {
    4638          yield return new TSPLIBHomogeneousPTSPDataDescriptor(
    4739            desc.Name + "-" + p.ToString(CultureInfo.InvariantCulture.NumberFormat),
    … …  
    5446    }
    5547
    56     protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    57       parser.Parse();
    58       if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
    59       var instance = new PTSPData();
    60       instance.Dimension = parser.Dimension;
    61       instance.Coordinates = parser.Vertices != null ? parser.Vertices : parser.DisplayVertices;
    62       instance.Distances = parser.Distances;
    63       switch (parser.EdgeWeightType) {
    64         case TSPLIBEdgeWeightTypes.ATT:
    65           instance.DistanceMeasure = DistanceMeasure.Att; break;
    66         case TSPLIBEdgeWeightTypes.CEIL_2D:
    67           instance.DistanceMeasure = DistanceMeasure.UpperEuclidean; break;
    68         case TSPLIBEdgeWeightTypes.EUC_2D:
    69           instance.DistanceMeasure = DistanceMeasure.RoundedEuclidean; break;
    70         case TSPLIBEdgeWeightTypes.EUC_3D:
    71           throw new InvalidDataException("3D coordinates are not supported.");
    72         case TSPLIBEdgeWeightTypes.EXPLICIT:
    73           instance.DistanceMeasure = DistanceMeasure.Direct; break;
    74         case TSPLIBEdgeWeightTypes.GEO:
    75           instance.DistanceMeasure = DistanceMeasure.Geo; break;
    76         case TSPLIBEdgeWeightTypes.MAN_2D:
    77           instance.DistanceMeasure = DistanceMeasure.Manhattan; break;
    78         case TSPLIBEdgeWeightTypes.MAN_3D:
    79           throw new InvalidDataException("3D coordinates are not supported.");
    80         case TSPLIBEdgeWeightTypes.MAX_2D:
    81           instance.DistanceMeasure = DistanceMeasure.Maximum; break;
    82         case TSPLIBEdgeWeightTypes.MAX_3D:
    83           throw new InvalidDataException("3D coordinates are not supported.");
    84         default:
    85           throw new InvalidDataException("The given edge weight is not supported by HeuristicLab.");
    86       }
    87 
    88       instance.Name = parser.Name;
    89       instance.Description = parser.Comment
    90         + Environment.NewLine + Environment.NewLine
    91         + GetInstanceDescription();
     48    protected override double[] GetProbabilities(IDataDescriptor descriptor, PTSPData instance) {
    9249      var ptspDesc = descriptor as TSPLIBHomogeneousPTSPDataDescriptor;
    93       instance.Probabilities = ptspDesc != null ? Enumerable.Range(0, instance.Dimension).Select(_ => ptspDesc.Probability).ToArray()
    94                                                 : Enumerable.Range(0, instance.Dimension).Select(_ => 0.5).ToArray();
    95 
    96       return instance;
     50      return ptspDesc != null ? Enumerable.Range(0, instance.Dimension).Select(_ => ptspDesc.Probability).ToArray()
     51                              : Enumerable.Range(0, instance.Dimension).Select(_ => 0.5).ToArray();
    9752    }
    98 
    99     protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
    100       parser.Parse();
    101       instance.BestKnownTour = parser.Tour.FirstOrDefault();
    102     }
    103 
    104     public PTSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
    105       var data = LoadInstance(new TSPLIBParser(tspFile));
    106       if (!String.IsNullOrEmpty(tourFile)) {
    107         var tourParser = new TSPLIBParser(tourFile);
    108         LoadSolution(tourParser, data);
    109       }
    110       if (bestQuality.HasValue)
    111         data.BestKnownQuality = bestQuality.Value;
    112       return data;
    113     }
    114 
    11553  }
    11654}

  • branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBPTSPInstanceProvider.cs

    r13451 r13470  
    2121
    2222using System;
    23 using System.Collections.Generic;
    24 using System.Globalization;
    2523using System.IO;
    2624using System.Linq;
    2725
    2826namespace HeuristicLab.Problems.Instances.TSPLIB {
    29   public class TSPLIBHomogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
    30     private static readonly double[] probabilities = new[] { 0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0 };
    31 
    32     public override string Name {
    33       get { return "TSPLIB (homogeneous symmetric PTSP)"; }
    34     }
     27  public abstract class TSPLIBPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
    3528
    3629    public override string Description {
    37       get { return "Traveling Salesman Problem Library"; }
     30      get { return "Traveling Salesman Problem Library (adapted for generating PTSP instances)"; }
    3831    }
    3932
    4033    protected override string FileExtension { get { return "tsp"; } }
    41 
    42     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    43       var tspDescriptors = base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>();
    44       foreach (var desc in tspDescriptors) {
    45         foreach (var p in probabilities) {
    46           yield return new TSPLIBHomogeneousPTSPDataDescriptor(
    47             desc.Name + "-" + p.ToString(CultureInfo.InvariantCulture.NumberFormat),
    48             desc.Description,
    49             desc.InstanceIdentifier,
    50             p == 1.0 ? desc.SolutionIdentifier : null,
    51             p);
    52         }
    53       }
    54     }
    5534
    5635    protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
    … …  
    9069        + Environment.NewLine + Environment.NewLine
    9170        + GetInstanceDescription();
    92       var ptspDesc = descriptor as TSPLIBHomogeneousPTSPDataDescriptor;
    93       instance.Probabilities = ptspDesc != null ? Enumerable.Range(0, instance.Dimension).Select(_ => ptspDesc.Probability).ToArray()
    94                                                 : Enumerable.Range(0, instance.Dimension).Select(_ => 0.5).ToArray();
    9571
     72      instance.Probabilities = GetProbabilities(descriptor, instance);
    9673      return instance;
    9774    }
     75
     76    protected abstract double[] GetProbabilities(IDataDescriptor descriptor, PTSPData instance);
    9877
    9978    protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
Note: See TracChangeset for help on using the changeset viewer.