Changeset 11228


Ignore:
Timestamp:
07/29/14 15:43:47 (8 years ago)
Author:
pfleck
Message:

#2208:

  • Fixed bugs in cost calculation of insertion and replacement
  • Rewritten Cleanup of infeasible tours
  • Small refactoring
Location:
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Creators/GreedyOrienteeringTourCreator.cs

    r11194 r11228  
    9090
    9191      // Find all points within the maximum distance allowed (ellipse)
    92       var feasiblePoints =
    93         from i in Enumerable.Range(0, numPoints)
    94         let distance = distances[startPoint, i] + distances[i, endPoint] + fixedPenalty
    95         where distance <= maxDistance && i != startPoint && i != endPoint
    96         select new { Index = i, Score = scores[i], Distance = distance };
    97 
    98       var orderedFeasiblePoints = feasiblePoints.OrderByDescending(p => p.Score).ToList();
     92      var feasiblePoints = (
     93        from point in Enumerable.Range(0, numPoints)
     94        let distance = distances[startPoint, point] + distances[point, endPoint] + fixedPenalty
     95        let score = scores[point]
     96        where distance <= maxDistance
     97        where point != startPoint && point != endPoint
     98        orderby score descending
     99        select point
     100      ).ToList();
    99101
    100102      // Add the starting and terminus point
     
    110112        insertionPerformed = false;
    111113
    112         for (int candidatePoint = 0; candidatePoint < orderedFeasiblePoints.Count; candidatePoint++) {
     114        for (int i = 0; i < feasiblePoints.Count; i++) {
    113115          for (int insertPosition = 1; insertPosition < tour.Count; insertPosition++) {
    114116            // Create the candidate tour
    115             double detour = distances.CalculateInsertionCosts(tour, orderedFeasiblePoints[candidatePoint].Index, insertPosition, fixedPenalty);
     117            double detour = distances.CalculateInsertionCosts(tour, insertPosition, feasiblePoints[i], fixedPenalty);
    116118
    117119            // If the insertion would be feasible, perform it
    118120            if (length + detour <= maxDistance) {
    119               tour.Insert(insertPosition, orderedFeasiblePoints[candidatePoint].Index);
     121              tour.Insert(insertPosition, feasiblePoints[i]);
    120122              length += detour;
    121               orderedFeasiblePoints.RemoveAt(candidatePoint);
     123              feasiblePoints.RemoveAt(i);
    122124              insertionPerformed = true;
    123125              break;
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/DistanceMatrix.cs

    r11193 r11228  
    5555    public double CalculateTourLength(IList<int> path, double fixedPenalty) {
    5656      double length = 0.0;
    57 
    58       for (int i = 1; i < path.Count; i++) {
    59         length += this[i - 1, i];
    60       }
    61 
     57      for (int i = 1; i < path.Count; i++)
     58        length += this[path[i - 1], path[i]];
    6259      // Add the fixed penalty for every vertex except for the starting and ending vertex
    6360      length += (path.Count - 2) * fixedPenalty;
    64 
    6561      return length;
    6662    }
    67 
    68     public double CalculateInsertionCosts(IList<int> path, int pointPosition, int insertPosition, double fixedPenalty) {
    69       double detour = this[path[insertPosition - 1], pointPosition] + this[pointPosition, path[insertPosition]];
     63    public double CalculateInsertionCosts(IList<int> path, int insertPosition, int point, double fixedPenalty) {
     64      double detour = this[path[insertPosition - 1], point] + this[point, path[insertPosition]];
    7065      detour += fixedPenalty;
    7166      detour -= this[path[insertPosition - 1], path[insertPosition]];
    7267      return detour;
    7368    }
    74 
    75     public double CalculateReplacementCosts(List<int> path, int pointPosition, int replacementPosition) {
    76       double detour = this[pointPosition - 1, replacementPosition] + this[replacementPosition, pointPosition + 1];
    77       detour -= this[pointPosition - 1, pointPosition] + this[pointPosition, pointPosition + 1];
     69    public double CalculateReplacementCosts(List<int> path, int replacePosition, int point) {
     70      double detour = this[path[replacePosition - 1], point] + this[point, path[replacePosition + 1]];
     71      detour -= this[path[replacePosition - 1], path[replacePosition]] + this[path[replacePosition], path[replacePosition + 1]];
    7872      return detour;
     73    }
     74    public double CalculateRemovementSaving(List<int> path, int removePosition, double fixedPenalty) {
     75      double saving = this[path[removePosition - 1], path[removePosition]];
     76      saving += this[path[removePosition], path[removePosition + 1]];
     77      saving -= this[path[removePosition - 1], path[removePosition + 1]];
     78      saving += fixedPenalty;
     79      return saving;
    7980    }
    8081  }
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

    r11226 r11228  
    5151          if (value != null && !(value is OrienteeringProblem))
    5252            throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
    53           //if (problem != null) DeregisterProblemEventHandlers();
    5453          problem = (OrienteeringProblem)value;
    55           //if (problem != null) RegisterProblemEventHandlers();
    56           //UpdateProblem();
    5754        }
    5855      }
     
    6461
    6562    #region Parameter Properties
    66 
    6763    public ILookupParameter<IntegerVector> IntegerVectorParameter {
    6864      get { return (ILookupParameter<IntegerVector>)Parameters["OrienteeringSolution"]; }
     
    104100      : base(original, cloner) {
    105101      this.problem = cloner.Clone(original.problem);
    106       //RegisterEventHandlers();
    107102    }
    108103    public OrienteeringLocalImprovementOperator()
     
    115110      Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
    116111      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
     112
    117113      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
    118114      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
    119115      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
    120 
    121       //RegisterEventHandlers();
    122116    }
    123117
     
    126120    }
    127121
    128     [StorableHook(HookType.AfterDeserialization)]
    129     private void AfterDeserialization() {
    130       //RegisterEventHandlers();
    131     }
    132 
    133122    public override IOperation Apply() {
    134       // TODO Use LocalImprovementorOperator Parameters
    135 
    136123      int numPoints = ScoresParameter.ActualValue.Length;
    137124      var distances = DistanceMatrixParameter.ActualValue;
    138125      var scores = ScoresParameter.ActualValue;
    139126      double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
     127      double maxLength = MaximumDistanceParameter.ActualValue.Value;
    140128
    141129      bool optimizationDone = true;
    142130
    143       // Find the maximum distance restriction
    144       double maxLength = MaximumDistanceParameter.ActualValue.Value;
    145 
    146131      var tour = IntegerVectorParameter.ActualValue.ToList();
    147132
    148133      double tourLength = distances.CalculateTourLength(tour, fixedPenalty);
    149       double score = tour.Sum(p => scores[p]);
     134      double tourScore = tour.Sum(point => scores[point]);
    150135
    151136      // Check if the tour can be improved by adding or replacing points
     
    167152        ReplacePoints(tour, visitablePoints,
    168153          distances, maxLength, scores,
    169           ref tourLength, ref score, ref optimizationDone);
    170       }
    171 
     154          ref tourLength, ref tourScore, ref optimizationDone);
     155      }
     156
     157      // Set new tour
    172158      IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());
    173159
     
    193179
    194180            double newLength = tourLength;
    195             for (int counterLength = (position - 1); counterLength < (position + blockLength); counterLength++) {
    196               newLength -= distances[tour[counterLength], tour[counterLength + 1]];
    197             }
    198             for (int counterLength = (position + blockLength - 1); counterLength > (position); counterLength--) {
    199               newLength += distances[tour[counterLength], tour[counterLength - 1]];
    200             }
     181            // Recalculate length of whole swapped part, in case distances are not symmetric
     182            for (int index = position - 1; index < position + blockLength; index++) newLength -= distances[tour[index], tour[index + 1]];
     183            for (int index = position + blockLength - 1; index > position; index--) newLength += distances[tour[index], tour[index - 1]];
    201184            newLength += distances[tour[position - 1], tour[position + blockLength - 1]];
    202185            newLength += distances[tour[position], tour[position + blockLength]];
    203186
    204 
    205             if (newLength <= (tourLength - 0.00001)) { // Avoid cycling caused by precision
    206               var partPath = tour.GetRange(position, blockLength);
     187            if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision
     188              var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse();
    207189
    208190              tour.RemoveRange(position, blockLength);
    209               tour.InsertRange(position, partPath.AsEnumerable().Reverse());
     191              tour.InsertRange(position, reversePart);
    210192
    211193              tourLength = newLength;
     
    263245          double newPointScore = scores[visitablePoints[i]];
    264246
    265           if (tourLength + detour <= maxLength && newPointScore > oldPointScore) {
     247          if ((tourLength + detour <= maxLength) && (newPointScore > oldPointScore)) {
    266248            // Replace the old point by the new one
    267249            tour[tourPosition] = visitablePoints[i];
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs

    r11226 r11228  
    5252      get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
    5353    }
    54 
    5554    public ILookupParameter<IntValue> NeighborhoodCountParameter {
    5655      get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
     
    5857    #endregion
    5958
     59    #region Parameter Properties
    6060    public ILookupParameter<IntegerVector> IntegerVectorParameter {
    6161      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
     
    8383      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    8484    }
     85    #endregion
    8586
    8687    [StorableConstructor]
     
    8889    private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)
    8990      : base(original, cloner) {
    90       //RegisterEventHandlers();
    9191    }
    9292    public OrienteeringShakingOperator()
     
    9494      Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
    9595      Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of operators that are available."));
    96       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
    9796
    9897      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
     
    104103      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
    105104
    106       //RegisterEventHandlers();
     105      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
    107106    }
    108107
    109108    public override IDeepCloneable Clone(Cloner cloner) {
    110109      return new OrienteeringShakingOperator(this, cloner);
    111     }
    112 
    113     [StorableHook(HookType.AfterDeserialization)]
    114     private void AfterDeserialization() {
    115       //RegisterEventHandlers();
    116110    }
    117111
     
    138132
    139133      // Find all points that are not yet included in the tour and are
    140       // within the maximum distance allowed (ellipse) and sort them with
    141       // regard to their utility
     134      // within the maximum distance allowed (ellipse)
     135      // and sort them with regard to their utility
    142136      var visitablePoints = (
    143           from i in Enumerable.Range(0, numPoints)
    144           // Calculate the distance when going from the starting point to this point and then to the end point
    145           let distance = distances[startingPoint, i] + distances[i, terminusPoint] + fixedPenalty
    146           // If this distance is feasible and the point is neither starting nor ending point, check the point
    147           where distance < maxDistance && i != startingPoint && i != terminusPoint
    148           // The point was not yet visited, so add it to the candidate list
    149           where !initialTour.Contains(i)
    150           // Calculate the utility of the point at this position
    151           let utility = scores[i]
    152           orderby utility
    153           select i
    154         ).ToList();
     137        from point in Enumerable.Range(0, numPoints)
     138        // Calculate the distance when going from the starting point to this point and then to the end point
     139        let distance = distances[startingPoint, point] + distances[point, terminusPoint] + fixedPenalty
     140        // If this distance is feasible and the point is neither starting nor ending point, check the point
     141        where distance < maxDistance && point != startingPoint && point != terminusPoint
     142        // The point was not yet visited, so add it to the candidate list
     143        where !initialTour.Contains(point)
     144        // Calculate the utility of the point at this position
     145        let utility = scores[point]
     146        orderby utility
     147        select point
     148      ).ToList();
     149
     150      // Initialize the new tour
     151      var actualTour = new List<int> { startingPoint };
     152
     153      // Perform the insertions according to the utility sorting
     154      InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);
     155
     156      // Bring the tour back to be feasible
     157      CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
     158
     159      // Set new Tour
     160      IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
     161
     162      return base.Apply();
     163    }
     164    private void InsertPoints(List<int> actualTour, IntegerVector initialTour,
     165      int neighborhood, List<int> visitablePoints, IRandom random) {
    155166
    156167      // Elect the starting index of the part to be replaced
     
    158169      int randomPosition = random.Next(tourSize - neighborhood - 2) + 1;
    159170
    160       // Initialize the new tour
    161       var actualTour = new List<int> { startingPoint };
    162 
    163       // Perform the insertions according to the utility sorting
    164171      for (int position = 1; position < tourSize; position++) {
    165172        if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
     
    170177          visitablePoints.Remove(initialTour[position]);
    171178        } else {
     179          // Point from within shaking range
    172180          if (visitablePoints.Count > 0) {
    173181            // Add the point with the highest utility from the candidate list
     
    183191            // We don't have any points left that could be inserted so we can only re-insert
    184192            // the removed and not already re-inserted points in a random order
    185             for (int reinsertPosition = randomPosition;
    186               reinsertPosition < (randomPosition + neighborhood);
    187               reinsertPosition++) {
     193            for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {
    188194              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
    189195
     
    198204        }
    199205      }
    200 
    201       // Bring the tour back to be feasible
    202       CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
    203 
    204       // Set new Tour
    205       IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
    206 
    207       return base.Apply();
    208     }
    209 
     206    }
    210207    private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {
    211       var distanceSavingsList = new List<double>();
    212       var sortedPoints = new List<int>();
    213 
    214       // Sort the points on the tour according to their score
    215       int tourPointMax = actualTour.Count - 1;
    216       for (int tourPoint = 1; tourPoint < tourPointMax; tourPoint++) {
    217         double distanceSaving = distances[actualTour[tourPoint - 1], actualTour[tourPoint]];
    218         distanceSaving += distances[actualTour[tourPoint], actualTour[tourPoint + 1]];
    219         distanceSaving -= distances[actualTour[tourPoint - 1], actualTour[tourPoint + 1]];
    220 
    221         bool inserted = false;
    222         int sortMax = sortedPoints.Count;
    223         for (int sortCounter = 0; sortCounter < sortMax; sortCounter++) {
    224           if (distanceSaving > distanceSavingsList[sortCounter]) {
    225             distanceSavingsList.Insert(sortCounter, distanceSaving);
    226             sortedPoints.Insert(sortCounter, tourPoint);
    227             inserted = true;
    228             break;
     208      // Sort the points on the tour according to their costs savings when removed
     209      var distanceSavings = (
     210        from removePosition in Enumerable.Range(1, actualTour.Count - 2)
     211        let saving = distances.CalculateRemovementSaving(actualTour, removePosition, fixedPenalty)
     212        orderby saving descending
     213        select new SavingInfo { Index = removePosition, Saving = saving }
     214      ).ToList();
     215
     216      double tourLength = distances.CalculateTourLength(actualTour, fixedPenalty);
     217
     218      // As long as the created path is infeasible, remove elements
     219      while (tourLength > maxDistance) {
     220        // Remove the point that frees the largest distance
     221        actualTour.RemoveAt(distanceSavings[0].Index);
     222        tourLength -= distanceSavings[0].Saving;
     223
     224        // Shift indices due to removal of a point in the tour
     225        for (int i = 1; i < distanceSavings.Count; i++) {
     226          if (distanceSavings[i].Index > distanceSavings[0].Index) {
     227            distanceSavings[i].Index--;
     228            // Note, distance savings are not updated after removal
    229229          }
    230230        }
    231         if (!inserted) {
    232           distanceSavingsList.Add(distanceSaving);
    233           sortedPoints.Add(tourPoint);
    234         }
     231        distanceSavings.RemoveAt(0);
    235232      }
    236 
    237       // As long as the created path is infeasible, remove elements
    238       while (distances.CalculateTourLength(actualTour, fixedPenalty) > maxDistance) {
    239         // Remove the point that frees the largest distance
    240         actualTour.RemoveAt(sortedPoints[0]);
    241 
    242         int sortMax = sortedPoints.Count;
    243         for (int sortCounter = 1; sortCounter < sortMax; sortCounter++) {
    244           if (sortedPoints[sortCounter] > sortedPoints[0]) {
    245             sortedPoints[sortCounter]--;
    246           }
    247         }
    248         sortedPoints.RemoveAt(0);
    249         distanceSavingsList.RemoveAt(0);
    250       }
     233    }
     234    //
     235    private class SavingInfo {
     236      public int Index;
     237      public double Saving;
    251238    }
    252239  }
Note: See TracChangeset for help on using the changeset viewer.