Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs @ 12955

Last change on this file since 12955 was 12955, checked in by gkronber, 9 years ago

#2471: implemented deterministic BFS and DFS for iterated symbolic expression construction

File size: 7.0 KB
RevLine 
[12909]1using System;
2using System.Collections.Generic;
3using System.Diagnostics.Contracts;
4using System.Linq;
5using System.Net.NetworkInformation;
6using System.Text;
7using System.Threading.Tasks;
8using HeuristicLab.Common;
9using HeuristicLab.Core;
10using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
11using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
12
13namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
14  // this class is a base class for symbolic expression construction policies
15  // it filters allowed actions based on tree length constraint
16  // and keeps all visited derivation paths in memory to prevent sampling of duplicates
17  [StorableClass]
18  public abstract class SymbolicExpressionConstructionPolicyBase : ParameterizedNamedItem, ISymbolicExpressionConstructionPolicy {
19    [Storable]
20    public SymbolicExpressionTreeProblem Problem { get; private set; }
21    [Storable]
22    public IRandom Random { get; private set; }
[12923]23    private SearchTree<ISymbol> searchTree; // tree of replacement symbols
[12909]24
25    private class Slot {
26      public ISymbolicExpressionTreeNode parent;
27      public int childIdx;
28      public int minSize;
29    }
30
31    [StorableHook(HookType.AfterDeserialization)]
32    private void AfterDeserialization() {
[12923]33      searchTree = new SearchTree<ISymbol>();
[12909]34    }
35    protected SymbolicExpressionConstructionPolicyBase(SymbolicExpressionConstructionPolicyBase original, Cloner cloner)
36      : base(original, cloner) {
37      this.Problem = cloner.Clone(original.Problem);
38      this.Random = cloner.Clone(original.Random);
39
40      // search tree is not cloned or stored
[12923]41      searchTree = new SearchTree<ISymbol>();
[12909]42    }
43
44    [StorableConstructor]
45    protected SymbolicExpressionConstructionPolicyBase(bool deserializing) : base(deserializing) { }
46
47    protected SymbolicExpressionConstructionPolicyBase() {
[12922]48
[12909]49    }
50
51    public virtual void Initialize(SymbolicExpressionTreeProblem problem, IRandom random) {
52      this.Problem = problem;
53      this.Random = random;
[12923]54      this.searchTree = new SearchTree<ISymbol>(); // represents all realized actionSequences as a prefix tree
[12909]55    }
56
[12923]57    public ISymbolicExpressionTree Sample(out IEnumerable<object> stateSequence) {
58      var actions = new List<ISymbol>();
[12909]59      var states = new List<object>();
60
61      var openSlots = new Stack<Slot>();
62      var g = Problem.Encoding.Grammar;
63      var root = g.ProgramRootSymbol.CreateTreeNode();
[12955]64      int maxDepth = Problem.Encoding.TreeDepthParameter.Value.Value; // ignored
[12909]65      int maxLen = Problem.Encoding.TreeLengthParameter.Value.Value;
66
67
68      Contract.Assert(Problem.Encoding.FunctionDefinitions == 0);
[12923]69      openSlots.Push(new Slot() { parent = root, childIdx = 0, minSize = g.GetMinimumExpressionLength(root.Symbol) - 1 }); // at least two nodes are necessary below root
[12909]70
71      // tree size lower bound is the current tree size + the sum of the minimal size for all open slots
72      int treeSize = 1;
73
74      searchTree.ResetPosition();
75
76      while (openSlots.Any()) {
[12955]77        var next = openSlots.First();
78        openSlots.Pop();
[12909]79        var parent = next.parent;
80        var childIdx = next.childIdx;
81
[12923]82        if (searchTree.IsLeafNode()) {
83          var allowedChildSymbols = g.GetAllowedChildSymbols(parent.Symbol, childIdx)
84            .Where(a => a.Enabled)
[12955]85            .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen)
86            .OrderBy(a => a.MaximumArity); // terminals should be tried first
[12909]87
[12923]88          searchTree.ExpandCurrentNode(allowedChildSymbols);
[12909]89        }
90
[12923]91        if (!searchTree.ChildValues.Any()) {
[12909]92          throw new InvalidProgramException(string.Format("Couldn't construct a valid tree of maximum length {0} or all possible trees have been visited", maxLen));
93        }
94
[12923]95        var alternatives = searchTree.ChildValues.ToArray(); // TODO perf
[12909]96
[12923]97        // generate follow states
98        var followStates = new object[alternatives.Length];
99        for (int i = 0; i < followStates.Length; i++) {
100          // temporarily make the replacement and create the followState object
101          var childNode = alternatives[i].CreateTreeNode();
102          if (childNode.HasLocalParameters) {
103            throw new NotSupportedException("Symbols with parameters are not supported by construction policies for symbolic expressions. " +
104                                            "Try to reformulate the problem so that only discrete actions are necessary");
105            // childNode.ResetLocalParameters(Random);
106          }
107          parent.AddSubtree(childNode);
108          actions.Add(alternatives[i]);
109
110          // states might be defined differently be different policies
111          // this allows policies to calculate the state as a function of the current tree and the position where it is changed,
112          // or as a function of the list of actions so far,
113          // or as a function of both
114          followStates[i] = CreateState(root, actions, parent, childIdx);
115
116          // roll back the change
117          parent.RemoveSubtree(parent.SubtreeCount - 1);
118          actions.RemoveAt(actions.Count - 1);
[12922]119        }
[12909]120
[12923]121        // select one of the follow states and prepare for the next step
122        var selectedIdx = Select(followStates, Random);
123        actions.Add(alternatives[selectedIdx]);
124        states.Add(followStates[selectedIdx]);
[12909]125
[12923]126        {
127          // and add child node to parent
128          var childNode = alternatives[selectedIdx].CreateTreeNode();
129
130          Contract.Assert(parent.SubtreeCount == childIdx); // enforce left-canonical derivation
131          parent.AddSubtree(childNode);
132          treeSize++;
133
134          // push new slots
[12955]135          for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) -1 ; chIdx >= 0; chIdx--) {
[12923]136            int minForChild = g.GetAllowedChildSymbols(childNode.Symbol, chIdx)
137              .Min(a => g.GetMinimumExpressionLength(a)); // min length of all possible alts for the slot
[12955]138            openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild });
[12923]139          }
[12909]140        }
141
142        // if this is the last slot we never have to revisit selectedIdx
143        if (!openSlots.Any()) {
[12923]144          searchTree.RemoveBranch(alternatives[selectedIdx]);
[12909]145        } else {
[12923]146          searchTree.Follow(alternatives[selectedIdx]);
[12909]147        }
148      }
149
[12923]150      stateSequence = states;
[12909]151      return new SymbolicExpressionTree(root);
152    }
153
[12923]154    /// <summary>
155    /// Choose one of the follow states
156    /// </summary>
157    /// <param name="followStates"></param>
158    /// <param name="random"></param>
159    /// <returns>The index of the selected follow state</returns>
160    protected abstract int Select(IReadOnlyList<object> followStates, IRandom random);
161    public abstract void Update(IEnumerable<object> stateSequence, double quality);
[12909]162
[12955]163    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx);
[12909]164  }
165}
Note: See TracBrowser for help on using the repository browser.