Changeset 6911


Ignore:
Timestamp:
10/12/11 17:06:14 (9 years ago)
Author:
mkommend
Message:

#1657: Corrected and adapted implementation of !PTC2 to handle symbol frequencies correctly and to always create trees of the target size. Additionally the performance of the grammars have been improved and a unit test was added.

Location:
trunk/sources
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

    r6803 r6911  
    120120      public int ChildIndex { get; set; }
    121121      public int ExtensionPointDepth { get; set; }
     122      public int MaximumExtensionLength { get; set; }
     123      public int MinimumExtensionLength { get; set; }
    122124    }
    123125
     
    132134      // tree length is limited by the grammar and by the explicit size constraints
    133135      int allowedMinLength = seedNode.Grammar.GetMinimumExpressionLength(seedNode.Symbol);
    134       int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol));
     136      int allowedMaxLength = Math.Min(maxLength, seedNode.Grammar.GetMaximumExpressionLength(seedNode.Symbol, maxDepth));
    135137      int tries = 0;
    136138      while (tries++ < MAX_TRIES) {
     
    140142        if (targetTreeLength <= 1 || maxDepth <= 1) return;
    141143
    142         bool success = TryCreateFullTreeFromSeed(random, seedNode, seedNode.Grammar, targetTreeLength, maxDepth);
     144        bool success = TryCreateFullTreeFromSeed(random, seedNode, targetTreeLength - 1, maxDepth - 1);
    143145
    144146        // if successful => check constraints and return the tree if everything looks ok       
     
    154156    }
    155157
    156     private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
     158    private static bool TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root,
    157159      int targetLength, int maxDepth) {
    158160      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
    159       int currentLength = 1;
    160       int totalListMinLength = globalGrammar.GetMinimumExpressionLength(root.Symbol) - 1;
    161       int actualArity = SampleArity(random, root, targetLength);
     161      int currentLength = 0;
     162      int actualArity = SampleArity(random, root, targetLength, maxDepth);
    162163      if (actualArity < 0) return false;
    163164
     
    166167        var dummy = new SymbolicExpressionTreeNode();
    167168        root.AddSubtree(dummy);
    168         extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 });
    169       }
     169        var x = new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 0 };
     170        FillExtensionLengths(x, maxDepth);
     171        extensionPoints.Add(x);
     172      }
     173      long minExtensionPointsLength = extensionPoints.Select(x => x.MinimumExtensionLength).Sum();
     174      long maxExtensionPointsLength = extensionPoints.Select(x => x.MaximumExtensionLength).Sum();
     175
    170176      // while there are pending extension points and we have not reached the limit of adding new extension points
    171       while (extensionPoints.Count > 0 && totalListMinLength + currentLength < targetLength) {
     177      while (extensionPoints.Count > 0 && minExtensionPointsLength + currentLength <= targetLength) {
    172178        int randomIndex = random.Next(extensionPoints.Count);
    173179        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
     
    176182        int argumentIndex = nextExtension.ChildIndex;
    177183        int extensionDepth = nextExtension.ExtensionPointDepth;
    178         if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) >= maxDepth - extensionDepth) {
     184
     185        if (parent.Grammar.GetMinimumExpressionDepth(parent.Symbol) > maxDepth - extensionDepth) {
    179186          ReplaceWithMinimalTree(random, root, parent, argumentIndex);
     187          int insertedTreeLength = parent.GetSubtree(argumentIndex).GetLength();
     188          currentLength += insertedTreeLength;
     189          minExtensionPointsLength -= insertedTreeLength;
     190          maxExtensionPointsLength -= insertedTreeLength;
    180191        } else {
    181           var allowedSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
    182                                 where s.InitialFrequency > 0.0
    183                                 where parent.Grammar.GetMinimumExpressionDepth(s) < maxDepth - extensionDepth + 1
    184                                 where parent.Grammar.GetMaximumExpressionLength(s) > targetLength - totalListMinLength - currentLength
    185                                 select s)
    186                                .ToList();
     192          //remove currently chosen extension point from calculation
     193          minExtensionPointsLength -= nextExtension.MinimumExtensionLength;
     194          maxExtensionPointsLength -= nextExtension.MaximumExtensionLength;
     195
     196          var symbols = from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, argumentIndex)
     197                        where s.InitialFrequency > 0.0
     198                        where parent.Grammar.GetMinimumExpressionDepth(s) <= maxDepth - extensionDepth
     199                        where parent.Grammar.GetMinimumExpressionLength(s) <= targetLength - currentLength - minExtensionPointsLength
     200                        select s;
     201          if (maxExtensionPointsLength < targetLength - currentLength)
     202            symbols = from s in symbols
     203                      where parent.Grammar.GetMaximumExpressionLength(s, maxDepth - extensionDepth) >= targetLength - currentLength - maxExtensionPointsLength
     204                      select s;
     205          var allowedSymbols = symbols.ToList();
     206
    187207          if (allowedSymbols.Count == 0) return false;
    188208          var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
     
    198218
    199219          currentLength++;
    200           totalListMinLength--;
    201 
    202           actualArity = SampleArity(random, newTree, targetLength - currentLength);
     220          actualArity = SampleArity(random, newTree, targetLength - currentLength, maxDepth - extensionDepth);
    203221          if (actualArity < 0) return false;
    204222          for (int i = 0; i < actualArity; i++) {
     
    206224            var dummy = new SymbolicExpressionTreeNode();
    207225            newTree.AddSubtree(dummy);
    208             extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
     226            var x = new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 };
     227            FillExtensionLengths(x, maxDepth);
     228            extensionPoints.Add(x);
     229            maxExtensionPointsLength += x.MaximumExtensionLength;
     230            minExtensionPointsLength += x.MinimumExtensionLength;
    209231          }
    210           totalListMinLength += newTree.Grammar.GetMinimumExpressionLength(newTree.Symbol);
    211232        }
    212233      }
     
    218239        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
    219240        int a = nextExtension.ChildIndex;
    220         int d = nextExtension.ExtensionPointDepth;
    221241        ReplaceWithMinimalTree(random, root, parent, a);
    222242      }
     
    252272    }
    253273
    254     private static bool IsTopLevelBranch(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode branch) {
    255       return branch is SymbolicExpressionTreeTopLevelNode;
    256     }
    257 
    258     private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength) {
     274    private static void FillExtensionLengths(TreeExtensionPoint extension, int maxDepth) {
     275      var grammar = extension.Parent.Grammar;
     276      int maxLength = int.MinValue;
     277      int minLength = int.MaxValue;
     278      foreach (ISymbol s in grammar.GetAllowedChildSymbols(extension.Parent.Symbol, extension.ChildIndex)) {
     279        if (s.InitialFrequency > 0.0) {
     280          int max = grammar.GetMaximumExpressionLength(s, maxDepth - extension.ExtensionPointDepth);
     281          maxLength = Math.Max(maxLength, max);
     282          int min = grammar.GetMinimumExpressionLength(s);
     283          minLength = Math.Min(minLength, min);
     284        }
     285      }
     286
     287      extension.MaximumExtensionLength = maxLength;
     288      extension.MinimumExtensionLength = minLength;
     289    }
     290
     291    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetLength, int maxDepth) {
    259292      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
    260293      int minArity = node.Grammar.GetMinimumSubtreeCount(node.Symbol);
     
    263296        maxArity = targetLength;
    264297      }
     298      if (minArity == maxArity) return minArity;
     299
    265300      // 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
    266301      // 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
     
    269304        aggregatedLongestExpressionLength += (from s in node.Grammar.GetAllowedChildSymbols(node.Symbol, i)
    270305                                              where s.InitialFrequency > 0.0
    271                                               select node.Grammar.GetMaximumExpressionLength(s)).Max();
     306                                              select node.Grammar.GetMaximumExpressionLength(s, maxDepth)).Max();
    272307        if (i > minArity && aggregatedLongestExpressionLength < targetLength) minArity = i + 1;
    273308        else break;
     
    289324      return random.Next(minArity, maxArity + 1);
    290325    }
     326
    291327  }
    292328}
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionGrammarBase.cs

    r6803 r6911  
    3939    int GetMaximumSubtreeCount(ISymbol symbol);
    4040
     41    int GetMinimumExpressionDepth(ISymbol start);
    4142    int GetMinimumExpressionLength(ISymbol start);
    42     int GetMaximumExpressionLength(ISymbol start);
    43     int GetMinimumExpressionDepth(ISymbol start);
     43    int GetMaximumExpressionLength(ISymbol start, int maxDepth);
    4444
    4545    event EventHandler Changed;
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs

    r6814 r6911  
    8080      : base(deserializing) {
    8181      cachedMinExpressionLength = new Dictionary<string, int>();
    82       cachedMaxExpressionLength = new Dictionary<string, int>();
     82      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    8383      cachedMinExpressionDepth = new Dictionary<string, int>();
    8484
     
    9292      : base(original, cloner) {
    9393      cachedMinExpressionLength = new Dictionary<string, int>();
    94       cachedMaxExpressionLength = new Dictionary<string, int>();
     94      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    9595      cachedMinExpressionDepth = new Dictionary<string, int>();
    9696
     
    115115      : base(name, description) {
    116116      cachedMinExpressionLength = new Dictionary<string, int>();
    117       cachedMaxExpressionLength = new Dictionary<string, int>();
     117      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    118118      cachedMinExpressionDepth = new Dictionary<string, int>();
    119119
     
    348348    }
    349349
    350     public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
    351       List<string> childs;
    352       if (!allowedChildSymbols.TryGetValue(parent.Name, out childs))
    353         return Enumerable.Empty<ISymbol>();
    354 
    355       return childs.Select(GetSymbol).Where(s => s.Enabled);
    356     }
    357 
    358     public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
    359       var result = Enumerable.Empty<string>();
    360 
    361       List<string> temp;
    362       if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
    363         result = result.Union(temp);
    364       var key = Tuple.Create(parent.Name, argumentIndex);
    365       if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
    366         result = result.Union(temp);
    367 
    368       return result.Select(GetSymbol).Where(s => s.Enabled);
     350    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
     351      return from child in AllowedSymbols
     352             where IsAllowedChildSymbol(parent, child)
     353             select child;
     354    }
     355
     356    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
     357      return from child in AllowedSymbols
     358             where IsAllowedChildSymbol(parent, child, argumentIndex)
     359             select child;
    369360    }
    370361
     
    392383        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    393384                                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
     385                                                                      where s.InitialFrequency > 0.0
    394386                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
    395387                                              select minForSlot).DefaultIfEmpty(0).Sum();
     
    401393    }
    402394
    403     private readonly Dictionary<string, int> cachedMaxExpressionLength;
    404     public int GetMaximumExpressionLength(ISymbol symbol) {
     395    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
     396    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
    405397      int temp;
    406       if (!cachedMaxExpressionLength.TryGetValue(symbol.Name, out temp)) {
    407         cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
     398      var key = Tuple.Create(symbol.Name, maxDepth);
     399      if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
     400        cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
    408401        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
    409402                                  let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
    410                                                           select GetMaximumExpressionLength(s)).DefaultIfEmpty(0).Max()
     403                                                          where s.InitialFrequency > 0.0
     404                                                          where GetMinimumExpressionDepth(s) < maxDepth
     405                                                          select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
    411406                                  select maxForSlot).DefaultIfEmpty(0).Sum();
    412         cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
    413         return cachedMaxExpressionLength[symbol.Name];
     407        cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
     408        return cachedMaxExpressionLength[key];
    414409      }
    415410      return temp;
     
    423418        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
    424419                             let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
     420                                                     where s.InitialFrequency > 0.0
    425421                                                     select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
    426422                             select minForSlot).DefaultIfEmpty(0).Max();
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeGrammar.cs

    r6814 r6911  
    8080      return grammar.IsAllowedChildSymbol(parent, child, argumentIndex) || base.IsAllowedChildSymbol(parent, child, argumentIndex);
    8181    }
    82     public override IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
    83       var symbols = grammar.GetAllowedChildSymbols(parent).Union(base.GetAllowedChildSymbols(parent));
    84       return symbols.SelectMany(s => s.Flatten()).Where(s => s.Enabled).Distinct();
    85     }
    86     public override IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
    87       var symbols = grammar.GetAllowedChildSymbols(parent, argumentIndex).Union(base.GetAllowedChildSymbols(parent, argumentIndex));
    88       return symbols.SelectMany(s => s.Flatten()).Where(s => s.Enabled).Distinct();
    89     }
    9082
    9183    public override int GetMinimumSubtreeCount(ISymbol symbol) {
     
    122114      base.SetSubtreeCount(symbol, minimumSubtreeCount, maximumSubtreeCount);
    123115    }
     116
     117    int ISymbolicExpressionGrammarBase.GetMinimumExpressionDepth(ISymbol symbol) {
     118      if (symbols.Count == 0) return grammar.GetMinimumExpressionDepth(symbol);
     119      else return base.GetMinimumExpressionDepth(symbol);
     120    }
     121    int ISymbolicExpressionGrammarBase.GetMinimumExpressionLength(ISymbol symbol) {
     122      if (symbols.Count == 0) return grammar.GetMinimumExpressionLength(symbol);
     123      else return base.GetMinimumExpressionLength(symbol);
     124    }
     125    int ISymbolicExpressionGrammarBase.GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
     126      if (symbols.Count == 0) return grammar.GetMaximumExpressionLength(symbol, maxDepth);
     127      else return base.GetMaximumExpressionLength(symbol, maxDepth);
     128    }
    124129  }
    125130}
  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/ProbabilisticTreeCreaterTest.cs

    r6866 r6911  
    7272        Util.GetTerminalDistributionString(randomTrees) + Environment.NewLine
    7373        );
    74       Assert.IsTrue(Math.Round(1000.0 / (msPerRandomTreeCreation)) > 300); // must achieve more than 500 random trees / s
     74      Assert.IsTrue(Math.Round(1000.0 / (msPerRandomTreeCreation)) > 250); // must achieve more than 250 random trees / s
     75    }
     76
     77    [TestMethod]
     78    public void ProbabilisticTreeCreatorSpecificTreeSizesTest() {
     79      var trees = new List<ISymbolicExpressionTree>();
     80      var grammar = Grammars.CreateSimpleArithmeticGrammar();
     81      var random = new MersenneTwister(31415);
     82      var treeGrammarType = SymbolicExpressionTreeGrammar_Accessor.ShadowedType.ReferencedType;
     83
     84
     85      for (int targetTreeSize = 1; targetTreeSize <= 100; targetTreeSize++) {
     86        var tree = new SymbolicExpressionTree();
     87        var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
     88        rootNode.SetGrammar((ISymbolicExpressionTreeGrammar)Activator.CreateInstance(treeGrammarType, grammar));
     89        if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
     90        var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
     91        startNode.SetGrammar((ISymbolicExpressionTreeGrammar)Activator.CreateInstance(treeGrammarType, grammar));
     92        if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
     93        rootNode.AddSubtree(startNode);
     94
     95        ProbabilisticTreeCreator_Accessor.TryCreateFullTreeFromSeed(random, startNode, targetTreeSize, ((int)Math.Log(targetTreeSize, 2)) + 1);
     96        tree.Root = rootNode;
     97        Assert.AreEqual(targetTreeSize + 2, tree.Length);  //the root and start node must be additionally added
     98      }
    7599    }
    76100  }
  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4/Util.cs

    r6866 r6911  
    154154      Assert.IsTrue(grammar.Symbols.Count() == grammar.Symbols.Distinct().Count());
    155155      foreach (ISymbol symbol in grammar.AllowedSymbols) {
    156         Assert.IsTrue(grammar.GetMinimumSubtreeCount(symbol) <= grammar.GetMaximumExpressionLength(symbol));
    157156        Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol).Count() == grammar.GetAllowedChildSymbols(symbol).Distinct().Count());
    158157        for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++) {
     
    165164        for (int i = 0; i < grammar.GetMaximumSubtreeCount(symbol); i++)
    166165          Assert.IsTrue(grammar.GetAllowedChildSymbols(symbol, i).Any());
    167 
    168         //if (symbol is ProgramRootSymbol) continue;
    169         ////check if symbol is allowed as at least one child symbol
    170         //bool result = false;
    171         //foreach (var parentSymbol in grammar.Symbols) {
    172         //  if (result) break;
    173         //  for (int i = 0; i < grammar.GetMaximumSubtreeCount(parentSymbol); i++)
    174         //    result = result || grammar.IsAllowedChildSymbol(parentSymbol, symbol, i);
    175         //}
    176         //Assert.IsTrue(result);
    177 
    178166      }
    179167    }
  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r6891 r6911  
    424424    <EmbeddedResource Include="HeuristicLab.Problems.QuadraticAssignment-3.3\QAPLIB\wil50.dat" />
    425425    <None Include="HeuristicLab.snk" />
     426    <Shadow Include="Test References\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.accessor" />
    426427    <Shadow Include="Test References\HeuristicLab.PluginInfrastructure-3.3.accessor" />
    427428    <Shadow Include="Test References\HeuristicLab.MainForm.WindowsForms-3.3.accessor" />
Note: See TracChangeset for help on using the changeset viewer.