Context Navigation

← Previous Changeset
Next Changeset →

Changeset 12955

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:

: 2 added
: 11 edited

Legend:

: Unmodified
: Added
: Removed

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction

Property svn:ignore

old	new
1	1	bin
	2	TestResults

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

r12924	r12955
169	169	<Compile Include="Plugin.cs" />
170	170	<Compile Include="Policies\BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs" />
	171	<Compile Include="Policies\DepthFirstSymbolicExpressionConstructionPolicy.cs" />
	172	<Compile Include="Policies\BreathFirstSymbolicExpressionConstructionPolicy.cs" />
171	173	<Compile Include="Policies\UcbTunedSymbolicExpressionConstructionPolicy.cs" />
172	174	<Compile Include="Policies\EpsGreedySymbolicExpressionConstructionPolicy.cs" />

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

r12924	r12955
68	68	}
69	69
70		protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
71		return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
	70	protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
	71	return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
72	72	}
73	73

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

r12923	r12955
62	62	}
63	63
64		protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
65		return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
	64	protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
	65	return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
66	66	}
67	67

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

r12924	r12955
26	26	}
27	27
28		protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
	28	protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
29	29	return null; // doesn't use state information
30	30	}

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

-                      r12923
+                      r12955
       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;
 …
       while (openSlots.Any()) {
+        var next = openSlots.Pop();
+        var next = openSlots.First();
+        openSlots.Pop();
         var parent = next.parent;
         var childIdx = next.childIdx;
 …
           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);
 …
           // 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 });
+          }
+        }
 …
     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

r12923	r12955
71	71	}
72	72
73		protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
74		return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
	73	protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
	74	return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
75	75	}
76	76

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

r12923	r12955
72	72	}
73	73
74		protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
75		return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
	74	protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
	75	return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
76	76	}
77	77

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

r12924	r12955
1	1	using System;
2	2	using System.Collections.Generic;
3		~~using System.Collections.Specialized;~~
4	3	using System.Linq;
5		~~using System.Runtime.InteropServices.WindowsRuntime;~~
6	4	using HeuristicLab.Algorithms.DataAnalysis;
7	5	using HeuristicLab.Common;
…	…
167	165
168	166	public void ClearState() {
169
170	167	}
171
172	168	}
173
174
175	169	}

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

r12924	r12955
72	72	protected TabularStateValueFunctionBase(TabularStateValueFunctionBase original, Cloner cloner)
73	73	: base(original, cloner) {
	74	// 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)
	75
74	76	this.q = new Dictionary<object, double>(original.q);
75	77	this.tries = new Dictionary<object, int>(original.tries);

branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/Tests
- Property svn:ignore set to
  bin
  obj

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 12955

Legend:

Download in other formats: