Changeset 11242

Timestamp:

07/30/14 15:02:35 (10 years ago)

Author:

pfleck

Message:

#2208

• Added MaximumBlockLength parameter in OrienteeringLocalImprovementOperator
• Use and set parameter from ILocalImprovementOperator

File:

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

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

@@ -83 +83 @@
     }
     #region ILocalImprovementOperator Parameters
+    public IValueLookupParameter<IntValue> LocalIterationsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["LocalIterations"]; }
+    }
     public IValueLookupParameter<IntValue> MaximumIterationsParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
@@ -95 +98 @@
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+    public IValueParameter<IntValue> MaximumBlockLengthParmeter {
+      get { return (IValueParameter<IntValue>)Parameters["MaximumBlockLength"]; }
+    }
+    public IValueParameter<BoolValue> UseMaximumBlockLengthParmeter {
+      get { return (IValueParameter<BoolValue>)Parameters["UseMaximumBlockLength"]; }
     }
     #endregion
@@ -114 +123 @@
       Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
 
+      Parameters.Add(new ValueLookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed.", new IntValue(0)));
       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."));
       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));
+
+      Parameters.Add(new ValueParameter<IntValue>("MaximumBlockLength", "The maximum length of the 2-opt shortening.", new IntValue(30)));
+      Parameters.Add(new ValueParameter<BoolValue>("UseMaximumBlockLength", "Use a limitation of the length for the 2-opt shortening.", new BoolValue(true)));
     }
 
@@ -130 +143 @@
       double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
       double maxLength = MaximumDistanceParameter.ActualValue.Value;
+      int maxIterations = MaximumIterationsParameter.ActualValue.Value;
+      int maxBlockLength = MaximumBlockLengthParmeter.Value.Value;
+      bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value;
 
       bool optimizationDone = true;
@@ -138 +154 @@
       double tourScore = tour.Sum(point => scores[point]);
 
+      var localIterations = LocalIterationsParameter.ActualValue;
+      var evaluatedSolutions = EvaluatedSolutionsParameter.ActualValue;
+      int evaluations = 0;
+
       // Check if the tour can be improved by adding or replacing points
-      while (optimizationDone) {
+      while (optimizationDone && localIterations.Value < maxIterations) {
         optimizationDone = false;
 
         // Try to shorten the path
-        ShortenPath(tour, distances, ref tourLength);
+        ShortenPath(tour, distances, maxBlockLength, useMaxBlockLength, ref tourLength, ref evaluations);
 
         // Determine all points that have not yet been visited by this tour
@@ -151 +171 @@
         IncludeNewPoints(tour, visitablePoints,
           distances, fixedPenalty, maxLength, scores,
-          ref tourLength, ref tourScore, ref optimizationDone);
+          ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);
 
         // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores
         ReplacePoints(tour, visitablePoints,
           distances, maxLength, scores,
-          ref tourLength, ref tourScore, ref optimizationDone);
-      }
+          ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);
+
+        localIterations.Value++;
+      }
+
+      localIterations.Value = 0;
+      evaluatedSolutions.Value += evaluations;
 
       // Set new tour
@@ -166 +191 @@
     }
 
-    private void ShortenPath(List<int> tour, DistanceMatrix distances, ref double tourLength) {
+    private void ShortenPath(List<int> tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) {
       bool optimizationDone = true;
       int pathSize = tour.Count;
-      int maxBlockLength = (pathSize > 31) ? 30 : (pathSize - 2);
+      maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2);
 
       // Perform a 2-opt
@@ -182 +207 @@
             // If an optimization has been done, start from the beginning
             if (optimizationDone) break;
+
+            evaluations++;
 
             double newLength = tourLength;
@@ -207 +234 @@
     private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,
       DistanceMatrix distances, double fixedPenalty, double maxLength, DoubleArray scores,
-      ref double tourLength, ref double tourScore, ref bool optimizationDone) {
+      ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {
 
       for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {
@@ -216 +243 @@
           // If an optimization has been done, start from the beginning
           if (optimizationDone) break;
+
+          evaluations++;
 
           double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], fixedPenalty);
@@ -236 +265 @@
     private void ReplacePoints(List<int> tour, List<int> visitablePoints,
       DistanceMatrix distances, double maxLength, DoubleArray scores,
-      ref double tourLength, ref double tourScore, ref bool optimizationDone) {
+      ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {
 
       for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) {
@@ -245 +274 @@
           // If an optimization has been done, start from the beginning
           if (optimizationDone) break;
+
+          evaluations++;
 
           double detour = distances.CalculateReplacementCosts(tour, tourPosition, visitablePoints[i]);