Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QAPPermutationProximityCalculator.cs @ 15069

Last change on this file since 15069 was 15069, checked in by abeham, 7 years ago

#2706:

  • Added or updated similarity calculators and population similarity analysis for several problems (BinPacking, LAP, Orienteering, Parameter optimization, PTSP, QAP, TF, TSP, VRP)
  • Made TSPSimilarityCalculator obsolete since it's essentially the same as the one in the permutation plugin
  • Made QAPPopulationDiversityAnalyzer obsolete as it is replaced by the newer PopulationSimilarityAnalyzer
  • Removed genotype specific similarity code in QAPPermutationProximityCalculator (again identical to the permutation plugin)
  • Changed QAPSimilarityCalculator to perform phenotype similarity instead of genotype similarity (has not been previously used)
File size: 2.7 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.Collections.Generic;
23using HeuristicLab.Data;
24using HeuristicLab.Encodings.PermutationEncoding;
25
26namespace HeuristicLab.Problems.QuadraticAssignment {
27  public static class QAPPermutationProximityCalculator {
28
29    public static double CalculatePhenotypeSimilarity(Permutation a, Permutation b, DoubleMatrix weights, DoubleMatrix distances) {
30      return 1.0 - CalculatePhenotypeDistance(a, b, weights, distances);
31    }
32
33    public static double CalculatePhenotypeDistance(Permutation a, Permutation b, DoubleMatrix weights, DoubleMatrix distances) {
34      Dictionary<double, Dictionary<double, int>> alleles = new Dictionary<double, Dictionary<double, int>>();
35      int distance = 0, len = a.Length;
36      for (int x = 0; x < len; x++) {
37        for (int y = 0; y < len; y++) {
38          // there's a limited universe of double values as they're all drawn from the same matrix
39          double dA = distances[a[x], a[y]], dB = distances[b[x], b[y]];
40          if (dA == dB) continue;
41
42          Dictionary<double, int> dAlleles;
43          if (!alleles.ContainsKey(weights[x, y])) {
44            dAlleles = new Dictionary<double, int>();
45            alleles.Add(weights[x, y], dAlleles);
46          } else dAlleles = alleles[weights[x, y]];
47
48          int countA = 1, countB = -1;
49
50          if (dAlleles.ContainsKey(dA)) countA += dAlleles[dA];
51          if (dAlleles.ContainsKey(dB)) countB += dAlleles[dB];
52
53          if (countA <= 0) distance--; // we've found in A an allele that was present in B
54          else distance++; // we've found in A a new allele
55          dAlleles[dA] = countA;
56
57          if (countB >= 0) distance--; // we've found in B an allele that was present in A
58          else distance++; // we've found in B a new allele
59          dAlleles[dB] = countB;
60        }
61      }
62      return distance / (double)(2 * len * len);
63    }
64  }
65}
Note: See TracBrowser for help on using the repository browser.