Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Analysis/3.3/PopulationSimilarityAnalysis/PopulationSimilarityAnalyzer.cs @ 14353

Last change on this file since 14353 was 14353, checked in by bburlacu, 8 years ago

#2685: Add correction step for values miscalculated due to cyclical symbol dependencies in the grammar. Updated unit test.
File size: 17.5 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 System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Analysis {
34  /// <summary>
35  /// An operator for analyzing the solution similarity in a population.
36  /// </summary>
37  [Item("PopulationSimilarityAnalyzer", "An operator for analyzing the solution similarity in a population.")]
38  [StorableClass]
39  public class PopulationSimilarityAnalyzer : SingleSuccessorOperator, IAnalyzer, ISimilarityBasedOperator {
40    private const string DiversityResultNameParameterName = "DiversityResultsName";
41    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
42    private const string MaxDegreeOfParallelismParameterName = "MaxDegreeOfParallelism";
43
44    #region Backwards compatible code, remove with 3.4
45    private ISolutionSimilarityCalculator oldSimilarityCalculator;
46    [Storable(AllowOneWay = true, Name = "SimilarityCalculator")]
47    [Obsolete]
48    private ISolutionSimilarityCalculator SimilarityCalculator { set { oldSimilarityCalculator = value; } }
49    #endregion
50
51    public virtual bool EnabledByDefault {
52      get { return false; }
53    }
54    public ScopeParameter CurrentScopeParameter {
55      get { return (ScopeParameter)Parameters["CurrentScope"]; }
56    }
57    public IValueLookupParameter<ResultCollection> ResultsParameter {
58      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
59    }
60    public IConstrainedValueParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
61      get { return (IConstrainedValueParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
62    }
63    public IValueParameter<BoolValue> StoreHistoryParameter {
64      get { return (IValueParameter<BoolValue>)Parameters["StoreHistory"]; }
65    }
66    public IValueParameter<IntValue> UpdateIntervalParameter {
67      get { return (IValueParameter<IntValue>)Parameters["UpdateInterval"]; }
68    }
69    public ILookupParameter<IntValue> UpdateCounterParameter {
70      get { return (ILookupParameter<IntValue>)Parameters["UpdateCounter"]; }
71    }
72    public IFixedValueParameter<StringValue> DiversityResultNameParameter {
73      get { return (FixedValueParameter<StringValue>)Parameters[DiversityResultNameParameterName]; }
74    }
75    public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
76      get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
77    }
78    public IFixedValueParameter<IntValue> MaxDegreeOfParallelismParameter {
79      get { return (IFixedValueParameter<IntValue>)Parameters[MaxDegreeOfParallelismParameterName]; }
80    }
81
82    public string DiversityResultName {
83      get { return DiversityResultNameParameter.Value.Value; }
84      set { DiversityResultNameParameter.Value.Value = value; }
85    }
86
87    public bool ExecuteInParallel {
88      get { return ExecuteInParallelParameter.Value.Value; }
89      set { ExecuteInParallelParameter.Value.Value = value; }
90    }
91
92    public int MaxDegreeOfParallelism {
93      get { return MaxDegreeOfParallelismParameter.Value.Value; }
94      set { MaxDegreeOfParallelismParameter.Value.Value = value; }
95    }
96
97    [StorableConstructor]
98    protected PopulationSimilarityAnalyzer(bool deserializing) : base(deserializing) { }
99
100    protected PopulationSimilarityAnalyzer(PopulationSimilarityAnalyzer original, Cloner cloner)
101      : base(original, cloner) {
102      RegisterParametersEventHandlers();
103    }
104
105    public PopulationSimilarityAnalyzer(IEnumerable<ISolutionSimilarityCalculator> validSimilarityCalculators)
106      : base() {
107      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solutions which should be analyzed."));
108      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the population diversity analysis results should be stored."));
109      Parameters.Add(new ConstrainedValueParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The similarity calculator that should be used to calculate population similarity."));
110      Parameters.Add(new ValueParameter<BoolValue>("StoreHistory", "True if the history of the population diversity analysis should be stored.", new BoolValue(false)));
111      Parameters.Add(new ValueParameter<IntValue>("UpdateInterval", "The interval in which the population diversity analysis should be applied.", new IntValue(1)));
112      Parameters.Add(new LookupParameter<IntValue>("UpdateCounter", "The value which counts how many times the operator was called since the last update.", "PopulationDiversityAnalyzerUpdateCounter"));
113      Parameters.Add(new FixedValueParameter<StringValue>(DiversityResultNameParameterName, "Specifies how the diversity results should be named.", new StringValue("PopulationDiversity")));
114      Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, "Specifies whether similarity calculations should be parallelized.", new BoolValue(false)));
115      Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParallelismParameterName, "Specifies the maximum number of threads when calculating similarities in parallel.", new IntValue(-1)));
116
117      var similarityCalculators = SimilarityCalculatorParameter.ValidValues;
118      foreach (var sc in validSimilarityCalculators) {
119        similarityCalculators.Add(sc);
120      }
121
122      ResultsParameter.Hidden = true;
123      UpdateCounterParameter.Hidden = true;
124      ExecuteInParallelParameter.Hidden = true;
125      MaxDegreeOfParallelismParameter.Hidden = true;
126
127      RegisterParametersEventHandlers();
128    }
129
130    private void RegisterParametersEventHandlers() {
131      ExecuteInParallelParameter.Value.ValueChanged += Value_ValueChanged;
132      MaxDegreeOfParallelismParameter.Value.ValueChanged += Value_ValueChanged;
133    }
134
135    private void Value_ValueChanged(object sender, EventArgs e) {
136      var similarityCalculators = SimilarityCalculatorParameter.ValidValues;
137      foreach (var similarityCalculator in similarityCalculators) {
138        if (similarityCalculator == null) continue;
139        similarityCalculator.ExecuteInParallel = ExecuteInParallel;
140        similarityCalculator.MaxDegreeOfParallelism = MaxDegreeOfParallelism;
141      }
142    }
143
144    public override IDeepCloneable Clone(Cloner cloner) {
145      return new PopulationSimilarityAnalyzer(this, cloner);
146    }
147
148    [StorableHook(HookType.AfterDeserialization)]
149    private void AfterDeserialization() {
150      // BackwardsCompatibility3.3
151      #region Backwards compatible code, remove with 3.4
152      if (!Parameters.ContainsKey(DiversityResultNameParameterName))
153        Parameters.Add(new FixedValueParameter<StringValue>(DiversityResultNameParameterName, "Specifies how the diversity results should be named.", new StringValue("PopulationDiversity")));
154
155      if (!Parameters.ContainsKey("SimilarityCalculator"))
156        Parameters.Add(new ConstrainedValueParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The similarity calculator that should be used to calculate solution similarity."));
157
158      if (oldSimilarityCalculator != null)
159        SimilarityCalculatorParameter.ValidValues.Add(oldSimilarityCalculator);
160
161      if (!Parameters.ContainsKey(ExecuteInParallelParameterName)) {
162        Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName,
163          "Specifies whether similarity calculations should be parallelized.", new BoolValue(false)));
164        ExecuteInParallelParameter.Hidden = true;
165      }
166      if (!Parameters.ContainsKey(MaxDegreeOfParallelismParameterName)) {
167        Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParallelismParameterName,
168          "Specifies the maximum number of threads when calculating similarities in parallel.", new IntValue(-1)));
169        MaxDegreeOfParallelismParameter.Hidden = true;
170      }
171
172      RegisterParametersEventHandlers();
173      #endregion
174    }
175
176    public override IOperation Apply() {
177      int updateInterval = UpdateIntervalParameter.Value.Value;
178      IntValue updateCounter = UpdateCounterParameter.ActualValue;
179      // if counter does not yet exist then initialize it with update interval
180      // to make sure the solutions are analyzed on the first application of this operator
181      if (updateCounter == null) {
182        updateCounter = new IntValue(updateInterval);
183        UpdateCounterParameter.ActualValue = updateCounter;
184      }
185      //analyze solutions only every 'updateInterval' times
186      if (updateCounter.Value != updateInterval) {
187        updateCounter.Value++;
188        return base.Apply();
189      }
190      updateCounter.Value = 1;
191
192      bool storeHistory = StoreHistoryParameter.Value.Value;
193      int count = CurrentScopeParameter.ActualValue.SubScopes.Count;
194
195      if (count > 1) {
196        var similarityCalculator = SimilarityCalculatorParameter.Value;
197        // calculate solution similarities
198        var similarityMatrix = similarityCalculator.CalculateSolutionCrowdSimilarity(CurrentScopeParameter.ActualValue);
199        double[,] similarities = new double[similarityMatrix.Length, similarityMatrix[0].Length];
200        for (int i = 0; i < similarityMatrix.Length; i++)
201          for (int j = 0; j < similarityMatrix[0].Length; j++)
202            similarities[i, j] = similarityMatrix[i][j];
203
204        // calculate minimum, average and maximum similarities
205        double similarity;
206        double[] minSimilarities = new double[count];
207        double[] avgSimilarities = new double[count];
208        double[] maxSimilarities = new double[count];
209        for (int i = 0; i < count; i++) {
210          minSimilarities[i] = 1;
211          avgSimilarities[i] = 0;
212          maxSimilarities[i] = 0;
213          for (int j = 0; j < count; j++) {
214            if (i != j) {
215              similarity = similarities[i, j];
216
217              if ((similarity < 0) || (similarity > 1))
218                throw new InvalidOperationException("Solution similarities have to be in the interval [0;1].");
219
220              if (minSimilarities[i] > similarity) minSimilarities[i] = similarity;
221              avgSimilarities[i] += similarity;
222              if (maxSimilarities[i] < similarity) maxSimilarities[i] = similarity;
223            }
224          }
225          avgSimilarities[i] = avgSimilarities[i] / (count - 1);
226        }
227        double avgMinSimilarity = minSimilarities.Average();
228        double avgAvgSimilarity = avgSimilarities.Average();
229        double avgMaxSimilarity = maxSimilarities.Average();
230
231        // fetch results collection
232        ResultCollection results;
233        if (!ResultsParameter.ActualValue.ContainsKey(DiversityResultName)) {
234          results = new ResultCollection();
235          ResultsParameter.ActualValue.Add(new Result(DiversityResultName, results));
236        } else {
237          results = (ResultCollection)ResultsParameter.ActualValue[DiversityResultName].Value;
238        }
239
240        // store similarities
241        HeatMap similaritiesHeatMap = new HeatMap(similarities, "Solution Similarities", 0.0, 1.0);
242        if (!results.ContainsKey("Solution Similarities"))
243          results.Add(new Result("Solution Similarities", similaritiesHeatMap));
244        else
245          results["Solution Similarities"].Value = similaritiesHeatMap;
246
247        // store similarities history
248        if (storeHistory) {
249          if (!results.ContainsKey("Solution Similarities History")) {
250            HeatMapHistory history = new HeatMapHistory();
251            history.Add(similaritiesHeatMap);
252            results.Add(new Result("Solution Similarities History", history));
253          } else {
254            ((HeatMapHistory)results["Solution Similarities History"].Value).Add(similaritiesHeatMap);
255          }
256        }
257
258        // store average minimum, average and maximum similarity
259        if (!results.ContainsKey("Average Minimum Solution Similarity"))
260          results.Add(new Result("Average Minimum Solution Similarity", new DoubleValue(avgMinSimilarity)));
261        else
262          ((DoubleValue)results["Average Minimum Solution Similarity"].Value).Value = avgMinSimilarity;
263
264        if (!results.ContainsKey("Average Average Solution Similarity"))
265          results.Add(new Result("Average Average Solution Similarity", new DoubleValue(avgAvgSimilarity)));
266        else
267          ((DoubleValue)results["Average Average Solution Similarity"].Value).Value = avgAvgSimilarity;
268
269        if (!results.ContainsKey("Average Maximum Solution Similarity"))
270          results.Add(new Result("Average Maximum Solution Similarity", new DoubleValue(avgMaxSimilarity)));
271        else
272          ((DoubleValue)results["Average Maximum Solution Similarity"].Value).Value = avgMaxSimilarity;
273
274        // store average minimum, average and maximum solution similarity data table
275        DataTable minAvgMaxSimilarityDataTable;
276        if (!results.ContainsKey("Average Minimum/Average/Maximum Solution Similarity")) {
277          minAvgMaxSimilarityDataTable = new DataTable("Average Minimum/Average/Maximum Solution Similarity");
278          minAvgMaxSimilarityDataTable.VisualProperties.XAxisTitle = "Iteration";
279          minAvgMaxSimilarityDataTable.VisualProperties.YAxisTitle = "Solution Similarity";
280          minAvgMaxSimilarityDataTable.Rows.Add(new DataRow("Average Minimum Solution Similarity", null));
281          minAvgMaxSimilarityDataTable.Rows["Average Minimum Solution Similarity"].VisualProperties.StartIndexZero = true;
282          minAvgMaxSimilarityDataTable.Rows.Add(new DataRow("Average Average Solution Similarity", null));
283          minAvgMaxSimilarityDataTable.Rows["Average Average Solution Similarity"].VisualProperties.StartIndexZero = true;
284          minAvgMaxSimilarityDataTable.Rows.Add(new DataRow("Average Maximum Solution Similarity", null));
285          minAvgMaxSimilarityDataTable.Rows["Average Maximum Solution Similarity"].VisualProperties.StartIndexZero = true;
286          results.Add(new Result("Average Minimum/Average/Maximum Solution Similarity", minAvgMaxSimilarityDataTable));
287        } else {
288          minAvgMaxSimilarityDataTable = (DataTable)results["Average Minimum/Average/Maximum Solution Similarity"].Value;
289        }
290        minAvgMaxSimilarityDataTable.Rows["Average Minimum Solution Similarity"].Values.Add(avgMinSimilarity);
291        minAvgMaxSimilarityDataTable.Rows["Average Average Solution Similarity"].Values.Add(avgAvgSimilarity);
292        minAvgMaxSimilarityDataTable.Rows["Average Maximum Solution Similarity"].Values.Add(avgMaxSimilarity);
293
294        // store minimum, average, maximum similarities data table
295        DataTable minAvgMaxSimilaritiesDataTable = new DataTable("Minimum/Average/Maximum Solution Similarities");
296        minAvgMaxSimilaritiesDataTable.VisualProperties.XAxisTitle = "Solution Index";
297        minAvgMaxSimilaritiesDataTable.VisualProperties.YAxisTitle = "Solution Similarity";
298        minAvgMaxSimilaritiesDataTable.Rows.Add(new DataRow("Minimum Solution Similarity", null, minSimilarities));
299        minAvgMaxSimilaritiesDataTable.Rows["Minimum Solution Similarity"].VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Points;
300        minAvgMaxSimilaritiesDataTable.Rows.Add(new DataRow("Average Solution Similarity", null, avgSimilarities));
301        minAvgMaxSimilaritiesDataTable.Rows["Average Solution Similarity"].VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Points;
302        minAvgMaxSimilaritiesDataTable.Rows.Add(new DataRow("Maximum Solution Similarity", null, maxSimilarities));
303        minAvgMaxSimilaritiesDataTable.Rows["Maximum Solution Similarity"].VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Points;
304        if (!results.ContainsKey("Minimum/Average/Maximum Solution Similarities")) {
305          results.Add(new Result("Minimum/Average/Maximum Solution Similarities", minAvgMaxSimilaritiesDataTable));
306        } else {
307          results["Minimum/Average/Maximum Solution Similarities"].Value = minAvgMaxSimilaritiesDataTable;
308        }
309
310        // store minimum, average, maximum similarities history
311        if (storeHistory) {
312          if (!results.ContainsKey("Minimum/Average/Maximum Solution Similarities History")) {
313            DataTableHistory history = new DataTableHistory();
314            history.Add(minAvgMaxSimilaritiesDataTable);
315            results.Add(new Result("Minimum/Average/Maximum Solution Similarities History", history));
316          } else {
317            ((DataTableHistory)results["Minimum/Average/Maximum Solution Similarities History"].Value).Add(minAvgMaxSimilaritiesDataTable);
318          }
319        }
320      }
321      return base.Apply();
322    }
323  }
324}
Note: See TracBrowser for help on using the repository browser.