Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis.PopulationDiversityAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/Analyzers/FineGrainedStructuralPopulationDiversityAnalyzer.cs @ 4886

Last change on this file since 4886 was 4886, checked in by swinkler, 12 years ago

Started working on fine grained structural similarity estimation for structural population diversity in GP. (#1278)

File size: 20.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Analysis;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Problems.DataAnalysis.Symbolic;
34using System.Collections.Generic;
35using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
36using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
37
38namespace HeuristicLab.Problems.DataAnalysis.Regression.Symbolic.Analyzers {
39  /// <summary>
40  /// An operator that analyzes the population diversity using fine grained structural tree similarity estimation.
41  /// </summary>
42  [Item("FineGrainedStructuralPopulationDiversityAnalyzer", "An operator that analyzes the population diversity using fine grained structural tree similarity estimation.")]
43  [StorableClass]
44  public sealed class FineGrainedStructuralPopulationDiversityAnalyzer : SymbolicRegressionPopulationDiversityAnalyzer {
45
46    [StorableConstructor]
47    private FineGrainedStructuralPopulationDiversityAnalyzer(bool deserializing) : base(deserializing) { }
48    private FineGrainedStructuralPopulationDiversityAnalyzer(FineGrainedStructuralPopulationDiversityAnalyzer original, Cloner cloner) : base(original, cloner) { }
49    public FineGrainedStructuralPopulationDiversityAnalyzer() : base() { }
50
51    public override IDeepCloneable Clone(Cloner cloner) {
52      return new FineGrainedStructuralPopulationDiversityAnalyzer(this, cloner);
53    }
54
55    protected override double[,] CalculateSimilarities(SymbolicExpressionTree[] solutions) {
56      int n = solutions.Length;
57      double[,] result = new double[n, n];
58      for (int i = 0; i < n; i++) {
59        for (int j = 0; j < n; j++) {
60          if (i == j)
61            result[i, j] = 1;
62          else
63            result[i, j] = 0;
64        }
65      }
66      return result;
67    }
68
69    /*
70    #region private class GeneticInformationItem, ported from HL 2
71
72    private class GeneticInformationItem {
73
74      private Type myAncestorDefinition;
75      public Type AncestorDefinition {
76        get { return myAncestorDefinition; }
77      }
78
79      private int myAncestorIndex;
80      public int AncestorIndex {
81        get { return myAncestorIndex; }
82      }
83
84      private Type myDescendantDefinition;
85      public Type DescendantDefinition {
86        get { return myDescendantDefinition; }
87      }
88
89      private int myLevelDelta;
90      public int LevelDelta {
91        get { return myLevelDelta; }
92      }
93
94      private double myAncestorCoefficient;
95      public double AncestorCoefficient {
96        get { return myAncestorCoefficient; }
97      }
98
99      private double myAncestorVariableIndex;
100      public double AncestorVariableIndex {
101        get { return myAncestorVariableIndex; }
102      }
103
104      private int myAncestorTimeOffset;
105      public int AncestorTimeOffset {
106        get { return myAncestorTimeOffset; }
107      }
108
109      // not used in HL 3.3
110      // private int myAncestorVariant;
111      // public int AncestorVariant {
112      //   get { return myAncestorVariant; }
113      // }
114
115      private double myDescendantCoefficient;
116      public double DescendantCoefficient {
117        get { return myDescendantCoefficient; }
118      }
119
120      private double myDescendantVariableIndex;
121      public double DescendantVariableIndex {
122        get { return myDescendantVariableIndex; }
123      }
124
125      private int myDescendantTimeOffset;
126      public int DescendantTimeOffset {
127        get { return myDescendantTimeOffset; }
128      }
129
130      private int myDescendantVariant;
131      public int DescendantVariant {
132        get { return myDescendantVariant; }
133      }
134
135      public GeneticInformationItem(SymbolicExpressionTreeNode Ancestor, SymbolicExpressionTreeNode Descendant) {
136
137        myAncestorDefinition = Ancestor.Symbol.GetType();
138        myAncestorCoefficient = Ancestor.Coefficient;
139        myAncestorTimeOffset = Ancestor.TimeOffset;
140        myAncestorVariableIndex = Ancestor.VariableIndex;
141        //myAncestorVariant = Ancestor.Variant;
142
143        myDescendantDefinition = Descendant.Symbol.GetType();
144        myDescendantCoefficient = Descendant.Coefficient;
145        myDescendantTimeOffset = Descendant.TimeOffset;
146        myDescendantVariableIndex = Descendant.VariableIndex;
147        //myDescendantVariant = Descendant.Variant;
148
149        myLevelDelta = Descendant.Level - Ancestor.Level;
150        if (myLevelDelta < 0)
151          throw new InvalidOperationException("ERROR in GeneticInformationItem: The Given ancestor is not an ancestor of the given descendant node.");
152        myAncestorIndex = CalculateAncestorIndex(Ancestor, Descendant);
153
154      }
155
156      private GeneticInformationItem(GeneticInformationItem item) {
157        myAncestorDefinition = item.myAncestorDefinition;
158        myAncestorCoefficient = item.myAncestorCoefficient;
159        myAncestorTimeOffset = item.myAncestorTimeOffset;
160        myAncestorVariableIndex = item.myAncestorVariableIndex;
161        // myAncestorVariant = item.myAncestorVariant;
162        myDescendantDefinition = item.myDescendantDefinition;
163        myDescendantCoefficient = item.myDescendantCoefficient;
164        myDescendantTimeOffset = item.myDescendantTimeOffset;
165        myDescendantVariableIndex = item.myDescendantVariableIndex;
166        myDescendantVariant = item.myDescendantVariant;
167        myLevelDelta = item.myLevelDelta;
168        myAncestorIndex = item.myAncestorIndex;
169      }
170
171      public GeneticInformationItem Clone() {
172        return new GeneticInformationItem(this);
173      }
174
175      public static List<GeneticInformationItem> CopyList(List<GeneticInformationItem> list) {
176        List<GeneticInformationItem> result = new List<GeneticInformationItem>();
177        for (int i = 0; i < list.Count; i++)
178          result.Add(list[i]);
179        return result;
180      }
181
182      private static int CalculateAncestorIndex(SymbolicExpressionTreeNode Ancestor, SymbolicExpressionTreeNode Descendant) {
183        if (Ancestor == Descendant)
184          return 0;
185        // Node lastParent = Descendant, parent = Descendant.Parent;
186        // while (parent != Ancestor) {
187        //   lastParent = parent;
188        //   parent = parent.Parent;
189        //   if (parent == null)
190        //     throw new InvalidOperationException("Error in GeneticInformationItem: The given ancestor node does not seem to be an ancestor of the given descendant.");
191        // }
192        // // parent == Ancestor, lastParent is child of Ancestor
193        // int childIndex = 0;
194        // while (Ancestor.GetChild(childIndex) != lastParent)
195        //   childIndex++;
196        // return childIndex;
197        //
198        for (int i = 0; i < Ancestor.SubTrees.Count; i++)
199          if (treeContainsNode(Ancestor.SubTrees[i], Descendant))
200            return i;
201        return -1;
202      }
203
204      private static bool treeContainsNode(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode node) {
205        if (node == root)
206          return true;
207        foreach (SymbolicExpressionTreeNode subTree in root.SubTrees)
208          if(treeContainsNode(subTree, node))
209            return true;
210        return false;
211      }
212
213      public static GeneticInformationItem FindBestPendant(GeneticInformationItem Item, List<GeneticInformationItem> ComparisonItems,
214          StructuralSimilarityAnalysisParameters Parameters,
215          int MaxTreeHeight, int MaxTimeOffset,
216          out double BestPendantSimilarity) {
217        int maxSimilarityIndex = -1;
218        double similarity, maxSimilarity = -double.MaxValue;
219        for (int i = 0; i < ComparisonItems.Count; i++) {
220          similarity = Similarity(Item, ComparisonItems[i], Parameters, MaxTreeHeight, MaxTimeOffset);
221          if (!double.IsNaN(similarity) && similarity > maxSimilarity) {
222            maxSimilarity = similarity;
223            maxSimilarityIndex = i;
224          }
225        }
226        BestPendantSimilarity = maxSimilarity;
227        if (maxSimilarityIndex >= 0)
228          return ComparisonItems[maxSimilarityIndex];
229        else
230          return null;
231      }
232
233      public static double Similarity(GeneticInformationItem Item1, GeneticInformationItem Item2,
234          StructuralSimilarityAnalysisParameters Parameters,
235          int MaxTreeHeight, int MaxTimeOffset) {
236
237        if (Item1.AncestorDefinition != Item2.AncestorDefinition ||
238          Item1.DescendantDefinition != Item2.DescendantDefinition)
239          return double.NaN;
240
241        // the two items for sure have the same behavior definitions
242        #region init
243        double punishmentContributionSum = 0;
244        double punishmentCoefficientsProduct = 1;
245        double ancestorCoefficientDifferencePunishment = 0;
246        double ancestorTimeOffsetDifferencePunishment = 0;
247        double ancestorVariantDifferencePunishment = 0;
248        double ancestorVariableIndexDifferencePunishment = 0;
249        double descendantCoefficientDifferencePunishment = 0;
250        double descendantTimeOffsetDifferencePunishment = 0;
251        double descendantVariantDifferencePunishment = 0;
252        double descendantVariableIndexDifferencePunishment = 0;
253        double ancestorIndexDifferencePunishment = 0;
254        double levelDifferencePunishment = 0;
255        #endregion
256
257        ITerminalDefinition ancestorTerminal = Item1.AncestorDefinition as ITerminalDefinition;
258        ITerminalDefinition descendantTerminal = Item1.DescendantDefinition as ITerminalDefinition;
259        IFunctionDefinition ancestorFunction = Item1.AncestorDefinition as IFunctionDefinition;
260        IFunctionDefinition descendantFunction = Item1.DescendantDefinition as IFunctionDefinition;
261
262        if (Parameters.ConsiderLevelDifference) {
263          levelDifferencePunishment = Item1.LevelDelta - Item2.LevelDelta;
264          if (levelDifferencePunishment < 0)
265            levelDifferencePunishment = -levelDifferencePunishment;
266          levelDifferencePunishment /= MaxTreeHeight;
267          if (levelDifferencePunishment > 1)
268            levelDifferencePunishment = 1;
269          levelDifferencePunishment *= Parameters.LevelDifferenceCoefficient;
270          punishmentContributionSum += Parameters.LevelDifferenceCoefficient;
271          punishmentCoefficientsProduct *= (1 - Parameters.LevelDifferenceCoefficient);
272        }
273        if (Parameters.ConsiderAncestorIndex) {
274          if (Item1.AncestorIndex != Item2.AncestorIndex)
275            ancestorIndexDifferencePunishment = 1;
276          else
277            ancestorIndexDifferencePunishment = 0;
278          ancestorIndexDifferencePunishment *= Parameters.AncestorIndexCoefficient;
279          punishmentContributionSum += Parameters.AncestorIndexCoefficient;
280          punishmentCoefficientsProduct *= (1 - Parameters.AncestorIndexCoefficient);
281        }
282
283        if (Item1.AncestorDefinition is ITerminalDefinition) {
284          if (Parameters.ConsiderCoefficient) {
285            double coefficientDifference = Math.Abs(Item1.myAncestorCoefficient - Item2.myAncestorCoefficient);
286            if (ancestorTerminal.Parametrization.CoefficientIsGaussian)
287              ancestorCoefficientDifferencePunishment = (coefficientDifference / (ancestorTerminal.Parametrization.CoefficientSigma * 4));
288            else
289              ancestorCoefficientDifferencePunishment = (coefficientDifference / (ancestorTerminal.Parametrization.CoefficientMaxValue - ancestorTerminal.Parametrization.CoefficientMinValue));
290            if (ancestorCoefficientDifferencePunishment > 1)
291              ancestorCoefficientDifferencePunishment = 1;
292            ancestorCoefficientDifferencePunishment *= Parameters.CoefficientCoefficient;
293            punishmentContributionSum += Parameters.CoefficientCoefficient;
294            punishmentCoefficientsProduct *= (1 - Parameters.CoefficientCoefficient);
295          }
296          if (Parameters.ConsiderTimeOffset) {
297            double timeOffsetDifference = Math.Abs(Item1.AncestorTimeOffset - Item2.AncestorTimeOffset);
298            if (MaxTimeOffset > 0)
299              ancestorTimeOffsetDifferencePunishment = timeOffsetDifference / MaxTimeOffset;
300            ancestorTimeOffsetDifferencePunishment *= Parameters.TimeOffsetCoefficient;
301            punishmentContributionSum += Parameters.TimeOffsetCoefficient;
302            punishmentCoefficientsProduct *= (1 - Parameters.TimeOffsetCoefficient);
303          }
304          if (Parameters.ConsiderVariableIndex) {
305            if (Item1.AncestorVariableIndex != Item2.AncestorVariableIndex)
306              ancestorVariableIndexDifferencePunishment = 1;
307            else
308              ancestorVariableIndexDifferencePunishment = 0;
309            ancestorVariableIndexDifferencePunishment *= Parameters.VariableIndexCoefficient;
310            punishmentContributionSum += Parameters.VariableIndexCoefficient;
311            punishmentCoefficientsProduct *= (1 - Parameters.VariableIndexCoefficient);
312          }
313        } else {
314          if (Parameters.ConsiderVariant) {
315            if (Item1.AncestorVariant != Item2.AncestorVariant)
316              ancestorVariantDifferencePunishment = 1;
317            else
318              ancestorVariantDifferencePunishment = 0;
319            ancestorVariantDifferencePunishment *= Parameters.VariantCoefficient;
320            punishmentContributionSum += Parameters.VariantCoefficient;
321            punishmentCoefficientsProduct *= (1 - Parameters.VariantCoefficient);
322          }
323        }
324
325        if (Item1.DescendantDefinition is ITerminalDefinition) {
326          if (Parameters.ConsiderCoefficient) {
327            double coefficientDifference = Math.Abs(Item1.myDescendantCoefficient - Item2.myDescendantCoefficient);
328            if (descendantTerminal.Parametrization.CoefficientIsGaussian)
329              descendantCoefficientDifferencePunishment = (coefficientDifference / (descendantTerminal.Parametrization.CoefficientSigma * 4));
330            else
331              descendantCoefficientDifferencePunishment = (coefficientDifference / (descendantTerminal.Parametrization.CoefficientMaxValue - descendantTerminal.Parametrization.CoefficientMinValue));
332            if (descendantCoefficientDifferencePunishment > 1)
333              descendantCoefficientDifferencePunishment = 1;
334            descendantCoefficientDifferencePunishment *= Parameters.CoefficientCoefficient;
335            punishmentContributionSum += Parameters.CoefficientCoefficient;
336            punishmentCoefficientsProduct *= (1 - Parameters.CoefficientCoefficient);
337          }
338          if (Parameters.ConsiderTimeOffset) {
339            double timeOffsetDifference = Math.Abs(Item1.DescendantTimeOffset - Item2.DescendantTimeOffset);
340            if (MaxTimeOffset > 0)
341              descendantTimeOffsetDifferencePunishment = timeOffsetDifference / MaxTimeOffset;
342            descendantTimeOffsetDifferencePunishment *= Parameters.TimeOffsetCoefficient;
343            punishmentContributionSum += Parameters.TimeOffsetCoefficient;
344            punishmentCoefficientsProduct *= (1 - Parameters.TimeOffsetCoefficient);
345          }
346          if (Parameters.ConsiderVariableIndex) {
347            if (Item1.DescendantVariableIndex != Item2.DescendantVariableIndex)
348              descendantVariableIndexDifferencePunishment = 1;
349            else
350              descendantVariableIndexDifferencePunishment = 0;
351            descendantVariableIndexDifferencePunishment *= Parameters.VariableIndexCoefficient;
352            punishmentContributionSum += Parameters.VariableIndexCoefficient;
353            punishmentCoefficientsProduct *= (1 - Parameters.VariableIndexCoefficient);
354          }
355        } else {
356          if (Parameters.ConsiderVariant) {
357            if (Item1.DescendantVariant != Item2.DescendantVariant)
358              descendantVariantDifferencePunishment = 1;
359            else
360              descendantVariantDifferencePunishment = 0;
361            descendantVariantDifferencePunishment *= Parameters.VariantCoefficient;
362            punishmentContributionSum += Parameters.VariantCoefficient;
363            punishmentCoefficientsProduct *= (1 - Parameters.VariantCoefficient);
364          }
365        }
366
367        double result;
368
369        if (Parameters.AdditiveSimilarityCalculation) {
370          double punishmentsSum =
371            ancestorCoefficientDifferencePunishment + ancestorTimeOffsetDifferencePunishment +
372            ancestorVariantDifferencePunishment + ancestorVariableIndexDifferencePunishment +
373            descendantCoefficientDifferencePunishment + descendantTimeOffsetDifferencePunishment +
374            descendantVariantDifferencePunishment + descendantVariableIndexDifferencePunishment +
375            ancestorIndexDifferencePunishment + levelDifferencePunishment;
376          result = (1 - punishmentsSum / punishmentContributionSum);
377        } else {
378          result =
379            (1 - ancestorCoefficientDifferencePunishment) *
380            (1 - ancestorTimeOffsetDifferencePunishment) *
381            (1 - ancestorVariantDifferencePunishment) *
382            (1 - ancestorVariableIndexDifferencePunishment) *
383            (1 - descendantCoefficientDifferencePunishment) *
384            (1 - descendantTimeOffsetDifferencePunishment) *
385            (1 - descendantVariantDifferencePunishment) *
386            (1 - descendantVariableIndexDifferencePunishment) *
387            (1 - ancestorIndexDifferencePunishment) *
388            (1 - levelDifferencePunishment);
389          // worst possible result is (1-punishmentCoefficientsProduct), so scale linearly to [0;1]:
390          result = (result - punishmentCoefficientsProduct) / (1 - punishmentCoefficientsProduct);
391        }
392
393        if (result < 0 || result > 1)
394          throw new InvalidOperationException("ERROR in GeneticInformationItem.Similarity: An invalid similarity value (" + result.ToString() + ") has been calculated.");
395
396        return result;
397
398      }
399
400      public static List<GeneticInformationItem> GetGeneticInformationItems(SymbolicExpressionTreeNode Formula, int MinLevelDifference, int MaxLevelDifference) {
401        List<GeneticInformationItem> result = new List<GeneticInformationItem>();
402        List<SymbolicExpressionTreeNode> allNodes = new List<SymbolicExpressionTreeNode>();
403        allNodes.Add(Formula);
404        allNodes.AddRange(getDescendants(Formula));
405        foreach (SymbolicExpressionTreeNode node in allNodes) {
406          List<SymbolicExpressionTreeNode> allDescendants = new List<SymbolicExpressionTreeNode>();
407          allDescendants.Add(node);
408          allDescendants.AddRange(getDescendants(node));
409          foreach (SymbolicExpressionTreeNode descendant in allDescendants) {
410            GeneticInformationItem item = new GeneticInformationItem(node, descendant);
411            if (item.LevelDelta >= MinLevelDifference && item.LevelDelta <= MaxLevelDifference)
412              result.Add(item);
413          }
414        }
415        return result;
416      }
417
418      public static List<SymbolicExpressionTreeNode> getDescendants(SymbolicExpressionTreeNode node) {
419        List<SymbolicExpressionTreeNode> descendants = new List<SymbolicExpressionTreeNode>();
420        foreach (SymbolicExpressionTreeNode subTreeNode in node.SubTrees) {
421          addDescendants(descendants, subTreeNode);
422        }
423        return descendants;
424      }
425      private static void addDescendants(List<SymbolicExpressionTreeNode> list, SymbolicExpressionTreeNode node) {
426        list.Add(node);
427        foreach (SymbolicExpressionTreeNode subTreeNode in node.SubTrees) {
428          addDescendants(list, subTreeNode);
429        }
430      }
431
432    }
433
434    #endregion
435    */
436
437  }
438}
Note: See TracBrowser for help on using the repository browser.