Free cookie consent management tool by TermsFeed Policy Generator

source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/SimilarityCalculator.cs @ 14453

Last change on this file since 14453 was 14450, checked in by abeham, 8 years ago

#2701: working on MemPR implementation

File size: 3.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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
22using System;
23using HeuristicLab.Encodings.PermutationEncoding;
24
25namespace HeuristicLab.Algorithms.MemPR.Permutation {
26  public static class PermutationSimilarityCalculator {
27
28    public static double CalculateSimilarity(Encodings.PermutationEncoding.Permutation left, Encodings.PermutationEncoding.Permutation right) {
29      if (left == null || right == null)
30        throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");
31      if (left.PermutationType != right.PermutationType)
32        throw new ArgumentException("Cannot calculate similarity because the provided solutions have different types.");
33      if (left.Length != right.Length)
34        throw new ArgumentException("Cannot calculate similarity because the provided solutions have different lengths.");
35      if (object.ReferenceEquals(left, right)) return 1.0;
36
37      switch (left.PermutationType) {
38        case PermutationTypes.Absolute:
39          return CalculateAbsolute(left, right);
40        case PermutationTypes.RelativeDirected:
41          return CalculateRelativeDirected(left, right);
42        case PermutationTypes.RelativeUndirected:
43          return CalculateRelativeUndirected(left, right);
44        default:
45          throw new InvalidOperationException("unknown permutation type");
46      }
47    }
48
49    private static double CalculateAbsolute(Encodings.PermutationEncoding.Permutation left, Encodings.PermutationEncoding.Permutation right) {
50      double similarity = 0.0;
51      for (int i = 0; i < left.Length; i++)
52        if (left[i] == right[i]) similarity++;
53
54      return similarity / left.Length;
55    }
56
57    private static double CalculateRelativeDirected(Encodings.PermutationEncoding.Permutation left, Encodings.PermutationEncoding.Permutation right) {
58      int[] edgesR = CalculateEdgesVector(right);
59      int[] edgesL = CalculateEdgesVector(left);
60
61      double similarity = 0.0;
62      for (int i = 0; i < left.Length; i++) {
63        if (edgesL[i] == edgesR[i]) similarity++;
64      }
65
66      return similarity / left.Length;
67    }
68
69    private static double CalculateRelativeUndirected(Encodings.PermutationEncoding.Permutation left, Encodings.PermutationEncoding.Permutation right) {
70      int[] edgesR = CalculateEdgesVector(right);
71      int[] edgesL = CalculateEdgesVector(left);
72
73      double similarity = 0.0;
74      for (int i = 0; i < left.Length; i++) {
75        if ((edgesL[i] == edgesR[i]) || (edgesL[edgesR[i]] == i))
76          similarity++;
77      }
78
79      return similarity / left.Length;
80    }
81
82    private static int[] CalculateEdgesVector(Encodings.PermutationEncoding.Permutation permutation) {
83      // transform path representation into adjacency representation
84      int[] edgesVector = new int[permutation.Length];
85      for (int i = 0; i < permutation.Length - 1; i++)
86        edgesVector[permutation[i]] = permutation[i + 1];
87      edgesVector[permutation[permutation.Length - 1]] = permutation[0];
88      return edgesVector;
89    }
90  }
91}
Note: See TracBrowser for help on using the repository browser.