Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/16/11 19:01:00 (14 years ago)
Author:
gkronber
Message:

#1418 changes in symbolic expression tree encoding.

Location:
branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4

    • Property svn:ignore

      •  

        old new  
        22obj
        33HeuristicLabEncodingsSymbolicExpressionTreeEncodingPlugin.cs
         4*.user

  • branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Creators/ProbabilisticTreeCreator.cs

    r5445 r5499  
    2727using HeuristicLab.Core;
    2828using HeuristicLab.Data;
    29 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators;
    30 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
    3129using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    32 
    33 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Creators {
     30using HeuristicLab.Parameters;
     31
     32namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3433  [StorableClass]
    3534  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
    36   public sealed class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {
     35  public sealed class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator,
     36    ISymbolicExpressionTreeSizeConstraintOperator, ISymbolicExpressionTreeGrammarBasedOperator, ISymbolicExpressionTreeArchitectureAlteringOperator {
    3737    private const int MAX_TRIES = 100;
     38    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     39    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
     40    private const string MaximumFunctionDefinitionsParameterName = "MaximumFunctionDefinitions";
     41    private const string MaximumFunctionArgumentsParameterName = "MaximumFunctionArguments";
     42    private const string SymbolicExpressionTreeGrammarParameterName = "SymbolicExpressionTreeGrammar";
     43    #region Parameter Properties
     44    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
     45      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
     46    }
     47    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
     48      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
     49    }
     50    public IValueLookupParameter<IntValue> MaximumFunctionDefinitionsParameter {
     51      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumFunctionDefinitionsParameterName]; }
     52    }
     53    public IValueLookupParameter<IntValue> MaximumFunctionArgumentsParameter {
     54      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumFunctionArgumentsParameterName]; }
     55    }
     56    public IValueLookupParameter<ISymbolicExpressionTreeGrammar> SymbolicExpressionTreeGrammarParameter {
     57      get { return (IValueLookupParameter<ISymbolicExpressionTreeGrammar>)Parameters[SymbolicExpressionTreeGrammarParameterName]; }
     58    }
     59    #endregion
     60    #region Properties
     61    public IntValue MaximumSymbolicExpressionTreeLength {
     62      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
     63    }
     64    public IntValue MaximumSymbolicExpressionTreeDepth {
     65      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
     66    }
     67    public IntValue MaximumFunctionDefinitions {
     68      get { return MaximumFunctionDefinitionsParameter.ActualValue; }
     69    }
     70    public IntValue MaximumFunctionArguments {
     71      get { return MaximumFunctionArgumentsParameter.ActualValue; }
     72    }
     73    public ISymbolicExpressionTreeGrammar SymbolicExpressionTreeGrammar {
     74      get { return SymbolicExpressionTreeGrammarParameter.ActualValue; }
     75    }
     76    #endregion
     77
    3878    [StorableConstructor]
    3979    private ProbabilisticTreeCreator(bool deserializing) : base(deserializing) { }
    4080    private ProbabilisticTreeCreator(ProbabilisticTreeCreator original, Cloner cloner) : base(original, cloner) { }
    41     public ProbabilisticTreeCreator() : base() { }
     81    public ProbabilisticTreeCreator()
     82      : base() {
     83      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
     84      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
     85      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumFunctionDefinitionsParameterName, "The maximum allowed number of automatically defined functions."));
     86      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumFunctionArgumentsParameterName, "The maximum allowed number of arguments of automatically defined functions."));
     87      Parameters.Add(new ValueLookupParameter<SymbolicExpressionTreeGrammar>(SymbolicExpressionTreeGrammarParameterName, "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
     88    }
    4289
    4390    public override IDeepCloneable Clone(Cloner cloner) {
    … …  
    4592    }
    4693
    47     protected override SymbolicExpressionTree Create(
    48       IRandom random,
    49       ISymbolicExpressionGrammar grammar,
    50       IntValue maxTreeSize, IntValue maxTreeHeight,
    51       IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
    52       return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
    53     }
    54 
    55     public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
     94    protected override SymbolicExpressionTree Create(IRandom random) {
     95      return Create(random, SymbolicExpressionTreeGrammar, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value,
     96        MaximumFunctionDefinitions.Value, MaximumFunctionArguments.Value);
     97    }
     98
     99    public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionTreeGrammar grammar,
    56100      int maxTreeSize, int maxTreeHeight,
    57101      int maxFunctionDefinitions, int maxFunctionArguments
    … …  
    66110
    67111    private class TreeExtensionPoint {
    68       public SymbolicExpressionTreeNode Parent { get; set; }
     112      public ISymbolicExpressionTreeNode Parent { get; set; }
    69113      public int ChildIndex { get; set; }
    70114      public int ExtensionPointDepth { get; set; }
    71115    }
    72116
    73     public static SymbolicExpressionTreeNode PTC2(IRandom random, SymbolicExpressionTreeNode seedNode,
     117    public static ISymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionTreeNode seedNode,
    74118      int maxTreeSize, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    75119      // tree size is limited by the grammar and by the explicit size constraints
    … …  
    79123      while (tries++ < MAX_TRIES) {
    80124        // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
    81         int treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);
     125        int treeSize;
     126        treeSize = random.Next(allowedMinSize, allowedMaxSize + 1);
    82127        if (treeSize <= 1 || maxDepth <= 1) return seedNode;
    83128
    … …  
    89134        } else {
    90135          // clean seedNode
    91           while (seedNode.SubTrees.Count > 0) seedNode.RemoveSubTree(0);
     136          while (seedNode.SubTrees.Count() > 0) seedNode.RemoveSubTree(0);
    92137        }
    93138        // try a different size MAX_TRIES times
    … …  
    96141    }
    97142
    98     private static bool CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar,
     143    private static bool CreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
    99144      int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    100145      try {
    … …  
    105150    }
    106151
    107     private static void TryCreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, ISymbolicExpressionGrammar globalGrammar,
     152    private static void TryCreateFullTreeFromSeed(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeGrammar globalGrammar,
    108153      int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
    109154      List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
    … …  
    122167        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
    123168        extensionPoints.RemoveAt(randomIndex);
    124         SymbolicExpressionTreeNode parent = nextExtension.Parent;
     169        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
    125170        int argumentIndex = nextExtension.ChildIndex;
    126171        int extensionDepth = nextExtension.ExtensionPointDepth;
    … …  
    128173          ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments);
    129174        } else {
    130           var allowedSymbols = from s in parent.Grammar.Symbols
    131                                where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
    132                                where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
    133                                where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
    134                                select s;
    135           Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols);
    136           SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
     175          var allowedSymbols = (from s in parent.Grammar.Symbols
     176                                where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
     177                                where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
     178                                where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
     179                                select s)
     180                               .ToList();
     181          var weights = allowedSymbols.Select(x => x.InitialFrequency).ToList();
     182          var selectedSymbol = allowedSymbols.SelectRandom(weights, random);
     183          ISymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
    137184          if (newTree.HasLocalParameters) newTree.ResetLocalParameters(random);
    138185          parent.RemoveSubTree(argumentIndex);
    … …  
    159206        TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
    160207        extensionPoints.RemoveAt(randomIndex);
    161         SymbolicExpressionTreeNode parent = nextExtension.Parent;
     208        ISymbolicExpressionTreeNode parent = nextExtension.Parent;
    162209        int a = nextExtension.ChildIndex;
    163210        int d = nextExtension.ExtensionPointDepth;
    … …  
    166213    }
    167214
    168     private static void ReplaceWithMinimalTree(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode parent, int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {
     215    private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent,
     216      int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {
    169217      // determine possible symbols that will lead to the smallest possible tree
    170218      var possibleSymbols = (from s in parent.GetAllowedSymbols(argumentIndex)
    171219                             group s by parent.Grammar.GetMinExpressionLength(s) into g
    172220                             orderby g.Key
    173                              select g).First();
    174       var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
     221                             select g).First().ToList();
     222      var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();
     223      var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
    175224      var tree = selectedSymbol.CreateTreeNode();
    176225      if (tree.HasLocalParameters) tree.ResetLocalParameters(random);
    … …  
    187236    }
    188237
    189     private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
     238    private static void InitializeNewTreeNode(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
    190239      // NB it is assumed that defuns are only allowed as children of root and nowhere else
    191240      // also assumes that newTree is already attached to root somewhere
    192241      if (IsTopLevelBranch(root, newTree)) {
    193         ((SymbolicExpressionTreeTopLevelNode)newTree).SetGrammar((ISymbolicExpressionGrammar)root.Grammar.Clone());
     242        ((SymbolicExpressionTreeTopLevelNode)newTree).SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
    194243
    195244        // allow invokes of existing ADFs with higher index
    196         int argIndex = root.SubTrees.IndexOf(newTree);
    197         for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {
    198           var otherDefunNode = root.SubTrees[i] as DefunTreeNode;
     245        int argIndex = root.IndexOfSubTree(newTree);
     246        for (int i = argIndex + 1; i < root.SubTrees.Count(); i++) {
     247          var otherDefunNode = root.GetSubTree(i) as DefunTreeNode;
    199248          if (otherDefunNode != null) {
    200249            GrammarModifier.AddDynamicSymbol(newTree.Grammar, newTree.Symbol, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);
    … …  
    219268        }
    220269        // in existing branches with smaller index allow invoke of current function
    221         int argIndex = root.SubTrees.IndexOf(newTree);
     270        int argIndex = root.IndexOfSubTree(newTree);
    222271        for (int i = 0; i < argIndex; i++) {
    223272          // if not dummy node
    224           if (root.SubTrees[i].Symbol != null) {
    225             var existingBranch = root.SubTrees[i];
     273          if (root.GetSubTree(i).Symbol != null) {
     274            var existingBranch = root.GetSubTree(i);
    226275            GrammarModifier.AddDynamicSymbol(existingBranch.Grammar, existingBranch.Symbol, functionName, nArgs);
    227276          }
    … …  
    230279    }
    231280
    232     private static bool IsTopLevelBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode branch) {
     281    private static bool IsTopLevelBranch(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode branch) {
    233282      return branch is SymbolicExpressionTreeTopLevelNode;
    234283    }
    235284
    236     private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
    237       var symbolList = symbols.ToList();
    238       var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
    239       if (ticketsSum == 0.0) throw new ArgumentException("The initial frequency of all allowed symbols is zero.");
    240       var r = random.NextDouble() * ticketsSum;
    241       double aggregatedTickets = 0;
    242       for (int i = 0; i < symbolList.Count; i++) {
    243         aggregatedTickets += symbolList[i].InitialFrequency;
    244         if (aggregatedTickets > r) {
    245           return symbolList[i];
    246         }
    247       }
    248       // this should never happen
    249       throw new ArgumentException("There is a problem with the initial frequency setting of allowed symbols.");
    250     }
    251 
    252     private static int SampleArity(IRandom random, SymbolicExpressionTreeNode node, int targetSize) {
     285    private static int SampleArity(IRandom random, ISymbolicExpressionTreeNode node, int targetSize) {
    253286      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
    254287      int minArity = node.GetMinSubtreeCount();
Note: See TracChangeset for help on using the changeset viewer.