1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


28  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


29 


30  namespace HeuristicLab.Problems.DataAnalysis.Symbolic {


31 


32  [Item("ProbabilisticFunctionalCrossover", "An operator which performs subtree swapping based on the behavioral similarity between subtrees.")]


33  public sealed class SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {


34  [StorableConstructor]


35  private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(bool deserializing) : base(deserializing) { }


36  private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(SymbolicDataAnalysisExpressionCrossover<T> original, Cloner cloner)


37  : base(original, cloner) { }


38  public SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover()


39  : base() {


40  }


41  public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T>(this, cloner); }


42 


43  public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {


44  ISymbolicDataAnalysisExpressionTreeInterpreter interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue;


45  List<int> rows = GenerateRowsToEvaluate().ToList();


46  T problemData = ProblemDataParameter.ActualValue;


47  return Cross(random, parent0, parent1, interpreter, problemData,


48  rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value);


49  }


50 


51  /// <summary>


52  /// Takes two parent individuals P0 and P1.


53  /// 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:


54  /// d(i,j) = 0.5 * ( abs(max(i)  max(j)) + abs(min(i)  min(j)) ).


55  /// Next, assign probabilities for the selection of the second cross point based on the inversed and normalized behavioral distance and


56  /// choose the second crosspoint via a random weighted selection procedure.


57  /// </summary>


58  public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,


59  ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, T problemData, IList<int> rows, int maxDepth, int maxLength) {


60  var crossoverPoints0 = new List<CutPoint>();


61  parent0.Root.ForEachNodePostfix((n) => {


62  if (n.Subtrees.Any() && n != parent0.Root)


63  crossoverPoints0.AddRange(from s in n.Subtrees


64  select new CutPoint(n, s));


65  });


66  var crossoverPoint0 = crossoverPoints0.SelectRandom(random);


67  int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);


68  int length = parent0.Root.GetLength()  crossoverPoint0.Child.GetLength();


69 


70  var allowedBranches = new List<ISymbolicExpressionTreeNode>();


71  parent1.Root.ForEachNodePostfix((n) => {


72  if (n.Subtrees.Any() && n != parent1.Root)


73  allowedBranches.AddRange(from s in n.Subtrees


74  where crossoverPoint0.IsMatchingPointType(s) && s.GetDepth() + level <= maxDepth && s.GetLength() + length <= maxLength


75  select s);


76  });


77 


78  if (allowedBranches.Count == 0)


79  return parent0;


80 


81  var dataset = problemData.Dataset;


82 


83  // create symbols in order to improvize an adhoc tree so that the child can be evaluated


84  var rootSymbol = new ProgramRootSymbol();


85  var startSymbol = new StartSymbol();


86  var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol); // this will change crossoverPoint0.Child.Parent


87  double min0 = 0.0, max0 = 0.0;


88  foreach (double v in interpreter.GetSymbolicExpressionTreeValues(tree0, dataset, rows)) {


89  if (min0 > v) min0 = v;


90  if (max0 < v) max0 = v;


91  }


92  crossoverPoint0.Child.Parent = crossoverPoint0.Parent; // restore correct parent


93 


94  var weights = new List<double>();


95  foreach (var node in allowedBranches) {


96  var parent = node.Parent;


97  var tree1 = CreateTreeFromNode(random, node, rootSymbol, startSymbol);


98  double min1 = 0.0, max1 = 0.0;


99  foreach (double v in interpreter.GetSymbolicExpressionTreeValues(tree1, dataset, rows)) {


100  if (min1 > v) min1 = v;


101  if (max1 < v) max1 = v;


102  }


103  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


104  weights.Add(behavioralDistance);


105  node.Parent = parent; // restore correct node parent


106  }


107 


108  // remove branches with an infinite or NaN behavioral distance


109  int count = weights.Count, idx = 0;


110  while (idx < count) {


111  if (Double.IsNaN(weights[idx])  Double.IsInfinity(weights[idx])) {


112  weights.RemoveAt(idx);


113  allowedBranches.RemoveAt(idx);


114  count;


115  } else {


116  ++idx;


117  }


118  }


119 


120  // check if there are any allowed branches left


121  if (allowedBranches.Count == 0)


122  return parent0;


123 


124  ISymbolicExpressionTreeNode selectedBranch;


125  double sum = weights.Sum();


126 


127  if (sum.IsAlmost(0.0)  weights.Count == 1) // if there is only one allowed branch, or if all weights are zero


128  selectedBranch = allowedBranches[0];


129  else {


130  for (int i = 0; i != weights.Count; ++i) // normalize and invert values


131  weights[i] = 1  weights[i] / sum;


132 


133  sum = weights.Sum(); // take new sum


134 


135  // compute the probabilities (selection weights)


136  for (int i = 0; i != weights.Count; ++i)


137  weights[i] /= sum;


138 


139  selectedBranch = allowedBranches.SelectRandom(weights, random);


140  }


141  swap(crossoverPoint0, selectedBranch);


142  return parent0;


143  }


144 


145  private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {


146  if (crossoverPoint.Child != null) {


147  // manipulate the tree of parent0 in place


148  // replace the branch in tree0 with the selected branch from tree1


149  crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);


150  if (selectedBranch != null) {


151  crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);


152  }


153  } else {


154  // child is null (additional child should be added under the parent)


155  if (selectedBranch != null) {


156  crossoverPoint.Parent.AddSubtree(selectedBranch);


157  }


158  }


159  }


160  }


161  }

