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.Encodings.PermutationEncoding;


26  using HeuristicLab.Optimization.Operators;


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


28 


29  namespace HeuristicLab.Problems.TravelingSalesman {


30  /// <summary>


31  /// An operator that performs similarity calculation between two traveling salesman solutions.


32  /// </summary>


33  /// <remarks>


34  /// The operator calculates the similarity based on the number of edges the two solutions have in common.


35  /// </remarks>


36  [StorableType("D5AD7A0957384F14AB3C4943C32FACC6")]


37  [Item("TSPSimilarityCalculator", "An operator that performs similarity calculation between two traveling salesman solutions. The operator calculates the similarity based on the number of edges the two solutions have in common.")]


38  public sealed class TSPSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {


39  protected override bool IsCommutative { get { return true; } }


40 


41  private TSPSimilarityCalculator(bool deserializing) : base(deserializing) { }


42  private TSPSimilarityCalculator(TSPSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }


43  public TSPSimilarityCalculator() : base() { }


44 


45  public override IDeepCloneable Clone(Cloner cloner) {


46  return new TSPSimilarityCalculator(this, cloner);


47  }


48 


49  public static double CalculateSimilarity(Permutation left, Permutation right) {


50  if (left == null  right == null)


51  throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");


52  if (left.PermutationType != right.PermutationType)


53  throw new ArgumentException("Cannot calculate similarity because the provided solutions have different types.");


54  if (left.Length != right.Length)


55  throw new ArgumentException("Cannot calculate similarity because the provided solutions have different lengths.");


56  if (object.ReferenceEquals(left, right)) return 1.0;


57 


58  switch (left.PermutationType) {


59  case PermutationTypes.Absolute:


60  return CalculateAbsolute(left, right);


61  case PermutationTypes.RelativeDirected:


62  return CalculateRelativeDirected(left, right);


63  case PermutationTypes.RelativeUndirected:


64  return CalculateRelativeUndirected(left, right);


65  default:


66  throw new InvalidOperationException("unknown permutation type");


67  }


68  }


69 


70  private static double CalculateAbsolute(Permutation left, Permutation right) {


71  double similarity = 0.0;


72  for (int i = 0; i < left.Length; i++)


73  if (left[i] == right[i]) similarity++;


74 


75  return similarity / left.Length;


76  }


77 


78  private static double CalculateRelativeDirected(Permutation left, Permutation right) {


79  int[] edgesR = CalculateEdgesVector(right);


80  int[] edgesL = CalculateEdgesVector(left);


81 


82  double similarity = 0.0;


83  for (int i = 0; i < left.Length; i++) {


84  if (edgesL[i] == edgesR[i]) similarity++;


85  }


86 


87  return similarity / left.Length;


88  }


89 


90  private static double CalculateRelativeUndirected(Permutation left, Permutation right) {


91  int[] edgesR = CalculateEdgesVector(right);


92  int[] edgesL = CalculateEdgesVector(left);


93 


94  double similarity = 0.0;


95  for (int i = 0; i < left.Length; i++) {


96  if ((edgesL[i] == edgesR[i])  (edgesL[edgesR[i]] == i))


97  similarity++;


98  }


99 


100  return similarity / left.Length;


101  }


102 


103  private static int[] CalculateEdgesVector(Permutation permutation) {


104  // transform path representation into adjacency representation


105  int[] edgesVector = new int[permutation.Length];


106  for (int i = 0; i < permutation.Length  1; i++)


107  edgesVector[permutation[i]] = permutation[i + 1];


108  edgesVector[permutation[permutation.Length  1]] = permutation[0];


109  return edgesVector;


110  }


111 


112  public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) {


113  var sol1 = leftSolution.Variables[SolutionVariableName].Value as Permutation;


114  var sol2 = rightSolution.Variables[SolutionVariableName].Value as Permutation;


115 


116  return CalculateSimilarity(sol1, sol2);


117  }


118  }


119  }

