Free cookie consent management tool by TermsFeed Policy Generator

Changeset 12922


Ignore:
Timestamp:
08/27/15 16:55:07 (9 years ago)
Author:
gkronber
Message:

#2471

  • added a simple implementation of Koza-style symbolic regression
  • added ucb tuned and estimation of variance to tabular quality functions
Location:
branches/HeuristicLab.Algorithms.IteratedSentenceConstruction
Files:
4 added
11 edited

Legend:

Unmodified
Added
Removed

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

    r12909 r12922  
    161161    <Compile Include="Plugin.cs" />
    162162    <Compile Include="Policies\BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs" />
     163    <Compile Include="Policies\UcbTunedSymbolicExpressionConstructionPolicy.cs" />
    163164    <Compile Include="Policies\EpsGreedySymbolicExpressionConstructionPolicy.cs" />
    164165    <Compile Include="Policies\SymbolicExpressionConstructionPolicyBase.cs" />
    … …  
    168169    </Compile>
    169170    <Compile Include="Properties\AssemblyInfo.cs" />
     171    <Compile Include="QualityFunctions\TabularQualityFunctionBase.cs" />
    170172    <Compile Include="QualityFunctions\TabularAvgQualityFunction.cs" />
    171173    <Compile Include="QualityFunctions\TabularMaxQualityFunction.cs" />

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

    r12909 r12922  
    99  // represents quality functions that use a table representation for states & actions and can therefore return the number of tries for each state/action pair
    1010  public interface ITabularQualityFunction : IQualityFunction {
     11    double QVariance(object state, int action); // estimate for the variance of observed rewards
    1112    int Tries(object state, int action);
    1213  }

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

    r12909 r12922  
    4646
    4747    protected SymbolicExpressionConstructionPolicyBase() {
     48
    4849    }
    4950
    … …  
    106107        // and add child node to parent
    107108        var childNode = alts[selectedIdx].CreateTreeNode();
    108         if (childNode.HasLocalParameters) childNode.ResetLocalParameters(Random);
     109        if (childNode.HasLocalParameters) {
     110          throw new NotSupportedException("Symbols with parameters are not supported by construction policies for symbolic expressions. Try to reformulate the problem so that only discrete actions are necessary");
     111          // childNode.ResetLocalParameters(Random);
     112        }
    109113
    110114        Contract.Assert(parent.SubtreeCount == childIdx);
    … …  
    113117
    114118        // push new slots
    115         for (int chIdx = childNode.Symbol.MinimumArity - 1; chIdx >= 0; chIdx--) {
     119        for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) - 1; chIdx >= 0; chIdx--) {
    116120          int minForChild = g.GetAllowedChildSymbols(childNode.Symbol, chIdx).Min(a => g.GetMinimumExpressionLength(a)); // min length of all possible alts for the slot
    117121          openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild });

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

    r12909 r12922  
    99  [StorableClass]
    1010  [Item("TabularAvgQualityFunction", "")]
    11   internal class TabularAvgQualityFunction : ParameterizedNamedItem, ITabularQualityFunction {
    12     [Storable]
    13     private readonly Dictionary<object, Dictionary<int, double>> q = new Dictionary<object, Dictionary<int, double>>();
    14     [Storable]
    15     private readonly Dictionary<object, Dictionary<int, int>> tries = new Dictionary<object, Dictionary<int, int>>();
     11  internal class TabularAvgQualityFunction : TabularQualityFunctionBase {
    1612
    17     public IStateFunction StateFunction {
    18       get {
    19         return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
    20       }
    21       set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
    22     }
    23 
    24     public TabularAvgQualityFunction() {
    25       Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
    26     }
    27 
    28     public double Q(object state, int action) {
    29       // an action that has never been tried has q == infinity
    30       Dictionary<int, double> stateActionQualities;
    31       if (!q.TryGetValue(state, out stateActionQualities)) return double.PositiveInfinity;
    32       double quality;
    33       if (!stateActionQualities.TryGetValue(action, out quality)) return double.PositiveInfinity;
    34       return quality;
    35     }
    36 
    37     public void Update(object state, int action, double observedQuality) {
    38       Dictionary<int, int> stateActionTries;
    39       if (!tries.TryGetValue(state, out stateActionTries)) {
    40         stateActionTries = new Dictionary<int, int>();
    41         tries.Add(state, stateActionTries);
    42       }
    43       Dictionary<int, double> stateActionQualities = null;
    44       if (!q.TryGetValue(state, out stateActionQualities)) {
    45         stateActionQualities = new Dictionary<int, double>();
    46         q.Add(state, stateActionQualities);
    47       }
    48       int t;
    49       if (!stateActionTries.TryGetValue(action, out t)) {
    50         t = 0;
    51         stateActionTries.Add(action, t + 1);
    52         stateActionQualities.Add(action, observedQuality);
    53       } else {
    54         stateActionTries[action] = t + 1;
    55         var delta = observedQuality - stateActionQualities[action];
    56         stateActionQualities[action] = stateActionQualities[action] + (1.0 / (t + 1)) * delta; // incremental calculation of average
    57       }
    58     }
    59 
    60     public int Tries(object state, int action) {
    61       Dictionary<int, int> stateTries;
    62       if (!tries.TryGetValue(state, out stateTries)) return 0;
    63       int stateActionTries;
    64       if (!stateTries.TryGetValue(action, out stateActionTries)) return 0;
    65       return stateActionTries;
     13    public TabularAvgQualityFunction()
     14      : base() {
    6615    }
    6716
    … …  
    7120    protected TabularAvgQualityFunction(TabularAvgQualityFunction original, Cloner cloner)
    7221      : base(original, cloner) {
    73       this.q = new Dictionary<object, Dictionary<int, double>>(original.q);
    74       this.tries = new Dictionary<object, Dictionary<int, int>>(original.tries);
    7522    }
    7623    public override IDeepCloneable Clone(Cloner cloner) {
    … …  
    7926    #endregion
    8027
    81     public void InitializeState() {
    82       ClearState();
    83     }
    84 
    85     public void ClearState() {
    86       q.Clear();
    87       tries.Clear();
     28    protected override double CalculateNewQ(object state, int action, double observedQuality) {
     29      var delta = observedQuality - Q(state, action);
     30      return Q(state, action) + (1.0 / Tries(state, action)) * delta; // iterative calculation of mean
    8831    }
    8932  }

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

    r12909 r12922  
    99  [StorableClass]
    1010  [Item("TabularMaxQualityFunction", "")]
    11   internal class TabularMaxQualityFunction : ParameterizedNamedItem, ITabularQualityFunction {
    12     [Storable]
    13     private readonly Dictionary<object, Dictionary<int, double>> q = new Dictionary<object, Dictionary<int, double>>();
    14     [Storable]
    15     private readonly Dictionary<object, Dictionary<int, int>> tries = new Dictionary<object, Dictionary<int, int>>();
     11  internal class TabularMaxQualityFunction : TabularQualityFunctionBase {
    1612
    17     public IStateFunction StateFunction {
    18       get {
    19         return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
    20       }
    21       set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
    22     }
    23 
    24     public TabularMaxQualityFunction() {
    25       Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
    26     }
    27 
    28     public double Q(object state, int action) {
    29       // an action that has never been tried has q == infinity
    30       Dictionary<int, double> stateActionQualities;
    31       if (!q.TryGetValue(state, out stateActionQualities)) return double.PositiveInfinity;
    32       double quality;
    33       if (!stateActionQualities.TryGetValue(action, out quality)) return double.PositiveInfinity;
    34       return quality;
    35     }
    36 
    37     public void Update(object state, int action, double observedQuality) {
    38       Dictionary<int, int> stateActionTries;
    39       if (!tries.TryGetValue(state, out stateActionTries)) {
    40         stateActionTries = new Dictionary<int, int>();
    41         tries.Add(state, stateActionTries);
    42       }
    43       Dictionary<int, double> stateActionQualities = null;
    44       if (!q.TryGetValue(state, out stateActionQualities)) {
    45         stateActionQualities = new Dictionary<int, double>();
    46         q.Add(state, stateActionQualities);
    47       }
    48       int t;
    49       if (!stateActionTries.TryGetValue(action, out t)) {
    50         t = 0;
    51         stateActionTries.Add(action, t + 1);
    52         stateActionQualities.Add(action, observedQuality);
    53       } else {
    54         stateActionTries[action] = t + 1;
    55         stateActionQualities[action] = Math.Max(stateActionQualities[action], observedQuality);
    56       }
    57     }
    58 
    59     public int Tries(object state, int action) {
    60       Dictionary<int, int> stateTries;
    61       if (!tries.TryGetValue(state, out stateTries)) return 0;
    62       int stateActionTries;
    63       if (!stateTries.TryGetValue(action, out stateActionTries)) return 0;
    64       return stateActionTries;
     13    public TabularMaxQualityFunction()
     14      : base() {
    6515    }
    6616
    … …  
    7020    protected TabularMaxQualityFunction(TabularMaxQualityFunction original, Cloner cloner)
    7121      : base(original, cloner) {
    72       this.q = new Dictionary<object, Dictionary<int, double>>(original.q);
    73       this.tries = new Dictionary<object, Dictionary<int, int>>(original.tries);
    7422    }
    7523    public override IDeepCloneable Clone(Cloner cloner) {
    … …  
    7826    #endregion
    7927
    80     public void InitializeState() {
    81       ClearState();
    82     }
    83 
    84     public void ClearState() {
    85       q.Clear();
    86       tries.Clear();
     28    protected override double CalculateNewQ(object state, int action, double observedQuality) {
     29      return Math.Max(Q(state, action), observedQuality);
    8730    }
    8831  }

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

    r12909 r12922  
    6262
    6363    private void RemoveRecursively(Node node) {
    64       if (node == null) return;
    6564      // when the last child has been removed we must remove the current node from it's parent
    66       if (node.children.All(ch => ch == null) && node.parent != null) {
     65      while (node.parent != null && node.children.All(ch => ch == null)) {
    6766        node.parent.children[Array.IndexOf(node.parent.children, node)] = null;
    68         RemoveRecursively(node.parent);
     67        node = node.parent;
    6968      }
    7069    }

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Problems.GeneticProgramming.Views/3.3

    • Property svn:ignore set to
      obj
      Plugin.cs

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Problems.GeneticProgramming.Views/3.3/Properties

    • Property svn:ignore set to
      AssemblyInfo.cs

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Problems.GeneticProgramming/3.3

    • Property svn:ignore set to
      obj
      Plugin.cs

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Problems.GeneticProgramming/3.3/HeuristicLab.Problems.GeneticProgramming-3.3.csproj

    r12919 r12922  
    141141      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
    142142    </Reference>
     143    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     144      <SpecificVersion>False</SpecificVersion>
     145      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis-3.4.dll</HintPath>
     146    </Reference>
     147    <Reference Include="HeuristicLab.Problems.Instances-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     148      <SpecificVersion>False</SpecificVersion>
     149      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
     150    </Reference>
    143151    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    144152      <SpecificVersion>False</SpecificVersion>
    … …  
    155163    <Compile Include="ArtificialAnt\Problem.cs" />
    156164    <Compile Include="ArtificialAnt\Trail.cs" />
     165    <Compile Include="BasicSymbolicRegression\Problem.cs" />
    157166    <Compile Include="LawnMower\Interpreter.cs" />
    158167    <Compile Include="LawnMower\Problem.cs" />

  • branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Problems.GeneticProgramming/3.3/Properties

    • Property svn:ignore set to
      AssemblyInfo.cs
Note: See TracChangeset for help on using the changeset viewer.