1  #region License Information


2  /* HeuristicLab


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


24  using HeuristicLab.Core;


25  using HeuristicLab.Data;


26  using HeuristicLab.Encodings.PermutationEncoding;


27  using HeuristicLab.Parameters;


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


29 


30  namespace HeuristicLab.Problems.PTSP {


31  [Item("PTSP Estimated Insertion Move Evaluator", "Evaluates an insertion move (1shift)")]


32  [StorableClass]


33  public class PTSPEstimatedInsertionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationTranslocationMoveOperator {


34 


35  public ILookupParameter<TranslocationMove> TranslocationMoveParameter {


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


37  }


38 


39  [StorableConstructor]


40  protected PTSPEstimatedInsertionMoveEvaluator(bool deserializing) : base(deserializing) { }


41  protected PTSPEstimatedInsertionMoveEvaluator(PTSPEstimatedInsertionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }


42  public PTSPEstimatedInsertionMoveEvaluator()


43  : base() {


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


45  }


46 


47  public override IDeepCloneable Clone(Cloner cloner) {


48  return new PTSPEstimatedInsertionMoveEvaluator(this, cloner);


49  }


50 


51  public static double EvaluateMove(Permutation tour, TranslocationMove move, Func<int, int, double> distance, ItemList<BoolArray> realizations) {


52  var afterMove = (Permutation)tour.Clone();


53  TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);


54  double moveQuality = 0;


55  var edges = new int[12];


56  var indices = new int[12];


57  edges[0] = tour.GetCircular(move.Index1  1);


58  indices[0] = DecreaseCircularIndex(tour.Length, move.Index1);


59  edges[1] = tour[move.Index1];


60  indices[1] = move.Index1;


61  edges[2] = tour[move.Index1];


62  indices[2] = move.Index1;


63  edges[3] = tour.GetCircular(move.Index1 + 1);


64  indices[3] = IncreaseCircularIndex(tour.Length, move.Index1);


65 


66  edges[6] = afterMove.GetCircular(move.Index3  1);


67  indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);


68  edges[7] = afterMove[move.Index3];


69  indices[7] = move.Index3;


70  edges[8] = afterMove[move.Index3];


71  indices[8] = move.Index3;


72  edges[9] = afterMove.GetCircular(move.Index3 + 1);


73  indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);


74 


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


76  edges[4] = tour[move.Index3];


77  indices[4] = move.Index3;


78  edges[5] = tour.GetCircular(move.Index3 + 1);


79  indices[5] = indices[9];


80  edges[10] = afterMove.GetCircular(move.Index1  1);


81  indices[10] = indices[0];


82  edges[11] = afterMove[move.Index1];


83  indices[11] = move.Index1;


84  } else {


85  edges[4] = tour.GetCircular(move.Index3  1);


86  indices[4] = indices[6];


87  edges[5] = tour[move.Index3];


88  indices[5] = move.Index3;


89  edges[10] = afterMove[move.Index1];


90  indices[10] = move.Index1;


91  edges[11] = afterMove.GetCircular(move.Index1 + 1);


92  indices[11] = indices[3];


93  }


94  int[] aPosteriori = new int[12];


95  foreach (var realization in realizations) {


96  for (int i = 0; i < edges.Length; i++) {


97  Permutation tempPermutation;


98  if (i < 6) {


99  tempPermutation = tour;


100  } else {


101  tempPermutation = afterMove;


102  }


103  if (realization[edges[i]]) {


104  aPosteriori[i] = edges[i];


105  } else {


106  int j = 1;


107  if (i % 2 == 0) {


108  // find nearest predecessor in realization if source edge


109  while (!realization[tempPermutation.GetCircular(indices[i]  j)]) {


110  j++;


111  }


112  aPosteriori[i] = tempPermutation.GetCircular(indices[i]  j);


113  } else {


114  // find nearest successor in realization if target edge


115  while (!realization[tempPermutation.GetCircular(indices[i] + j)]) {


116  j++;


117  }


118  aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);


119  }


120  }


121  }


122  if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&


123  !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&


124  !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {


125  // compute cost difference between the two a posteriori solutions


126  moveQuality = moveQuality + distance(aPosteriori[6], aPosteriori[7]) + distance(aPosteriori[8], aPosteriori[9]) + distance(aPosteriori[10], aPosteriori[11]);


127  moveQuality = moveQuality  distance(aPosteriori[0], aPosteriori[1])  distance(aPosteriori[2], aPosteriori[3])  distance(aPosteriori[4], aPosteriori[5]);


128  }


129  Array.Clear(aPosteriori, 0, aPosteriori.Length);


130  }


131  // return average of cost differences


132  return moveQuality / realizations.Count;


133  }


134 


135  private static int DecreaseCircularIndex(int length, int index) {


136  var result = index  1;


137  if (result == 1) {


138  result = length  1;


139  }


140  return result;


141  }


142 


143  private static int IncreaseCircularIndex(int length, int index) {


144  var result = index + 1;


145  if (result == length + 1) {


146  result = 0;


147  }


148  return result;


149  }


150 


151  protected override double EvaluateMove(Permutation tour, Func<int, int, double> distance, ItemList<BoolArray> realizations) {


152  return EvaluateMove(tour, TranslocationMoveParameter.ActualValue, distance, realizations);


153  }


154  }


155  }

