Free cookie consent management tool by TermsFeed Policy Generator

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

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

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