Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2208 Fixed random index calculation bug in shaking operator

File size: 11.8 KB
Line 
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
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  [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]
48  public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {
49
50    #region Shaking Parameter Properties
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    }
57    #endregion
58
59    #region Parameter Properties
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    }
85    #endregion
86
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
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
105      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator that will be used."));
106    }
107
108    public override IDeepCloneable Clone(Cloner cloner) {
109      return new OrienteeringShakingOperator(this, cloner);
110    }
111
112    public override IOperation Apply() {
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;
121
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
128      if (initialTour.Length > 2) {
129        // Limit the neighborhood to the tour length
130        int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
131        int limit = initialTour.Length - 2; // neighborhood limit within [0, changable tour length - 1)
132        int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;
133
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();
150
151        // Initialize the new tour
152        var actualTour = new List<int> { startingPoint };
153
154        // Perform the insertions according to the utility sorting
155        InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);
156
157        // Bring the tour back to be feasible
158        CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
159
160        // Set new Tour
161        IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
162      }
163
164      return base.Apply();
165    }
166    private void InsertPoints(List<int> actualTour, IntegerVector initialTour,
167      int neighborhood, List<int> visitablePoints, IRandom random) {
168
169      // Elect the starting index of the part to be replaced
170      int tourSize = initialTour.Length;
171      int randomPosition = random.Next(tourSize - neighborhood - 1) + 1;
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 {
181          // Point from within shaking range
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
195            for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {
196              bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
197
198              if (!alreadyReinserted)
199                visitablePoints.Add(initialTour[reinsertPosition]);
200            }
201
202            int randomIndex = random.Next(visitablePoints.Count);
203            actualTour.Add(visitablePoints[randomIndex]);
204            visitablePoints.Clear();
205          }
206        }
207      }
208    }
209    private void CleanupTour(List<int> actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {
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();
217
218      //double tourLength = distances.CalculateTourLength(actualTour, fixedPenalty);
219
220      // As long as the created path is infeasible, remove elements
221      while (distances.CalculateTourLength(actualTour, fixedPenalty) > maxDistance) {
222        // Remove the point that frees the largest distance
223        actualTour.RemoveAt(distanceSavings[0].Index);
224        //tourLength -= distanceSavings[0].Saving;
225
226        // Shift indices due to removal of a point in the tour
227        for (int i = 1; i < distanceSavings.Count; i++) {
228          if (distanceSavings[i].Index > distanceSavings[0].Index) {
229            distanceSavings[i].Index--;
230            // Note, distance savings are not updated after removal
231          }
232        }
233        distanceSavings.RemoveAt(0);
234      }
235    }
236    //
237    private class SavingInfo {
238      public int Index;
239      public double Saving;
240    }
241  }
242}
Note: See TracBrowser for help on using the repository browser.