Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/16/12 16:28:49 (13 years ago)
Author:
gkronber
Message:

merged r7609:7840 from trunk into time series branch

Location:
branches/HeuristicLab.TimeSeries
Files:
12 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.TimeSeries

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

    • Property svn:mergeinfo set to (toggle deleted branches)
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.SymbolicExpressionTreeEncodingmergedeligible
      /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncodingmergedeligible
      /branches/Benchmarking/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6917-7005
      /branches/CloningRefactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding4656-4721
      /branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5471-5808
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5815-6180
      /branches/DataAnalysis/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding4458-4459,​4462,​4464
      /branches/GP.Grammar.Editor/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6284-6795
      /branches/HeuristicLab.Crossovers/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding7343-7503
      /branches/NET40/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5138-5162
      /branches/ParallelEngine/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5175-5192
      /branches/ProblemInstancesRegressionAndClassification/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding7568-7810
      /branches/QAPAlgorithms/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6828
      /branches/SuccessProgressAnalysis/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5370-5682
      /branches/Trunk/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6829-6865
      /branches/VNS/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5594-5752
      /branches/histogram/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5959-6341

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Analyzers/SymbolicExpressionTreeLengthAnalyzer.cs

    r7460 r7842  
    153153        // if the table was not created yet, we create it here
    154154        if (treeLengthsTable == null) {
    155           treeLengthsTable = new DataTable("Histogram");
     155          treeLengthsTable = new DataTable("Tree Length Histogram");
    156156          SymbolicExpressionTreeLengthsParameter.ActualValue = treeLengthsTable;
    157157        }

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTree.cs

    r7268 r7842  
    2929    int Depth { get; }
    3030
     31    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth();
    3132    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix();
    3233    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNode.cs

    r7615 r7842  
    3434    int GetBranchLevel(ISymbolicExpressionTreeNode child);
    3535
     36    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth();
    3637    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();
    3738    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix();

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs

    r7268 r7842  
    2424using HeuristicLab.Core;
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using System.Collections.Generic;
    2627
    2728namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    2930  [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]
    3031  public sealed class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator {
     32    private const int MAX_TRIES = 100;
     33
    3134    [StorableConstructor]
    3235    private ChangeNodeTypeManipulation(bool deserializing) : base(deserializing) { }
    … …  
    4346
    4447    public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
    45       // select any node as parent (except the root node)
    46       var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
    47                                 let subtreeCount = parent.Subtrees.Count()
    48                                 from subtreeIndex in Enumerable.Range(0, subtreeCount)
    49                                 let subtree = parent.GetSubtree(subtreeIndex)
    50                                 let existingSubtreeCount = subtree.Subtrees.Count()
    51                                 // find possible symbols for the node (also considering the existing branches below it)
    52                                 let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
    53                                                       // do not replace the existing symbol with itself
    54                                                       where symbol.Name != subtree.Symbol.Name
    55                                                       where symbol.InitialFrequency > 0
    56                                                       where existingSubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(symbol)
    57                                                       where existingSubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(symbol)
    58                                                       // keep only symbols that are still possible considering the existing sub-trees
    59                                                       where (from existingSubtreeIndex in Enumerable.Range(0, existingSubtreeCount)
    60                                                              let existingSubtree = subtree.GetSubtree(existingSubtreeIndex)
    61                                                              select parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex))
    62                                                              .All(x => x == true)
    63                                                       select symbol)
    64                                                       .ToList()
    65                                 where allowedSymbols.Count() > 0
    66                                 select new { Parent = parent, Child = subtree, Index = subtreeIndex, AllowedSymbols = allowedSymbols })
    67                                .ToList();
    68       if (manipulationPoints.Count == 0) { return; }
    69       var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
     48      List<ISymbol> allowedSymbols = new List<ISymbol>();
     49      ISymbolicExpressionTreeNode parent;
     50      int childIndex;
     51      ISymbolicExpressionTreeNode child;
     52      // repeat until a fitting parent and child are found (MAX_TRIES times)
     53      int tries = 0;
     54      do {
     55        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
     56        childIndex = random.Next(parent.SubtreeCount);
    7057
    71       var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
    72       var newSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
     58        child = parent.GetSubtree(childIndex);
     59        int existingSubtreeCount = child.SubtreeCount;
     60        allowedSymbols.Clear();
     61        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
     62          // check basic properties that the new symbol must have
     63          if (symbol.Name != child.Symbol.Name &&
     64            symbol.InitialFrequency > 0 &&
     65            existingSubtreeCount <= parent.Grammar.GetMinimumSubtreeCount(symbol) &&
     66            existingSubtreeCount >= parent.Grammar.GetMaximumSubtreeCount(symbol)) {
     67            // check that all existing subtrees are also allowed for the new symbol
     68            bool allExistingSubtreesAllowed = true;
     69            for (int existingSubtreeIndex = 0; existingSubtreeIndex < existingSubtreeCount && allExistingSubtreesAllowed; existingSubtreeIndex++) {
     70              var existingSubtree = child.GetSubtree(existingSubtreeIndex);
     71              allExistingSubtreesAllowed &= parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex);
     72            }
     73            if (allExistingSubtreesAllowed) {
     74              allowedSymbols.Add(symbol);
     75            }
     76          }
     77        }
     78        tries++;
     79      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
    7380
    74       // replace the old node with the new node
    75       var newNode = newSymbol.CreateTreeNode();
    76       if (newNode.HasLocalParameters)
    77         newNode.ResetLocalParameters(random);
    78       foreach (var subtree in selectedManipulationPoint.Child.Subtrees)
    79         newNode.AddSubtree(subtree);
    80       selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
    81       selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, newNode);
     81      if (tries < MAX_TRIES) {
     82        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
     83        var newSymbol = allowedSymbols.SelectRandom(weights, random);
     84
     85        // replace the old node with the new node
     86        var newNode = newSymbol.CreateTreeNode();
     87        if (newNode.HasLocalParameters)
     88          newNode.ResetLocalParameters(random);
     89        foreach (var subtree in child.Subtrees)
     90          newNode.AddSubtree(subtree);
     91        parent.RemoveSubtree(childIndex);
     92        parent.InsertSubtree(childIndex, newNode);
     93      }
    8294    }
    8395  }

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ReplaceBranchManipulation.cs

    r7268 r7842  
    2626using HeuristicLab.Parameters;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using System.Collections.Generic;
    2829
    2930namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    3132  [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
    3233  public sealed class ReplaceBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
     34    private const int MAX_TRIES = 100;
    3335    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
    3436    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
    … …  
    6870
    6971    public static void ReplaceRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
    70       // select any node as parent (except the root node)
    71       var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
    72                                 from subtree in parent.Subtrees
    73                                 let subtreeIndex = parent.IndexOfSubtree(subtree)
    74                                 let maxLength = maxTreeLength - symbolicExpressionTree.Length + subtree.GetLength()
    75                                 let maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + subtree.GetDepth()
    76                                 // find possible symbols for the node (also considering the existing branches below it)
    77                                 let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
    78                                                       // do not replace symbol with the same symbol
    79                                                       where symbol.Name != subtree.Symbol.Name
    80                                                       where symbol.InitialFrequency > 0
    81                                                       where parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth
    82                                                       where parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength
    83                                                       select symbol)
    84                                                       .ToList()
    85                                 where allowedSymbols.Count > 0
    86                                 select new {
    87                                   Parent = parent,
    88                                   Child = subtree,
    89                                   Index = subtreeIndex,
    90                                   AllowedSymbols = allowedSymbols,
    91                                   MaxLength = maxLength,
    92                                   MaxDepth = maxDepth
    93                                 })
    94                                .ToList();
     72      var allowedSymbols = new List<ISymbol>();
     73      ISymbolicExpressionTreeNode parent;
     74      int childIndex;
     75      int maxLength;
     76      int maxDepth;
     77      // repeat until a fitting parent and child are found (MAX_TRIES times)
     78      int tries = 0;
     79      do {
     80        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
     81        childIndex = random.Next(parent.SubtreeCount);
     82        var child = parent.GetSubtree(childIndex);
     83        maxLength = maxTreeLength - symbolicExpressionTree.Length + child.GetLength();
     84        maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + child.GetDepth();
    9585
    96       if (manipulationPoints.Count == 0) return;
    97       var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
     86        allowedSymbols.Clear();
     87        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
     88          // check basic properties that the new symbol must have
     89          if (symbol.Name != child.Symbol.Name &&
     90            symbol.InitialFrequency > 0 &&
     91            parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth &&
     92            parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength) {
     93            allowedSymbols.Add(symbol);
     94          }
     95        }
     96        tries++;
     97      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
    9898
    99       var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
    100       var seedSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
    101       // replace the old node with the new node
    102       var seedNode = seedSymbol.CreateTreeNode();
    103       if (seedNode.HasLocalParameters)
    104         seedNode.ResetLocalParameters(random);
     99      if (tries < MAX_TRIES) {
     100        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
     101        var seedSymbol = allowedSymbols.SelectRandom(weights, random);
     102        // replace the old node with the new node
     103        var seedNode = seedSymbol.CreateTreeNode();
     104        if (seedNode.HasLocalParameters)
     105          seedNode.ResetLocalParameters(random);
    105106
    106       selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
    107       selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, seedNode);
    108       ProbabilisticTreeCreator.PTC2(random, seedNode, selectedManipulationPoint.MaxLength, selectedManipulationPoint.MaxDepth);
     107        parent.RemoveSubtree(childIndex);
     108        parent.InsertSubtree(childIndex, seedNode);
     109        ProbabilisticTreeCreator.PTC2(random, seedNode, maxLength, maxDepth);
     110      }
    109111    }
    110112  }

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammar.cs

    r7268 r7842  
    181181
    182182    #region IStatefulItem methods
    183     void IStatefulItem.InitializeState() { }
     183    void IStatefulItem.InitializeState()
     184    {
     185      ReadOnly = false;
     186    }
    184187    void IStatefulItem.ClearState() {
    185188      ReadOnly = false;

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs

    r7268 r7842  
    308308    }
    309309    public virtual IEnumerable<ISymbol> AllowedSymbols {
    310       get { return Symbols.Where(s => s.Enabled); }
     310      get { foreach (var s in Symbols) if (s.Enabled) yield return s; }
    311311    }
    312312    public virtual bool ContainsSymbol(ISymbol symbol) {
    … …  
    316316    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
    317317    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
     318      if (allowedChildSymbols.Count == 0) return false;
    318319      if (!child.Enabled) return false;
    319320
    320321      bool result;
    321       if (cachedIsAllowedChildSymbol.TryGetValue(Tuple.Create(parent.Name, child.Name), out result)) return result;
     322      var key = Tuple.Create(parent.Name, child.Name);
     323      if (cachedIsAllowedChildSymbol.TryGetValue(key, out result)) return result;
     324
    322325      List<string> temp;
    323326      if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
    324327        //if (temp.Contains(child.Name)) return true;
    325         if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
    326           cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), true);
     328        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
     329          cachedIsAllowedChildSymbol.Add(key, true);
    327330          return true;
    328331        }
    329332      }
    330       cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), false);
     333      cachedIsAllowedChildSymbol.Add(key, false);
    331334      return false;
    332335    }
    … …  
    336339      if (!child.Enabled) return false;
    337340      if (IsAllowedChildSymbol(parent, child)) return true;
     341      if (allowedChildSymbolsPerIndex.Count == 0) return false;
    338342
    339343      bool result;
    340       if (cachedIsAllowedChildSymbolIndex.TryGetValue(Tuple.Create(parent.Name, child.Name, argumentIndex), out result)) return result;
     344      var key = Tuple.Create(parent.Name, child.Name, argumentIndex);
     345      if (cachedIsAllowedChildSymbolIndex.TryGetValue(key, out result)) return result;
     346
    341347      List<string> temp;
    342       var key = Tuple.Create(parent.Name, argumentIndex);
    343       if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp)) {
    344         //if (temp.Contains(child.Name)) return true;
    345         if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
    346           cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), true);
     348      if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, argumentIndex), out temp)) {
     349        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
     350          cachedIsAllowedChildSymbolIndex.Add(key, true);
    347351          return true;
    348352        }
    349353      }
    350       cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), false);
     354      cachedIsAllowedChildSymbolIndex.Add(key, false);
    351355      return false;
    352356    }
    353357
    354358    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
    355       return from child in AllowedSymbols
    356              where IsAllowedChildSymbol(parent, child)
    357              select child;
     359      foreach (ISymbol child in AllowedSymbols) {
     360        if (IsAllowedChildSymbol(parent, child)) yield return child;
     361      }
    358362    }
    359363
    360364    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
    361       return from child in AllowedSymbols
    362              where IsAllowedChildSymbol(parent, child, argumentIndex)
    363              select child;
     365      foreach (ISymbol child in AllowedSymbols) {
     366        if (IsAllowedChildSymbol(parent, child, argumentIndex)) yield return child;
     367      }
    364368    }
    365369

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTree.cs

    r7268 r7842  
    7575    }
    7676
     77    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
     78      if (root == null)
     79        return new SymbolicExpressionTreeNode[0];
     80      return root.IterateNodesBreadth();
     81    }
     82
    7783    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
    7884      if (root == null)

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeGrammar.cs

    r7268 r7842  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Linq;
    2524using HeuristicLab.Common;
    2625using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    5150
    5251    public override IEnumerable<ISymbol> Symbols {
    53       get { return grammar.Symbols.Union(base.Symbols); }
     52      get {
     53        foreach (var s in grammar.Symbols) yield return s;
     54        foreach (var s in base.symbols.Values) yield return s;
     55      }
    5456    }
    5557    public override IEnumerable<ISymbol> AllowedSymbols {

  • branches/HeuristicLab.TimeSeries/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs

    r7615 r7842  
    5353    protected SymbolicExpressionTreeNode(bool deserializing) { }
    5454    protected SymbolicExpressionTreeNode(SymbolicExpressionTreeNode original, Cloner cloner)
    55       : base() {
     55      : base(original, cloner) {
    5656      symbol = original.symbol; // symbols are reused
     57      length = original.length;
     58      depth = original.depth;
    5759      if (original.subtrees != null) {
    5860        subtrees = new List<ISymbolicExpressionTreeNode>(original.subtrees.Count);
    … …  
    172174    }
    173175
     176    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesBreadth() {
     177      var list = new List<ISymbolicExpressionTreeNode>() { this };
     178      int i = 0;
     179      while (i != list.Count) {
     180        for (int j = 0; j != list[i].SubtreeCount; ++j)
     181          list.Add(list[i].GetSubtree(j));
     182        ++i;
     183      }
     184      return list;
     185    }
     186
    174187    public IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPrefix() {
    175188      List<ISymbolicExpressionTreeNode> list = new List<ISymbolicExpressionTreeNode>();
Note: See TracChangeset for help on using the changeset viewer.