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.Persistence.Default.CompositeSerializers.Storable;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


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  Name = "ProbabilisticFunctionalCrossover";


41  }


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


43 


44  protected override ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {


45  ISymbolicDataAnalysisExpressionTreeInterpreter interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue;


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


47  T problemData = ProblemDataParameter.ActualValue;


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


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


50  }


51 


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


53  return Cross(random, parent0, parent1);


54  }


55 


56  /// <summary>


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


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


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


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


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


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  if (n.Subtrees.Any() && n != parent0.Root)


68  crossoverPoints0.AddRange(from s in n.Subtrees


69  select new CutPoint(n, s));


70  });


71  var crossoverPoint0 = crossoverPoints0.SelectRandom(random);


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


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


74 


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


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


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


78  allowedBranches.AddRange(from s in n.Subtrees


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


80  select s);


81  });


82 


83  if (allowedBranches.Count == 0)


84  return parent0;


85 


86  var dataset = problemData.Dataset;


87 


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


89  var rootSymbol = new ProgramRootSymbol();


90  var startSymbol = new StartSymbol();


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


92  double min0 = 0.0, max0 = 0.0;


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


94  if (min0 > v) min0 = v;


95  if (max0 < v) max0 = v;


96  }


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


98 


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


100  foreach (var node in allowedBranches) {


101  var parent = node.Parent;


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


103  double min1 = 0.0, max1 = 0.0;


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


105  if (min1 > v) min1 = v;


106  if (max1 < v) max1 = v;


107  }


108  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


109  weights.Add(behavioralDistance);


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


111  }


112 


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


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


115  while (idx < count) {


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


117  weights.RemoveAt(idx);


118  allowedBranches.RemoveAt(idx);


119  count;


120  } else {


121  ++idx;


122  }


123  }


124 


125  // check if there are any allowed branches left


126  if (allowedBranches.Count == 0)


127  return parent0;


128 


129  ISymbolicExpressionTreeNode selectedBranch;


130  double sum = weights.Sum();


131 


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


133  selectedBranch = allowedBranches[0];


134  else {


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


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


137 


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


139 


140  // compute the probabilities (selection weights)


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


142  weights[i] /= sum;


143 


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


145  }


146  swap(crossoverPoint0, selectedBranch);


147  return parent0;


148  }


149 


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


151  if (crossoverPoint.Child != null) {


152  // manipulate the tree of parent0 in place


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


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


155  if (selectedBranch != null) {


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


157  }


158  } else {


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


160  if (selectedBranch != null) {


161  crossoverPoint.Parent.AddSubtree(selectedBranch);


162  }


163  }


164  }


165  }


166  }

