Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GBT/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover.cs @ 12495

Last change on this file since 12495 was 12495, checked in by gkronber, 9 years ago

#2261: merged trunk changes to branch
r12494
#2403: added a null check in the MatlabParameterVectorEvaluator to prevent exceptions when clearstate is called


r12493
#2369: added support for squared errors and relative errors to error-characteristic-curve view


r12492
#2392: implemented PearsonsRCalculator to fix incorrect correlation values in the correlation matrix.


r12491
#2402 don't set task state to waiting when it fails


r12490
#2401 added missing Mono.Cecil plugin dependency


r12488
#2400 - Interfaces for Capaciated-, PickupAndDelivery- and TimeWindowed-ProblemInstances now specify an additional penalty parameter to set the current penalty factor for the constraint relaxation. - The setter of the penalty-property in ...


r12485
#2374 made RegressionSolution and ClassificationSolution non-abstract


r12482
#2320: Fixed warnings in unit test solutions introduced in r12420 by marking methods as obsolete.


r12481
#2320: Fixed AfterDeserialization of GEArtifialAntEvaluator.


r12480
#2320: Fixed error in symbolicexpressiontree crossover regarding the wiring of lookup parameters if persisted file is loaded.


r12479
#2397 moved GeoIP project into ExtLibs


r12478
#2329 fixed bug in simple code editor


r12476
#2331 removed outdated plugins


r12475
#2368 fixed compile warnings


r12474
#2399 worked on Mono project prepare script


r12473
#2329 added a simple code editor for Linux


r12472
#2399 - fixed MathJax.js file name - worked on Mono project prepare script


r12471
#2399 worked on Mono project prepare script


r12470
#2399 fixed pre-build events in project files


r12465
#2399 worked on mono project prepare script


r12464
#2399 added patch to project


r12463
#2399 fixed EPPlus so that it compiles on Linux


r12461
#2398: Skip root and start symbols when calculating impacts and replacement values in the pruning operators.


r12458
#2354 show label when no data is displayed and don't show the legend


r12457
#2353 removed duplicated call to Any() in Hive Status page


r12456
#2368 fixed modifier


r12455
#2368 added support in persistence for typecaches in streams


r12445
#2394: Changed Web.config compilation from debug to release to force script bundling. Changed history loading type from lazy to eager loading to increase performance. Fixed "getCoreStatus" typo in statusCtrl.js


r12443
#2394: Fixed UserTaskQuery and GetStatusHistory in the WebApp.Status plugin


r12442
#2394 added nuget folders to svn ignore list


r12435
#2394: Improved PluginManager and updated hive status monitor.


r12434
#2396 added symbolic expression tree formatter for C#


r12433
#2395: Minor change in DoubleValue.GetValue.


r12432
#2395 Use simple round-trip format for doubles because G17 prints some strange numbers (20.22 to 20.219999999999999999). Some accuracy can still be lost on 64bit machines, but should be very rare and minimal. double.MaxValue can still be pa...


r12431
#2395 Fixed parsing issues by using the G17 format.


r12430
#2394 added missing package config


r12429
#2394 added missing package config


r12428
#2394 added web app and status page to trunk


r12424
#2320: Adapted plugin file and updated project file of SymbolicExpressionTreeEncoding.


r12422
#2320: Merged the encoding class and all accompanying changes in the trunk.


r12401
#2387 Fixed a bug where the automatic selection of the first element behaved differently for the NewItemDialog.


r12400
#2387 Forgot to commit a file.


r12399
#2387 - Added context-menu for expanding and collapsing tree-nodes. - Improve response time when expanding/collapsing all nodes for TypeSelector and NewItemDialog.


r12398
#2387 - Added clearSearch-button in TypeSelector. - Adapted behavior of TypeSelector and NewItemDialog that a selected node stays selected as long as it matches the search criteria.


r12397
#2387 - Adapted behavior of the matching in the TypeSelector that it behave the same as the NewItemDialog. The search string is tokenized by space and matches if all tokens are contained, (eg. "Sym Reg" matches "SymbolicRegression...")...


r12393
#2025 - Removed Expand/CollapseAll buttons. - Removed cycling of items.


r12392
#2386: Updated GetHashCode method in the EnumerableBoolEqualityComparer.


File size: 7.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Random;
30
31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
32  [Item("ProbabilisticFunctionalCrossover", "An operator which performs subtree swapping based on the behavioral similarity between subtrees:\n" +
33                                            "- Take two parent individuals P0 and P1\n" +
34                                            "- Randomly choose a node N from P0\n" +
35                                            "- For each matching node M from P1, calculate the behavioral distance:\n" +
36                                            "\t\tD(N,M) = 0.5 * ( abs(max(N) - max(M)) + abs(min(N) - min(M)) )\n" +
37                                            "- Make a probabilistic weighted choice of node M from P1, based on the inversed and normalized behavioral distance")]
38  public sealed class SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
39    [StorableConstructor]
40    private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(bool deserializing) : base(deserializing) { }
41    private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(SymbolicDataAnalysisExpressionCrossover<T> original, Cloner cloner)
42      : base(original, cloner) { }
43    public SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover()
44      : base() {
45      name = "ProbabilisticFunctionalCrossover";
46    }
47    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T>(this, cloner); }
48
49    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
50      ISymbolicDataAnalysisExpressionTreeInterpreter interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue;
51      List<int> rows = GenerateRowsToEvaluate().ToList();
52      T problemData = ProblemDataParameter.ActualValue;
53      return Cross(random, parent0, parent1, interpreter, problemData,
54                   rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value);
55    }
56
57    /// <summary>
58    /// Takes two parent individuals P0 and P1.
59    /// Randomly choose a node i from the first parent, then for each matching node j from the second parent, calculate the behavioral distance based on the range:
60    /// d(i,j) = 0.5 * ( abs(max(i) - max(j)) + abs(min(i) - min(j)) ).
61    /// Next, assign probabilities for the selection of a node j based on the inversed and normalized behavioral distance, then make a random weighted choice.
62    /// </summary>
63    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
64                                                ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, T problemData, IList<int> rows, int maxDepth, int maxLength) {
65      var crossoverPoints0 = new List<CutPoint>();
66      parent0.Root.ForEachNodePostfix((n) => {
67        // the if clauses prevent the root or the startnode from being selected, although the startnode can be the parent of the node being swapped.
68        if (n.Parent != null && n.Parent != parent0.Root) {
69          crossoverPoints0.Add(new CutPoint(n.Parent, n));
70        }
71      });
72
73      var crossoverPoint0 = crossoverPoints0.SampleRandom(random);
74      int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
75      int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
76
77      var allowedBranches = new List<ISymbolicExpressionTreeNode>();
78      parent1.Root.ForEachNodePostfix((n) => {
79        if (n.Parent != null && n.Parent != parent1.Root) {
80          if (n.GetDepth() + level <= maxDepth && n.GetLength() + length <= maxLength && crossoverPoint0.IsMatchingPointType(n))
81            allowedBranches.Add(n);
82        }
83      });
84
85      if (allowedBranches.Count == 0)
86        return parent0;
87
88      var dataset = problemData.Dataset;
89
90      // create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
91      var rootSymbol = new ProgramRootSymbol();
92      var startSymbol = new StartSymbol();
93      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol); // this will change crossoverPoint0.Child.Parent
94      double min0 = 0.0, max0 = 0.0;
95      foreach (double v in interpreter.GetSymbolicExpressionTreeValues(tree0, dataset, rows)) {
96        if (min0 > v) min0 = v;
97        if (max0 < v) max0 = v;
98      }
99      crossoverPoint0.Child.Parent = crossoverPoint0.Parent; // restore correct parent
100
101      var weights = new List<double>();
102      foreach (var node in allowedBranches) {
103        var parent = node.Parent;
104        var tree1 = CreateTreeFromNode(random, node, rootSymbol, startSymbol);
105        double min1 = 0.0, max1 = 0.0;
106        foreach (double v in interpreter.GetSymbolicExpressionTreeValues(tree1, dataset, rows)) {
107          if (min1 > v) min1 = v;
108          if (max1 < v) max1 = v;
109        }
110        double behavioralDistance = (Math.Abs(min0 - min1) + Math.Abs(max0 - max1)) / 2; // this can be NaN of Infinity because some trees are crazy like exp(exp(exp(...))), we correct that below
111        weights.Add(behavioralDistance);
112        node.Parent = parent; // restore correct node parent
113      }
114
115      // remove branches with an infinite or NaN behavioral distance
116      for (int i = weights.Count - 1; i >= 0; --i) {
117        if (Double.IsNaN(weights[i]) || Double.IsInfinity(weights[i])) {
118          weights.RemoveAt(i);
119          allowedBranches.RemoveAt(i);
120        }
121      }
122      // check if there are any allowed branches left
123      if (allowedBranches.Count == 0)
124        return parent0;
125
126      ISymbolicExpressionTreeNode selectedBranch;
127      double sum = weights.Sum();
128
129      if (sum.IsAlmost(0.0) || weights.Count == 1) // if there is only one allowed branch, or if all weights are zero
130        selectedBranch = allowedBranches[0];
131      else {
132        for (int i = 0; i != weights.Count; ++i) // normalize and invert values
133          weights[i] = 1 - weights[i] / sum;
134
135        sum = weights.Sum(); // take new sum
136
137        // compute the probabilities (selection weights)
138        for (int i = 0; i != weights.Count; ++i)
139          weights[i] /= sum;
140
141#pragma warning disable 612, 618
142        selectedBranch = allowedBranches.SelectRandom(weights, random);
143#pragma warning restore 612, 618
144      }
145      Swap(crossoverPoint0, selectedBranch);
146      return parent0;
147    }
148  }
149}
Note: See TracBrowser for help on using the repository browser.