Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
03/26/12 14:11:46 (13 years ago)
Author:
gkronber
Message:

#1806 improved memory usage of ChangeNodeTypeManipulation and ReplaceBranchManipulation by replacing the linq statements

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs

    r7259 r7662  
    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  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ReplaceBranchManipulation.cs

    r7259 r7662  
    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  }
Note: See TracChangeset for help on using the changeset viewer.