Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs @ 16270

Last change on this file since 16270 was 16270, checked in by bburlacu, 5 years ago

#2950: Fix compilation error in SymbolicDataAnalysisExpressionDiversityPreservingCrossover

File size: 6.8 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5using HeuristicLab.Common;
6using HeuristicLab.Core;
7using HeuristicLab.Data;
8using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
9using HeuristicLab.Parameters;
10using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
11using HeuristicLab.Random;
12using static HeuristicLab.Problems.DataAnalysis.Symbolic.SymbolicExpressionHashExtensions;
13
14namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
15  [Item("DiversityCrossover", "Simple crossover operator prioritizing internal nodes according to the given probability.")]
16  [StorableClass]
17  public sealed class SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
18
19    private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";
20    private const string WindowingParameterName = "Windowing";
21    private const string ProportionalSamplingParameterName = "ProportionalSampling";
22
23    #region Parameter Properties
24    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
25      get { return (IValueLookupParameter<PercentValue>)Parameters[InternalCrossoverPointProbabilityParameterName]; }
26    }
27
28    public IValueLookupParameter<BoolValue> WindowingParameter {
29      get { return (IValueLookupParameter<BoolValue>)Parameters[WindowingParameterName]; }
30    }
31
32    public IValueLookupParameter<BoolValue> ProportionalSamplingParameter {
33      get { return (IValueLookupParameter<BoolValue>)Parameters[ProportionalSamplingParameterName]; }
34    }
35    #endregion
36
37    #region Properties
38    public PercentValue InternalCrossoverPointProbability {
39      get { return InternalCrossoverPointProbabilityParameter.ActualValue; }
40    }
41
42    public BoolValue Windowing {
43      get { return WindowingParameter.ActualValue; }
44    }
45
46    public BoolValue ProportionalSampling {
47      get { return ProportionalSamplingParameter.ActualValue; }
48    }
49    #endregion
50
51    public SymbolicDataAnalysisExpressionDiversityPreservingCrossover() {
52      name = "DiversityCrossover";
53      Parameters.Add(new ValueLookupParameter<PercentValue>(InternalCrossoverPointProbabilityParameterName, "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
54      Parameters.Add(new ValueLookupParameter<BoolValue>(WindowingParameterName, "Use proportional sampling with windowing for cutpoint selection.", new BoolValue(false)));
55      Parameters.Add(new ValueLookupParameter<BoolValue>(ProportionalSamplingParameterName, "Select cutpoints proportionally using probabilities as weights instead of randomly.", new BoolValue(true)));
56    }
57
58    private SymbolicDataAnalysisExpressionDiversityPreservingCrossover(SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> original, Cloner cloner) : base(original, cloner) {
59    }
60
61    public override IDeepCloneable Clone(Cloner cloner) {
62      return new SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T>(this, cloner);
63    }
64
65    [StorableConstructor]
66    private SymbolicDataAnalysisExpressionDiversityPreservingCrossover(bool deserializing) : base(deserializing) { }
67
68    private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {
69      return tree.Root.GetSubtree(0).GetSubtree(0);
70    }
71
72    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, double internalCrossoverPointProbability, int maxLength, int maxDepth, bool windowing, bool proportionalSampling = false) {
73      var leafCrossoverPointProbability = 1 - internalCrossoverPointProbability;
74
75      var nodes0 = ActualRoot(parent0).MakeNodes().Sort();
76      var nodes1 = ActualRoot(parent1).MakeNodes().Sort();
77
78      IList<HashNode<ISymbolicExpressionTreeNode>> sampled0;
79      IList<HashNode<ISymbolicExpressionTreeNode>> sampled1;
80
81      if (proportionalSampling) {
82        var p = internalCrossoverPointProbability;
83        var weights0 = nodes0.Select(x => x.IsLeaf ? 1 - p : p);
84        sampled0 = nodes0.SampleProportionalWithoutRepetition(random, nodes0.Length, weights0, windowing: windowing).ToArray();
85
86        var weights1 = nodes1.Select(x => x.IsLeaf ? 1 - p : p);
87        sampled1 = nodes1.SampleProportionalWithoutRepetition(random, nodes1.Length, weights1, windowing: windowing).ToArray();
88      } else {
89        sampled0 = ChooseNodes(random, nodes0, internalCrossoverPointProbability).ShuffleInPlace(random);
90        sampled1 = ChooseNodes(random, nodes1, internalCrossoverPointProbability).ShuffleInPlace(random);
91      }
92
93      foreach (var selected in sampled0) {
94        var cutpoint = new CutPoint(selected.Data.Parent, selected.Data);
95
96        var maxAllowedDepth = maxDepth - parent0.Root.GetBranchLevel(selected.Data);
97        var maxAllowedLength = maxLength - (parent0.Length - selected.Data.GetLength());
98
99        foreach (var candidate in sampled1) {
100          if (candidate.CalculatedHashValue == selected.CalculatedHashValue
101            || candidate.Data.GetDepth() > maxAllowedDepth
102            || candidate.Data.GetLength() > maxAllowedLength
103            || !cutpoint.IsMatchingPointType(candidate.Data)) {
104            continue;
105          }
106
107          Swap(cutpoint, candidate.Data);
108          return parent0;
109        }
110      }
111      return parent0;
112    }
113
114    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
115      if (this.ExecutionContext == null) {
116        throw new InvalidOperationException("ExecutionContext not set.");
117      }
118
119      var maxDepth = MaximumSymbolicExpressionTreeDepth.Value;
120      var maxLength = MaximumSymbolicExpressionTreeLength.Value;
121
122      var internalCrossoverPointProbability = InternalCrossoverPointProbability.Value;
123      var windowing = Windowing.Value;
124      var proportionalSampling = ProportionalSampling.Value;
125
126      return Cross(random, parent0, parent1, internalCrossoverPointProbability, maxLength, maxDepth, windowing, proportionalSampling);
127    }
128
129    private static List<HashNode<ISymbolicExpressionTreeNode>> ChooseNodes(IRandom random, IEnumerable<HashNode<ISymbolicExpressionTreeNode>> nodes, double internalCrossoverPointProbability) {
130      var list = new List<HashNode<ISymbolicExpressionTreeNode>>();
131
132      var chooseInternal = random.NextDouble() < internalCrossoverPointProbability;
133
134      if (chooseInternal) {
135        list.AddRange(nodes.Where(x => !x.IsLeaf && x.Data.Parent != null));
136      }
137      if (!chooseInternal || list.Count == 0) {
138        list.AddRange(nodes.Where(x => x.IsLeaf && x.Data.Parent != null));
139      }
140
141      return list;
142    }
143  }
144}
Note: See TracBrowser for help on using the repository browser.