Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/28/15 17:50:53 (9 years ago)
Author:
gkronber
Message:

#2471

  • implemented a demo for value approximation with gbt and a trivial feature function
Location:
branches/HeuristicLab.Algorithms.IteratedSentenceConstruction
Files:
1 added
11 edited

Legend:

Unmodified
Added
Removed

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

    r12923 r12924  
    9999  </PropertyGroup>
    100100  <ItemGroup>
     101    <Reference Include="HeuristicLab.Algorithms.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     102      <SpecificVersion>False</SpecificVersion>
     103      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Algorithms.DataAnalysis-3.4.dll</HintPath>
     104    </Reference>
    101105    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    102106      <SpecificVersion>False</SpecificVersion>
    … …  
    142146      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
    143147      <Private>False</Private>
     148    </Reference>
     149    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     150      <SpecificVersion>False</SpecificVersion>
     151      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis-3.4.dll</HintPath>
    144152    </Reference>
    145153    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    … …  
    169177    </Compile>
    170178    <Compile Include="Properties\AssemblyInfo.cs" />
     179    <Compile Include="QualityFunctions\GbtApproximateStateValueFunction.cs" />
    171180    <Compile Include="QualityFunctions\TabularStateValueFunctionBase.cs" />
    172181    <Compile Include="QualityFunctions\TabularAvgStateValueFunction.cs" />
    … …  
    198207    </BootstrapperPackage>
    199208  </ItemGroup>
    200   <ItemGroup />
     209  <ItemGroup>
     210    <Folder Include="FeatureFunctions\" />
     211  </ItemGroup>
    201212  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    202213  <!-- To modify your build process, add your task inside one of the targets below and uncomment it.

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateValueFunction.cs

    r12923 r12924  
    88namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
    99  // represents the state value function (V(s))
    10   public interface IStateValueFunction : IStatefulItem {
     10  public interface IStateValueFunction : IItem {
    1111    double Value(object state);
    1212    void Update(object state, double observedQuality);

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

    r12923 r12924  
    4545      var idxs = Enumerable.Range(0, followStates.Count);
    4646      // find best action
    47       var bestQuality = double.NegativeInfinity;
    4847      if (followStates.Any(s => StateValueFunction.Tries(s) == 0)) {
    4948        return idxs.Where(idx => StateValueFunction.Tries(followStates[idx]) == 0).SampleRandom(random);

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

    r12923 r12924  
    2323
    2424    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
    25 
    2625      // ignore
    2726    }

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgStateValueFunction.cs

    r12923 r12924  
    99  [StorableClass]
    1010  [Item("TabularAvgQualityFunction", "")]
    11   internal class TabularAvgStateValueFunction : TabularStateValueFunctionBase {
     11  public class TabularAvgStateValueFunction : TabularStateValueFunctionBase {
    1212
    1313    public TabularAvgStateValueFunction()

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxStateValueFunction.cs

    r12923 r12924  
    99  [StorableClass]
    1010  [Item("TabularMaxStateValueFunction", "")]
    11   internal class TabularMaxStateValueFunction : TabularStateValueFunctionBase {
     11  public class TabularMaxStateValueFunction : TabularStateValueFunctionBase {
    1212
    1313    public TabularMaxStateValueFunction()

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

    r12923 r12924  
    88namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
    99  [StorableClass]
    10   internal abstract class TabularStateValueFunctionBase : ParameterizedNamedItem, ITabularStateValueFunction {
     10  public abstract class TabularStateValueFunctionBase : ParameterizedNamedItem, ITabularStateValueFunction {
    1111    [Storable]
    1212    private readonly Dictionary<object, double> q = new Dictionary<object, double>();
    … …  
    7878    #endregion
    7979
    80     public void InitializeState() {
    81       ClearState();
    82     }
    83 
    84     public void ClearState() {
    85       q.Clear();
    86       tries.Clear();
    87       qVariance.Clear();
    88     }
     80    //public void InitializeState() {
     81    //  ClearState();
     82    //}
     83    //
     84    //public void ClearState() {
     85    //  q.Clear();
     86    //  tries.Clear();
     87    //  qVariance.Clear();
     88    //}
    8989  }
    9090}

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs

    r12923 r12924  
    88namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
    99  internal class SearchTree<TValue> {
    10     private class Node<TValue> {
     10    private class Node {
    1111      internal TValue value;
    12       internal Node<TValue> parent;
    13       internal Node<TValue>[] children;
     12      internal Node parent;
     13      internal Node[] children;
    1414      // children == null -> never visited
    1515      // children[i] != null -> visited at least once, still allowed
    … …  
    1717    }
    1818
    19     private Node<TValue> root;
     19    private Node root;
    2020
    2121    // for iteration
    22     private Node<TValue> currentNode;
     22    private Node currentNode;
    2323
    2424    public SearchTree() {
    25       root = new Node<TValue>();
     25      root = new Node();
    2626      currentNode = root;
    2727    }
    … …  
    3838      Contract.Assert(values.Any());
    3939      Contract.Assert(currentNode.children == null);
    40       currentNode.children = values.Select(val => new Node<TValue>() { value = val, parent = currentNode }).ToArray();
     40      currentNode.children = values.Select(val => new Node() { value = val, parent = currentNode }).ToArray();
    4141    }
    4242
    … …  
    7171    }
    7272
    73     private void RemoveRecursively(Node<TValue> node) {
     73    private void RemoveRecursively(Node node) {
    7474      // when the last child has been removed we must remove the current node from it's parent
    7575      while (node.parent != null && node.children.All(ch => ch == null)) {

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/DefaultStateFunction.cs

    r12923 r12924  
    1313  [StorableClass]
    1414  [Item("DefaultStateFunction", "")]
    15   internal class DefaultStateFunction : Item, IStateFunction {
     15  public class DefaultStateFunction : Item, IStateFunction {
    1616    public DefaultStateFunction()
    1717      : base() {
    … …  
    1919
    2020    public object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parentNode, int childIdx) {
    21       return string.Join(",", actions.Select(a => a.Name));
     21      return string.Join(",", actions.Select(a => a.Name)); // TODO: perf
    2222    }
    2323

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/ParentChildStateFunction.cs

    r12923 r12924  
    1414  [StorableClass]
    1515  [Item("ParentChildStateFunction", "")]
    16   internal class ParentChildStateFunction : Item, IStateFunction {
     16  public class ParentChildStateFunction : Item, IStateFunction {
    1717    public ParentChildStateFunction()
    1818      : base() {
    … …  
    2020
    2121    public object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parentNode, int childIdx) {
    22       return (parentNode == null ? "" : parentNode.Symbol.Name) + childIdx;
     22      if (parentNode == null) return string.Empty;
     23      else return parentNode.Symbol.Name + "." + string.Join(".", parentNode.Subtrees.Select(t => t.Symbol.Name));
    2324    }
    2425

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/Tests/IteratedSymbolicExpressionConstructionTest.cs

    r12923 r12924  
    1212
    1313      // see Langdon and Poli, "Why Ants are Hard", Table 2 (http://marvin.cs.uidaho.edu/Teaching/CS472/santaFeTrailSpace.pdf)
    14       TestAlg(problem: new Problem(), maxLen: 3, expectedEvals: 3, expectedBestQuality: 3);
    15       TestAlg(problem: new Problem(), maxLen: 4, expectedEvals: 3, expectedBestQuality: 3);
    16       TestAlg(problem: new Problem(), maxLen: 5, expectedEvals: 21, expectedBestQuality: 11);
    17       TestAlg(problem: new Problem(), maxLen: 6, expectedEvals: 48, expectedBestQuality: 11);
    18       TestAlg(problem: new Problem(), maxLen: 10, expectedEvals: 25455, expectedBestQuality: 47);
    19       TestAlg(problem: new Problem(), maxLen: 13, expectedEvals: 3191259, expectedBestQuality: 89);
     14      TestAlg(problem: new Problem(), policy: new RandomSymbolicExpressionConstructionPolicy(), maxLen: 3, expectedEvals: 3, expectedBestQuality: 3);
     15      TestAlg(problem: new Problem(), policy: new RandomSymbolicExpressionConstructionPolicy(), maxLen: 4, expectedEvals: 3, expectedBestQuality: 3);
     16      TestAlg(problem: new Problem(), policy: new RandomSymbolicExpressionConstructionPolicy(), maxLen: 5, expectedEvals: 21, expectedBestQuality: 11);
     17      TestAlg(problem: new Problem(), policy: new RandomSymbolicExpressionConstructionPolicy(), maxLen: 6, expectedEvals: 48, expectedBestQuality: 11);
     18      TestAlg(problem: new Problem(), policy: new RandomSymbolicExpressionConstructionPolicy(), maxLen: 10, expectedEvals: 25455, expectedBestQuality: 47);
     19      TestAlg(problem: new Problem(), policy: new RandomSymbolicExpressionConstructionPolicy(), maxLen: 13, expectedEvals: 3191259, expectedBestQuality: 89);
    2020
    2121      // log of runtimes (28.08.2015), single core, Intel Core i5 @3.2 GHz
    … …  
    2929    }
    3030
    31     private void TestAlg(Problem problem, int maxLen, int expectedEvals, double expectedBestQuality) {
     31    [TestMethod]
     32    public void TestStateAggregation() {
     33      var stateValueFunction = new TabularMaxStateValueFunction();
     34      stateValueFunction.StateFunction = new ParentChildStateFunction();
     35      var pol = new UcbSymbolicExpressionConstructionPolicy();
     36      pol.StateValueFunction = stateValueFunction;
     37      TestAlg(new Problem(), pol, maxLen: 13, expectedEvals: 3191259, expectedBestQuality: 89);
     38    }
     39
     40    [TestMethod]
     41    public void TestStateValueApproximation() {
     42      var stateValueFunction = new GbtApproximateStateValueFunction();
     43      var pol = new EpsGreedySymbolicExpressionConstructionPolicy();
     44      pol.StateValueFunction = stateValueFunction;     
     45      TestAlg(new Problem(), pol, maxLen: 13, expectedEvals: 3191259, expectedBestQuality: 89);
     46    }
     47
     48    private void TestAlg(Problem problem, ISymbolicExpressionConstructionPolicy policy, int maxLen, int expectedEvals, double expectedBestQuality) {
    3249      var alg = new IteratedSymbolicExpressionConstruction();
    3350      problem.Encoding.TreeLength = maxLen;
    3451      alg.Problem = problem;
    35       alg.PolicyParameter.Value = new RandomSymbolicExpressionConstructionPolicy();
     52      alg.PolicyParameter.Value = policy;
    3653      alg.MaximumEvaluations = 5000000;
    3754
Note: See TracChangeset for help on using the changeset viewer.