Changeset 7076


Ignore:
Timestamp:
11/25/11 15:25:54 (8 years ago)
Author:
mkommend
Message:

#1654: Corrected tree creators for symbolic expression encoding.

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4
Files:
4 edited

Legend:

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

    r7012 r7076  
    6363      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
    6464    }
    65    
     65
    6666    public IntValue MaximumSymbolicExpressionTreeLength {
    6767      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
     
    107107
    108108    public override ISymbolicExpressionTree CreateTree(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) {
    109      return Create(random, grammar, maxTreeLength, maxTreeDepth);
     109      return Create(random, grammar, maxTreeLength, maxTreeDepth);
    110110    }
    111111
     
    149149
    150150      for (var i = 0; i != arity; ++i) {
    151         var possibleSymbols = seedNode.Grammar.GetAllowedChildSymbols(seedNode.Symbol,i).Where(s => s.InitialFrequency > 0.0 && seedNode.Grammar.GetMaximumSubtreeCount(s) > 0);
     151        var possibleSymbols = seedNode.Grammar.GetAllowedChildSymbols(seedNode.Symbol, i).Where(s => s.InitialFrequency > 0.0 && seedNode.Grammar.GetMaximumSubtreeCount(s) > 0);
    152152        var selectedSymbol = possibleSymbols.SelectRandom(random);
    153153        var tree = selectedSymbol.CreateTreeNode();
     
    168168        throw new ArgumentException("Cannot grow node of arity zero. Expected a function node.");
    169169
     170      for (var i = 0; i != arity; ++i) {
     171        var possibleSymbols = root.Grammar.GetAllowedChildSymbols(root.Symbol, i);
     172        possibleSymbols = possibleSymbols.Where(s => s.InitialFrequency > 0.0 &&
     173                                          root.Grammar.GetMinimumExpressionDepth(s) - 1 <= maxDepth - currentDepth &&
     174                                          root.Grammar.GetMaximumExpressionDepth(s) > maxDepth - currentDepth);
    170175
    171       for (var i = 0; i != arity; ++i) {
    172         var possibleSymbols = currentDepth < maxDepth ?
    173           root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(s => s.InitialFrequency > 0.0 && root.Grammar.GetMaximumSubtreeCount(s) > 0) :
    174           root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(s => s.InitialFrequency > 0.0 && root.Grammar.GetMaximumSubtreeCount(s) == 0);
     176
     177        if (!possibleSymbols.Any()) throw new InvalidOperationException("No symbols are available for the tree.");
    175178        var selectedSymbol = possibleSymbols.SelectRandom(random);
    176179        var tree = selectedSymbol.CreateTreeNode();
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/GrowTreeCreator.cs

    r7012 r7076  
    6464    }
    6565
    66     public IntValue MaximumSymbolicExpressionTreeLength { 
     66    public IntValue MaximumSymbolicExpressionTreeLength {
    6767      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
    6868    }
     
    166166        throw new ArgumentException("Cannot grow node of arity zero. Expected a function node.");
    167167
    168 
    169168      for (var i = 0; i != arity; ++i) {
    170         var possibleSymbols = currentDepth < maxDepth
    171                                 ? root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(s => s.InitialFrequency > 0.0)
    172                                 : root.Grammar.GetAllowedChildSymbols(root.Symbol,i).Where(
    173                                   s => s.InitialFrequency > 0.0 && root.Grammar.GetMaximumSubtreeCount(s) == 0);
     169        var possibleSymbols = root.Grammar.GetAllowedChildSymbols(root.Symbol, i);
     170        possibleSymbols = possibleSymbols.Where(s => s.InitialFrequency > 0.0 &&
     171                                          root.Grammar.GetMinimumExpressionDepth(s) - 1 <= maxDepth - currentDepth);
     172        if (!possibleSymbols.Any()) throw new InvalidOperationException("No symbols are available for the tree.");
    174173        var selectedSymbol = possibleSymbols.SelectRandom(random);
    175174        var tree = selectedSymbol.CreateTreeNode();
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionGrammarBase.cs

    r6911 r7076  
    4040
    4141    int GetMinimumExpressionDepth(ISymbol start);
     42    int GetMaximumExpressionDepth(ISymbol start);
    4243    int GetMinimumExpressionLength(ISymbol start);
    4344    int GetMaximumExpressionLength(ISymbol start, int maxDepth);
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs

    r7001 r7076  
    8282      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    8383      cachedMinExpressionDepth = new Dictionary<string, int>();
     84      cachedMaxExpressionDepth = new Dictionary<string, int>();
    8485
    8586      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
     
    9495      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    9596      cachedMinExpressionDepth = new Dictionary<string, int>();
     97      cachedMaxExpressionDepth = new Dictionary<string, int>();
    9698
    9799      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
     
    117119      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
    118120      cachedMinExpressionDepth = new Dictionary<string, int>();
     121      cachedMaxExpressionDepth = new Dictionary<string, int>();
    119122
    120123      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
     
    372375      cachedMaxExpressionLength.Clear();
    373376      cachedMinExpressionDepth.Clear();
     377      cachedMaxExpressionDepth.Clear();
    374378
    375379      cachedIsAllowedChildSymbol.Clear();
     
    428432    }
    429433
     434    private readonly Dictionary<string, int> cachedMaxExpressionDepth;
     435    public int GetMaximumExpressionDepth(ISymbol symbol) {
     436      int temp;
     437      if (!cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) {
     438        cachedMaxExpressionDepth[symbol.Name] = int.MaxValue;
     439        long maxDepth = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
     440                             let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
     441                                                     where s.InitialFrequency > 0.0
     442                                                     select GetMaximumExpressionDepth(s)).DefaultIfEmpty(0).Max()
     443                             select maxForSlot).DefaultIfEmpty(0).Max();
     444        cachedMaxExpressionDepth[symbol.Name] = (int)Math.Min(maxDepth, int.MaxValue);
     445        return cachedMaxExpressionDepth[symbol.Name];
     446      }
     447      return temp;
     448    }
     449
    430450    public event EventHandler Changed;
    431451    protected virtual void OnChanged() {
Note: See TracChangeset for help on using the changeset viewer.