Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs @ 6009

Last change on this file since 6009 was 6009, checked in by gkronber, 13 years ago

#1472 implemented a check in PTC2 operator, fixed bugs in SymbolicExpressionGrammarBase and made some small changes in both classes to prevent numeric overflow exceptions.

File size: 14.9 KB
RevLine 
[645]1#region License Information
2/* HeuristicLab
[5445]3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[645]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
[3462]22using System;
[4068]23using System.Collections.Generic;
[3462]24using System.Linq;
[4722]25using HeuristicLab.Common;
[645]26using HeuristicLab.Core;
27using HeuristicLab.Data;
[5521]28using HeuristicLab.Parameters;
[4068]29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[645]30
[5499]31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[3223]32  [StorableClass]
[5549]33  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed length")]
[5618]34  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
[5686]35    ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator {
[3369]36    private const int MAX_TRIES = 100;
[5499]37    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
38    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
39    private const string SymbolicExpressionTreeGrammarParameterName = "SymbolicExpressionTreeGrammar";
40    #region Parameter Properties
41    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
42      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
43    }
44    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
45      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
46    }
[5686]47    public IValueLookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionTreeGrammarParameter {
48      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters[SymbolicExpressionTreeGrammarParameterName]; }
[5499]49    }
50    #endregion
51    #region Properties
52    public IntValue MaximumSymbolicExpressionTreeLength {
53      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
54    }
55    public IntValue MaximumSymbolicExpressionTreeDepth {
56      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
57    }
[5686]58    public ISymbolicExpressionGrammar SymbolicExpressionTreeGrammar {
[5499]59      get { return SymbolicExpressionTreeGrammarParameter.ActualValue; }
60    }
61    #endregion
62
[4722]63    [StorableConstructor]
[5618]64    protected ProbabilisticTreeCreator(bool deserializing) : base(deserializing) { }
65    protected ProbabilisticTreeCreator(ProbabilisticTreeCreator original, Cloner cloner) : base(original, cloner) { }
[5499]66    public ProbabilisticTreeCreator()
67      : base() {
68      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
69      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
[5686]70      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>(SymbolicExpressionTreeGrammarParameterName, "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
[5499]71    }
[3338]72
[4722]73    public override IDeepCloneable Clone(Cloner cloner) {
74      return new ProbabilisticTreeCreator(this, cloner);
[645]75    }
76
[5510]77    protected override ISymbolicExpressionTree Create(IRandom random) {
[5686]78      return Create(random, SymbolicExpressionTreeGrammar, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
79
[2447]80    }
81
[5686]82    public static ISymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
83      int maxTreeLength, int maxTreeDepth) {
[3223]84      SymbolicExpressionTree tree = new SymbolicExpressionTree();
[5686]85      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
[3442]86      if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
[4249]87      rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
[5686]88      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
89      startNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
90      if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
[5733]91      rootNode.AddSubtree(startNode);
[5686]92      PTC2(random, startNode, maxTreeLength, maxTreeDepth);
93      tree.Root = rootNode;
[3223]94      return tree;
95    }
96
[3338]97    private class TreeExtensionPoint {
[5499]98      public ISymbolicExpressionTreeNode Parent { get; set; }
[3338]99      public int ChildIndex { get; set; }
100      public int ExtensionPointDepth { get; set; }
[3223]101    }
[3360]102
[5686]103    public static void PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
104      int maxLength, int maxDepth) {
[6009]105      // make sure it is possible to create a trees smaller than maxLength and maxDepth
106      if (seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol) > maxLength)
107        throw new ArgumentException("Cannot create trees of length " + maxLength + " or shorter because of grammar constraints.", "maxLength");
108      if (seedNode.Grammar.GetMinimumExpressionDepth(seedNode.Symbol) > maxDepth)
109        throw new ArgumentException("Cannot create trees of depth " + maxDepth + " or smaller because of grammar constraints.", "maxDepth");
110
[5549]111      // tree length is limited by the grammar and by the explicit size constraints
[5686]112      int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
113      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol));
[3369]114      int tries = 0;
115      while (tries++ < MAX_TRIES) {
[5549]116        // select a target tree length uniformly in the possible range (as determined by explicit limits and limits of the grammar)
117        int targetTreeLength;
118        targetTreeLength = random.Next(allowedMinLength, allowedMaxLength + 1);
[5686]119        if (targetTreeLength <= 1 || maxDepth <= 1) return;
[3369]120
[5727]121        bool success = TryCreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth);
[3369]122
[4189]123        // if successful => check constraints and return the tree if everything looks ok       
[5549]124        if (success && seedNode.GetLength() <= maxLength && seedNode.GetDepth() <= maxDepth) {
[5686]125          return;
[3369]126        } else {
127          // clean seedNode
[5733]128          while (seedNode.Subtrees.Count() > 0) seedNode.RemoveSubtree(0);
[3360]129        }
[5549]130        // try a different length MAX_TRIES times
[3369]131      }
[3825]132      throw new ArgumentException("Couldn't create a random valid tree.");
[3338]133    }
134
[5727]135    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
[5686]136      int targetLength, int maxDepth) {
[3338]137      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
[5549]138      int currentLength = 1;
[5686]139      int totalListMinLength = globalGrammar.GetMinimumExpressionLength(root.Symbol) - 1;
[5549]140      int actualArity = SampleArity(random, root, targetLength);
[5727]141      if (actualArity < 0) return false;
142
[3223]143      for (int i = 0; i < actualArity; i++) {
144        // insert a dummy sub-tree and add the pending extension to the list
[3338]145        var dummy = new SymbolicExpressionTreeNode();
[5733]146        root.AddSubtree(dummy);
[4219]147        extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 });
[3223]148      }
149      // while there are pending extension points and we have not reached the limit of adding new extension points
[5549]150      while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
[3294]151        int randomIndex = random.Next(extensionPoints.Count);
[3338]152        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
[3294]153        extensionPoints.RemoveAt(randomIndex);
[5499]154        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
[3338]155        int argumentIndex = nextExtension.ChildIndex;
156        int extensionDepth = nextExtension.ExtensionPointDepth;
[6009]157        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) >= maxDepth - extensionDepth) {
[5686]158          ReplaceWithMinimalTree(random, root, parent, argumentIndex);
[3223]159        } else {
[5499]160          var allowedSymbols = (from s in parent.Grammar.Symbols
[5925]161                                where s.InitialFrequency > 0.0
[5686]162                                where parent.Grammar.IsAllowedChildSymbol(parent.Symbol, s, argumentIndex)
[6009]163                                where parent.Grammar.GetMinimumExpressionDepth(s) < maxDepth - extensionDepth + 1
[5686]164                                where parent.Grammar.GetMaximumExpressionLength(s) > targetLength - totalListMinLength - currentLength
[5499]165                                select s)
166                               .ToList();
167          var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
168          var selectedSymbol = allowedSymbols.SelectRandom(weights, random);
169          ISymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
[3442]170          if (newTree.HasLocalParameters) newTree.ResetLocalParameters(random);
[5733]171          parent.RemoveSubtree(argumentIndex);
172          parent.InsertSubtree(argumentIndex, newTree);
[3338]173
[5686]174          var topLevelNode = newTree as SymbolicExpressionTreeTopLevelNode;
175          if (topLevelNode != null)
176            topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
[3338]177
[5549]178          currentLength++;
179          totalListMinLength--;
[3223]180
[5549]181          actualArity = SampleArity(random, newTree, targetLength - currentLength);
[5727]182          if (actualArity < 0) return false;
[3223]183          for (int i = 0; i < actualArity; i++) {
184            // insert a dummy sub-tree and add the pending extension to the list
[3338]185            var dummy = new SymbolicExpressionTreeNode();
[5733]186            newTree.AddSubtree(dummy);
[3338]187            extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
[3223]188          }
[5686]189          totalListMinLength += newTree.Grammar.GetMinimumExpressionLength(newTree.Symbol);
[3223]190        }
191      }
192      // fill all pending extension points
[3294]193      while (extensionPoints.Count > 0) {
194        int randomIndex = random.Next(extensionPoints.Count);
[3338]195        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
[3294]196        extensionPoints.RemoveAt(randomIndex);
[5499]197        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
[3338]198        int a = nextExtension.ChildIndex;
199        int d = nextExtension.ExtensionPointDepth;
[5686]200        ReplaceWithMinimalTree(random, root, parent, a);
[3223]201      }
[5727]202      return true;
[2210]203    }
[3223]204
[5499]205    private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent,
[5686]206      int childIndex) {
[3338]207      // determine possible symbols that will lead to the smallest possible tree
[5686]208      var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)
[5925]209                             where s.InitialFrequency > 0.0
[5686]210                             group s by parent.Grammar.GetMinimumExpressionLength(s) into g
[3338]211                             orderby g.Key
[5499]212                             select g).First().ToList();
213      var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();
214      var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
[3338]215      var tree = selectedSymbol.CreateTreeNode();
[3442]216      if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
[5733]217      parent.RemoveSubtree(childIndex);
218      parent.InsertSubtree(childIndex, tree);
[5686]219
220      var topLevelNode = tree as SymbolicExpressionTreeTopLevelNode;
221      if (topLevelNode != null)
222        topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
223
224      for (int i = 0; i < tree.Grammar.GetMinimumSubtreeCount(tree.Symbol); i++) {
[3338]225        // insert a dummy sub-tree and add the pending extension to the list
226        var dummy = new SymbolicExpressionTreeNode();
[5733]227        tree.AddSubtree(dummy);
[3338]228        // replace the just inserted dummy by recursive application
[5686]229        ReplaceWithMinimalTree(random, root, tree, i);
[3338]230      }
231    }
[3360]232
[5499]233    private static bool IsTopLevelBranch(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode branch) {
[3369]234      return branch is SymbolicExpressionTreeTopLevelNode;
[3338]235    }
236
[5549]237    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
[3223]238      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
[5686]239      int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
240      int maxArity = node.Grammar.GetMaximumSubtreeCount(node.Symbol);
[5549]241      if (maxArity > targetLength) {
242        maxArity = targetLength;
[3223]243      }
[5549]244      // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree length
245      // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target length then minArity should be at least 2
[3237]246      long aggregatedLongestExpressionLength = 0;
[3223]247      for (int i = 0; i < maxArity; i++) {
[5686]248        aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
[5925]249                                              where s.InitialFrequency > 0.0
[5686]250                                              select node.Grammar.GetMaximumExpressionLength(s)).Max();
[5925]251        if (aggregatedLongestExpressionLength < targetLength) minArity = i + 1;
[3223]252        else break;
253      }
254
[5549]255      // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree length
256      // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target length then maxArity should be at most 0
[3237]257      long aggregatedShortestExpressionLength = 0;
[3223]258      for (int i = 0; i < maxArity; i++) {
[5686]259        aggregatedShortestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
[5925]260                                               where s.InitialFrequency > 0.0
[5686]261                                               select node.Grammar.GetMinimumExpressionLength(s)).Min();
[5549]262        if (aggregatedShortestExpressionLength > targetLength) {
[3223]263          maxArity = i;
264          break;
265        }
266      }
[5727]267      if (minArity > maxArity) return -1;
[3223]268      return random.Next(minArity, maxArity + 1);
269    }
[2447]270  }
[645]271}
Note: See TracBrowser for help on using the repository browser.