Changeset 17253 for branches/2521_ProblemRefactoring/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

Timestamp:

09/16/19 16:12:21 (5 years ago)

Author:

abeham

Message:

#2521: worked on refactoring PTSP

File:

• branches/2521_ProblemRefactoring/HeuristicLab.Problems.PTSP/3.3/PTSP.cs (modified) (3 diffs)

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

@@ -22 +22 @@
 using System;
 using System.Linq;
-using HeuristicLab.Analysis;
+using HEAL.Attic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -28 +28 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
-using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
-using HEAL.Attic;
 using HeuristicLab.Problems.Instances;
+using HeuristicLab.Problems.TravelingSalesman;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.PTSP {
-  [Item("Probabilistic Traveling Salesman Problem (PTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
-  [StorableType("4CB8ACF3-C3D4-4CC6-BB1F-986BDE16B30A")]
-  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
-  IProblemInstanceConsumer<PTSPData> {
+  [Item("Probabilistic TSP (p-TSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
+  [StorableType("86041a8c-14e6-46e1-b20f-566892c871f6")]
+  public abstract class ProbabilisticTSP : PermutationProblem,
+      IProblemInstanceConsumer<PTSPData> {
     protected bool SuppressEvents { get; set; }
 
-    private static readonly int DistanceMatrixSizeLimit = 1000;
+    public static int DistanceMatrixSizeLimit = 1000;
 
     #region Parameter Properties
-    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
-      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 IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
-      get { return (IFixedValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
-    }
-    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
-      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
-    }
-    public IValueParameter<DoubleArray> ProbabilitiesParameter {
-      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
-    }
+    [Storable] public ValueParameter<IProbabilisticTSPData> PTSPDataParameter { get; private set; }
+    [Storable] public OptionalValueParameter<ITSPSolution> BestKnownSolutionParameter { get; private set; }
     #endregion
 
     #region Properties
-    public DoubleMatrix Coordinates {
-      get { return CoordinatesParameter.Value; }
-      set { CoordinatesParameter.Value = value; }
+    public IProbabilisticTSPData ProbabilisticTSPData {
+      get { return PTSPDataParameter.Value; }
+      set { PTSPDataParameter.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 bool UseDistanceMatrix {
-      get { return UseDistanceMatrixParameter.Value.Value; }
-      set { UseDistanceMatrixParameter.Value.Value = value; }
-    }
-    public Permutation BestKnownSolution {
+    public ITSPSolution BestKnownSolution {
       get { return BestKnownSolutionParameter.Value; }
       set { BestKnownSolutionParameter.Value = value; }
     }
-    public DoubleArray Probabilities {
-      get { return ProbabilitiesParameter.Value; }
-      set { ProbabilitiesParameter.Value = value; }
-    }
-
     #endregion
 
@@ -96 +63 @@
 
     [StorableConstructor]
-    protected ProbabilisticTravelingSalesmanProblem(StorableConstructorFlag _) : base(_) { }
-    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
+    protected ProbabilisticTSP(StorableConstructorFlag _) : base(_) { }
+    protected ProbabilisticTSP(ProbabilisticTSP original, Cloner cloner)
       : base(original, cloner) {
-      RegisterEventHandlers();
+      PTSPDataParameter = cloner.Clone(original.PTSPDataParameter);
+      BestKnownSolutionParameter = cloner.Clone(original.BestKnownSolutionParameter);
     }
-    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 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>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
+    protected ProbabilisticTSP() {
+      Parameters.Add(PTSPDataParameter = new ValueParameter<IProbabilisticTSPData>("PTSP Data", "The main parameters for the p-TSP."));
+      Parameters.Add(BestKnownSolutionParameter = new OptionalValueParameter<ITSPSolution>("BestKnownSolution", "The best known solution of this p-TSP instance."));
 
-      var coordinates = new DoubleMatrix(new double[,] {
-        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
-        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
-        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
-        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
-      });
-      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());
-
-      InitializeOperators();
-      Parameterize();
-      RegisterEventHandlers();
-    }
-
-    private void InitializeOperators() {
-      Operators.Add(new HammingSimilarityCalculator());
-      Operators.Add(new QualitySimilarityCalculator());
-      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
-    }
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      RegisterEventHandlers();
+      ProbabilisticTSPData = new MatrixProbabilisticTSPData();
+      Encoding.Length = ProbabilisticTSPData.Cities;
     }
 
     protected override void OnEncodingChanged() {
       base.OnEncodingChanged();
-      Encoding.Length = Coordinates.Rows;
-      Parameterize();
+      Encoding.Length = ProbabilisticTSPData.Cities;
     }
 
-    private void RegisterEventHandlers() {
-      CoordinatesParameter.ValueChanged += CoordinatesParameterOnValueChanged;
-      if (Coordinates != null) {
-        Coordinates.RowsChanged += CoordinatesOnChanged;
-        Coordinates.ItemChanged += CoordinatesOnChanged;
+    public override void Analyze(Permutation[] solutions, double[] qualities, ResultCollection results, IRandom random) {
+      base.Analyze(solutions, qualities, results, random);
+      var max = Maximization;
+
+      var i = !max ? qualities.Select((x, index) => new { index, x }).OrderBy(x => x).First().index
+                   : qualities.Select((x, index) => new { index, x }).OrderByDescending(x => x).First().index;
+
+      if (double.IsNaN(BestKnownQuality) ||
+          max && qualities[i] > BestKnownQuality ||
+          !max && qualities[i] < BestKnownQuality) {
+        BestKnownQuality = qualities[i];
+        BestKnownSolution = ProbabilisticTSPData.GetSolution((Permutation)solutions[i].Clone(), qualities[i]);
       }
-      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();
-    }
-
-    public override double Evaluate(Individual individual, IRandom random) {
-      return Evaluate(individual.Permutation(), random);
-    }
-
-    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;
+      IResult bestSolutionResult;
+      if (results.TryGetValue("Best p-TSP Solution", out bestSolutionResult)) {
+        var bestSolution = bestSolutionResult.Value as ITSPSolution;
+        if (bestSolution == null || Maximization && bestSolution.TourLength.Value < qualities[i]
+          || !Maximization && bestSolution.TourLength.Value > qualities[i]) {
+          bestSolutionResult.Value = ProbabilisticTSPData.GetSolution(solutions[i], qualities[i]);
+        }
+      } else results.Add(new Result("Best p-TSP Solution", ProbabilisticTSPData.GetSolution(solutions[i], qualities[i])));
     }
 
     public virtual void Load(PTSPData data) {
-      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.");
+      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.");
 
+      Encoding.Length = data.Dimension;
+      Name = data.Name;
+      Description = data.Description;
+
+      if (data.Dimension <= DistanceMatrixSizeLimit) {
+        ProbabilisticTSPData = new MatrixProbabilisticTSPData(data.Name, data.GetDistanceMatrix(), data.Probabilities, data.Coordinates) { Description = data.Description };
+      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
+        ProbabilisticTSPData = new MatrixProbabilisticTSPData(data.Name, data.Distances, data.Probabilities, data.Coordinates) { Description = data.Description };
+      } else {
         switch (data.DistanceMeasure) {
-          case DistanceMeasure.Direct:
-            DistanceCalculator = null;
-            if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
-              DistanceCalculator = new EuclideanDistance();
-              UseDistanceMatrix = false;
-            } else UseDistanceMatrix = true;
+          case DistanceMeasure.Att:
+            ProbabilisticTSPData = new AttPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
             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");
+          case DistanceMeasure.Euclidean:
+            ProbabilisticTSPData = new EuclideanPTSPData(data.Name, data.Coordinates, data.Probabilities, EuclideanTSPData.DistanceRounding.None) { Description = data.Description };
+            break;
+          case DistanceMeasure.RoundedEuclidean:
+            ProbabilisticTSPData = new EuclideanPTSPData(data.Name, data.Coordinates, data.Probabilities, EuclideanTSPData.DistanceRounding.Midpoint) { Description = data.Description };
+            break;
+          case DistanceMeasure.UpperEuclidean:
+            ProbabilisticTSPData = new EuclideanPTSPData(data.Name, data.Coordinates, data.Probabilities, EuclideanTSPData.DistanceRounding.Ceiling) { Description = data.Description };
+            break;
+          case DistanceMeasure.Geo:
+            ProbabilisticTSPData = new GeoPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
+            break;
+          case DistanceMeasure.Manhattan:
+            ProbabilisticTSPData = new ManhattanPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
+            break;
+          case DistanceMeasure.Maximum:
+            ProbabilisticTSPData = new MaximumPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
+            break;
+          default:
+            throw new System.IO.InvalidDataException("An unknown distance measure is given in the instance!");
         }
+      }
+      BestKnownSolution = null;
+      BestKnownQuality = double.NaN;
 
-        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; }
+      if (data.BestKnownTour != null) {
+        try {
+          var tour = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
+          var tourLength = Evaluate(tour, new FastRandom(1));
+          BestKnownSolution = new TSPSolution(data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null, tour, new DoubleValue(tourLength));
+          BestKnownQuality = tourLength;
+        } catch (InvalidOperationException) {
+          if (data.BestKnownQuality.HasValue)
+            BestKnownQuality = data.BestKnownQuality.Value;
+        }
+      } else if (data.BestKnownQuality.HasValue) {
+        BestKnownQuality = data.BestKnownQuality.Value;
+      }
       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;
-    }
-
-    private void Parameterize() {
-      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
-        similarityCalculator.SolutionVariableName = Encoding.SolutionCreator.PermutationParameter.ActualName;
-        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
-      }
     }
   }