Changeset 13470 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

Timestamp:

12/15/15 16:38:08 (9 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

File:

• branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs (modified) (6 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -35 +36 @@
   public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
   IProblemInstanceConsumer<PTSPData> {
+    protected bool SuppressEvents { get; set; }
+
     private static readonly int DistanceMatrixSizeLimit = 1000;
 
@@ -92 +95 @@
     [StorableConstructor]
     protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
-    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
+    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
+      : base(original, cloner) {
+      RegisterEventHandlers();
+    }
     protected ProbabilisticTravelingSalesmanProblem() {
       Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
@@ -101 +107 @@
       Parameters.Add(new ValueParameter<DoubleArray>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
 
-      Coordinates = new DoubleMatrix(new double[,] {
+      var coordinates = new DoubleMatrix(new double[,] {
         { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
         { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
@@ -107 +113 @@
         { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
       });
-
-      Probabilities = new DoubleArray(new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
+      Coordinates = coordinates;
+      Encoding.Length = coordinates.Rows;
+      DistanceCalculator = new EuclideanDistance();
+      DistanceMatrix = new DistanceMatrix(CalculateDistances());
+      Probabilities = new DoubleArray(Enumerable.Range(0, coordinates.Rows).Select(x => 0.5).ToArray());
+
+      RegisterEventHandlers();
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEventHandlers();
+    }
+
+    private void RegisterEventHandlers() {
+      CoordinatesParameter.ValueChanged += CoordinatesParameterOnValueChanged;
+      if (Coordinates != null) {
+        Coordinates.RowsChanged += CoordinatesOnChanged;
+        Coordinates.ItemChanged += CoordinatesOnChanged;
+      }
+      UseDistanceMatrixParameter.Value.ValueChanged += UseDistanceMatrixValueChanged;
+      DistanceCalculatorParameter.ValueChanged += DistanceCalculatorParameterOnValueChanged;
+    }
+
+    private void CoordinatesParameterOnValueChanged(object sender, EventArgs eventArgs) {
+      if (Coordinates != null) {
+        Coordinates.RowsChanged += CoordinatesOnChanged;
+        Coordinates.ItemChanged += CoordinatesOnChanged;
+      }
+      if (SuppressEvents) return;
+      UpdateInstance();
+    }
+
+    private void CoordinatesOnChanged(object sender, EventArgs eventArgs) {
+      if (SuppressEvents) return;
+      UpdateInstance();
+    }
+
+    private void UseDistanceMatrixValueChanged(object sender, EventArgs eventArgs) {
+      if (SuppressEvents) return;
+      UpdateInstance();
+    }
+
+    private void DistanceCalculatorParameterOnValueChanged(object sender, EventArgs eventArgs) {
+      if (SuppressEvents) return;
+      UpdateInstance();
     }
 
@@ -117 +167 @@
     public abstract double Evaluate(Permutation tour, IRandom random);
 
+    public double[,] CalculateDistances() {
+      var coords = Coordinates;
+      var len = coords.Rows;
+      var dist = DistanceCalculator;
+
+      var matrix = new double[len, len];
+      for (var i = 0; i < len - 1; i++)
+        for (var j = i + 1; j < len; j++)
+          matrix[i, j] = matrix[j, i] = dist.Calculate(i, j, coords);
+
+      return matrix;
+    }
+
     public virtual void Load(PTSPData data) {
-      if (data.Coordinates == null && data.Distances == null)
-        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
-      if (data.Dimension > DistanceMatrixSizeLimit && (data.Coordinates == null || data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
-        throw new System.IO.InvalidDataException("The given instance is too large for using a distance matrix and there is a problem with the coordinates.");
-      if (data.Coordinates != null && (data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
-        throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates respectively.");
-
-      switch (data.DistanceMeasure) {
-        case DistanceMeasure.Direct:
-          DistanceCalculator = null;
-          if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
-            DistanceCalculator = new EuclideanDistance();
-            UseDistanceMatrix = false;
-          } else UseDistanceMatrix = true;
-          break;
-        case DistanceMeasure.Att: DistanceCalculator = new AttDistance(); break;
-        case DistanceMeasure.Euclidean: DistanceCalculator = new EuclideanDistance(); break;
-        case DistanceMeasure.Geo: DistanceCalculator = new GeoDistance(); break;
-        case DistanceMeasure.Manhattan: DistanceCalculator = new ManhattanDistance(); break;
-        case DistanceMeasure.Maximum: DistanceCalculator = new MaximumDistance(); break;
-        case DistanceMeasure.RoundedEuclidean: DistanceCalculator = new RoundedEuclideanDistance(); break;
-        case DistanceMeasure.UpperEuclidean: DistanceCalculator = new UpperEuclideanDistance(); break;
-        default: throw new ArgumentException("Distance measure is unknown");
-      }
-
-      Name = data.Name;
-      Description = data.Description;
-
-      Probabilities = new DoubleArray(data.Probabilities);
-      BestKnownSolution = data.BestKnownTour != null ? new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour) : null;
-      Coordinates = data.Coordinates != null && data.Coordinates.GetLength(0) > 0 ? new DoubleMatrix(data.Coordinates) : null;
-      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
-
-      Encoding.Length = data.Dimension;
-
+      try {
+        SuppressEvents = true;
+        if (data.Coordinates == null && data.Distances == null)
+          throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
+        if (data.Dimension > DistanceMatrixSizeLimit && (data.Coordinates == null || data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
+          throw new System.IO.InvalidDataException("The given instance is too large for using a distance matrix and there is a problem with the coordinates.");
+        if (data.Coordinates != null && (data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
+          throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates respectively.");
+
+        switch (data.DistanceMeasure) {
+          case DistanceMeasure.Direct:
+            DistanceCalculator = null;
+            if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
+              DistanceCalculator = new EuclideanDistance();
+              UseDistanceMatrix = false;
+            } else UseDistanceMatrix = true;
+            break;
+          case DistanceMeasure.Att: DistanceCalculator = new AttDistance(); break;
+          case DistanceMeasure.Euclidean: DistanceCalculator = new EuclideanDistance(); break;
+          case DistanceMeasure.Geo: DistanceCalculator = new GeoDistance(); break;
+          case DistanceMeasure.Manhattan: DistanceCalculator = new ManhattanDistance(); break;
+          case DistanceMeasure.Maximum: DistanceCalculator = new MaximumDistance(); break;
+          case DistanceMeasure.RoundedEuclidean: DistanceCalculator = new RoundedEuclideanDistance(); break;
+          case DistanceMeasure.UpperEuclidean: DistanceCalculator = new UpperEuclideanDistance(); break;
+          default: throw new ArgumentException("Distance measure is unknown");
+        }
+
+        Name = data.Name;
+        Description = data.Description;
+
+        Probabilities = new DoubleArray(data.Probabilities);
+        BestKnownSolution = data.BestKnownTour != null ? new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour) : null;
+        Coordinates = data.Coordinates != null && data.Coordinates.GetLength(0) > 0 ? new DoubleMatrix(data.Coordinates) : null;
+        DistanceMatrix = data.Dimension <= DistanceMatrixSizeLimit && UseDistanceMatrix ? new DistanceMatrix(data.GetDistanceMatrix()) : null;
+
+        Encoding.Length = data.Dimension;
+      } finally { SuppressEvents = false; }
       OnReset();
+    }
+
+    private void UpdateInstance() {
+      var len = GetProblemDimension();
+      if (Coordinates != null && Coordinates.Rows <= DistanceMatrixSizeLimit
+        && DistanceCalculator != null && UseDistanceMatrix)
+        DistanceMatrix = new DistanceMatrix(CalculateDistances());
+      if (!UseDistanceMatrix) DistanceMatrix = null;
+      Encoding.Length = len;
+
+      OnReset();
+    }
+
+    private int GetProblemDimension() {
+      if (Coordinates == null && DistanceMatrix == null) throw new InvalidOperationException("Both coordinates and distance matrix are null, please specify at least one of them.");
+      return Coordinates != null ? Coordinates.Rows : DistanceMatrix.Rows;
     }
   }