1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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 HeuristicLab.Common;


23  using HeuristicLab.Core;


24  using HeuristicLab.Data;


25  using HeuristicLab.Encodings.PermutationEncoding;


26  using HeuristicLab.Parameters;


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


28 


29  namespace HeuristicLab.Problems.TravelingSalesman {


30  /// <summary>


31  /// An operator to evaluate a translocation or insertion move.


32  /// </summary>


33  [Item("TSPTranslocationMovePathEvaluator", "Evaluates a translocation or insertion move (3opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]


34  [StorableClass]


35  public abstract class TSPTranslocationMovePathEvaluator : TSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {


36  public ILookupParameter<TranslocationMove> TranslocationMoveParameter {


37  get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }


38  }


39 


40  [StorableConstructor]


41  protected TSPTranslocationMovePathEvaluator(bool deserializing) : base(deserializing) { }


42  protected TSPTranslocationMovePathEvaluator(TSPTranslocationMovePathEvaluator original, Cloner cloner) : base(original, cloner) { }


43  public TSPTranslocationMovePathEvaluator()


44  : base() {


45  Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));


46  }


47 


48  protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {


49  TranslocationMove move = TranslocationMoveParameter.ActualValue;


50  int edge1source = permutation.GetCircular(move.Index1  1);


51  int edge1target = permutation[move.Index1];


52  int edge2source = permutation[move.Index2];


53  int edge2target = permutation.GetCircular(move.Index2 + 1);


54  int edge3source, edge3target;


55  if (move.Index3 > move.Index1) {


56  edge3source = permutation.GetCircular(move.Index3 + move.Index2  move.Index1);


57  edge3target = permutation.GetCircular(move.Index3 + move.Index2  move.Index1 + 1);


58  } else {


59  edge3source = permutation.GetCircular(move.Index3  1);


60  edge3target = permutation[move.Index3];


61  }


62  if (move.Index1 == move.Index3


63   move.Index2  move.Index1 >= permutation.Length  2


64   move.Index1 == permutation.Length  1 && move.Index3 == 0


65   move.Index1 == 0 && move.Index3 == permutation.Length  1) return 0;


66  double moveQuality = 0;


67  // remove three edges


68  moveQuality = CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],


69  coordinates[edge1target, 0], coordinates[edge1target, 1]);


70  moveQuality = CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],


71  coordinates[edge2target, 0], coordinates[edge2target, 1]);


72  moveQuality = CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],


73  coordinates[edge3target, 0], coordinates[edge3target, 1]);


74  // add three edges


75  moveQuality += CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],


76  coordinates[edge1target, 0], coordinates[edge1target, 1]);


77  moveQuality += CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],


78  coordinates[edge3target, 0], coordinates[edge3target, 1]);


79  moveQuality += CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],


80  coordinates[edge2target, 0], coordinates[edge2target, 1]);


81  return moveQuality;


82  }


83 


84  protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {


85  TranslocationMove move = TranslocationMoveParameter.ActualValue;


86  int edge1source = permutation.GetCircular(move.Index1  1);


87  int edge1target = permutation[move.Index1];


88  int edge2source = permutation[move.Index2];


89  int edge2target = permutation.GetCircular(move.Index2 + 1);


90  int edge3source, edge3target;


91  if (move.Index3 > move.Index1) {


92  edge3source = permutation.GetCircular(move.Index3 + move.Index2  move.Index1);


93  edge3target = permutation.GetCircular(move.Index3 + move.Index2  move.Index1 + 1);


94  } else {


95  edge3source = permutation.GetCircular(move.Index3  1);


96  edge3target = permutation[move.Index3];


97  }


98  if (move.Index1 == move.Index3


99   move.Index2  move.Index1 >= permutation.Length  2


100   move.Index1 == permutation.Length  1 && move.Index3 == 0


101   move.Index1 == 0 && move.Index3 == permutation.Length  1) return 0;


102  double moveQuality = 0;


103  // remove three edges


104  moveQuality = distanceMatrix[edge1source, edge1target];


105  moveQuality = distanceMatrix[edge2source, edge2target];


106  moveQuality = distanceMatrix[edge3source, edge3target];


107  // add three edges


108  moveQuality += distanceMatrix[edge3source, edge1target];


109  moveQuality += distanceMatrix[edge2source, edge3target];


110  moveQuality += distanceMatrix[edge1source, edge2target];


111  return moveQuality;


112  }


113  }


114  }

