Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Analysis/3.3/PopulationDiversityAnalysis/SingleObjectivePopulationDiversityAnalyzer.cs @ 8478

Last change on this file since 8478 was 8478, checked in by jkarder, 10 years ago

#1899: added population diversity analyzer which uses problem specific similarity calculators

File size: 14.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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 HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Analysis {
33  /// <summary>
34  /// An operator for analyzing the solution diversity in a population.
35  /// </summary>
36  [Item("SingleObjectivePopulationDiversityAnalyzer", "An operator for analyzing the solution diversity in a population.")]
37  [StorableClass]
38  public class SingleObjectivePopulationDiversityAnalyzer : SingleSuccessorOperator, IAnalyzer, ISimilarityBasedOperator {
39    #region ISimilarityBasedOperator Members
40    public ISolutionSimilarityCalculator SimilarityCalculator { get; set; }
41    #endregion
42
43    public virtual bool EnabledByDefault {
44      get { return false; }
45    }
46
47    public ScopeParameter CurrentScopeParameter {
48      get { return (ScopeParameter)Parameters["CurrentScope"]; }
49    }
50    public LookupParameter<BoolValue> MaximizationParameter {
51      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
52    }
53    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
54      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
55    }
56    public ValueLookupParameter<ResultCollection> ResultsParameter {
57      get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
58    }
59    public ValueParameter<BoolValue> StoreHistoryParameter {
60      get { return (ValueParameter<BoolValue>)Parameters["StoreHistory"]; }
61    }
62    public ValueParameter<IntValue> UpdateIntervalParameter {
63      get { return (ValueParameter<IntValue>)Parameters["UpdateInterval"]; }
64    }
65    public LookupParameter<IntValue> UpdateCounterParameter {
66      get { return (LookupParameter<IntValue>)Parameters["UpdateCounter"]; }
67    }
68
69    [StorableConstructor]
70    protected SingleObjectivePopulationDiversityAnalyzer(bool deserializing) : base(deserializing) { }
71    protected SingleObjectivePopulationDiversityAnalyzer(SingleObjectivePopulationDiversityAnalyzer original, Cloner cloner) : base(original, cloner) { }
72    public SingleObjectivePopulationDiversityAnalyzer()
73      : base() {
74      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solutions which should be analyzed."));
75      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem."));
76      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the solutions which should be analyzed."));
77      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the population diversity analysis results should be stored."));
78      Parameters.Add(new ValueParameter<BoolValue>("StoreHistory", "True if the history of the population diversity analysis should be stored.", new BoolValue(false)));
79      Parameters.Add(new ValueParameter<IntValue>("UpdateInterval", "The interval in which the population diversity analysis should be applied.", new IntValue(1)));
80      Parameters.Add(new LookupParameter<IntValue>("UpdateCounter", "The value which counts how many times the operator was called since the last update.", "PopulationDiversityAnalyzerUpdateCounter"));
81
82      MaximizationParameter.Hidden = true;
83      QualityParameter.Hidden = true;
84      ResultsParameter.Hidden = true;
85      UpdateCounterParameter.Hidden = true;
86    }
87
88    public override IDeepCloneable Clone(Cloner cloner) {
89      return new SingleObjectivePopulationDiversityAnalyzer(this, cloner);
90    }
91
92    public override IOperation Apply() {
93      int updateInterval = UpdateIntervalParameter.Value.Value;
94      IntValue updateCounter = UpdateCounterParameter.ActualValue;
95      // if counter does not yet exist then initialize it with update interval
96      // to make sure the solutions are analyzed on the first application of this operator
97      if (updateCounter == null) {
98        updateCounter = new IntValue(updateInterval);
99        UpdateCounterParameter.ActualValue = updateCounter;
100      } else updateCounter.Value++;
101
102      //analyze solutions only every 'updateInterval' times
103      if (updateCounter.Value == updateInterval) {
104        updateCounter.Value = 0;
105
106        bool max = MaximizationParameter.ActualValue.Value;
107        ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
108        bool storeHistory = StoreHistoryParameter.Value.Value;
109        int count = CurrentScopeParameter.ActualValue.SubScopes.Count;
110
111        if (count > 1) {
112          // calculate solution similarities
113          var similarityMatrix = SimilarityCalculator.CalculateSolutionCrowdSimilarity(CurrentScopeParameter.ActualValue);
114
115          // sort similarities by quality
116          double[][] sortedSimilarityMatrix = null;
117          if (max)
118            sortedSimilarityMatrix = similarityMatrix
119              .Select((x, index) => new { Solutions = x, Quality = qualities[index] })
120              .OrderByDescending(x => x.Quality)
121              .Select(x => x.Solutions)
122              .ToArray();
123          else
124            sortedSimilarityMatrix = similarityMatrix
125              .Select((x, index) => new { Solutions = x, Quality = qualities[index] })
126              .OrderBy(x => x.Quality)
127              .Select(x => x.Solutions)
128              .ToArray();
129
130          double[,] similarities = new double[similarityMatrix.Length, similarityMatrix[0].Length];
131          for (int i = 0; i < similarityMatrix.Length; i++)
132            for (int j = 0; j < similarityMatrix[0].Length; j++)
133              similarities[i, j] = similarityMatrix[i][j];
134
135          // calculate minimum, average and maximum similarities
136          double similarity;
137          double[] minSimilarities = new double[count];
138          double[] avgSimilarities = new double[count];
139          double[] maxSimilarities = new double[count];
140          for (int i = 0; i < count; i++) {
141            minSimilarities[i] = 1;
142            avgSimilarities[i] = 0;
143            maxSimilarities[i] = 0;
144            for (int j = 0; j < count; j++) {
145              if (i != j) {
146                similarity = similarities[i, j];
147
148                if ((similarity < 0) || (similarity > 1))
149                  throw new InvalidOperationException("Solution similarities have to be in the interval [0;1].");
150
151                if (minSimilarities[i] > similarity) minSimilarities[i] = similarity;
152                avgSimilarities[i] += similarity;
153                if (maxSimilarities[i] < similarity) maxSimilarities[i] = similarity;
154              }
155            }
156            avgSimilarities[i] = avgSimilarities[i] / (count - 1);
157          }
158          double avgMinSimilarity = minSimilarities.Average();
159          double avgAvgSimilarity = avgSimilarities.Average();
160          double avgMaxSimilarity = maxSimilarities.Average();
161
162          // fetch results collection
163          ResultCollection results;
164          if (!ResultsParameter.ActualValue.ContainsKey(Name + " Results")) {
165            results = new ResultCollection();
166            ResultsParameter.ActualValue.Add(new Result(Name + " Results", results));
167          } else {
168            results = (ResultCollection)ResultsParameter.ActualValue[Name + " Results"].Value;
169          }
170
171          // store similarities
172          HeatMap similaritiesHeatMap = new HeatMap(similarities, "Solution Similarities", 0.0, 1.0);
173          if (!results.ContainsKey("Solution Similarities"))
174            results.Add(new Result("Solution Similarities", similaritiesHeatMap));
175          else
176            results["Solution Similarities"].Value = similaritiesHeatMap;
177
178          // store similarities history
179          if (storeHistory) {
180            if (!results.ContainsKey("Solution Similarities History")) {
181              HeatMapHistory history = new HeatMapHistory();
182              history.Add(similaritiesHeatMap);
183              results.Add(new Result("Solution Similarities History", history));
184            } else {
185              ((HeatMapHistory)results["Solution Similarities History"].Value).Add(similaritiesHeatMap);
186            }
187          }
188
189          // store average minimum, average and maximum similarity
190          if (!results.ContainsKey("Average Minimum Solution Similarity"))
191            results.Add(new Result("Average Minimum Solution Similarity", new DoubleValue(avgMinSimilarity)));
192          else
193            ((DoubleValue)results["Average Minimum Solution Similarity"].Value).Value = avgMinSimilarity;
194
195          if (!results.ContainsKey("Average Average Solution Similarity"))
196            results.Add(new Result("Average Average Solution Similarity", new DoubleValue(avgAvgSimilarity)));
197          else
198            ((DoubleValue)results["Average Average Solution Similarity"].Value).Value = avgAvgSimilarity;
199
200          if (!results.ContainsKey("Average Maximum Solution Similarity"))
201            results.Add(new Result("Average Maximum Solution Similarity", new DoubleValue(avgMaxSimilarity)));
202          else
203            ((DoubleValue)results["Average Maximum Solution Similarity"].Value).Value = avgMaxSimilarity;
204
205          // store average minimum, average and maximum solution similarity data table
206          DataTable minAvgMaxSimilarityDataTable;
207          if (!results.ContainsKey("Average Minimum/Average/Maximum Solution Similarity")) {
208            minAvgMaxSimilarityDataTable = new DataTable("Average Minimum/Average/Maximum Solution Similarity");
209            minAvgMaxSimilarityDataTable.VisualProperties.XAxisTitle = "Iteration";
210            minAvgMaxSimilarityDataTable.VisualProperties.YAxisTitle = "Solution Similarity";
211            minAvgMaxSimilarityDataTable.Rows.Add(new DataRow("Average Minimum Solution Similarity", null));
212            minAvgMaxSimilarityDataTable.Rows["Average Minimum Solution Similarity"].VisualProperties.StartIndexZero = true;
213            minAvgMaxSimilarityDataTable.Rows.Add(new DataRow("Average Average Solution Similarity", null));
214            minAvgMaxSimilarityDataTable.Rows["Average Average Solution Similarity"].VisualProperties.StartIndexZero = true;
215            minAvgMaxSimilarityDataTable.Rows.Add(new DataRow("Average Maximum Solution Similarity", null));
216            minAvgMaxSimilarityDataTable.Rows["Average Maximum Solution Similarity"].VisualProperties.StartIndexZero = true;
217            results.Add(new Result("Average Minimum/Average/Maximum Solution Similarity", minAvgMaxSimilarityDataTable));
218          } else {
219            minAvgMaxSimilarityDataTable = (DataTable)results["Average Minimum/Average/Maximum Solution Similarity"].Value;
220          }
221          minAvgMaxSimilarityDataTable.Rows["Average Minimum Solution Similarity"].Values.Add(avgMinSimilarity);
222          minAvgMaxSimilarityDataTable.Rows["Average Average Solution Similarity"].Values.Add(avgAvgSimilarity);
223          minAvgMaxSimilarityDataTable.Rows["Average Maximum Solution Similarity"].Values.Add(avgMaxSimilarity);
224
225          // store minimum, average, maximum similarities data table
226          DataTable minAvgMaxSimilaritiesDataTable = new DataTable("Minimum/Average/Maximum Solution Similarities");
227          minAvgMaxSimilaritiesDataTable.VisualProperties.XAxisTitle = "Solution Index";
228          minAvgMaxSimilaritiesDataTable.VisualProperties.YAxisTitle = "Solution Similarity";
229          minAvgMaxSimilaritiesDataTable.Rows.Add(new DataRow("Minimum Solution Similarity", null, minSimilarities));
230          minAvgMaxSimilaritiesDataTable.Rows["Minimum Solution Similarity"].VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Points;
231          minAvgMaxSimilaritiesDataTable.Rows.Add(new DataRow("Average Solution Similarity", null, avgSimilarities));
232          minAvgMaxSimilaritiesDataTable.Rows["Average Solution Similarity"].VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Points;
233          minAvgMaxSimilaritiesDataTable.Rows.Add(new DataRow("Maximum Solution Similarity", null, maxSimilarities));
234          minAvgMaxSimilaritiesDataTable.Rows["Maximum Solution Similarity"].VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Points;
235          if (!results.ContainsKey("Minimum/Average/Maximum Solution Similarities")) {
236            results.Add(new Result("Minimum/Average/Maximum Solution Similarities", minAvgMaxSimilaritiesDataTable));
237          } else {
238            results["Minimum/Average/Maximum Solution Similarities"].Value = minAvgMaxSimilaritiesDataTable;
239          }
240
241          // store minimum, average, maximum similarities history
242          if (storeHistory) {
243            if (!results.ContainsKey("Minimum/Average/Maximum Solution Similarities History")) {
244              DataTableHistory history = new DataTableHistory();
245              history.Add(minAvgMaxSimilaritiesDataTable);
246              results.Add(new Result("Minimum/Average/Maximum Solution Similarities History", history));
247            } else {
248              ((DataTableHistory)results["Minimum/Average/Maximum Solution Similarities History"].Value).Add(minAvgMaxSimilaritiesDataTable);
249            }
250          }
251        }
252      }
253      return base.Apply();
254    }
255  }
256}
Note: See TracBrowser for help on using the repository browser.