Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs @ 11266

Last change on this file since 11266 was 11266, checked in by pfleck, 10 years ago

#2208

  • Changed path visualization to line strip instead of polygon since start and end point must not match
  • Used correct incremental length calculation in CleanupTour
File size: 11.8 KB
RevLine 
[11195]1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
[11226]22using System.Collections.Generic;
23using System.Linq;
[11195]24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
[11226]27using HeuristicLab.Encodings.IntegerVectorEncoding;
[11195]28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.Orienteering {
34  [Item("OrienteeringShakingOperator", @"The used neighborhood operator is based on a two point exchange move. A move in
35the k-th neighborhood consists of removing k consecutive vertices from the tour, starting
36at a randomly selected position. Afterwards, a sorted list of all vertices not yet included
37in the current tour is built. The vertices are sorted in descending order with respect to the
38objective value increase using the current weights. Out of the first three entries with the
39highest ranking in this list, one randomly selected vertex is reinserted into the current tour
40at the same position as the removed vertices. This way, l new vertices are inserted into the
41tour. The largest neighborhood is a complete exchange of all vertices on the tour.
42The shaking procedure does not guarantee that the new tour does not exceed the cost
43limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The
44vertices are sorted in descending order with respect to costs saved when removing the vertex
45from the tour. Vertices are removed as long as the cost limit is violated.
46(Schilde et. al. 2009)")]
47  [StorableClass]
[11226]48  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {
[11195]49
[11226]50    #region Shaking Parameter Properties
[11195]51    public IValueLookupParameter<IntValue> CurrentNeighborhoodIndexParameter {
52      get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
53    }
54    public ILookupParameter<IntValue> NeighborhoodCountParameter {
55      get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
56    }
[11226]57    #endregion
[11195]58
[11228]59    #region Parameter Properties
[11226]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"]; }
84    }
[11228]85    #endregion
[11226]86
[11195]87    [StorableConstructor]
88    private OrienteeringShakingOperator(bool deserializing) : base(deserializing) { }
89    private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)
90      : base(original, cloner) {
91    }
92    public OrienteeringShakingOperator()
93      : base() {
94      Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
95      Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of operators that are available."));
96
[11226]97      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
98      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
99      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
100      Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
101      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
102      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
103      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
104
[11228]105      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
[11195]106    }
107
108    public override IDeepCloneable Clone(Cloner cloner) {
109      return new OrienteeringShakingOperator(this, cloner);
110    }
111
112    public override IOperation Apply() {
[11226]113      var initialTour = IntegerVectorParameter.ActualValue;
114      var distances = DistanceMatrixParameter.ActualValue;
115      var scores = ScoresParameter.ActualValue;
116      var startingPoint = StartingPointParameter.ActualValue.Value;
117      var terminusPoint = TerminusPointParameter.ActualValue.Value;
118      var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
119      double maxDistance = MaximumDistanceParameter.ActualValue.Value;
120      int numPoints = scores.Length;
[11195]121
[11226]122      if (NeighborhoodCountParameter.ActualValue == null)
123        NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);
124      else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;
125
126      var random = RandomParameter.ActualValue;
127
[11245]128      if (initialTour.Length > 2) {
129        // Limit the neighborhood to the tour length
130        int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
[11264]131        int limit = initialTour.Length - 2; // neighborhood limit within [0, changable tour length - 1)
[11245]132        int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;
[11226]133
[11245]134        // Find all points that are not yet included in the tour and are
135        // within the maximum distance allowed (ellipse)
136        // and sort them with regard to their utility
137        var visitablePoints = (
138          from point in Enumerable.Range(0, numPoints)
139          // Calculate the distance when going from the starting point to this point and then to the end point
140          let distance = distances[startingPoint, point] + distances[point, terminusPoint] + fixedPenalty
141          // If this distance is feasible and the point is neither starting nor ending point, check the point
142          where distance < maxDistance && point != startingPoint && point != terminusPoint
143          // The point was not yet visited, so add it to the candidate list
144          where !initialTour.Contains(point)
145          // Calculate the utility of the point at this position
146          let utility = scores[point]
147          orderby utility
148          select point
149          ).ToList();
[11226]150
[11245]151        // Initialize the new tour
152        var actualTour = new List<int> { startingPoint };
[11228]153
[11245]154        // Perform the insertions according to the utility sorting
155        InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);
[11228]156
[11245]157        // Bring the tour back to be feasible
158        CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
[11228]159
[11245]160        // Set new Tour
161        IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
162      }
[11228]163
164      return base.Apply();
165    }
166    private void InsertPoints(List<int> actualTour, IntegerVector initialTour,
167      int neighborhood, List<int> visitablePoints, IRandom random) {
168
[11226]169      // Elect the starting index of the part to be replaced
170      int tourSize = initialTour.Length;
[11264]171      int randomPosition = random.Next(tourSize - neighborhood - 1) + 1;
[11226]172
173      for (int position = 1; position < tourSize; position++) {
174        if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
175          // Copy from initial tour when outside shaking range
176          actualTour.Add(initialTour[position]);
177
178          // Delete this point from the candidate list
179          visitablePoints.Remove(initialTour[position]);
180        } else {
[11228]181          // Point from within shaking range
[11226]182          if (visitablePoints.Count > 0) {
183            // Add the point with the highest utility from the candidate list
184            int randomFactor = random.Next(3);
185            int insertionIndex = visitablePoints.Count - 1;
186            if (visitablePoints.Count > 4) insertionIndex -= randomFactor;
187
188            actualTour.Add(visitablePoints[insertionIndex]);
189
190            // Delete this point from the candidate list
191            visitablePoints.RemoveAt(insertionIndex);
192          } else {
193            // We don't have any points left that could be inserted so we can only re-insert
194            // the removed and not already re-inserted points in a random order
[11228]195            for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {
[11226]196              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
197
198              if (!alreadyReinserted)
199                visitablePoints.Add(initialTour[reinsertPosition]);
200            }
201
[11245]202            int randomIndex = random.Next(visitablePoints.Count);
[11226]203            actualTour.Add(visitablePoints[randomIndex]);
204            visitablePoints.Clear();
205          }
206        }
207      }
[11195]208    }
[11226]209    private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {
[11228]210      // Sort the points on the tour according to their costs savings when removed
211      var distanceSavings = (
212        from removePosition in Enumerable.Range(1, actualTour.Count - 2)
213        let saving = distances.CalculateRemovementSaving(actualTour, removePosition, fixedPenalty)
214        orderby saving descending
215        select new SavingInfo { Index = removePosition, Saving = saving }
216      ).ToList();
[11226]217
[11266]218      double tourLength = distances.CalculateTourLength(actualTour, fixedPenalty);
[11226]219
220      // As long as the created path is infeasible, remove elements
[11266]221      while (tourLength > maxDistance) {
[11226]222        // Remove the point that frees the largest distance
[11266]223        // Note, distance savings are not updated after removal
224        tourLength -= distances.CalculateRemovementSaving(actualTour, distanceSavings[0].Index, fixedPenalty);
[11228]225        actualTour.RemoveAt(distanceSavings[0].Index);
[11226]226
[11228]227        // Shift indices due to removal of a point in the tour
228        for (int i = 1; i < distanceSavings.Count; i++) {
229          if (distanceSavings[i].Index > distanceSavings[0].Index) {
230            distanceSavings[i].Index--;
[11226]231          }
232        }
[11228]233        distanceSavings.RemoveAt(0);
[11226]234      }
235    }
[11228]236    //
237    private class SavingInfo {
238      public int Index;
239      public double Saving;
240    }
[11195]241  }
242}
Note: See TracBrowser for help on using the repository browser.