source: trunk/sources/HeuristicLab.Optimization.Operators/3.3/SolutionSimilarityCalculator.cs @ 13005

Last change on this file since 13005 was 13005, checked in by ascheibe, 7 years ago

#2377 applied and improved bburlacus patch

File size: 7.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 System.Linq;
24using System.Threading.Tasks;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Optimization.Operators {
31  /// <summary>
32  /// A base class for items that perform similarity calculation between two solutions.
33  /// </summary>
34  [Item("SimilarityCalculator", "A base class for items that perform similarity calculation between two solutions.")]
35  [StorableClass]
36  public abstract class SolutionSimilarityCalculator : Item, ISolutionSimilarityCalculator {
37    protected abstract bool IsCommutative { get; }
38
39    #region Properties
40    [Storable]
41    public string SolutionVariableName { get; set; }
42    [Storable]
43    public string QualityVariableName { get; set; }
44    [Storable]
45    public bool ExecuteInParallel { get; set; }
46    [Storable]
47    public int MaxDegreeOfParallelism { get; set; }
48    #endregion
49
50    [StorableConstructor]
51    protected SolutionSimilarityCalculator(bool deserializing) : base(deserializing) { }
52
53    protected SolutionSimilarityCalculator(SolutionSimilarityCalculator original, Cloner cloner)
54      : base(original, cloner) {
55      SolutionVariableName = original.SolutionVariableName;
56      QualityVariableName = original.QualityVariableName;
57      ExecuteInParallel = original.ExecuteInParallel;
58      MaxDegreeOfParallelism = original.MaxDegreeOfParallelism;
59    }
60
61    protected SolutionSimilarityCalculator() : base() {
62      ExecuteInParallel = false;
63      MaxDegreeOfParallelism = -1;
64    }
65
66    [StorableHook(HookType.AfterDeserialization)]
67    private void AfterDeserialization() {
68      if (MaxDegreeOfParallelism == 0) {
69        ExecuteInParallel = false;
70        MaxDegreeOfParallelism = -1;
71      }
72    }
73
74    public double[][] CalculateSolutionCrowdSimilarity(IScope leftSolutionCrowd, IScope rightSolutionCrowd) {
75      if (leftSolutionCrowd == null || rightSolutionCrowd == null)
76        throw new ArgumentException("Cannot calculate similarity because one of the provided crowds or both are null.");
77
78      var leftIndividuals = leftSolutionCrowd.SubScopes;
79      var rightIndividuals = rightSolutionCrowd.SubScopes;
80
81      if (!leftIndividuals.Any() || !rightIndividuals.Any())
82        throw new ArgumentException("Cannot calculate similarity because one of the provided crowds or both are empty.");
83
84      var similarityMatrix = new double[leftIndividuals.Count][];
85      for (int i = 0; i < leftIndividuals.Count; i++) {
86        similarityMatrix[i] = new double[rightIndividuals.Count];
87        for (int j = 0; j < rightIndividuals.Count; j++) {
88          similarityMatrix[i][j] = CalculateSolutionSimilarity(leftIndividuals[i], rightIndividuals[j]);
89        }
90      }
91
92      return similarityMatrix;
93    }
94
95    public double[][] CalculateSolutionCrowdSimilarity(IScope solutionCrowd) {
96      if (solutionCrowd == null) {
97        throw new ArgumentException("Cannot calculate similarity because the provided crowd is null.");
98      }
99      var individuals = solutionCrowd.SubScopes;
100
101      if (!individuals.Any()) {
102        throw new ArgumentException("Cannot calculate similarity because the provided crowd is empty.");
103      }
104
105      var similarityMatrix = new double[individuals.Count][];
106      for (int i = 0; i < individuals.Count; i++) {
107        similarityMatrix[i] = new double[individuals.Count];
108      }
109
110      if (ExecuteInParallel) {
111        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = MaxDegreeOfParallelism };
112        if (IsCommutative) {
113          Parallel.For(0, individuals.Count, parallelOptions, i => {
114            for (int j = i; j < individuals.Count; j++) {
115              similarityMatrix[i][j] =
116                similarityMatrix[j][i] = CalculateSolutionSimilarity(individuals[i], individuals[j]);
117            }
118          });
119        } else {
120          Parallel.For(0, individuals.Count, parallelOptions, i => {
121            for (int j = i; j < individuals.Count; j++) {
122              similarityMatrix[i][j] = CalculateSolutionSimilarity(individuals[i], individuals[j]);
123              if (i == j) continue;
124              similarityMatrix[j][i] = CalculateSolutionSimilarity(individuals[j], individuals[i]);
125            }
126          });
127        }
128      } else {
129        if (IsCommutative) {
130          for (int i = 0; i < individuals.Count; i++) {
131            for (int j = i; j < individuals.Count; j++) {
132              similarityMatrix[i][j] =
133                similarityMatrix[j][i] = CalculateSolutionSimilarity(individuals[i], individuals[j]);
134            }
135          }
136        } else {
137          for (int i = 0; i < individuals.Count; i++) {
138            for (int j = i; j < individuals.Count; j++) {
139              similarityMatrix[i][j] = CalculateSolutionSimilarity(individuals[i], individuals[j]);
140              if (i == j) continue;
141              similarityMatrix[j][i] = CalculateSolutionSimilarity(individuals[j], individuals[i]);
142            }
143          }
144        }
145      }
146
147      return similarityMatrix;
148    }
149
150    public abstract double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution);
151
152    public virtual bool Equals(IScope x, IScope y) {
153      if (ReferenceEquals(x, y)) return true;
154      if (x == null || y == null) return false;
155
156      var q1 = x.Variables[QualityVariableName].Value;
157      var q2 = y.Variables[QualityVariableName].Value;
158
159      return CheckQualityEquality(q1, q2) && CalculateSolutionSimilarity(x, y).IsAlmost(1.0);
160    }
161
162    public virtual int GetHashCode(IScope scope) {
163      var quality = scope.Variables[QualityVariableName].Value;
164      var dv = quality as DoubleValue;
165      if (dv != null)
166        return dv.Value.GetHashCode();
167
168      var da = quality as DoubleArray;
169      if (da != null) {
170        int hash = 17;
171        unchecked {
172          for (int i = 0; i < da.Length; ++i) {
173            hash += hash * 23 + da[i].GetHashCode();
174          }
175          return hash;
176        }
177      }
178      return 0;
179    }
180
181    private static bool CheckQualityEquality(IItem q1, IItem q2) {
182      var d1 = q1 as DoubleValue;
183      var d2 = q2 as DoubleValue;
184
185      if (d1 != null && d2 != null)
186        return d1.Value.IsAlmost(d2.Value);
187
188      var da1 = q1 as DoubleArray;
189      var da2 = q2 as DoubleArray;
190
191      if (da1 != null && da2 != null) {
192        if (da1.Length != da2.Length)
193          throw new ArgumentException("The quality arrays must have the same length.");
194
195        for (int i = 0; i < da1.Length; ++i) {
196          if (!da1[i].IsAlmost(da2[i]))
197            return false;
198        }
199
200        return true;
201      }
202
203      throw new ArgumentException("Could not determine quality equality.");
204    }
205  }
206}
Note: See TracBrowser for help on using the repository browser.