Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2839_HiveProjectManagement/HeuristicLab.Problems.Orienteering/3.3/Shakers/OrienteeringShakingOperator.cs @ 17035

Last change on this file since 17035 was 16057, checked in by jkarder, 6 years ago

#2839:

File size: 12.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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
22using System.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.Orienteering {
34  /// <summary>
35  /// The used neighborhood operator is based on a two point exchange move. A move in
36  /// the k-th neighborhood consists of removing k consecutive vertices from the tour, starting
37  /// at a randomly selected position. Afterwards, a sorted list of all vertices not yet included
38  /// in the current tour is built. The vertices are sorted in descending order with respect to the
39  /// objective value increase using the current weights. Out of the first three entries with the
40  /// highest ranking in this list, one randomly selected vertex is reinserted into the current tour
41  /// at the same position as the removed vertices. This way, l new vertices are inserted into the
42  /// tour. The largest neighborhood is a complete exchange of all vertices on the tour.
43  /// The shaking procedure does not guarantee that the new tour does not exceed the cost
44  /// limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The
45  /// vertices are sorted in descending order with respect to costs saved when removing the vertex
46  /// from the tour. Vertices are removed as long as the cost limit is violated.
47  /// (Schilde et. al. 2009)
48  /// </summary>
49  [Item("OrienteeringShakingOperator", @"Implements the shaking procedure described in Schilde M., Doerner K.F., Hartl R.F., Kiechle G. 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, Volume 3, Issue 3, pp 179-201.")]
50  [StorableClass]
51  public sealed class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {
52
53    #region Shaking Parameter Properties
54    public IValueLookupParameter<IntValue> CurrentNeighborhoodIndexParameter {
55      get { return (IValueLookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
56    }
57    public ILookupParameter<IntValue> NeighborhoodCountParameter {
58      get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
59    }
60    #endregion
61
62    #region Parameter Properties
63    public ILookupParameter<IntegerVector> IntegerVectorParameter {
64      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
65    }
66    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
67      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
68    }
69    public ILookupParameter<IntValue> StartingPointParameter {
70      get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }
71    }
72    public ILookupParameter<IntValue> TerminalPointParameter {
73      get { return (ILookupParameter<IntValue>)Parameters["TerminalPoint"]; }
74    }
75    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
76      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
77    }
78    public ILookupParameter<DoubleArray> ScoresParameter {
79      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
80    }
81    public ILookupParameter<DoubleValue> PointVisitingCostsParameter {
82      get { return (ILookupParameter<DoubleValue>)Parameters["PointVisitingCosts"]; }
83    }
84
85    public ILookupParameter<IRandom> RandomParameter {
86      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
87    }
88    #endregion
89
90    [StorableConstructor]
91    private OrienteeringShakingOperator(bool deserializing) : base(deserializing) { }
92    private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)
93      : base(original, cloner) {
94    }
95    public OrienteeringShakingOperator()
96      : base() {
97      Parameters.Add(new ValueLookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
98      Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of operators that are available."));
99
100      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
101      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
102      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
103      Parameters.Add(new LookupParameter<IntValue>("TerminalPoint", "Index of the ending point."));
104      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
105      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
106      Parameters.Add(new LookupParameter<DoubleValue>("PointVisitingCosts", "The costs for visiting a point."));
107
108      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
109    }
110
111    public override IDeepCloneable Clone(Cloner cloner) {
112      return new OrienteeringShakingOperator(this, cloner);
113    }
114
115    public override IOperation Apply() {
116      var initialTour = IntegerVectorParameter.ActualValue;
117      var distances = DistanceMatrixParameter.ActualValue;
118      var scores = ScoresParameter.ActualValue;
119      var startingPoint = StartingPointParameter.ActualValue.Value;
120      var terminalPoint = TerminalPointParameter.ActualValue.Value;
121      var pointVisitingCosts = PointVisitingCostsParameter.ActualValue.Value;
122      double maxDistance = MaximumDistanceParameter.ActualValue.Value;
123      int numPoints = scores.Length;
124
125      if (NeighborhoodCountParameter.ActualValue == null)
126        NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);
127      else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;
128
129      var random = RandomParameter.ActualValue;
130
131      if (initialTour.Length > 2) {
132        // Limit the neighborhood to the tour length
133        int currentNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
134        int maximumNeighborhood = initialTour.Length - 2; // neighborhood limit within [0, changable tour length - 1)
135        maximumNeighborhood = (maximumNeighborhood > currentNeighborhood) ? currentNeighborhood : maximumNeighborhood;
136        int neighborhood = maximumNeighborhood;
137
138        // Find all points that are not yet included in the tour and are
139        // within the maximum distance allowed (ellipse)
140        // and sort them with regard to their utility
141        var visitablePoints = (
142          from point in Enumerable.Range(0, numPoints)
143          // Calculate the distance when going from the starting point to this point and then to the end point
144          let distance = distances[startingPoint, point] + distances[point, terminalPoint] + pointVisitingCosts
145          // If this distance is feasible and the point is neither starting nor ending point, check the point
146          where distance < maxDistance && point != startingPoint && point != terminalPoint
147          // The point was not yet visited, so add it to the candidate list
148          where !initialTour.Contains(point)
149          // Calculate the utility of the point at this position
150          let utility = scores[point]
151          orderby utility
152          select point
153          ).ToList();
154
155        // Initialize the new tour
156        var actualTour = new List<int> { startingPoint };
157
158        // Perform the insertions according to the utility sorting
159        InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);
160
161        // Bring the tour back to be feasible
162        CleanupTour(actualTour, distances, maxDistance, pointVisitingCosts);
163
164        // Set new Tour
165        IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
166      }
167
168      return base.Apply();
169    }
170
171    private void InsertPoints(List<int> actualTour, IntegerVector initialTour,
172      int neighborhood, List<int> visitablePoints, IRandom random) {
173
174      // Elect the starting index of the part to be replaced
175      int tourSize = initialTour.Length;
176      int randomPosition = random.Next(tourSize - neighborhood - 1) + 1;
177
178      for (int position = 1; position < tourSize; position++) {
179        if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
180          // Copy from initial tour when outside shaking range
181          actualTour.Add(initialTour[position]);
182
183          // Delete this point from the candidate list
184          visitablePoints.Remove(initialTour[position]);
185        } else {
186          // Point from within shaking range
187          if (visitablePoints.Count > 0) {
188            // Add the point with the highest utility from the candidate list
189            int randomFactor = random.Next(3);
190            int insertionIndex = visitablePoints.Count - 1;
191            if (visitablePoints.Count > 4) insertionIndex -= randomFactor;
192
193            actualTour.Add(visitablePoints[insertionIndex]);
194
195            // Delete this point from the candidate list
196            visitablePoints.RemoveAt(insertionIndex);
197          } else {
198            // We don't have any points left that could be inserted so we can only re-insert
199            // the removed and not already re-inserted points in a random order
200            for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {
201              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
202
203              if (!alreadyReinserted)
204                visitablePoints.Add(initialTour[reinsertPosition]);
205            }
206
207            int randomIndex = random.Next(visitablePoints.Count);
208            actualTour.Add(visitablePoints[randomIndex]);
209            visitablePoints.Clear();
210          }
211        }
212      }
213    }
214
215    private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double pointVisitingCosts) {
216      // Sort the points on the tour according to their costs savings when removed
217      var distanceSavings = (
218        from removePosition in Enumerable.Range(1, actualTour.Count - 2)
219        let saving = distances.CalculateRemovementSaving(actualTour, removePosition, pointVisitingCosts)
220        orderby saving descending
221        select new SavingInfo { Index = removePosition, Saving = saving }
222      ).ToList();
223
224      double tourLength = distances.CalculateTourLength(actualTour, pointVisitingCosts);
225
226      // As long as the created path is infeasible, remove elements
227      while (tourLength > maxDistance) {
228        // Remove the point that frees the largest distance
229        // Note, distance savings are not updated after removal
230        tourLength -= distances.CalculateRemovementSaving(actualTour, distanceSavings[0].Index, pointVisitingCosts);
231        actualTour.RemoveAt(distanceSavings[0].Index);
232
233        // Shift indices due to removal of a point in the tour
234        for (int i = 1; i < distanceSavings.Count; i++) {
235          if (distanceSavings[i].Index > distanceSavings[0].Index) {
236            distanceSavings[i].Index--;
237          }
238        }
239        distanceSavings.RemoveAt(0);
240      }
241    }
242
243    private class SavingInfo {
244      public int Index;
245      public double Saving;
246    }
247  }
248}
Note: See TracBrowser for help on using the repository browser.