Changeset 11226


Ignore:
Timestamp:
07/28/14 14:24:09 (8 years ago)
Author:
pfleck
Message:

#2208:

  • Fixed bug in LocalImprovementOperator.
  • Implemented ShakingOperator.
Location:
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

    r11194 r11226  
    4040    #region IGenericLocalImprovementOperator Properties
    4141    public Type ProblemType { get { return typeof(OrienteeringProblem); } }
    42     public IProblem Problem {
     42
     43    public OrienteeringProblem Problem {
     44      get { return problem; }
     45      set { ((ILocalImprovementOperator)this).Problem = value; }
     46    }
     47    IProblem ILocalImprovementOperator.Problem {
    4348      get { return problem; }
    4449      set {
     
    6166
    6267    public ILookupParameter<IntegerVector> IntegerVectorParameter {
    63       get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
     68      get { return (ILookupParameter<IntegerVector>)Parameters["OrienteeringSolution"]; }
    6469    }
    6570    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
     
    103108    public OrienteeringLocalImprovementOperator()
    104109      : base() {
    105       Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
     110      Parameters.Add(new LookupParameter<IntegerVector>("OrienteeringSolution", "The Orienteering Solution given in path representation."));
    106111      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
    107112      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/OrienteeringProblem.cs

    r11195 r11226  
    282282      }
    283283      foreach (var op in Operators.OfType<OrienteeringShakingOperator>()) {
    284         // TODO
     284        op.IntegerVectorParameter.ActualName = SolutionCreator.IntegerVectorParameter.ActualName;
     285        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
     286        op.ScoresParameter.ActualName = ScoresParameter.Name;
     287        op.MaximumDistanceParameter.ActualName = MaximumDistanceParameter.Name;
     288        op.StartingPointParameter.ActualName = StartingPointParameter.Name;
     289        op.TerminusPointParameter.ActualName = TerminusPointParameter.Name;
     290        op.FixedPenaltyParameter.ActualName = FixedPenaltyParameter.Name;
    285291      }
    286292    }
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs

    r11195 r11226  
    2020#endregion
    2121
     22using System.Collections.Generic;
     23using System.Linq;
    2224using HeuristicLab.Common;
    2325using HeuristicLab.Core;
    2426using HeuristicLab.Data;
     27using HeuristicLab.Encodings.IntegerVectorEncoding;
    2528using HeuristicLab.Operators;
    2629using HeuristicLab.Optimization;
     
    4346(Schilde et. al. 2009)")]
    4447  [StorableClass]
    45   public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator {
    46 
     48  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {
     49
     50    #region Shaking Parameter Properties
    4751    public IValueLookupParameter<IntValue> CurrentNeighborhoodIndexParameter {
    4852      get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
     
    5155    public ILookupParameter<IntValue> NeighborhoodCountParameter {
    5256      get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
     57    }
     58    #endregion
     59
     60    public ILookupParameter<IntegerVector> IntegerVectorParameter {
     61      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
     62    }
     63    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
     64      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
     65    }
     66    public ILookupParameter<IntValue> StartingPointParameter {
     67      get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }
     68    }
     69    public ILookupParameter<IntValue> TerminusPointParameter {
     70      get { return (ILookupParameter<IntValue>)Parameters["TerminusPoint"]; }
     71    }
     72    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
     73      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
     74    }
     75    public ILookupParameter<DoubleArray> ScoresParameter {
     76      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
     77    }
     78    public ILookupParameter<DoubleValue> FixedPenaltyParameter {
     79      get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }
     80    }
     81
     82    public ILookupParameter<IRandom> RandomParameter {
     83      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    5384    }
    5485
     
    6394      Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
    6495      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."));
     97
     98      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
     99      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
     100      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
     101      Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
     102      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
     103      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
     104      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
    65105
    66106      //RegisterEventHandlers();
     
    77117
    78118    public override IOperation Apply() {
    79       // TODO
     119      var initialTour = IntegerVectorParameter.ActualValue;
     120      var distances = DistanceMatrixParameter.ActualValue;
     121      var scores = ScoresParameter.ActualValue;
     122      var startingPoint = StartingPointParameter.ActualValue.Value;
     123      var terminusPoint = TerminusPointParameter.ActualValue.Value;
     124      var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
     125      double maxDistance = MaximumDistanceParameter.ActualValue.Value;
     126      int numPoints = scores.Length;
     127
     128      if (NeighborhoodCountParameter.ActualValue == null)
     129        NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);
     130      else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;
     131
     132      var random = RandomParameter.ActualValue;
     133
     134      // Limit the neighborhood to the tour length
     135      int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
     136      int limit = initialTour.Length - 3;
     137      int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;
     138
     139      // 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
     142      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();
     155
     156      // Elect the starting index of the part to be replaced
     157      int tourSize = initialTour.Length;
     158      int randomPosition = random.Next(tourSize - neighborhood - 2) + 1;
     159
     160      // Initialize the new tour
     161      var actualTour = new List<int> { startingPoint };
     162
     163      // Perform the insertions according to the utility sorting
     164      for (int position = 1; position < tourSize; position++) {
     165        if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
     166          // Copy from initial tour when outside shaking range
     167          actualTour.Add(initialTour[position]);
     168
     169          // Delete this point from the candidate list
     170          visitablePoints.Remove(initialTour[position]);
     171        } else {
     172          if (visitablePoints.Count > 0) {
     173            // Add the point with the highest utility from the candidate list
     174            int randomFactor = random.Next(3);
     175            int insertionIndex = visitablePoints.Count - 1;
     176            if (visitablePoints.Count > 4) insertionIndex -= randomFactor;
     177
     178            actualTour.Add(visitablePoints[insertionIndex]);
     179
     180            // Delete this point from the candidate list
     181            visitablePoints.RemoveAt(insertionIndex);
     182          } else {
     183            // We don't have any points left that could be inserted so we can only re-insert
     184            // the removed and not already re-inserted points in a random order
     185            for (int reinsertPosition = randomPosition;
     186              reinsertPosition < (randomPosition + neighborhood);
     187              reinsertPosition++) {
     188              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
     189
     190              if (!alreadyReinserted)
     191                visitablePoints.Add(initialTour[reinsertPosition]);
     192            }
     193
     194            int randomIndex = random.Next(visitablePoints.Count - 1);
     195            actualTour.Add(visitablePoints[randomIndex]);
     196            visitablePoints.Clear();
     197          }
     198        }
     199      }
     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());
    80206
    81207      return base.Apply();
     208    }
     209
     210    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;
     229          }
     230        }
     231        if (!inserted) {
     232          distanceSavingsList.Add(distanceSaving);
     233          sortedPoints.Add(tourPoint);
     234        }
     235      }
     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      }
    82251    }
    83252  }
Note: See TracChangeset for help on using the changeset viewer.