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 HeuristicLab.Core;


23  using HeuristicLab.Data;


24  using HeuristicLab.Random;


25  using System;


26  using System.Linq;


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


28  using System.Collections.Generic;


29 


30  namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {


31  [StorableClass]


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


33  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {


34  public ProbabilisticTreeCreator()


35  : base() {


36  }


37 


38  protected override SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight) {


39  return Apply(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);


40  }


41 


42  public SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight) {


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


44  int allowedMinSize = grammar.MinimalExpressionLength(grammar.StartSymbol);


45  int allowedMaxSize = Math.Min(maxTreeSize, grammar.MaximalExpressionLength(grammar.StartSymbol));


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


47  int treeSize = random.Next(allowedMinSize, allowedMaxSize);


48  SymbolicExpressionTree tree = new SymbolicExpressionTree();


49  do {


50  try {


51  tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1);


52  }


53  catch (ArgumentException) {


54  // try a different size


55  treeSize = random.Next(allowedMinSize, allowedMaxSize);


56  }


57  } while (tree.Root == null  tree.Size > maxTreeSize  tree.Height > maxTreeHeight);


58  return tree;


59  }


60 


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


62  var symbolList = symbols.ToList();


63  return symbolList[random.Next(symbolList.Count)];


64  }


65 


66 


67  private SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {


68  SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();


69  if (size <= 1  maxDepth <= 1) return root;


70  List<object[]> list = new List<object[]>();


71  int currentSize = 1;


72  int totalListMinSize = grammar.MinimalExpressionLength(rootSymbol)  1;


73 


74  int actualArity = SampleArity(random, grammar, rootSymbol, size);


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


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


77  root.AddSubTree(null);


78  list.Add(new object[] { root, i, 2 });


79  }


80 


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


82  while (list.Count > 0 && totalListMinSize + currentSize < size) {


83  int randomIndex = random.Next(list.Count);


84  object[] nextExtension = list[randomIndex];


85  list.RemoveAt(randomIndex);


86  SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];


87  int argumentIndex = (int)nextExtension[1];


88  int extensionDepth = (int)nextExtension[2];


89  if (extensionDepth + grammar.MinimalExpressionDepth(parent.Symbol) >= maxDepth) {


90  parent.RemoveSubTree(argumentIndex);


91  SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, argumentIndex));


92  parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree


93  currentSize += branch.GetSize();


94  totalListMinSize = branch.GetSize();


95  } else {


96  var allowedSubFunctions = from s in grammar.AllowedSymbols(parent.Symbol, argumentIndex)


97  where grammar.MinimalExpressionDepth(parent.Symbol) + extensionDepth  1 < maxDepth


98  where grammar.MaximalExpressionLength(s) > size  totalListMinSize  currentSize 


99  totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow


100  // terminals or terminalbranches


101  select s;


102  Symbol selectedSymbol = SelectRandomSymbol(random, allowedSubFunctions);


103  SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();


104  parent.RemoveSubTree(argumentIndex);


105  parent.InsertSubTree(argumentIndex, newTree);


106  currentSize++;


107  totalListMinSize;


108 


109  actualArity = SampleArity(random, grammar, selectedSymbol, size  currentSize);


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


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


112  newTree.AddSubTree(null);


113  list.Add(new object[] { newTree, i, extensionDepth + 1 });


114  }


115  totalListMinSize += grammar.MinimalExpressionLength(selectedSymbol);


116  }


117  }


118  // fill all pending extension points


119  while (list.Count > 0) {


120  int randomIndex = random.Next(list.Count);


121  object[] nextExtension = list[randomIndex];


122  list.RemoveAt(randomIndex);


123  SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];


124  int a = (int)nextExtension[1];


125  int d = (int)nextExtension[2];


126  parent.RemoveSubTree(a);


127  parent.InsertSubTree(a,


128  CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height


129  }


130  return root;


131  }


132 


133  private int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {


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


135  int minArity = grammar.MinSubTrees(symbol);


136  int maxArity = grammar.MaxSubTrees(symbol);


137  if (maxArity > targetSize) {


138  maxArity = targetSize;


139  }


140  // 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


141  // 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


142  long aggregatedLongestExpressionLength = 0;


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


144  aggregatedLongestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)


145  select grammar.MaximalExpressionLength(s)).Max();


146  if (aggregatedLongestExpressionLength < targetSize) minArity = i;


147  else break;


148  }


149 


150  // 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


151  // 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


152  long aggregatedShortestExpressionLength = 0;


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


154  aggregatedShortestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)


155  select grammar.MinimalExpressionLength(s)).Min();


156  if (aggregatedShortestExpressionLength > targetSize) {


157  maxArity = i;


158  break;


159  }


160  }


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


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


163  }


164 


165  private SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {


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


167  var possibleSymbols = (from s in symbols


168  group s by grammar.MinimalExpressionLength(s) into g


169  orderby g.Key


170  select g).First();


171  var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);


172  // build minimal tree by recursive application


173  var tree = selectedSymbol.CreateTreeNode();


174  for (int i = 0; i < grammar.MinSubTrees(selectedSymbol); i++)


175  tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.AllowedSymbols(selectedSymbol, i)));


176  return tree;


177  }


178  }


179  } 
