Changeset 13412 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs
- Timestamp:
- 11/28/15 23:38:51 (9 years ago)
- Location:
- branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt
- Files:
-
- 1 added
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs
r13408 r13412 20 20 #endregion 21 21 22 using System; 22 23 using HeuristicLab.Common; 23 24 using HeuristicLab.Core; … … 26 27 using HeuristicLab.Parameters; 27 28 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 28 using System;29 29 30 30 namespace HeuristicLab.Problems.PTSP { 31 /// <summary> 32 /// An operator to evaluate inversion moves (2-opt). 33 /// </summary> 34 [Item("PTSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")] 31 [Item("PTSPEstimatedInversionMoveEvaluator", "Evaluates an inversion move (2-opt) over several realizations of tours by summing up the length of all added edges and subtracting the length of all deleted edges.")] 35 32 [StorableClass] 36 public class PTSPEstimatedInversionEvaluator : PTSPMoveEvaluator, IPermutationInversionMoveOperator { 37 public override Type EvaluatorType { 38 get { return typeof(PTSPEstimatedInversionEvaluator); } 39 } 33 public class PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator { 34 40 35 public ILookupParameter<InversionMove> InversionMoveParameter { 41 36 get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; } 42 37 } 43 38 44 45 46 39 [StorableConstructor] 47 protected PTSPEstimatedInversion Evaluator(bool deserializing) : base(deserializing) { }48 protected PTSPEstimatedInversion Evaluator(PTSPEstimatedInversionEvaluator original, Cloner cloner) : base(original, cloner) { }49 public PTSPEstimatedInversion Evaluator()40 protected PTSPEstimatedInversionMoveEvaluator(bool deserializing) : base(deserializing) { } 41 protected PTSPEstimatedInversionMoveEvaluator(PTSPEstimatedInversionMoveEvaluator original, Cloner cloner) : base(original, cloner) { } 42 public PTSPEstimatedInversionMoveEvaluator() 50 43 : base() { 51 44 Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate.")); … … 53 46 54 47 public override IDeepCloneable Clone(Cloner cloner) { 55 return new PTSPEstimatedInversion Evaluator(this, cloner);48 return new PTSPEstimatedInversionMoveEvaluator(this, cloner); 56 49 } 57 50 58 public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, PTSPEstimatedInversionEvaluator evaluator) { 59 int edge1source = permutation.GetCircular(move.Index1 - 1); 60 int edge1target = permutation[move.Index1]; 61 int edge2source = permutation[move.Index2]; 62 int edge2target = permutation.GetCircular(move.Index2 + 1); 63 if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0; 51 public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) { 64 52 double moveQuality = 0; 65 // remove two edges 66 moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1], 67 coordinates[edge1target, 0], coordinates[edge1target, 1]); 68 moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1], 69 coordinates[edge2target, 0], coordinates[edge2target, 1]); 70 // add two edges 71 moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1], 72 coordinates[edge2source, 0], coordinates[edge2source, 1]); 73 moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1], 74 coordinates[edge2target, 0], coordinates[edge2target, 1]); 75 return moveQuality; 76 } 77 78 public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) { 79 double moveQuality = 0; 80 int[] edges = new int[4]; 81 int[] indices = new int[4]; 53 var edges = new int[4]; 54 var indices = new int[4]; 82 55 edges[0] = permutation.GetCircular(move.Index1 - 1); 83 indices[0] = move.Index1 -1;56 indices[0] = move.Index1 - 1; 84 57 if (indices[0] == -1) indices[0] = permutation.Length - 1; 85 58 edges[1] = permutation[move.Index1]; … … 88 61 indices[2] = move.Index2; 89 62 edges[3] = permutation.GetCircular(move.Index2 + 1); 90 indices[3] = move.Index2 +1;63 indices[3] = move.Index2 + 1; 91 64 if (indices[3] == permutation.Length + 1) indices[3] = 0; 92 int[]aPosteriori = new int[4];93 foreach ( ItemList<IntValue>realization in realizations) {94 for ( inti = 0; i < edges.Length; i++) {95 if (realization[edges[i]] .Value == 1) {65 var aPosteriori = new int[4]; 66 foreach (var realization in realizations) { 67 for (var i = 0; i < edges.Length; i++) { 68 if (realization[edges[i]]) { 96 69 aPosteriori[i] = edges[i]; 97 70 } else { 98 int j=1;99 if (i %2==0) {71 var j = 1; 72 if (i % 2 == 0) { 100 73 // find nearest predecessor in realization if source edge 101 while (realization[permutation.GetCircular(indices[i]-j)].Value==0) {74 while (!realization[permutation.GetCircular(indices[i] - j)]) { 102 75 j++; 103 76 } … … 105 78 } else { 106 79 // find nearest successor in realization if target edge 107 while(realization[permutation.GetCircular(indices[i]+j)].Value==0) { 80 while (!realization[permutation.GetCircular(indices[i] + j)]) { 81 j++; 82 } 83 aPosteriori[i] = permutation.GetCircular(indices[i] + j); 84 } 85 } 86 } 87 // compute cost difference between the two a posteriori solutions 88 if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) { 89 moveQuality = moveQuality 90 + distanceCalculator.Calculate(0, 2, coordinates) 91 + distanceCalculator.Calculate(1, 3, coordinates) 92 - distanceCalculator.Calculate(0, 1, coordinates) 93 - distanceCalculator.Calculate(2, 3, coordinates); 94 } 95 Array.Clear(aPosteriori, 0, aPosteriori.Length); 96 } 97 // return average of cost differences 98 return moveQuality / realizations.Count; 99 } 100 101 public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) { 102 double moveQuality = 0; 103 var edges = new int[4]; 104 var indices = new int[4]; 105 edges[0] = permutation.GetCircular(move.Index1 - 1); 106 indices[0] = move.Index1 - 1; 107 if (indices[0] == -1) indices[0] = permutation.Length - 1; 108 edges[1] = permutation[move.Index1]; 109 indices[1] = move.Index1; 110 edges[2] = permutation[move.Index2]; 111 indices[2] = move.Index2; 112 edges[3] = permutation.GetCircular(move.Index2 + 1); 113 indices[3] = move.Index2 + 1; 114 if (indices[3] == permutation.Length + 1) indices[3] = 0; 115 var aPosteriori = new int[4]; 116 foreach (var realization in realizations) { 117 for (var i = 0; i < edges.Length; i++) { 118 if (realization[edges[i]]) { 119 aPosteriori[i] = edges[i]; 120 } else { 121 var j = 1; 122 if (i % 2 == 0) { 123 // find nearest predecessor in realization if source edge 124 while (!realization[permutation.GetCircular(indices[i] - j)]) { 125 j++; 126 } 127 aPosteriori[i] = permutation.GetCircular(indices[i] - j); 128 } else { 129 // find nearest successor in realization if target edge 130 while (!realization[permutation.GetCircular(indices[i] + j)]) { 108 131 j++; 109 132 } … … 122 145 } 123 146 124 protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates ) {125 return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);147 protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) { 148 return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue); 126 149 } 127 150 128 151 protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) { 129 return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value); 130 } 131 132 protected override double CalculateDistance(double x1, double y1, double x2, double y2) { 133 return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))); 152 return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue); 134 153 } 135 154 }
Note: See TracChangeset
for help on using the changeset viewer.