Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs @ 16565

Last change on this file since 16565 was 16565, checked in by gkronber, 6 years ago

#2520: merged changes from PersistenceOverhaul branch (r16451:16564) into trunk

File size: 13.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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 HEAL.Attic;
32
33namespace HeuristicLab.Problems.Orienteering {
34  /// <summary>
35  /// Iterative improvement consists of three basic operators: shortening, vertex insert and vertex
36  /// exchange. The shortening operator tries to rearrange the vertices within a tour in order to
37  /// minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009)
38  /// </summary>
39  [Item("OrienteeringLocalImprovementOperator", @"Implements the iterative improvement 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.")]
40  [StorableType("92FA69B3-F243-4D12-A67A-AA1D7EBCD302")]
41  public sealed class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator {
42
43    #region Parameter Properties
44    public ILookupParameter<IntegerVector> IntegerVectorParameter {
45      get { return (ILookupParameter<IntegerVector>)Parameters["OrienteeringSolution"]; }
46    }
47    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
48      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
49    }
50    public ILookupParameter<DoubleArray> ScoresParameter {
51      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
52    }
53    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
54      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
55    }
56    public ILookupParameter<IntValue> StartingPointParameter {
57      get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }
58    }
59    public ILookupParameter<IntValue> TerminalPointParameter {
60      get { return (ILookupParameter<IntValue>)Parameters["TerminalPoint"]; }
61    }
62    public ILookupParameter<DoubleValue> PointVisitingCostsParameter {
63      get { return (ILookupParameter<DoubleValue>)Parameters["PointVisitingCosts"]; }
64    }
65    #region ILocalImprovementOperator Parameters
66    public IValueLookupParameter<IntValue> LocalIterationsParameter {
67      get { return (IValueLookupParameter<IntValue>)Parameters["LocalIterations"]; }
68    }
69    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
70      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
71    }
72    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
73      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
74    }
75    public ILookupParameter<ResultCollection> ResultsParameter {
76      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
77    }
78    #endregion
79    public ILookupParameter<DoubleValue> QualityParameter {
80      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
81    }
82    public IValueParameter<IntValue> MaximumBlockLengthParmeter {
83      get { return (IValueParameter<IntValue>)Parameters["MaximumBlockLength"]; }
84    }
85    public IValueParameter<BoolValue> UseMaximumBlockLengthParmeter {
86      get { return (IValueParameter<BoolValue>)Parameters["UseMaximumBlockLength"]; }
87    }
88    #endregion
89
90    [StorableConstructor]
91    private OrienteeringLocalImprovementOperator(StorableConstructorFlag _) : base(_) { }
92    private OrienteeringLocalImprovementOperator(OrienteeringLocalImprovementOperator original, Cloner cloner)
93      : base(original, cloner) {
94    }
95    public OrienteeringLocalImprovementOperator()
96      : base() {
97      Parameters.Add(new LookupParameter<IntegerVector>("OrienteeringSolution", "The Orienteering Solution given in path representation."));
98      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
99      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
100      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
101      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
102      Parameters.Add(new LookupParameter<IntValue>("TerminalPoint", "Index of the ending point."));
103      Parameters.Add(new LookupParameter<DoubleValue>("PointVisitingCosts", "The costs for visiting a point."));
104
105      Parameters.Add(new ValueLookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed.", new IntValue(0)));
106      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
107      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
108      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
109      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));
110
111      Parameters.Add(new ValueParameter<IntValue>("MaximumBlockLength", "The maximum length of the 2-opt shortening.", new IntValue(30)));
112      Parameters.Add(new ValueParameter<BoolValue>("UseMaximumBlockLength", "Use a limitation of the length for the 2-opt shortening.", new BoolValue(false)));
113    }
114
115    public override IDeepCloneable Clone(Cloner cloner) {
116      return new OrienteeringLocalImprovementOperator(this, cloner);
117    }
118
119    public override IOperation Apply() {
120      int numPoints = ScoresParameter.ActualValue.Length;
121      var distances = DistanceMatrixParameter.ActualValue;
122      var scores = ScoresParameter.ActualValue;
123      double pointVisitingCosts = PointVisitingCostsParameter.ActualValue.Value;
124      double maxLength = MaximumDistanceParameter.ActualValue.Value;
125      int maxIterations = MaximumIterationsParameter.ActualValue.Value;
126      int maxBlockLength = MaximumBlockLengthParmeter.Value.Value;
127      bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value;
128
129      bool solutionChanged = true;
130
131      var tour = IntegerVectorParameter.ActualValue.ToList();
132
133      double tourLength = 0;
134      double tourScore = tour.Sum(point => scores[point]);
135
136      var localIterations = LocalIterationsParameter.ActualValue;
137      var evaluatedSolutions = EvaluatedSolutionsParameter.ActualValue;
138      int evaluations = 0;
139
140      // Check if the tour can be improved by adding or replacing points
141      while (solutionChanged && localIterations.Value < maxIterations) {
142        solutionChanged = false;
143
144        if (localIterations.Value == 0)
145          tourLength = distances.CalculateTourLength(tour, pointVisitingCosts);
146
147        // Try to shorten the path
148        ShortenPath(tour, distances, maxBlockLength, useMaxBlockLength, ref tourLength, ref evaluations);
149
150        // Determine all points that have not yet been visited by this tour
151        var visitablePoints = Enumerable.Range(0, numPoints).Except(tour).ToList();
152
153        // Determine if any of the visitable points can be included at any position within the tour
154        IncludeNewPoints(tour, visitablePoints,
155          distances, pointVisitingCosts, maxLength, scores,
156          ref tourLength, ref tourScore, ref evaluations, ref solutionChanged);
157
158        // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores
159        ReplacePoints(tour, visitablePoints,
160          distances, maxLength, scores,
161          ref tourLength, ref tourScore, ref evaluations, ref solutionChanged);
162
163        localIterations.Value++;
164      }
165
166      localIterations.Value = 0;
167      evaluatedSolutions.Value += evaluations;
168
169      // Set new tour
170      IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());
171      QualityParameter.ActualValue.Value = tourScore;
172
173      return base.Apply();
174    }
175
176    private void ShortenPath(List<int> tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) {
177      bool solutionChanged;
178      int pathSize = tour.Count;
179      maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2);
180
181      // Perform a 2-opt
182      do {
183        solutionChanged = false;
184
185        for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) {
186          // If an optimization has been done, start from the beginning
187          if (solutionChanged) break;
188
189          for (int position = 1; position < (pathSize - blockLength); position++) {
190            // If an optimization has been done, start from the beginning
191            if (solutionChanged) break;
192
193            evaluations++;
194
195            double newLength = tourLength;
196            // Recalculate length of whole swapped part, in case distances are not symmetric
197            for (int index = position - 1; index < position + blockLength; index++) newLength -= distances[tour[index], tour[index + 1]];
198            for (int index = position + blockLength - 1; index > position; index--) newLength += distances[tour[index], tour[index - 1]];
199            newLength += distances[tour[position - 1], tour[position + blockLength - 1]];
200            newLength += distances[tour[position], tour[position + blockLength]];
201
202            if (newLength < tourLength - 0.00001) {
203              // Avoid cycling caused by precision
204              var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse();
205
206              tour.RemoveRange(position, blockLength);
207              tour.InsertRange(position, reversePart);
208
209              tourLength = newLength;
210
211              // Re-run the optimization
212              solutionChanged = true;
213            }
214          }
215        }
216      } while (solutionChanged);
217    }
218
219    private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,
220      DistanceMatrix distances, double pointVisitingCosts, double maxLength, DoubleArray scores,
221      ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) {
222
223      for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {
224        // If an optimization has been done, start from the beginning
225        if (solutionChanged) break;
226
227        for (int i = 0; i < visitablePoints.Count; i++) {
228          // If an optimization has been done, start from the beginning
229          if (solutionChanged) break;
230
231          evaluations++;
232
233          double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], pointVisitingCosts);
234
235          // Determine if including the point does not violate any constraint
236          if (tourLength + detour <= maxLength) {
237            // Insert the new point at this position
238            tour.Insert(tourPosition, visitablePoints[i]);
239
240            // Update the overall tour tourLength and score
241            tourLength += detour;
242            tourScore += scores[visitablePoints[i]];
243
244            // Re-run this optimization
245            solutionChanged = true;
246          }
247        }
248      }
249    }
250
251    private void ReplacePoints(List<int> tour, List<int> visitablePoints,
252      DistanceMatrix distances, double maxLength, DoubleArray scores,
253      ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) {
254
255      for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) {
256        // If an optimization has been done, start from the beginning
257        if (solutionChanged) break;
258
259        for (int i = 0; i < visitablePoints.Count; i++) {
260          // If an optimization has been done, start from the beginning
261          if (solutionChanged) break;
262
263          evaluations++;
264
265          double detour = distances.CalculateReplacementCosts(tour, tourPosition, visitablePoints[i]);
266
267          double oldPointScore = scores[tour[tourPosition]];
268          double newPointScore = scores[visitablePoints[i]];
269
270          if ((tourLength + detour <= maxLength) && (newPointScore > oldPointScore)) {
271            // Replace the old point by the new one
272            tour[tourPosition] = visitablePoints[i];
273
274            // Update the overall tour tourLength
275            tourLength += detour;
276
277            // Update the scores achieved by visiting this point
278            tourScore += newPointScore - oldPointScore;
279
280            // Re-run this optimization
281            solutionChanged = true;
282          }
283        }
284      }
285    }
286  }
287}
Note: See TracBrowser for help on using the repository browser.