source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs @ 17099

Last change on this file since 17099 was 17099, checked in by mkommend, 2 months ago

#2950: Merged 16979, 16980, 16983 into stable.

File size: 8.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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 HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30using HeuristicLab.Parameters;
31using HeuristicLab.Random;
32using static HeuristicLab.Problems.DataAnalysis.Symbolic.SymbolicExpressionHashExtensions;
33
34namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
35  [Item("DiversityCrossover", "Simple crossover operator preventing swap between subtrees with the same hash value.")]
36  [StorableType("ED35B0D9-9704-4D32-B10B-8F9870E76781")]
37  public sealed class SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
38
39    private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";
40    private const string WindowingParameterName = "Windowing";
41    private const string ProportionalSamplingParameterName = "ProportionalSampling";
42    private const string StrictHashingParameterName = "StrictHashing";
43
44    private static readonly Func<byte[], ulong> hashFunction = HashUtil.JSHash;
45
46    #region Parameter Properties
47    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
48      get { return (IValueLookupParameter<PercentValue>)Parameters[InternalCrossoverPointProbabilityParameterName]; }
49    }
50
51    public IValueLookupParameter<BoolValue> WindowingParameter {
52      get { return (IValueLookupParameter<BoolValue>)Parameters[WindowingParameterName]; }
53    }
54
55    public IValueLookupParameter<BoolValue> ProportionalSamplingParameter {
56      get { return (IValueLookupParameter<BoolValue>)Parameters[ProportionalSamplingParameterName]; }
57    }
58
59    public IFixedValueParameter<BoolValue> StrictHashingParameter {
60      get { return (IFixedValueParameter<BoolValue>)Parameters[StrictHashingParameterName]; }
61    }
62    #endregion
63
64    #region Properties
65    public PercentValue InternalCrossoverPointProbability {
66      get { return InternalCrossoverPointProbabilityParameter.ActualValue; }
67    }
68
69    public BoolValue Windowing {
70      get { return WindowingParameter.ActualValue; }
71    }
72
73    public BoolValue ProportionalSampling {
74      get { return ProportionalSamplingParameter.ActualValue; }
75    }
76
77    bool StrictHashing {
78      get { return StrictHashingParameter.Value.Value; }
79    }
80    #endregion
81
82
83    [StorableHook(HookType.AfterDeserialization)]
84    private void AfterDeserialization() {
85      if (!Parameters.ContainsKey(StrictHashingParameterName)) {
86        Parameters.Add(new FixedValueParameter<BoolValue>(StrictHashingParameterName, "Use strict hashing when calculating subtree hash values."));
87      }
88    }
89
90    public SymbolicDataAnalysisExpressionDiversityPreservingCrossover() {
91      name = "DiversityCrossover";
92      Parameters.Add(new ValueLookupParameter<PercentValue>(InternalCrossoverPointProbabilityParameterName, "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
93      Parameters.Add(new ValueLookupParameter<BoolValue>(WindowingParameterName, "Use proportional sampling with windowing for cutpoint selection.", new BoolValue(false)));
94      Parameters.Add(new ValueLookupParameter<BoolValue>(ProportionalSamplingParameterName, "Select cutpoints proportionally using probabilities as weights instead of randomly.", new BoolValue(true)));
95      Parameters.Add(new FixedValueParameter<BoolValue>(StrictHashingParameterName, "Use strict hashing when calculating subtree hash values."));
96    }
97
98    private SymbolicDataAnalysisExpressionDiversityPreservingCrossover(SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T> original, Cloner cloner) : base(original, cloner) {
99    }
100
101    public override IDeepCloneable Clone(Cloner cloner) {
102      return new SymbolicDataAnalysisExpressionDiversityPreservingCrossover<T>(this, cloner);
103    }
104
105    [StorableConstructor]
106    private SymbolicDataAnalysisExpressionDiversityPreservingCrossover(StorableConstructorFlag _) : base(_) { }
107
108    private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {
109      return tree.Root.GetSubtree(0).GetSubtree(0);
110    }
111
112    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, double internalCrossoverPointProbability, int maxLength, int maxDepth, bool windowing, bool proportionalSampling = false, bool strictHashing = false) {
113      var nodes0 = ActualRoot(parent0).MakeNodes(strictHashing).Sort(hashFunction);
114      var nodes1 = ActualRoot(parent1).MakeNodes(strictHashing).Sort(hashFunction);
115
116      IList<HashNode<ISymbolicExpressionTreeNode>> sampled0;
117      IList<HashNode<ISymbolicExpressionTreeNode>> sampled1;
118
119      if (proportionalSampling) {
120        var p = internalCrossoverPointProbability;
121        var weights0 = nodes0.Select(x => x.IsLeaf ? 1 - p : p);
122        sampled0 = nodes0.SampleProportionalWithoutRepetition(random, nodes0.Length, weights0, windowing: windowing).ToArray();
123
124        var weights1 = nodes1.Select(x => x.IsLeaf ? 1 - p : p);
125        sampled1 = nodes1.SampleProportionalWithoutRepetition(random, nodes1.Length, weights1, windowing: windowing).ToArray();
126      } else {
127        sampled0 = ChooseNodes(random, nodes0, internalCrossoverPointProbability).ShuffleInPlace(random);
128        sampled1 = ChooseNodes(random, nodes1, internalCrossoverPointProbability).ShuffleInPlace(random);
129      }
130
131      foreach (var selected in sampled0) {
132        var cutpoint = new CutPoint(selected.Data.Parent, selected.Data);
133
134        var maxAllowedDepth = maxDepth - parent0.Root.GetBranchLevel(selected.Data);
135        var maxAllowedLength = maxLength - (parent0.Length - selected.Data.GetLength());
136
137        foreach (var candidate in sampled1) {
138          if (candidate.CalculatedHashValue == selected.CalculatedHashValue
139            || candidate.Data.GetDepth() > maxAllowedDepth
140            || candidate.Data.GetLength() > maxAllowedLength
141            || !cutpoint.IsMatchingPointType(candidate.Data)) {
142            continue;
143          }
144
145          Swap(cutpoint, candidate.Data);
146          return parent0;
147        }
148      }
149      return parent0;
150    }
151
152    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
153      if (this.ExecutionContext == null) {
154        throw new InvalidOperationException("ExecutionContext not set.");
155      }
156
157      var maxDepth = MaximumSymbolicExpressionTreeDepth.Value;
158      var maxLength = MaximumSymbolicExpressionTreeLength.Value;
159
160      var internalCrossoverPointProbability = InternalCrossoverPointProbability.Value;
161      var windowing = Windowing.Value;
162      var proportionalSampling = ProportionalSampling.Value;
163
164      return Cross(random, parent0, parent1, internalCrossoverPointProbability, maxLength, maxDepth, windowing, proportionalSampling, StrictHashing);
165    }
166
167    private static List<HashNode<ISymbolicExpressionTreeNode>> ChooseNodes(IRandom random, IEnumerable<HashNode<ISymbolicExpressionTreeNode>> nodes, double internalCrossoverPointProbability) {
168      var list = new List<HashNode<ISymbolicExpressionTreeNode>>();
169
170      var chooseInternal = random.NextDouble() < internalCrossoverPointProbability;
171
172      if (chooseInternal) {
173        list.AddRange(nodes.Where(x => !x.IsLeaf && x.Data.Parent != null));
174      }
175      if (!chooseInternal || list.Count == 0) {
176        list.AddRange(nodes.Where(x => x.IsLeaf && x.Data.Parent != null));
177      }
178
179      return list;
180    }
181  }
182}
Note: See TracBrowser for help on using the repository browser.