Changeset 11228 for branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

Timestamp:

07/29/14 15:43:47 (10 years ago)

Author:

pfleck

Message:

#2208:

• Fixed bugs in cost calculation of insertion and replacement
• Rewritten Cleanup of infeasible tours
• Small refactoring

File:

• branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs (modified) (8 diffs)

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

@@ -51 +51 @@
           if (value != null && !(value is OrienteeringProblem))
             throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
-          //if (problem != null) DeregisterProblemEventHandlers();
           problem = (OrienteeringProblem)value;
-          //if (problem != null) RegisterProblemEventHandlers();
-          //UpdateProblem();
         }
       }
@@ -64 +61 @@
 
     #region Parameter Properties
-
     public ILookupParameter<IntegerVector> IntegerVectorParameter {
       get { return (ILookupParameter<IntegerVector>)Parameters["OrienteeringSolution"]; }
@@ -104 +100 @@
       : base(original, cloner) {
       this.problem = cloner.Clone(original.problem);
-      //RegisterEventHandlers();
     }
     public OrienteeringLocalImprovementOperator()
@@ -115 +110 @@
       Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
       Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
+
       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
       Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
-
-      //RegisterEventHandlers();
     }
 
@@ -126 +120 @@
     }
 
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      //RegisterEventHandlers();
-    }
-
     public override IOperation Apply() {
-      // TODO Use LocalImprovementorOperator Parameters
-
       int numPoints = ScoresParameter.ActualValue.Length;
       var distances = DistanceMatrixParameter.ActualValue;
       var scores = ScoresParameter.ActualValue;
       double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
+      double maxLength = MaximumDistanceParameter.ActualValue.Value;
 
       bool optimizationDone = true;
 
-      // Find the maximum distance restriction
-      double maxLength = MaximumDistanceParameter.ActualValue.Value;
-
       var tour = IntegerVectorParameter.ActualValue.ToList();
 
       double tourLength = distances.CalculateTourLength(tour, fixedPenalty);
-      double score = tour.Sum(p => scores[p]);
+      double tourScore = tour.Sum(point => scores[point]);
 
       // Check if the tour can be improved by adding or replacing points
@@ -167 +152 @@
         ReplacePoints(tour, visitablePoints,
           distances, maxLength, scores,
-          ref tourLength, ref score, ref optimizationDone);
-      }
-
+          ref tourLength, ref tourScore, ref optimizationDone);
+      }
+
+      // Set new tour
       IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());
 
@@ -193 +179 @@
 
             double newLength = tourLength;
-            for (int counterLength = (position - 1); counterLength < (position + blockLength); counterLength++) {
-              newLength -= distances[tour[counterLength], tour[counterLength + 1]];
-            }
-            for (int counterLength = (position + blockLength - 1); counterLength > (position); counterLength--) {
-              newLength += distances[tour[counterLength], tour[counterLength - 1]];
-            }
+            // Recalculate length of whole swapped part, in case distances are not symmetric
+            for (int index = position - 1; index < position + blockLength; index++) newLength -= distances[tour[index], tour[index + 1]];
+            for (int index = position + blockLength - 1; index > position; index--) newLength += distances[tour[index], tour[index - 1]];
             newLength += distances[tour[position - 1], tour[position + blockLength - 1]];
             newLength += distances[tour[position], tour[position + blockLength]];
 
-
-            if (newLength <= (tourLength - 0.00001)) { // Avoid cycling caused by precision
-              var partPath = tour.GetRange(position, blockLength);
+            if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision
+              var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse();
 
               tour.RemoveRange(position, blockLength);
-              tour.InsertRange(position, partPath.AsEnumerable().Reverse());
+              tour.InsertRange(position, reversePart);
 
               tourLength = newLength;
@@ -263 +245 @@
           double newPointScore = scores[visitablePoints[i]];
 
-          if (tourLength + detour <= maxLength && newPointScore > oldPointScore) {
+          if ((tourLength + detour <= maxLength) && (newPointScore > oldPointScore)) {
             // Replace the old point by the new one
             tour[tourPosition] = visitablePoints[i];