1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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.Persistence.Default.CompositeSerializers.Storable;


28  using HeuristicLab.PluginInfrastructure;


29 


30  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {


31  [NonDiscoverableType]


32  [StorableClass]


33  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]


34  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,


35  ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator {


36  private const int MAX_TRIES = 100;


37 


38  [StorableConstructor]


39  protected ProbabilisticTreeCreator(bool deserializing) : base(deserializing) { }


40  protected ProbabilisticTreeCreator(ProbabilisticTreeCreator original, Cloner cloner) : base(original, cloner) { }


41  public ProbabilisticTreeCreator()


42  : base() {


43 


44  }


45 


46  public override IDeepCloneable Clone(Cloner cloner) {


47  return new ProbabilisticTreeCreator(this, cloner);


48  }


49 


50 


51  protected override ISymbolicExpressionTree Create(IRandom random) {


52  return Create(random, ClonedSymbolicExpressionTreeGrammarParameter.ActualValue,


53  MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value, MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value);


54  }


55 


56  public override ISymbolicExpressionTree CreateTree(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) {


57  return Create(random, grammar, maxTreeLength, maxTreeDepth);


58  }


59 


60  public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) {


61  SymbolicExpressionTree tree = new SymbolicExpressionTree();


62  var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();


63  if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);


64  rootNode.SetGrammar(grammar.CreateExpressionTreeGrammar());


65 


66  var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();


67  if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);


68  startNode.SetGrammar(grammar.CreateExpressionTreeGrammar());


69 


70  rootNode.AddSubtree(startNode);


71  PTC2(random, startNode, maxTreeLength, maxTreeDepth);


72  tree.Root = rootNode;


73  return tree;


74  }


75 


76  public static ISymbolicExpressionTree CreateExpressionTree(IRandom random, ISymbolicExpressionGrammar grammar, int targetLength,


77  int maxTreeDepth) {


78  SymbolicExpressionTree tree = new SymbolicExpressionTree();


79  var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();


80  if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);


81  rootNode.SetGrammar(grammar.CreateExpressionTreeGrammar());


82 


83  var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();


84  if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);


85  startNode.SetGrammar(grammar.CreateExpressionTreeGrammar());


86 


87  rootNode.AddSubtree(startNode);


88  bool success = TryCreateFullTreeFromSeed(random, startNode, targetLength  2, maxTreeDepth  1);


89  if (!success) throw new InvalidOperationException(string.Format("Could not create a tree with target length {0} and max depth {1}", targetLength, maxTreeDepth));


90 


91  tree.Root = rootNode;


92  return tree;


93 


94  }


95 


96  private class TreeExtensionPoint {


97  public ISymbolicExpressionTreeNode Parent { get; set; }


98  public int ChildIndex { get; set; }


99  public int ExtensionPointDepth { get; set; }


100  public int MaximumExtensionLength { get; set; }


101  public int MinimumExtensionLength { get; set; }


102  }


103 


104  public static void PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,


105  int maxLength, int maxDepth) {


106  // make sure it is possible to create a trees smaller than maxLength and maxDepth


107  if (seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol) > maxLength)


108  throw new ArgumentException("Cannot create trees of length " + maxLength + " or shorter because of grammar constraints.", "maxLength");


109  if (seedNode.Grammar.GetMinimumExpressionDepth(seedNode.Symbol) > maxDepth)


110  throw new ArgumentException("Cannot create trees of depth " + maxDepth + " or smaller because of grammar constraints.", "maxDepth");


111 


112  // tree length is limited by the grammar and by the explicit size constraints


113  int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);


114  int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol, maxDepth));


115  int tries = 0;


116  while (tries++ < MAX_TRIES) {


117  // select a target tree length uniformly in the possible range (as determined by explicit limits and limits of the grammar)


118  int targetTreeLength;


119  targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);


120  if (targetTreeLength <= 1  maxDepth <= 1) return;


121 


122  bool success = TryCreateFullTreeFromSeed(random, seedNode, targetTreeLength  1, maxDepth  1);


123 


124  // if successful => check constraints and return the tree if everything looks ok


125  if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {


126  return;


127  } else {


128  // clean seedNode


129  while (seedNode.Subtrees.Any()) seedNode.RemoveSubtree(0);


130  }


131  // try a different length MAX_TRIES times


132  }


133  throw new ArgumentException("Couldn't create a random valid tree.");


134  }


135 


136  private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root,


137  int targetLength, int maxDepth) {


138  List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();


139  int currentLength = 0;


140  int actualArity = SampleArity(random, root, targetLength, maxDepth);


141  if (actualArity < 0) return false;


142 


143  for (int i = 0; i < actualArity; i++) {


144  // insert a dummy subtree and add the pending extension to the list


145  var dummy = new SymbolicExpressionTreeNode();


146  root.AddSubtree(dummy);


147  var x = new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 };


148  FillExtensionLengths(x, maxDepth);


149  extensionPoints.Add(x);


150  }


151  //necessary to use long data type as the extension point length could be int.MaxValue


152  long minExtensionPointsLength = extensionPoints.Select(x => (long)x.MinimumExtensionLength).Sum();


153  long maxExtensionPointsLength = extensionPoints.Select(x => (long)x.MaximumExtensionLength).Sum();


154 


155  // while there are pending extension points and we have not reached the limit of adding new extension points


156  while (extensionPoints.Count > 0 && minExtensionPointsLength + currentLength <= targetLength) {


157  int randomIndex = random.Next(extensionPoints.Count);


158  TreeExtensionPoint nextExtension = extensionPoints[randomIndex];


159  extensionPoints.RemoveAt(randomIndex);


160  ISymbolicExpressionTreeNode parent = nextExtension.Parent;


161  int argumentIndex = nextExtension.ChildIndex;


162  int extensionDepth = nextExtension.ExtensionPointDepth;


163 


164  if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) > maxDepth  extensionDepth) {


165  ReplaceWithMinimalTree(random, root, parent, argumentIndex);


166  int insertedTreeLength = parent.GetSubtree(argumentIndex).GetLength();


167  currentLength += insertedTreeLength;


168  minExtensionPointsLength = insertedTreeLength;


169  maxExtensionPointsLength = insertedTreeLength;


170  } else {


171  //remove currently chosen extension point from calculation


172  minExtensionPointsLength = nextExtension.MinimumExtensionLength;


173  maxExtensionPointsLength = nextExtension.MaximumExtensionLength;


174 


175  var symbols = from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)


176  where s.InitialFrequency > 0.0


177  where parent.Grammar.GetMinimumExpressionDepth(s) <= maxDepth  extensionDepth


178  where parent.Grammar.GetMinimumExpressionLength(s) <= targetLength  currentLength  minExtensionPointsLength


179  select s;


180  if (maxExtensionPointsLength < targetLength  currentLength)


181  symbols = from s in symbols


182  where parent.Grammar.GetMaximumExpressionLength(s, maxDepth  extensionDepth) >= targetLength  currentLength  maxExtensionPointsLength


183  select s;


184  var allowedSymbols = symbols.ToList();


185 


186  if (allowedSymbols.Count == 0) return false;


187  var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();


188 


189  #pragma warning disable 612, 618


190  var selectedSymbol = allowedSymbols.SelectRandom(weights, random);


191  #pragma warning restore 612, 618


192 


193  ISymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();


194  if (newTree.HasLocalParameters) newTree.ResetLocalParameters(random);


195  parent.RemoveSubtree(argumentIndex);


196  parent.InsertSubtree(argumentIndex, newTree);


197 


198  var topLevelNode = newTree as SymbolicExpressionTreeTopLevelNode;


199  if (topLevelNode != null)


200  topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());


201 


202  currentLength++;


203  actualArity = SampleArity(random, newTree, targetLength  currentLength, maxDepth  extensionDepth);


204  if (actualArity < 0) return false;


205  for (int i = 0; i < actualArity; i++) {


206  // insert a dummy subtree and add the pending extension to the list


207  var dummy = new SymbolicExpressionTreeNode();


208  newTree.AddSubtree(dummy);


209  var x = new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 };


210  FillExtensionLengths(x, maxDepth);


211  extensionPoints.Add(x);


212  maxExtensionPointsLength += x.MaximumExtensionLength;


213  minExtensionPointsLength += x.MinimumExtensionLength;


214  }


215  }


216  }


217  // fill all pending extension points


218  while (extensionPoints.Count > 0) {


219  int randomIndex = random.Next(extensionPoints.Count);


220  TreeExtensionPoint nextExtension = extensionPoints[randomIndex];


221  extensionPoints.RemoveAt(randomIndex);


222  ISymbolicExpressionTreeNode parent = nextExtension.Parent;


223  int a = nextExtension.ChildIndex;


224  ReplaceWithMinimalTree(random, root, parent, a);


225  }


226  return true;


227  }


228 


229  private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent,


230  int childIndex) {


231  // determine possible symbols that will lead to the smallest possible tree


232  var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)


233  where s.InitialFrequency > 0.0


234  group s by parent.Grammar.GetMinimumExpressionLength(s) into g


235  orderby g.Key


236  select g).First().ToList();


237  var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();


238 


239  #pragma warning disable 612, 618


240  var selectedSymbol = possibleSymbols.SelectRandom(weights, random);


241  #pragma warning restore 612, 618


242 


243  var tree = selectedSymbol.CreateTreeNode();


244  if (tree.HasLocalParameters) tree.ResetLocalParameters(random);


245  parent.RemoveSubtree(childIndex);


246  parent.InsertSubtree(childIndex, tree);


247 


248  var topLevelNode = tree as SymbolicExpressionTreeTopLevelNode;


249  if (topLevelNode != null)


250  topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());


251 


252  for (int i = 0; i < tree.Grammar.GetMinimumSubtreeCount(tree.Symbol); i++) {


253  // insert a dummy subtree and add the pending extension to the list


254  var dummy = new SymbolicExpressionTreeNode();


255  tree.AddSubtree(dummy);


256  // replace the just inserted dummy by recursive application


257  ReplaceWithMinimalTree(random, root, tree, i);


258  }


259  }


260 


261  private static void FillExtensionLengths(TreeExtensionPoint extension, int maxDepth) {


262  var grammar = extension.Parent.Grammar;


263  int maxLength = int.MinValue;


264  int minLength = int.MaxValue;


265  foreach (ISymbol s in grammar.GetAllowedChildSymbols(extension.Parent.Symbol, extension.ChildIndex)) {


266  if (s.InitialFrequency > 0.0) {


267  int max = grammar.GetMaximumExpressionLength(s, maxDepth  extension.ExtensionPointDepth);


268  maxLength = Math.Max(maxLength, max);


269  int min = grammar.GetMinimumExpressionLength(s);


270  minLength = Math.Min(minLength, min);


271  }


272  }


273 


274  extension.MaximumExtensionLength = maxLength;


275  extension.MinimumExtensionLength = minLength;


276  }


277 


278  private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength, int maxDepth) {


279  // select actualArity randomly with the constraint that the subtrees in the minimal arity can become large enough


280  int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);


281  int maxArity = node.Grammar.GetMaximumSubtreeCount(node.Symbol);


282  if (maxArity > targetLength) {


283  maxArity = targetLength;


284  }


285  if (minArity == maxArity) return minArity;


286 


287  // the min number of subtrees has to be set to a value that is large enough so that the largest possible tree is at least tree length


288  // if 1..3 trees are possible and the largest possible first subtree is smaller larger than the target length then minArity should be at least 2


289  long aggregatedLongestExpressionLength = 0;


290  for (int i = 0; i < maxArity; i++) {


291  aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)


292  where s.InitialFrequency > 0.0


293  select node.Grammar.GetMaximumExpressionLength(s, maxDepth)).Max();


294  if (i > minArity && aggregatedLongestExpressionLength < targetLength) minArity = i + 1;


295  else break;


296  }


297 


298  // the max number of subtrees has to be set to a value that is small enough so that the smallest possible tree is at most tree length


299  // if 1..3 trees are possible and the smallest possible first subtree is already larger than the target length then maxArity should be at most 0


300  long aggregatedShortestExpressionLength = 0;


301  for (int i = 0; i < maxArity; i++) {


302  aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)


303  where s.InitialFrequency > 0.0


304  select node.Grammar.GetMinimumExpressionLength(s)).Min();


305  if (aggregatedShortestExpressionLength > targetLength) {


306  maxArity = i;


307  break;


308  }


309  }


310  if (minArity > maxArity) return 1;


311  return random.Next(minArity, maxArity + 1);


312  }


313 


314  }


315  } 
