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

Last change on this file since 11194 was 11194, checked in by pfleck, 8 years ago

#2208

  • Added OrienteeringLocalImprovementOperator parameterization
  • Renamed some stuff
File size: 12.0 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 class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator {
40    #region IGenericLocalImprovementOperator Properties
41    public Type ProblemType { get { return typeof(OrienteeringProblem); } }
42    public IProblem Problem {
43      get { return problem; }
44      set {
45        if (problem != value) {
46          if (value != null && !(value is OrienteeringProblem))
47            throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
48          //if (problem != null) DeregisterProblemEventHandlers();
49          problem = (OrienteeringProblem)value;
50          //if (problem != null) RegisterProblemEventHandlers();
51          //UpdateProblem();
52        }
53      }
54    }
55    #endregion
56
57    [Storable]
58    private OrienteeringProblem problem;
59
60    #region Parameter Properties
61
62    public ILookupParameter<IntegerVector> IntegerVectorParameter {
63      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
64    }
65    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
66      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
67    }
68    public ILookupParameter<DoubleArray> ScoresParameter {
69      get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }
70    }
71    public ILookupParameter<DoubleValue> MaximumDistanceParameter {
72      get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }
73    }
74    public ILookupParameter<IntValue> StartingPointParameter {
75      get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }
76    }
77    public ILookupParameter<IntValue> TerminusPointParameter {
78      get { return (ILookupParameter<IntValue>)Parameters["TerminusPoint"]; }
79    }
80    public ILookupParameter<DoubleValue> FixedPenaltyParameter {
81      get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }
82    }
83    #region ILocalImprovementOperator Parameters
84    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
85      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
86    }
87    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
88      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
89    }
90    public ILookupParameter<ResultCollection> ResultsParameter {
91      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
92    }
93    #endregion
94    #endregion
95
96    [StorableConstructor]
97    private OrienteeringLocalImprovementOperator(bool deserializing) : base(deserializing) { }
98    private OrienteeringLocalImprovementOperator(OrienteeringLocalImprovementOperator original, Cloner cloner)
99      : base(original, cloner) {
100      this.problem = cloner.Clone(original.problem);
101      //RegisterEventHandlers();
102    }
103    public OrienteeringLocalImprovementOperator()
104      : base() {
105      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The Orienteering Solution given in path representation."));
106      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));
107      Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));
108      Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));
109      Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));
110      Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));
111      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
112      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
113      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
114      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
115
116      //RegisterEventHandlers();
117    }
118
119    public override IDeepCloneable Clone(Cloner cloner) {
120      return new OrienteeringLocalImprovementOperator(this, cloner);
121    }
122
123    [StorableHook(HookType.AfterDeserialization)]
124    private void AfterDeserialization() {
125      //RegisterEventHandlers();
126    }
127
128    public override IOperation Apply() {
129      // TODO Use LocalImprovementorOperator Parameters
130
131      int numPoints = ScoresParameter.ActualValue.Length;
132      var distances = DistanceMatrixParameter.ActualValue;
133      var scores = ScoresParameter.ActualValue;
134      double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
135
136      bool optimizationDone = true;
137
138      // Find the maximum distance restriction
139      double maxLength = MaximumDistanceParameter.ActualValue.Value;
140
141      var tour = IntegerVectorParameter.ActualValue.ToList();
142
143      double tourLength = distances.CalculateTourLength(tour, fixedPenalty);
144      double score = tour.Sum(p => scores[p]);
145
146      // Check if the tour can be improved by adding or replacing points
147      while (optimizationDone) {
148        optimizationDone = false;
149
150        // Try to shorten the path
151        ShortenPath(tour, distances, ref tourLength);
152
153        // Determine all points that have not yet been visited by this tour
154        var visitablePoints = Enumerable.Range(0, numPoints).Except(tour).ToList();
155
156        // Determine if any of the visitable points can be included at any position within the tour
157        IncludeNewPoints(tour, visitablePoints,
158          distances, fixedPenalty, maxLength,
159          ref tourLength, ref optimizationDone);
160
161        // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores
162        ReplacePoints(tour, visitablePoints,
163          distances, maxLength, scores,
164          ref tourLength, ref score, ref optimizationDone);
165      }
166
167      IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());
168
169      return base.Apply();
170    }
171
172    private void ShortenPath(List<int> tour, DistanceMatrix distances, ref double tourLength) {
173      bool optimizationDone = true;
174      int pathSize = tour.Count;
175      int maxBlockLength = (pathSize > 31) ? 30 : (pathSize - 2);
176
177      // Perform a 2-opt
178      while (optimizationDone) {
179        optimizationDone = false;
180
181        for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) {
182          // If an optimization has been done, start from the beginning
183          if (optimizationDone) break;
184
185          for (int position = 1; position < (pathSize - blockLength); position++) {
186            // If an optimization has been done, start from the beginning
187            if (optimizationDone) break;
188
189            double newLength = tourLength;
190            for (int counterLength = (position - 1); counterLength < (position + blockLength); counterLength++) {
191              newLength -= distances[tour[counterLength], tour[counterLength + 1]];
192            }
193            for (int counterLength = (position + blockLength - 1); counterLength > (position); counterLength--) {
194              newLength += distances[tour[counterLength], tour[counterLength - 1]];
195            }
196            newLength += distances[tour[position - 1], tour[position + blockLength - 1]];
197            newLength += distances[tour[position], tour[position + blockLength]];
198
199
200            if (newLength <= (tourLength - 0.00001)) { // Avoid cycling caused by precision
201              var partPath = tour.GetRange(position, blockLength);
202
203              tour.RemoveRange(position, blockLength);
204              tour.InsertRange(position, partPath.AsEnumerable().Reverse());
205
206              tourLength = newLength;
207
208              // Re-run the optimization
209              optimizationDone = true;
210            }
211          }
212        }
213      }
214    }
215    private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,
216      DistanceMatrix distances, double fixedPenalty, double maxLength,
217      ref double tourLength, ref bool optimizationDone) {
218
219      for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {
220        // If an optimization has been done, start from the beginning
221        if (optimizationDone) break;
222
223        for (int i = 0; i < visitablePoints.Count; i++) {
224          // If an optimization has been done, start from the beginning
225          if (optimizationDone) break;
226
227          double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], fixedPenalty);
228
229          // Determine if including the point does not violate any constraint
230          if (tourLength + detour <= maxLength) {
231            // Insert the new point at this position
232            tour.Insert(tourPosition, visitablePoints[i]);
233
234            // Update the overall tour tourLength
235            tourLength += detour;
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 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          double detour = distances.CalculateReplacementCosts(tour, tourPosition, visitablePoints[i]);
256
257          double oldPointScore = scores[tour[tourPosition]];
258          double newPointScore = scores[visitablePoints[i]];
259
260          if (tourLength + detour <= maxLength && newPointScore > oldPointScore) {
261            // Replace the old point by the new one
262            tour[tourPosition] = visitablePoints[i];
263
264            // Update the overall tour tourLength
265            tourLength += detour;
266
267            // Update the scores achieved by visiting this point
268            tourScore += newPointScore - oldPointScore;
269
270            // Re-run this optimization
271            optimizationDone = true;
272          }
273        }
274      }
275    }
276  }
277}
Note: See TracBrowser for help on using the repository browser.