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

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

#2208:

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