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;


23  using System.Collections.Generic;


24  using System.Linq;


25  using System.Text;


26  using HeuristicLab.Core;


27  using HeuristicLab.Data;


28  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators;


29  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;


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


31 


32  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Creators {


33  [StorableClass]


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


35  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {


36  private const int MAX_TRIES = 100;


37 


38  public ProbabilisticTreeCreator()


39  : base() {


40  }


41 


42  protected override SymbolicExpressionTree Create(


43  IRandom random,


44  ISymbolicExpressionGrammar grammar,


45  IntValue maxTreeSize, IntValue maxTreeHeight,


46  IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {


47  return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);


48  }


49 


50  public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,


51  int maxTreeSize, int maxTreeHeight,


52  int maxFunctionDefinitions, int maxFunctionArguments


53  ) {


54  SymbolicExpressionTree tree = new SymbolicExpressionTree();


55  var rootNode = grammar.StartSymbol.CreateTreeNode();


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


57  rootNode.Grammar = grammar;


58  tree.Root = PTC2(random, rootNode, maxTreeSize, maxTreeHeight, maxFunctionDefinitions, maxFunctionArguments);


59  return tree;


60  }


61 


62  private class TreeExtensionPoint {


63  public SymbolicExpressionTreeNode Parent { get; set; }


64  public int ChildIndex { get; set; }


65  public int ExtensionPointDepth { get; set; }


66  }


67 


68  public static SymbolicExpressionTreeNode PTC2(IRandom random, SymbolicExpressionTreeNode seedNode,


69  int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {


70  // tree size is limited by the grammar and by the explicit size constraints


71  int allowedMinSize = seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol);


72  int allowedMaxSize = Math.Min(maxTreeSize, seedNode.Grammar.GetMaxExpressionLength(seedNode.Symbol));


73  int tries = 0;


74  while (tries++ < MAX_TRIES) {


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


76  int treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);


77  if (treeSize <= 1  maxDepth <= 1) return seedNode;


78 


79  bool success = CreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, treeSize, maxDepth, maxFunctionDefinitions, maxFunctionArguments);


80 


81  // if successfull => check constraints and return the tree if everything looks ok


82  if (success && seedNode.GetSize() <= maxTreeSize && seedNode.GetHeight() <= maxDepth) {


83  return seedNode;


84  } else {


85  // clean seedNode


86  while (seedNode.SubTrees.Count > 0) seedNode.RemoveSubTree(0);


87  }


88  // try a different size MAX_TRIES times


89  }


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


91  }


92 


93  private static bool CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar,


94  int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {


95  try {


96  TryCreateFullTreeFromSeed(random, root, globalGrammar, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments);


97  return true;


98  }


99  catch (ArgumentException) { return false; }


100  }


101 


102  private static void TryCreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar,


103  int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {


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


105  int currentSize = 1;


106  int totalListMinSize = globalGrammar.GetMinExpressionLength(root.Symbol)  1;


107  int actualArity = SampleArity(random, root, size);


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


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


110  var dummy = new SymbolicExpressionTreeNode();


111  root.AddSubTree(dummy);


112  extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 2 });


113  }


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


115  while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {


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


117  TreeExtensionPoint nextExtension = extensionPoints[randomIndex];


118  extensionPoints.RemoveAt(randomIndex);


119  SymbolicExpressionTreeNode parent = nextExtension.Parent;


120  int argumentIndex = nextExtension.ChildIndex;


121  int extensionDepth = nextExtension.ExtensionPointDepth;


122  if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {


123  ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments);


124  } else {


125  var allowedSymbols = from s in parent.Grammar.Symbols


126  where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)


127  where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth  1 < maxDepth


128  where parent.Grammar.GetMaxExpressionLength(s) > size  totalListMinSize  currentSize


129  select s;


130  Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols);


131  SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();


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


133  parent.RemoveSubTree(argumentIndex);


134  parent.InsertSubTree(argumentIndex, newTree);


135 


136  InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);


137 


138  currentSize++;


139  totalListMinSize;


140 


141  actualArity = SampleArity(random, newTree, size  currentSize);


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


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


144  var dummy = new SymbolicExpressionTreeNode();


145  newTree.AddSubTree(dummy);


146  extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });


147  }


148  totalListMinSize += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);


149  }


150  }


151  // fill all pending extension points


152  while (extensionPoints.Count > 0) {


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


154  TreeExtensionPoint nextExtension = extensionPoints[randomIndex];


155  extensionPoints.RemoveAt(randomIndex);


156  SymbolicExpressionTreeNode parent = nextExtension.Parent;


157  int a = nextExtension.ChildIndex;


158  int d = nextExtension.ExtensionPointDepth;


159  ReplaceWithMinimalTree(random, root, parent, a, maxFunctionDefinitions, maxFunctionArguments);


160  }


161  }


162 


163  private static void ReplaceWithMinimalTree(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode parent, int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {


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


165  var possibleSymbols = (from s in parent.GetAllowedSymbols(argumentIndex)


166  group s by parent.Grammar.GetMinExpressionLength(s) into g


167  orderby g.Key


168  select g).First();


169  var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);


170  var tree = selectedSymbol.CreateTreeNode();


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


172  parent.RemoveSubTree(argumentIndex);


173  parent.InsertSubTree(argumentIndex, tree);


174  InitializeNewTreeNode(random, root, tree, maxFunctionDefinitions, maxFunctionArguments);


175  for (int i = 0; i < tree.GetMinSubtreeCount(); i++) {


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


177  var dummy = new SymbolicExpressionTreeNode();


178  tree.AddSubTree(dummy);


179  // replace the just inserted dummy by recursive application


180  ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments);


181  }


182  }


183 


184  private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {


185  // NB it is assumed that defuns are only allowed as children of root and nowhere else


186  // also assumes that newTree is already attached to root somewhere


187  if (IsTopLevelBranch(root, newTree)) {


188  newTree.Grammar = (ISymbolicExpressionGrammar)root.Grammar.Clone();


189 


190  // allow invokes of existing ADFs with higher index


191  int argIndex = root.SubTrees.IndexOf(newTree);


192  for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {


193  var otherDefunNode = root.SubTrees[i] as DefunTreeNode;


194  if (otherDefunNode != null) {


195  GrammarModifier.AddDynamicSymbol(newTree.Grammar, newTree.Symbol, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);


196  }


197  }


198  }


199  if (newTree.Symbol is Defun) {


200  var defunTree = newTree as DefunTreeNode;


201  string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10  1)).ToString(); // >= 100 functions => ###


202  var allowedNames = from index in Enumerable.Range(0, maxFunctionDefinitions)


203  select "ADF" + index.ToString(formatString);


204  var takenNames = (from node in root.IterateNodesPrefix().OfType<DefunTreeNode>()


205  select node.FunctionName).Distinct();


206  var remainingNames = allowedNames.Except(takenNames).ToList();


207  string functionName = remainingNames[random.Next(remainingNames.Count)];


208  // set name and number of arguments of the ADF


209  int nArgs = random.Next(maxFunctionArguments);


210  defunTree.FunctionName = functionName;


211  defunTree.NumberOfArguments = nArgs;


212  if (nArgs > 0) {


213  GrammarModifier.AddDynamicArguments(defunTree.Grammar, defunTree.Symbol, Enumerable.Range(0, nArgs));


214  }


215  // in existing branches with smaller index allow invoke of current function


216  int argIndex = root.SubTrees.IndexOf(newTree);


217  for (int i = 0; i < argIndex; i++) {


218  // if not dummy node


219  if (root.SubTrees[i].Symbol != null) {


220  var existingBranch = root.SubTrees[i];


221  GrammarModifier.AddDynamicSymbol(existingBranch.Grammar, existingBranch.Symbol, functionName, nArgs);


222  }


223  }


224  }


225  }


226 


227  private static bool IsTopLevelBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode branch) {


228  return branch is SymbolicExpressionTreeTopLevelNode;


229  }


230 


231  private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {


232  var symbolList = symbols.ToList();


233  var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();


234  if (ticketsSum == 0.0) throw new ArgumentException("The initial frequency of all allowed symbols is zero.");


235  var r = random.NextDouble() * ticketsSum;


236  double aggregatedTickets = 0;


237  for (int i = 0; i < symbolList.Count; i++) {


238  aggregatedTickets += symbolList[i].InitialFrequency;


239  if (aggregatedTickets > r) {


240  return symbolList[i];


241  }


242  }


243  // this should never happen


244  throw new ArgumentException("There is a problem with the initial frequency setting of allowed symbols.");


245  }


246 


247  private static int SampleArity(IRandom random, SymbolicExpressionTreeNode node, int targetSize) {


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


249  int minArity = node.GetMinSubtreeCount();


250  int maxArity = node.GetMaxSubtreeCount();


251  if (maxArity > targetSize) {


252  maxArity = targetSize;


253  }


254  // 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 size


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


256  long aggregatedLongestExpressionLength = 0;


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


258  aggregatedLongestExpressionLength += (from s in node.GetAllowedSymbols(i)


259  select node.Grammar.GetMaxExpressionLength(s)).Max();


260  if (aggregatedLongestExpressionLength < targetSize) minArity = i;


261  else break;


262  }


263 


264  // 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 size


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


266  long aggregatedShortestExpressionLength = 0;


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


268  aggregatedShortestExpressionLength += (from s in node.GetAllowedSymbols(i)


269  select node.Grammar.GetMinExpressionLength(s)).Min();


270  if (aggregatedShortestExpressionLength > targetSize) {


271  maxArity = i;


272  break;


273  }


274  }


275  if (minArity > maxArity) throw new ArgumentException();


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


277  }


278  }


279  } 
