Changeset 11226 for branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs

Timestamp:

07/28/14 14:24:09 (10 years ago)

Author:

pfleck

Message:

#2208:

• Fixed bug in LocalImprovementOperator.
• Implemented ShakingOperator.

File:

• branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs (modified) (5 diffs)

branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs

@@ -20 +20 @@
 #endregion
 
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Operators;
 using HeuristicLab.Optimization;
@@ -43 +46 @@
 (Schilde et. al. 2009)")]
   [StorableClass]
-  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator {
-
+  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {
+
+    #region Shaking Parameter Properties
     public IValueLookupParameter<IntValue> CurrentNeighborhoodIndexParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
@@ -51 +55 @@
     public ILookupParameter<IntValue> NeighborhoodCountParameter {
       get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
+    }
+    #endregion
+
+    public ILookupParameter<IntegerVector> IntegerVectorParameter {
+      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
+    }
+    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
+    }
+    public ILookupParameter<IntValue> StartingPointParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }
+    }
+    public ILookupParameter<IntValue> TerminusPointParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["TerminusPoint"]; }
+    }
+    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
+      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ILookupParameter<DoubleArray> ScoresParameter {
+      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
+    }
+    public ILookupParameter<DoubleValue> FixedPenaltyParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }
+    }
+
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
 
@@ -63 +94 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
       Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of operators that are available."));
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
+
+      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
+      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
+      Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
+      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
+      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
+      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
 
       //RegisterEventHandlers();
@@ -77 +117 @@
 
     public override IOperation Apply() {
-      // TODO
+      var initialTour = IntegerVectorParameter.ActualValue;
+      var distances = DistanceMatrixParameter.ActualValue;
+      var scores = ScoresParameter.ActualValue;
+      var startingPoint = StartingPointParameter.ActualValue.Value;
+      var terminusPoint = TerminusPointParameter.ActualValue.Value;
+      var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
+      double maxDistance = MaximumDistanceParameter.ActualValue.Value;
+      int numPoints = scores.Length;
+
+      if (NeighborhoodCountParameter.ActualValue == null)
+        NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);
+      else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;
+
+      var random = RandomParameter.ActualValue;
+
+      // Limit the neighborhood to the tour length
+      int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
+      int limit = initialTour.Length - 3;
+      int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;
+
+      // Find all points that are not yet included in the tour and are
+      // within the maximum distance allowed (ellipse) and sort them with
+      // regard to their utility 
+      var visitablePoints = (
+          from i in Enumerable.Range(0, numPoints)
+          // Calculate the distance when going from the starting point to this point and then to the end point
+          let distance = distances[startingPoint, i] + distances[i, terminusPoint] + fixedPenalty
+          // If this distance is feasible and the point is neither starting nor ending point, check the point
+          where distance < maxDistance && i != startingPoint && i != terminusPoint
+          // The point was not yet visited, so add it to the candidate list
+          where !initialTour.Contains(i)
+          // Calculate the utility of the point at this position
+          let utility = scores[i]
+          orderby utility
+          select i
+        ).ToList();
+
+      // Elect the starting index of the part to be replaced
+      int tourSize = initialTour.Length;
+      int randomPosition = random.Next(tourSize - neighborhood - 2) + 1;
+
+      // Initialize the new tour
+      var actualTour = new List<int> { startingPoint };
+
+      // Perform the insertions according to the utility sorting
+      for (int position = 1; position < tourSize; position++) {
+        if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
+          // Copy from initial tour when outside shaking range
+          actualTour.Add(initialTour[position]);
+
+          // Delete this point from the candidate list
+          visitablePoints.Remove(initialTour[position]);
+        } else {
+          if (visitablePoints.Count > 0) {
+            // Add the point with the highest utility from the candidate list
+            int randomFactor = random.Next(3);
+            int insertionIndex = visitablePoints.Count - 1;
+            if (visitablePoints.Count > 4) insertionIndex -= randomFactor;
+
+            actualTour.Add(visitablePoints[insertionIndex]);
+
+            // Delete this point from the candidate list
+            visitablePoints.RemoveAt(insertionIndex);
+          } else {
+            // We don't have any points left that could be inserted so we can only re-insert
+            // the removed and not already re-inserted points in a random order
+            for (int reinsertPosition = randomPosition;
+              reinsertPosition < (randomPosition + neighborhood);
+              reinsertPosition++) {
+              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
+
+              if (!alreadyReinserted)
+                visitablePoints.Add(initialTour[reinsertPosition]);
+            }
+
+            int randomIndex = random.Next(visitablePoints.Count - 1);
+            actualTour.Add(visitablePoints[randomIndex]);
+            visitablePoints.Clear();
+          }
+        }
+      }
+
+      // Bring the tour back to be feasible 
+      CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
+
+      // Set new Tour
+      IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
 
       return base.Apply();
+    }
+
+    private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {
+      var distanceSavingsList = new List<double>();
+      var sortedPoints = new List<int>();
+
+      // Sort the points on the tour according to their score
+      int tourPointMax = actualTour.Count - 1;
+      for (int tourPoint = 1; tourPoint < tourPointMax; tourPoint++) {
+        double distanceSaving = distances[actualTour[tourPoint - 1], actualTour[tourPoint]];
+        distanceSaving += distances[actualTour[tourPoint], actualTour[tourPoint + 1]];
+        distanceSaving -= distances[actualTour[tourPoint - 1], actualTour[tourPoint + 1]];
+
+        bool inserted = false;
+        int sortMax = sortedPoints.Count;
+        for (int sortCounter = 0; sortCounter < sortMax; sortCounter++) {
+          if (distanceSaving > distanceSavingsList[sortCounter]) {
+            distanceSavingsList.Insert(sortCounter, distanceSaving);
+            sortedPoints.Insert(sortCounter, tourPoint);
+            inserted = true;
+            break;
+          }
+        }
+        if (!inserted) {
+          distanceSavingsList.Add(distanceSaving);
+          sortedPoints.Add(tourPoint);
+        }
+      }
+
+      // As long as the created path is infeasible, remove elements
+      while (distances.CalculateTourLength(actualTour, fixedPenalty) > maxDistance) {
+        // Remove the point that frees the largest distance
+        actualTour.RemoveAt(sortedPoints[0]);
+
+        int sortMax = sortedPoints.Count;
+        for (int sortCounter = 1; sortCounter < sortMax; sortCounter++) {
+          if (sortedPoints[sortCounter] > sortedPoints[0]) {
+            sortedPoints[sortCounter]--;
+          }
+        }
+        sortedPoints.RemoveAt(0);
+        distanceSavingsList.RemoveAt(0);
+      }
     }
   }