Changeset 12955 for branches/HeuristicLab.Algorithms.IteratedSentenceConstruction

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/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj (modified) (1 diff)
• 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)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/GbtApproximateStateValueFunction.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularStateValueFunctionBase.cs (modified) (1 diff)
• Tests (modified) (1 prop)

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction

@@ -1 +1 @@
 bin
+TestResults

@@ -1 +1 @@
 bin
+TestResults

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj

@@ -169 +169 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Policies\BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs" />
+    <Compile Include="Policies\DepthFirstSymbolicExpressionConstructionPolicy.cs" />
+    <Compile Include="Policies\BreathFirstSymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="Policies\UcbTunedSymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="Policies\EpsGreedySymbolicExpressionConstructionPolicy.cs" />

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);
     }
 

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/GbtApproximateStateValueFunction.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
-using System.Collections.Specialized;
 using System.Linq;
-using System.Runtime.InteropServices.WindowsRuntime;
 using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Common;
@@ -167 +165 @@
 
     public void ClearState() {
-
     }
-
   }
-
-
 }

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularStateValueFunctionBase.cs

@@ -72 +72 @@
     protected TabularStateValueFunctionBase(TabularStateValueFunctionBase original, Cloner cloner)
       : base(original, cloner) {
+      // TODO: these become really large when using this class only from BasicAlgorithms it would not be necessary to clone and reset everything, (pause is not allowed)
+
       this.q = new Dictionary<object, double>(original.q);
       this.tries = new Dictionary<object, int>(original.tries);

@@ -1 +1 @@
 bin
+TestResults