Changeset 12721 for branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs
- Timestamp:
- 07/10/15 16:38:17 (9 years ago)
- Location:
- branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3
- Property svn:ignore
-
old new 2 2 obj 3 3 Plugin.cs 4 *.DotSettings
-
- Property svn:ignore
-
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs
r11323 r12721 1 1 #region License Information 2 2 /* HeuristicLab 3 * Copyright (C) 2002-201 4Heuristic and Evolutionary Algorithms Laboratory (HEAL)3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL) 4 4 * 5 5 * This file is part of HeuristicLab. … … 20 20 #endregion 21 21 22 using System;23 22 using System.Collections.Generic; 24 23 using System.Linq; … … 33 32 34 33 namespace HeuristicLab.Problems.Orienteering { 35 [Item("OrienteeringLocalImprovementOperator", @"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)")] 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.")] 38 40 [StorableClass] 39 41 public sealed class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator { … … 125 127 bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value; 126 128 127 bool optimizationDone= true;129 bool solutionChanged = true; 128 130 129 131 var tour = IntegerVectorParameter.ActualValue.ToList(); … … 137 139 138 140 // Check if the tour can be improved by adding or replacing points 139 while ( optimizationDone&& localIterations.Value < maxIterations) {140 optimizationDone= false;141 while (solutionChanged && localIterations.Value < maxIterations) { 142 solutionChanged = false; 141 143 142 144 if (localIterations.Value == 0) … … 152 154 IncludeNewPoints(tour, visitablePoints, 153 155 distances, pointVisitingCosts, maxLength, scores, 154 ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);156 ref tourLength, ref tourScore, ref evaluations, ref solutionChanged); 155 157 156 158 // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores 157 159 ReplacePoints(tour, visitablePoints, 158 160 distances, maxLength, scores, 159 ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);161 ref tourLength, ref tourScore, ref evaluations, ref solutionChanged); 160 162 161 163 localIterations.Value++; … … 173 175 174 176 private void ShortenPath(List<int> tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) { 175 bool optimizationDone = true;177 bool solutionChanged; 176 178 int pathSize = tour.Count; 177 179 maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2); 178 180 179 181 // Perform a 2-opt 180 while (optimizationDone){181 optimizationDone= false;182 do { 183 solutionChanged = false; 182 184 183 185 for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) { 184 186 // If an optimization has been done, start from the beginning 185 if ( optimizationDone) break;187 if (solutionChanged) break; 186 188 187 189 for (int position = 1; position < (pathSize - blockLength); position++) { 188 190 // If an optimization has been done, start from the beginning 189 if ( optimizationDone) break;191 if (solutionChanged) break; 190 192 191 193 evaluations++; … … 198 200 newLength += distances[tour[position], tour[position + blockLength]]; 199 201 200 if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision 202 if (newLength < tourLength - 0.00001) { 203 // Avoid cycling caused by precision 201 204 var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse(); 202 205 … … 207 210 208 211 // Re-run the optimization 209 optimizationDone= true;212 solutionChanged = true; 210 213 } 211 214 } 212 215 } 213 } 214 } 216 } while (solutionChanged); 217 } 218 215 219 private void IncludeNewPoints(List<int> tour, List<int> visitablePoints, 216 220 DistanceMatrix distances, double pointVisitingCosts, double maxLength, DoubleArray scores, 217 ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {221 ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) { 218 222 219 223 for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) { 220 224 // If an optimization has been done, start from the beginning 221 if ( optimizationDone) break;225 if (solutionChanged) break; 222 226 223 227 for (int i = 0; i < visitablePoints.Count; i++) { 224 228 // If an optimization has been done, start from the beginning 225 if ( optimizationDone) break;229 if (solutionChanged) break; 226 230 227 231 evaluations++; … … 239 243 240 244 // Re-run this optimization 241 optimizationDone= true;245 solutionChanged = true; 242 246 } 243 247 } 244 248 } 245 249 } 250 246 251 private void ReplacePoints(List<int> tour, List<int> visitablePoints, 247 252 DistanceMatrix distances, double maxLength, DoubleArray scores, 248 ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {253 ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) { 249 254 250 255 for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) { 251 256 // If an optimization has been done, start from the beginning 252 if ( optimizationDone) break;257 if (solutionChanged) break; 253 258 254 259 for (int i = 0; i < visitablePoints.Count; i++) { 255 260 // If an optimization has been done, start from the beginning 256 if ( optimizationDone) break;261 if (solutionChanged) break; 257 262 258 263 evaluations++; … … 274 279 275 280 // Re-run this optimization 276 optimizationDone= true;281 solutionChanged = true; 277 282 } 278 283 }
Note: See TracChangeset
for help on using the changeset viewer.