Changeset 12955 for branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies

Timestamp:

09/17/15 17:35:45 (9 years ago)

Author:

gkronber

Message:

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

Location:

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction

Files:

• . (modified) (1 prop)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BreathFirstSymbolicExpressionConstructionPolicy.cs (added)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/DepthFirstSymbolicExpressionConstructionPolicy.cs (added)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/EpsGreedySymbolicExpressionConstructionPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/RandomSymbolicExpressionConstructionPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbSymbolicExpressionConstructionPolicy.cs (modified) (1 diff)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs (modified) (1 diff)

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction

@@ -1 +1 @@
 bin
+TestResults

@@ -1 +1 @@
 bin
+TestResults

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs

@@ -68 +68 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
     }
 

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/EpsGreedySymbolicExpressionConstructionPolicy.cs

@@ -62 +62 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
     }
 

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/RandomSymbolicExpressionConstructionPolicy.cs

@@ -26 +26 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
       return null; // doesn't use state information
     }

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs

@@ -62 +62 @@
       var g = Problem.Encoding.Grammar;
       var root = g.ProgramRootSymbol.CreateTreeNode();
-      int maxDepth = Problem.Encoding.TreeDepthParameter.Value.Value;
+      int maxDepth = Problem.Encoding.TreeDepthParameter.Value.Value; // ignored
       int maxLen = Problem.Encoding.TreeLengthParameter.Value.Value;
 
@@ -75 +75 @@
 
       while (openSlots.Any()) {
-        var next = openSlots.Pop();
+        var next = openSlots.First();
+        openSlots.Pop();
         var parent = next.parent;
         var childIdx = next.childIdx;
@@ -82 +83 @@
           var allowedChildSymbols = g.GetAllowedChildSymbols(parent.Symbol, childIdx)
             .Where(a => a.Enabled)
-            .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen);
+            .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen)
+            .OrderBy(a => a.MaximumArity); // terminals should be tried first
 
           searchTree.ExpandCurrentNode(allowedChildSymbols);
@@ -131 +133 @@
 
           // push new slots 
-          for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) - 1; chIdx >= 0; chIdx--) {
+          for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) -1 ; chIdx >= 0; chIdx--) {
             int minForChild = g.GetAllowedChildSymbols(childNode.Symbol, chIdx)
               .Min(a => g.GetMinimumExpressionLength(a)); // min length of all possible alts for the slot
-            openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild });
+            openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild }); 
           }
         }
@@ -159 +161 @@
     public abstract void Update(IEnumerable<object> stateSequence, double quality);
 
-    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx);
+    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx);
   }
 }

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbSymbolicExpressionConstructionPolicy.cs

@@ -71 +71 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
     }
 

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs

@@ -72 +72 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
     }
 

@@ -1 +1 @@
 bin
+TestResults