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

Timestamp:

11/28/15 23:38:51 (8 years ago)

Author:

abeham

Message:

#2221:

• Completely refactored PTSP branch
  • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
  • Implemented missing EvaluateByCoordinates for 1-shift moves
  • Made it clear that move evaluators are for estimated PTSP only
  • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
  • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
  • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
  • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types

File:

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

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -30 +31 @@
 
 namespace HeuristicLab.Problems.PTSP {
-  [Item("Probabilistic Traveling Salesman Problem", "Represents a Probabilistic Traveling Salesman Problem.")]
+  [Item("Probabilistic Traveling Salesman Problem (PTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
   [StorableClass]
-  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
+  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
   IProblemInstanceConsumer<PTSPData> {
     private static readonly int DistanceMatrixSizeLimit = 1000;
@@ -40 +41 @@
       get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
     }
+    public OptionalValueParameter<DistanceCalculator> DistanceCalculatorParameter {
+      get { return (OptionalValueParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
+    }
     public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
       get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
     }
-    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
-      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
+    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     }
     public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
       get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     }
-    public ValueParameter<DoubleArray> ProbabilityMatrixParameter {
-      get { return (ValueParameter<DoubleArray>)Parameters["ProbabilityMatrix"]; }
+    public IValueParameter<DoubleArray> ProbabilitiesParameter {
+      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
     }
-
-
     #endregion
 
@@ -61 +63 @@
       set { CoordinatesParameter.Value = value; }
     }
+    public DistanceCalculator DistanceCalculator {
+      get { return DistanceCalculatorParameter.Value; }
+      set { DistanceCalculatorParameter.Value = value; }
+    }
     public DistanceMatrix DistanceMatrix {
       get { return DistanceMatrixParameter.Value; }
       set { DistanceMatrixParameter.Value = value; }
     }
-    public BoolValue UseDistanceMatrix {
-      get { return UseDistanceMatrixParameter.Value; }
-      set { UseDistanceMatrixParameter.Value = value; }
+    public bool UseDistanceMatrix {
+      get { return UseDistanceMatrixParameter.Value.Value; }
+      set { UseDistanceMatrixParameter.Value.Value = value; }
     }
     public Permutation BestKnownSolution {
@@ -73 +79 @@
       set { BestKnownSolutionParameter.Value = value; }
     }
-    public DoubleArray ProbabilityMatrix {
-      get { return ProbabilityMatrixParameter.Value; }
-      set { ProbabilityMatrixParameter.Value = value; }
+    public DoubleArray Probabilities {
+      get { return ProbabilitiesParameter.Value; }
+      set { ProbabilitiesParameter.Value = value; }
     }
 
     #endregion
-
 
     public override bool Maximization {
@@ -87 +92 @@
     [StorableConstructor]
     protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
-    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
-      : base(original, cloner) {
-    }
-
-    public ProbabilisticTravelingSalesmanProblem() {
+    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
+    protected ProbabilisticTravelingSalesmanProblem() {
       Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
+      Parameters.Add(new OptionalValueParameter<DistanceCalculator>("DistanceCalculator", "Calculates the distance between two rows in the coordinates matrix."));
       Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
-      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
       Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
-      Parameters.Add(new ValueParameter<DoubleArray>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
+      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[,] {
@@ -105 +108 @@
       });
 
-      ProbabilityMatrix = new DoubleArray(new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
+      Probabilities = new DoubleArray(new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
+    }
 
+    public override double Evaluate(Individual individual, IRandom random) {
+      return Evaluate(individual.Permutation(), random);
     }
+
+    public abstract double Evaluate(Permutation tour, IRandom random);
 
     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.DistanceMeasure == DistanceMeasure.Att
-        || data.DistanceMeasure == DistanceMeasure.Manhattan
-        || data.DistanceMeasure == DistanceMeasure.Maximum))
-        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
-      if (data.Coordinates != null && 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.");
+      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;
 
-      ProbabilityMatrix = new DoubleArray(data.Probabilities);
-
-      if (data.BestKnownTour != null) {
-        BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
-      }
-
+      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());