1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022010 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.Collections.Generic;


23  using HeuristicLab.Core;


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


25  using HeuristicLab.Data;


26  using System.Linq;


27  using System;


28  using HeuristicLab.Parameters;


29  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {


30 


31 


32  /// <summary>


33  /// Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.


34  /// And replaces the branch with root0 N0 in P0 with N1 from P1 if the treesize limits are not violated.


35  /// When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1


36  /// until a valid configuration is found.


37  /// </summary>


38  [Item("SubtreeCrossover", "An operator which performs subtree swapping crossover.")]


39  [StorableClass]


40  public class SubtreeCrossover : SymbolicExpressionTreeCrossover {


41  private const int MAX_TRIES = 100;


42 


43  public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {


44  get { return (IValueLookupParameter<PercentValue>)Parameters["InternalCrossoverPointProbability"]; }


45  }


46 


47  public SubtreeCrossover()


48  : base() {


49  Parameters.Add(new ValueLookupParameter<PercentValue>("InternalCrossoverPointProbability", "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));


50  }


51 


52  protected override SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,


53  SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,


54  IntValue maxTreeSize, IntValue maxTreeHeight) {


55  return Apply(random, grammar, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value);


56  }


57 


58  public static SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar,


59  SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,


60  double internalCrossoverPointProbability, int maxTreeSize, int maxTreeHeight) {


61  int tries = 0;


62  while (tries++ < MAX_TRIES) {


63  // select a random crossover point in the first parent


64  SymbolicExpressionTreeNode crossoverPoint0;


65  int replacedSubtreeIndex;


66  SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, out crossoverPoint0, out replacedSubtreeIndex);


67 


68  // calculate the max size and height that the inserted branch can have


69  int maxInsertedBranchSize = maxTreeSize  (parent0.Size  crossoverPoint0.SubTrees[replacedSubtreeIndex].GetSize());


70  int maxInsertedBranchHeight = maxTreeHeight  GetBranchLevel(parent0.Root, crossoverPoint0);


71 


72  var allowedBranches = from branch in IterateNodes(parent1.Root)


73  where branch.GetSize() < maxInsertedBranchSize


74  where branch.GetHeight() < maxInsertedBranchHeight


75  where grammar.AllowedSymbols(crossoverPoint0.Symbol, replacedSubtreeIndex).Contains(branch.Symbol)


76  select branch;


77 


78  if (allowedBranches.Count() > 0) {


79  var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);


80 


81  // manipulate the tree of parent0 in place


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


83  crossoverPoint0.RemoveSubTree(replacedSubtreeIndex);


84  crossoverPoint0.InsertSubTree(replacedSubtreeIndex, selectedBranch);


85  return parent0;


86  }


87  }


88 


89  // TODO: we should have a way to track the number of failed crossover attempts


90  // for now just return the first parent unchanged


91  return parent0;


92  }


93 


94  private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {


95  var crossoverPoints = from branch in IterateNodes(parent0.Root)


96  where branch.SubTrees.Count > 0


97  from index in Enumerable.Range(0, branch.SubTrees.Count)


98  let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }


99  select p;


100  var internalCrossoverPoints = (from p in crossoverPoints


101  where !p.IsLeaf


102  select p).ToList();


103  // select internal crossover point or leaf


104  if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {


105  var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];


106  crossoverPoint = selectedCrossoverPoint.CrossoverPoint;


107  subtreeIndex = selectedCrossoverPoint.SubtreeIndex;


108  } else {


109  var leafCrossoverPoints = (from p in crossoverPoints


110  where p.IsLeaf


111  select p).ToList();


112  var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];


113  crossoverPoint = selectedCrossoverPoint.CrossoverPoint;


114  subtreeIndex = selectedCrossoverPoint.SubtreeIndex;


115  }


116  }


117 


118  private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<SymbolicExpressionTreeNode> branches, double internalNodeProbability) {


119  if (internalNodeProbability < 0.0  internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");


120  var groupedBranches = from branch in branches


121  group branch by branch.SubTrees.Count into g


122  select g;


123  var allowedInternalBranches = (from g in groupedBranches


124  where g.Key > 0


125  from branch in g


126  select branch).ToList();


127  if (random.NextDouble() < internalNodeProbability && allowedInternalBranches.Count > 0) {


128  return allowedInternalBranches[random.Next(allowedInternalBranches.Count)];


129  } else {


130  var allowedLeafBranches = (from g in groupedBranches


131  where g.Key == 0


132  from leaf in g


133  select leaf).ToList();


134  return allowedLeafBranches[random.Next(allowedLeafBranches.Count)];


135  }


136  }


137 


138  private static IEnumerable<SymbolicExpressionTreeNode> IterateNodes(SymbolicExpressionTreeNode root) {


139  foreach (var subTree in root.SubTrees) {


140  foreach (var branch in IterateNodes(subTree)) {


141  yield return branch;


142  }


143  }


144  yield return root;


145  }


146 


147  private static int GetBranchLevel(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode point) {


148  if (root == point) return 0;


149  foreach (var subtree in root.SubTrees) {


150  int branchLevel = GetBranchLevel(subtree, point);


151  if (branchLevel < int.MaxValue) return 1 + branchLevel;


152  }


153  return int.MaxValue;


154  }


155  }


156  }

