1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022019 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.Optimization.Operators;


26  using HEAL.Attic;


27 


28  namespace HeuristicLab.Encodings.PermutationEncoding {


29  [Item("Hamming Similarity Calculator for Permutation", "An operator that performs similarity calculation between two permutationencoded solutions.")]


30  [StorableType("CD7CC097C46E42A582BFE47CEB945B9B")]


31  public sealed class HammingSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {


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


33 


34  [StorableConstructor]


35  private HammingSimilarityCalculator(StorableConstructorFlag _) : base(_) { }


36  private HammingSimilarityCalculator(HammingSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }


37  public HammingSimilarityCalculator() : base() { }


38 


39  public override IDeepCloneable Clone(Cloner cloner) {


40  return new HammingSimilarityCalculator(this, cloner);


41  }


42 


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


44  if (left == null  right == null)


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


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


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


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


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


50  if (left.Length == 0)


51  throw new ArgumentException("Cannot calculate similarity because solutions are of length 0.");


52  if (ReferenceEquals(left, right)) return 1.0;


53 


54  switch (left.PermutationType) {


55  case PermutationTypes.Absolute:


56  return CalculateAbsolute(left, right);


57  case PermutationTypes.RelativeDirected:


58  return CalculateRelativeDirected(left, right);


59  case PermutationTypes.RelativeUndirected:


60  return CalculateRelativeUndirected(left, right);


61  default:


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


63  }


64  }


65 


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


67  double similarity = 0.0;


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


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


70 


71  return similarity / left.Length;


72  }


73 


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


75  int[] edgesR = CalculateEdgesVector(right);


76  int[] edgesL = CalculateEdgesVector(left);


77 


78  double similarity = 0.0;


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


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


81  }


82 


83  return similarity / left.Length;


84  }


85 


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


87  int[] edgesR = CalculateEdgesVector(right);


88  int[] edgesL = CalculateEdgesVector(left);


89 


90  double similarity = 0.0;


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


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


93  similarity++;


94  }


95 


96  return similarity / left.Length;


97  }


98 


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


100  // transform path representation into adjacency representation


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


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


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


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


105  return edgesVector;


106  }


107 


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


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


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


111 


112  return CalculateSimilarity(sol1, sol2);


113  }


114  }


115  }

