Changeset 13412 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/PTSPTwoPointFiveMoveEvaluator.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/Moves/TwoPointFiveOpt/PTSPTwoPointFiveMoveEvaluator.cs (copied) (copied from branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoPointFiveOpt/PTSP25MoveEvaluator.cs) (2 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/PTSPTwoPointFiveMoveEvaluator.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -27 +26 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Optimization;
-using HeuristicLab.Operators;
 
 namespace HeuristicLab.Problems.PTSP {
-  /// <summary>
-  /// A base class for operators which evaluate TSP solutions.
-  /// </summary>
-  [Item("PTSP25MoveEvaluator", "Operator that evaluates 2.5-p-opt moves of PTSP")]
+  [Item("PTSP 2.5-MoveEvaluator", "Operator that evaluates 2.5-p-opt moves of PTSP")]
   [StorableClass]
-  public class PTSP25MoveEvaluator : SingleSuccessorOperator, I25MoveOperator, ISingleObjectiveMoveEvaluator {
-    public ILookupParameter<Permutation> PermutationParameter {
-      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
-    }
-    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
-      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
-    }
-    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
-      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
-    }
-    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
-      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
-    }
-    public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
-      get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
-    }
+  public class PTSPTwoPointFiveMoveEvaluator : EstimatedPTSPMoveEvaluator, ITwoPointFiveMoveOperator {
+
     public ILookupParameter<TwoPointFiveMove> TwoPointFiveMoveParameter {
       get { return (ILookupParameter<TwoPointFiveMove>)Parameters["TwoPointFiveMove"]; }
     }
-    public ILookupParameter<DoubleValue> QualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
-    }
-    public ILookupParameter<DoubleValue> MoveQualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
-    }
 
     [StorableConstructor]
-    protected PTSP25MoveEvaluator(bool deserializing) : base(deserializing) { }
-    protected PTSP25MoveEvaluator(PTSP25MoveEvaluator original, Cloner cloner) : base(original, cloner) { }
-    public PTSP25MoveEvaluator()
+    protected PTSPTwoPointFiveMoveEvaluator(bool deserializing) : base(deserializing) { }
+    protected PTSPTwoPointFiveMoveEvaluator(PTSPTwoPointFiveMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
+    public PTSPTwoPointFiveMoveEvaluator()
       : base() {
-      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
-      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The city's coordinates."));
-      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
-      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false."));
-      Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
       Parameters.Add(new LookupParameter<TwoPointFiveMove>("TwoPointFiveMove", "The move to evaluate."));
-      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution."));
-      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution."));
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new PTSP25MoveEvaluator(this, cloner);
+      return new PTSPTwoPointFiveMoveEvaluator(this, cloner);
     }
 
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      // BackwardsCompatibility3.3
-      #region Backwards compatible code (remove with 3.4)
-      LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
-      if (oldDistanceMatrixParameter != null) {
-        Parameters.Remove(oldDistanceMatrixParameter);
-        Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
-        DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
-      }
-      #endregion
+    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
+      var move = TwoPointFiveMoveParameter.ActualValue;
+      var realizations = RealizationsParameter.ActualValue;
+      return EvaluateByCoordinates(permutation, coordinates, distanceCalculator, move, realizations);
     }
 
-    public override IOperation Apply() {
-      Permutation permutation = PermutationParameter.ActualValue;
-      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
-      double relativeQualityDifference = 0;
-      if (UseDistanceMatrixParameter.ActualValue.Value) {
-        DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
-        if (distanceMatrix == null) {
-          if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
-          distanceMatrix = CalculateDistanceMatrix(coordinates);
-          DistanceMatrixParameter.ActualValue = distanceMatrix;
-        }
-        relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
-      } 
-      DoubleValue moveQuality = MoveQualityParameter.ActualValue;
-      if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
-      else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
-      return base.Apply();
+    public static double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, TwoPointFiveMove move, ItemList<BoolArray> realizations) {
+      if (move.IsInvert) {
+        return PTSPEstimatedInversionMoveEvaluator.EvaluateByCoordinates(permutation,
+          new InversionMove(move.Index1, move.Index2, move.Permutation),
+          coordinates, distanceCalculator, realizations);
+      } else {
+        return PTSPEstimatedInsertionMoveEvaluator.EvaluateByCoordinates(permutation,
+          new TranslocationMove(move.Index1, move.Index1, move.Index2),
+          coordinates, distanceCalculator, realizations);
+      }
     }
 
-    protected double CalculateDistance(double x1, double y1, double x2, double y2) {
-      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
+    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
+      var move = TwoPointFiveMoveParameter.ActualValue;
+      var realizations = RealizationsParameter.ActualValue;
+      return EvaluateByDistanceMatrix(permutation, distanceMatrix, move, realizations);
     }
 
-    private static int decreaseCircularIndex(int length, int index) {
-      int result = index - 1;
-      if (result == -1) {
-        result = length - 1;
+    public static double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix, TwoPointFiveMove move, ItemList<BoolArray> realizations) {
+      if (move.IsInvert) {
+        return PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(permutation,
+          new InversionMove(move.Index1, move.Index2, move.Permutation),
+          distanceMatrix, realizations);
+      } else {
+        return PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(permutation,
+          new TranslocationMove(move.Index1, move.Index1, move.Index2),
+          distanceMatrix, realizations);
       }
-      return result;
-    }
-
-    private static int increaseCircularIndex(int length, int index) {
-      int result = index + 1;
-      if (result == length + 1) {
-        result = 0;
-      }
-      return result;
-    }
-    
-
-    public static double EvaluateInversionByDistanceMatrix(Permutation permutation, TwoPointFiveMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
-      double moveQuality = 0;
-      int[] edges = new int[4];
-      int[] indices = new int[4];
-      edges[0] = permutation.GetCircular(move.Index1 - 1);
-      indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
-      edges[1] = permutation[move.Index1];
-      indices[1] = move.Index1;
-      edges[2] = permutation[move.Index2];
-      indices[2] = move.Index2;
-      edges[3] = permutation.GetCircular(move.Index2 + 1);
-      indices[3] = increaseCircularIndex(permutation.Length, move.Index2);
-      int[] aPosteriori = new int[4];
-      foreach (ItemList<IntValue> realization in realizations) {
-        for (int i = 0; i < edges.Length; i++) {
-          if (realization[edges[i]].Value == 1) {
-            aPosteriori[i] = edges[i];
-          } else {
-            int j = 1;
-            if (i % 2 == 0) {
-              // find nearest predecessor in realization if source edge
-              while (realization[permutation.GetCircular(indices[i] - j)].Value == 0) {
-                j++;
-              }
-              aPosteriori[i] = permutation.GetCircular(indices[i] - j);
-            } else {
-              // find nearest successor in realization if target edge
-              while (realization[permutation.GetCircular(indices[i] + j)].Value == 0) {
-                j++;
-              }
-              aPosteriori[i] = permutation.GetCircular(indices[i] + j);
-            }
-          }
-        }
-        // compute cost difference between the two a posteriori solutions
-        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
-          moveQuality = moveQuality + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
-        }
-        Array.Clear(aPosteriori, 0, aPosteriori.Length);
-      }
-      // return average of cost differences
-      return moveQuality / realizations.Count;
-    }
-    public static double EvaluateInsertionByDistanceMatrix(Permutation permutation, TwoPointFiveMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
-      Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
-      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index2);
-      double moveQuality = 0;
-      int[] edges = new int[12];
-      int[] indices = new int[12];
-      edges[0] = permutation.GetCircular(move.Index1 - 1);
-      indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
-      edges[1] = permutation[move.Index1];
-      indices[1] = move.Index1;
-      edges[2] = permutation[move.Index1];
-      indices[2] = move.Index1;
-      edges[3] = permutation.GetCircular(move.Index1 + 1);
-      indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
-
-      edges[6] = afterMove.GetCircular(move.Index2 - 1);
-      indices[6] = decreaseCircularIndex(afterMove.Length, move.Index2);
-      edges[7] = afterMove[move.Index2];
-      indices[7] = move.Index2;
-      edges[8] = afterMove[move.Index2];
-      indices[8] = move.Index2;
-      edges[9] = afterMove.GetCircular(move.Index2 + 1);
-      indices[9] = increaseCircularIndex(afterMove.Length, move.Index2);
-
-      if (move.Index2 > move.Index1) {
-        edges[4] = permutation[move.Index2];
-        indices[4] = move.Index2;
-        edges[5] = permutation.GetCircular(move.Index2 + 1);
-        indices[5] = indices[9];
-        edges[10] = afterMove.GetCircular(move.Index1 - 1);
-        indices[10] = indices[0];
-        edges[11] = afterMove[move.Index1];
-        indices[11] = move.Index1;
-      } else {
-        edges[4] = permutation.GetCircular(move.Index2 - 1);
-        indices[4] = indices[6];
-        edges[5] = permutation[move.Index2];
-        indices[5] = move.Index2;
-        edges[10] = afterMove[move.Index1];
-        indices[10] = move.Index1;
-        edges[11] = afterMove.GetCircular(move.Index1 + 1);
-        indices[11] = indices[3];
-      }
-      int[] aPosteriori = new int[12];
-      Permutation tempPermutation;
-      foreach (ItemList<IntValue> realization in realizations) {
-        for (int i = 0; i < edges.Length; i++) {
-          if (i < 6) {
-            tempPermutation = permutation;
-          } else {
-            tempPermutation = afterMove;
-          }
-          if (realization[edges[i]].Value == 1) {
-            aPosteriori[i] = edges[i];
-          } else {
-            int j = 1;
-            if (i % 2 == 0) {
-              // find nearest predecessor in realization if source edge
-              while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
-                j++;
-              }
-              aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
-            } else {
-              // find nearest successor in realization if target edge
-              while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
-                j++;
-              }
-              aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
-            }
-          }
-        }
-        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
-          !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
-          !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
-          // compute cost difference between the two a posteriori solutions
-          moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
-          moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
-        }
-        Array.Clear(aPosteriori, 0, aPosteriori.Length);
-      }
-      // return average of cost differences
-      return moveQuality / realizations.Count;
-    }
-    protected double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
-      TwoPointFiveMove currentMove = TwoPointFiveMoveParameter.ActualValue;
-      if (currentMove.IsInvert) {
-        return EvaluateInversionByDistanceMatrix(permutation, currentMove, distanceMatrix, RealizationsParameter.Value);
-      } else {
-        return EvaluateInsertionByDistanceMatrix(permutation, currentMove, distanceMatrix, RealizationsParameter.Value);
-      } 
-    }
-
-    private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
-      DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
-      for (int i = 0; i < distanceMatrix.Rows; i++) {
-        for (int j = 0; j < distanceMatrix.Columns; j++)
-          distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
-      }
-      return (DistanceMatrix)distanceMatrix.AsReadOnly();
     }
   }