1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022008 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 System.Text;


26  using HeuristicLab.Core;


27  using HeuristicLab.Operators;


28  using HeuristicLab.Random;


29  using HeuristicLab.Data;


30  using HeuristicLab.Constraints;


31  using System.Diagnostics;


32 


33  namespace HeuristicLab.GP {


34  /// <summary>


35  /// Implementation of a size fair crossover operator as described in:


36  /// William B. Langdon


37  /// Size Fair and Homologous Tree Genetic Programming Crossovers,


38  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95119, April 2000


39  /// </summary>


40  public class SizeFairCrossOver : OperatorBase {


41  private const int MAX_RECOMBINATION_TRIES = 20;


42  public override string Description {


43  get {


44  return @"";


45  }


46  }


47  public SizeFairCrossOver()


48  : base() {


49  AddVariableInfo(new VariableInfo("Random", "Pseudo random number generator", typeof(MersenneTwister), VariableKind.In));


50  AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));


51  AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));


52  AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));


53  AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In  VariableKind.New));


54  AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));


55  AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));


56  }


57 


58  public override IOperation Apply(IScope scope) {


59  MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);


60  GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);


61  int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;


62  int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;


63 


64  TreeGardener gardener = new TreeGardener(random, opLibrary);


65 


66  if((scope.SubScopes.Count % 2) != 0)


67  throw new InvalidOperationException("Number of parents is not even");


68 


69  CompositeOperation initOperations = new CompositeOperation();


70 


71  int children = scope.SubScopes.Count / 2;


72  for(int i = 0; i < children; i++) {


73  IScope parent1 = scope.SubScopes[0];


74  scope.RemoveSubScope(parent1);


75  IScope parent2 = scope.SubScopes[0];


76  scope.RemoveSubScope(parent2);


77  IScope child = new Scope(i.ToString());


78  IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);


79  initOperations.AddOperation(childInitOperation);


80  scope.AddSubScope(child);


81  }


82 


83  return initOperations;


84  }


85 


86  private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,


87  IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {


88  List<IFunctionTree> newBranches;


89  IFunctionTree newTree = Cross(gardener, parent1, parent2,


90  random, maxTreeSize, maxTreeHeight, out newBranches);


91 


92 


93  int newTreeSize = newTree.Size;


94  int newTreeHeight = newTree.Height;


95  child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));


96  child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));


97  child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));


98 


99  // check if the new tree is valid and if the height of is still in the allowed bounds (we are not so strict for the maxsize)


100  Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);


101  return gardener.CreateInitializationOperation(newBranches, child);


102  }


103 


104 


105  private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {


106  IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);


107  int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;


108  int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;


109 


110  IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);


111  int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;


112  int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;


113 


114  if(tree0Size == 1 && tree1Size == 1) {


115  return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);


116  } else {


117  newBranches = new List<IFunctionTree>();


118 


119  // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal


120  // in case both trees are higher than 1 we swap the trees with probability 50%


121  if(tree0Height == 1  (tree1Height > 1 && random.Next(2) == 0)) {


122  IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;


123  int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;


124  int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;


125  }


126 


127  // select a random suboperator of the 'receiving' tree


128  IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);


129  int removedBranchIndex;


130  IFunctionTree removedBranch;


131  IList<IFunction> allowedFunctions;


132  if(crossoverPoint == null) {


133  removedBranchIndex = 0;


134  removedBranch = tree0;


135  allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);


136  } else {


137  removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);


138  removedBranch = crossoverPoint.SubTrees[removedBranchIndex];


139  allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);


140  }


141  int removedBranchSize = removedBranch.Size;


142  int maxBranchSize = maxTreeSize  (tree0.Size  removedBranchSize);


143  int maxBranchHeight = maxTreeHeight  gardener.GetBranchLevel(tree0, removedBranch);


144  IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);


145 


146  int tries = 0;


147  while(insertedBranch == null) {


148  if(tries++ > MAX_RECOMBINATION_TRIES) {


149  if(random.Next() > 0.5) return tree1;


150  else return tree0;


151  }


152 


153  // retry with a different crossoverPoint


154  crossoverPoint = gardener.GetRandomParentNode(tree0);


155  if(crossoverPoint == null) {


156  removedBranchIndex = 0;


157  removedBranch = tree0;


158  allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);


159  } else {


160  removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);


161  removedBranch = crossoverPoint.SubTrees[removedBranchIndex];


162  allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);


163  }


164  removedBranchSize = removedBranch.Size;


165  maxBranchSize = maxTreeSize  (tree0.Size  removedBranchSize);


166  maxBranchHeight = maxTreeHeight  gardener.GetBranchLevel(tree0, removedBranch) + 1;


167  insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);


168  }


169  if(crossoverPoint != null) {


170  // replace the branch below the crossoverpoint with the selected branch from root1


171  crossoverPoint.RemoveSubTree(removedBranchIndex);


172  crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);


173  return tree0;


174  } else {


175  return insertedBranch;


176  }


177  }


178  }


179 


180  private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {


181  var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)


182  .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);


183 


184  var shorterBranches = branches.Where(t => t.Size < removedBranchSize);


185  var longerBranches = branches.Where(t => t.Size > removedBranchSize);


186  var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);


187 


188  if(shorterBranches.Count() == 0  longerBranches.Count() == 0) {


189  if(equalLengthBranches.Count() == 0) {


190  return null;


191  } else {


192  return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;


193  }


194  } else {


195  // invariant: shorterBranches > 0 and longerBranches > 0


196  double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;


197  double pLonger = (1.0  pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));


198  double pShorter = (1.0  pEqualLength  pLonger);


199 


200  double r = random.NextDouble();


201  if(r < pLonger) {


202  return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;


203  } else if(r < pLonger + pShorter) {


204  return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;


205  } else {


206  return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;


207  }


208  }


209  }


210 


211 


212  // take f and g and create a tree that has f and g as subtrees


213  // example


214  // O


215  // /\


216  // g 2 f


217  //


218  private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {


219  newBranches = new List<IFunctionTree>();


220  // determine the set of possible parent functions


221  ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });


222  if(possibleParents.Count == 0) throw new InvalidProgramException();


223  // and select a random one


224  IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();


225 


226  int nSlots = Math.Max(2, parent.Function.MinArity);


227  // determine which slot can take which subtrees


228  List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];


229  for(int slot = 0; slot < nSlots; slot++) {


230  ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);


231  List<IFunctionTree> allowedTrees = new List<IFunctionTree>();


232  if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);


233  if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);


234  slots[slot] = allowedTrees;


235  }


236  // fill the slots in the order of degrees of freedom


237  int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();


238 


239  // tmp arry to store the tree for each subtree slot of the parent


240  IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];


241 


242  // fill the subtree slots of the parent starting with the slots that can take potentially both functions (f and g)


243  for(int i = 0; i < slotSequence.Length; i++) {


244  int slot = slotSequence[i];


245  List<IFunctionTree> allowedTrees = slots[slot];


246  // when neither f nor g fit into the slot => create a new random tree


247  if(allowedTrees.Count() == 0) {


248  var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);


249  selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);


250  newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));


251  } else {


252  // select randomly which tree to insert into this slot


253  IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];


254  selectedFunctionTrees[slot] = selectedTree;


255  // remove the tree that we used in this slot from following functionsets


256  for(int j = i + 1; j < slotSequence.Length; j++) {


257  int otherSlot = slotSequence[j];


258  slots[otherSlot].Remove(selectedTree);


259  }


260  }


261  }


262  // actually append the subtrees to the parent tree


263  for(int i = 0; i < selectedFunctionTrees.Length; i++) {


264  parent.InsertSubTree(i, selectedFunctionTrees[i]);


265  }


266 


267  return parent;


268  }


269  }


270  }

