1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022014 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.IntegerVectorEncoding;


29  using HeuristicLab.Operators;


30  using HeuristicLab.Optimization;


31  using HeuristicLab.Parameters;


32  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


33 


34  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 2opt 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  problem = (OrienteeringProblem)value;


54  }


55  }


56  }


57  #endregion


58 


59  [Storable]


60  private OrienteeringProblem problem;


61 


62  #region Parameter Properties


63  public ILookupParameter<IntegerVector> IntegerVectorParameter {


64  get { return (ILookupParameter<IntegerVector>)Parameters["OrienteeringSolution"]; }


65  }


66  public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {


67  get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }


68  }


69  public ILookupParameter<DoubleArray> ScoresParameter {


70  get { return (ILookupParameter<DoubleArray>)Parameters["Scores"]; }


71  }


72  public ILookupParameter<DoubleValue> MaximumDistanceParameter {


73  get { return (ILookupParameter<DoubleValue>)Parameters["MaximumDistance"]; }


74  }


75  public ILookupParameter<IntValue> StartingPointParameter {


76  get { return (ILookupParameter<IntValue>)Parameters["StartingPoint"]; }


77  }


78  public ILookupParameter<IntValue> TerminusPointParameter {


79  get { return (ILookupParameter<IntValue>)Parameters["TerminusPoint"]; }


80  }


81  public ILookupParameter<DoubleValue> FixedPenaltyParameter {


82  get { return (ILookupParameter<DoubleValue>)Parameters["FixedPenalty"]; }


83  }


84  #region ILocalImprovementOperator Parameters


85  public IValueLookupParameter<IntValue> MaximumIterationsParameter {


86  get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }


87  }


88  public ILookupParameter<IntValue> EvaluatedSolutionsParameter {


89  get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }


90  }


91  public ILookupParameter<ResultCollection> ResultsParameter {


92  get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }


93  }


94  #endregion


95  public ILookupParameter<DoubleValue> QualityParameter {


96  get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }


97  }


98  #endregion


99 


100  [StorableConstructor]


101  private OrienteeringLocalImprovementOperator(bool deserializing) : base(deserializing) { }


102  private OrienteeringLocalImprovementOperator(OrienteeringLocalImprovementOperator original, Cloner cloner)


103  : base(original, cloner) {


104  this.problem = cloner.Clone(original.problem);


105  }


106  public OrienteeringLocalImprovementOperator()


107  : base() {


108  Parameters.Add(new LookupParameter<IntegerVector>("OrienteeringSolution", "The Orienteering Solution given in path representation."));


109  Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the points."));


110  Parameters.Add(new LookupParameter<DoubleArray>("Scores", "The scores of the points."));


111  Parameters.Add(new LookupParameter<DoubleValue>("MaximumDistance", "The maximum distance constraint for a Orienteering solution."));


112  Parameters.Add(new LookupParameter<IntValue>("StartingPoint", "Index of the starting point."));


113  Parameters.Add(new LookupParameter<IntValue>("TerminusPoint", "Index of the ending point."));


114  Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));


115 


116  Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));


117  Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));


118  Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));


119  Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));


120  }


121 


122  public override IDeepCloneable Clone(Cloner cloner) {


123  return new OrienteeringLocalImprovementOperator(this, cloner);


124  }


125 


126  public override IOperation Apply() {


127  int numPoints = ScoresParameter.ActualValue.Length;


128  var distances = DistanceMatrixParameter.ActualValue;


129  var scores = ScoresParameter.ActualValue;


130  double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;


131  double maxLength = MaximumDistanceParameter.ActualValue.Value;


132 


133  bool optimizationDone = true;


134 


135  var tour = IntegerVectorParameter.ActualValue.ToList();


136 


137  double tourLength = distances.CalculateTourLength(tour, fixedPenalty);


138  double tourScore = tour.Sum(point => scores[point]);


139 


140  // Check if the tour can be improved by adding or replacing points


141  while (optimizationDone) {


142  optimizationDone = false;


143 


144  // Try to shorten the path


145  ShortenPath(tour, distances, ref tourLength);


146 


147  // Determine all points that have not yet been visited by this tour


148  var visitablePoints = Enumerable.Range(0, numPoints).Except(tour).ToList();


149 


150  // Determine if any of the visitable points can be included at any position within the tour


151  IncludeNewPoints(tour, visitablePoints,


152  distances, fixedPenalty, maxLength, scores,


153  ref tourLength, ref tourScore, ref optimizationDone);


154 


155  // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores


156  ReplacePoints(tour, visitablePoints,


157  distances, maxLength, scores,


158  ref tourLength, ref tourScore, ref optimizationDone);


159  }


160 


161  // Set new tour


162  IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray());


163  QualityParameter.ActualValue.Value = tourScore;


164 


165  return base.Apply();


166  }


167 


168  private void ShortenPath(List<int> tour, DistanceMatrix distances, ref double tourLength) {


169  bool optimizationDone = true;


170  int pathSize = tour.Count;


171  int maxBlockLength = (pathSize > 31) ? 30 : (pathSize  2);


172 


173  // Perform a 2opt


174  while (optimizationDone) {


175  optimizationDone = false;


176 


177  for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) {


178  // If an optimization has been done, start from the beginning


179  if (optimizationDone) break;


180 


181  for (int position = 1; position < (pathSize  blockLength); position++) {


182  // If an optimization has been done, start from the beginning


183  if (optimizationDone) break;


184 


185  double newLength = tourLength;


186  // Recalculate length of whole swapped part, in case distances are not symmetric


187  for (int index = position  1; index < position + blockLength; index++) newLength = distances[tour[index], tour[index + 1]];


188  for (int index = position + blockLength  1; index > position; index) newLength += distances[tour[index], tour[index  1]];


189  newLength += distances[tour[position  1], tour[position + blockLength  1]];


190  newLength += distances[tour[position], tour[position + blockLength]];


191 


192  if (newLength < tourLength  0.00001) { // Avoid cycling caused by precision


193  var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse();


194 


195  tour.RemoveRange(position, blockLength);


196  tour.InsertRange(position, reversePart);


197 


198  tourLength = newLength;


199 


200  // Rerun the optimization


201  optimizationDone = true;


202  }


203  }


204  }


205  }


206  }


207  private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,


208  DistanceMatrix distances, double fixedPenalty, double maxLength, DoubleArray scores,


209  ref double tourLength, ref double tourScore, ref bool optimizationDone) {


210 


211  for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {


212  // If an optimization has been done, start from the beginning


213  if (optimizationDone) break;


214 


215  for (int i = 0; i < visitablePoints.Count; i++) {


216  // If an optimization has been done, start from the beginning


217  if (optimizationDone) break;


218 


219  double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], fixedPenalty);


220 


221  // Determine if including the point does not violate any constraint


222  if (tourLength + detour <= maxLength) {


223  // Insert the new point at this position


224  tour.Insert(tourPosition, visitablePoints[i]);


225 


226  // Update the overall tour tourLength and score


227  tourLength += detour;


228  tourScore += scores[visitablePoints[i]];


229 


230  // Rerun this optimization


231  optimizationDone = true;


232  }


233  }


234  }


235  }


236  private void ReplacePoints(List<int> tour, List<int> visitablePoints,


237  DistanceMatrix distances, double maxLength, DoubleArray scores,


238  ref double tourLength, ref double tourScore, ref bool optimizationDone) {


239 


240  for (int tourPosition = 1; tourPosition < tour.Count  1; tourPosition++) {


241  // If an optimization has been done, start from the beginning


242  if (optimizationDone) break;


243 


244  for (int i = 0; i < visitablePoints.Count; i++) {


245  // If an optimization has been done, start from the beginning


246  if (optimizationDone) break;


247 


248  double detour = distances.CalculateReplacementCosts(tour, tourPosition, visitablePoints[i]);


249 


250  double oldPointScore = scores[tour[tourPosition]];


251  double newPointScore = scores[visitablePoints[i]];


252 


253  if ((tourLength + detour <= maxLength) && (newPointScore > oldPointScore)) {


254  // Replace the old point by the new one


255  tour[tourPosition] = visitablePoints[i];


256 


257  // Update the overall tour tourLength


258  tourLength += detour;


259 


260  // Update the scores achieved by visiting this point


261  tourScore += newPointScore  oldPointScore;


262 


263  // Rerun this optimization


264  optimizationDone = true;


265  }


266  }


267  }


268  }


269  }


270  } 
