Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs @ 11307

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

#2208

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