Changeset 7662

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

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs (modified) (3 diffs)
• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ReplaceBranchManipulation.cs (modified) (3 diffs)
• HeuristicLab.PluginInfrastructure/3.3/LightweightApplicationManager.cs (modified) (1 diff)
• HeuristicLab.Tests/HeuristicLab-3.3/SamplesTest.cs (modified) (3 diffs)

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

@@ -24 +24 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
@@ -29 +30 @@
   [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]
   public sealed class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator {
+    private const int MAX_TRIES = 100;
+
     [StorableConstructor]
     private ChangeNodeTypeManipulation(bool deserializing) : base(deserializing) { }
@@ -43 +46 @@
 
     public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
-      // select any node as parent (except the root node)
-      var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
-                                let subtreeCount = parent.Subtrees.Count()
-                                from subtreeIndex in Enumerable.Range(0, subtreeCount)
-                                let subtree = parent.GetSubtree(subtreeIndex)
-                                let existingSubtreeCount = subtree.Subtrees.Count()
-                                // find possible symbols for the node (also considering the existing branches below it)
-                                let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
-                                                      // do not replace the existing symbol with itself
-                                                      where symbol.Name != subtree.Symbol.Name
-                                                      where symbol.InitialFrequency > 0
-                                                      where existingSubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(symbol)
-                                                      where existingSubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(symbol)
-                                                      // keep only symbols that are still possible considering the existing sub-trees
-                                                      where (from existingSubtreeIndex in Enumerable.Range(0, existingSubtreeCount)
-                                                             let existingSubtree = subtree.GetSubtree(existingSubtreeIndex)
-                                                             select parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex))
-                                                             .All(x => x == true)
-                                                      select symbol)
-                                                      .ToList()
-                                where allowedSymbols.Count() > 0
-                                select new { Parent = parent, Child = subtree, Index = subtreeIndex, AllowedSymbols = allowedSymbols })
-                               .ToList();
-      if (manipulationPoints.Count == 0) { return; }
-      var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
+      List<ISymbol> allowedSymbols = new List<ISymbol>();
+      ISymbolicExpressionTreeNode parent;
+      int childIndex;
+      ISymbolicExpressionTreeNode child;
+      // repeat until a fitting parent and child are found (MAX_TRIES times)
+      int tries = 0;
+      do {
+        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
+        childIndex = random.Next(parent.SubtreeCount);
 
-      var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
-      var newSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
+        child = parent.GetSubtree(childIndex);
+        int existingSubtreeCount = child.SubtreeCount;
+        allowedSymbols.Clear();
+        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
+          // check basic properties that the new symbol must have
+          if (symbol.Name != child.Symbol.Name &&
+            symbol.InitialFrequency > 0 &&
+            existingSubtreeCount <= parent.Grammar.GetMinimumSubtreeCount(symbol) &&
+            existingSubtreeCount >= parent.Grammar.GetMaximumSubtreeCount(symbol)) {
+            // check that all existing subtrees are also allowed for the new symbol
+            bool allExistingSubtreesAllowed = true;
+            for (int existingSubtreeIndex = 0; existingSubtreeIndex < existingSubtreeCount && allExistingSubtreesAllowed; existingSubtreeIndex++) {
+              var existingSubtree = child.GetSubtree(existingSubtreeIndex);
+              allExistingSubtreesAllowed &= parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex);
+            }
+            if (allExistingSubtreesAllowed) {
+              allowedSymbols.Add(symbol);
+            }
+          }
+        }
+        tries++;
+      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
 
-      // replace the old node with the new node
-      var newNode = newSymbol.CreateTreeNode();
-      if (newNode.HasLocalParameters)
-        newNode.ResetLocalParameters(random);
-      foreach (var subtree in selectedManipulationPoint.Child.Subtrees)
-        newNode.AddSubtree(subtree);
-      selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
-      selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, newNode);
+      if (tries < MAX_TRIES) {
+        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
+        var newSymbol = allowedSymbols.SelectRandom(weights, random);
+
+        // replace the old node with the new node
+        var newNode = newSymbol.CreateTreeNode();
+        if (newNode.HasLocalParameters)
+          newNode.ResetLocalParameters(random);
+        foreach (var subtree in child.Subtrees)
+          newNode.AddSubtree(subtree);
+        parent.RemoveSubtree(childIndex);
+        parent.InsertSubtree(childIndex, newNode);
+      }
     }
   }

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

@@ -26 +26 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
@@ -31 +32 @@
   [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
   public sealed class ReplaceBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
+    private const int MAX_TRIES = 100;
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
@@ -68 +70 @@
 
     public static void ReplaceRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
-      // select any node as parent (except the root node)
-      var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
-                                from subtree in parent.Subtrees
-                                let subtreeIndex = parent.IndexOfSubtree(subtree)
-                                let maxLength = maxTreeLength - symbolicExpressionTree.Length + subtree.GetLength()
-                                let maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + subtree.GetDepth()
-                                // find possible symbols for the node (also considering the existing branches below it)
-                                let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
-                                                      // do not replace symbol with the same symbol
-                                                      where symbol.Name != subtree.Symbol.Name
-                                                      where symbol.InitialFrequency > 0
-                                                      where parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth
-                                                      where parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength
-                                                      select symbol)
-                                                      .ToList()
-                                where allowedSymbols.Count > 0
-                                select new {
-                                  Parent = parent,
-                                  Child = subtree,
-                                  Index = subtreeIndex,
-                                  AllowedSymbols = allowedSymbols,
-                                  MaxLength = maxLength,
-                                  MaxDepth = maxDepth
-                                })
-                               .ToList();
+      var allowedSymbols = new List<ISymbol>();
+      ISymbolicExpressionTreeNode parent;
+      int childIndex;
+      int maxLength;
+      int maxDepth;
+      // repeat until a fitting parent and child are found (MAX_TRIES times)
+      int tries = 0;
+      do {
+        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
+        childIndex = random.Next(parent.SubtreeCount);
+        var child = parent.GetSubtree(childIndex);
+        maxLength = maxTreeLength - symbolicExpressionTree.Length + child.GetLength();
+        maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + child.GetDepth();
 
-      if (manipulationPoints.Count == 0) return;
-      var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
+        allowedSymbols.Clear();
+        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
+          // check basic properties that the new symbol must have
+          if (symbol.Name != child.Symbol.Name &&
+            symbol.InitialFrequency > 0 &&
+            parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth &&
+            parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength) {
+            allowedSymbols.Add(symbol);
+          }
+        }
+        tries++;
+      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
 
-      var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
-      var seedSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
-      // replace the old node with the new node
-      var seedNode = seedSymbol.CreateTreeNode();
-      if (seedNode.HasLocalParameters)
-        seedNode.ResetLocalParameters(random);
+      if (tries < MAX_TRIES) {
+        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
+        var seedSymbol = allowedSymbols.SelectRandom(weights, random);
+        // replace the old node with the new node
+        var seedNode = seedSymbol.CreateTreeNode();
+        if (seedNode.HasLocalParameters)
+          seedNode.ResetLocalParameters(random);
 
-      selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
-      selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, seedNode);
-      ProbabilisticTreeCreator.PTC2(random, seedNode, selectedManipulationPoint.MaxLength, selectedManipulationPoint.MaxDepth);
+        parent.RemoveSubtree(childIndex);
+        parent.InsertSubtree(childIndex, seedNode);
+        ProbabilisticTreeCreator.PTC2(random, seedNode, maxLength, maxDepth);
+      }
     }
   }

trunk/sources/HeuristicLab.PluginInfrastructure/3.3/LightweightApplicationManager.cs

@@ -123 +123 @@
     private static IEnumerable<Type> GetTypes(Type type, Assembly assembly, bool onlyInstantiable = true, bool includeGenericTypeDefinitions = false) {
       try {
+        // necessary to make sure the exception is immediately thrown
+        // instead of later when the enumerable is iterated?
         var assemblyTypes = assembly.GetTypes();
 

trunk/sources/HeuristicLab.Tests/HeuristicLab-3.3/SamplesTest.cs

@@ -187 +187 @@
       ga.SetSeedRandomly.Value = false;
       RunAlgorithm(ga);
-      Assert.AreEqual(63, GetDoubleResult(ga, "BestQuality"));
-      Assert.AreEqual(47.26, GetDoubleResult(ga, "CurrentAverageQuality"));
+      Assert.AreEqual(67, GetDoubleResult(ga, "BestQuality"));
+      Assert.AreEqual(45.813, GetDoubleResult(ga, "CurrentAverageQuality"));
       Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"));
       Assert.AreEqual(50950, GetIntResult(ga, "EvaluatedSolutions"));
@@ -238 +238 @@
       ga.SetSeedRandomly.Value = false;
       RunAlgorithm(ga);
-      Assert.AreEqual(0.82932035115203739, GetDoubleResult(ga, "BestQuality"));
-      Assert.AreEqual(0.53850226351927422, GetDoubleResult(ga, "CurrentAverageQuality"));
-      Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"));
+      Assert.AreEqual(0.78855594192122458, GetDoubleResult(ga, "BestQuality"), 1E-8);
+      Assert.AreEqual(0.61395271071681523, GetDoubleResult(ga, "CurrentAverageQuality"), 1E-8);
+      Assert.AreEqual(0, GetDoubleResult(ga, "CurrentWorstQuality"), 1E-8);
       Assert.AreEqual(50950, GetIntResult(ga, "EvaluatedSolutions"));
     }
@@ -341 +341 @@
       ga.SetSeedRandomly.Value = false;
       RunAlgorithm(ga);
-      Assert.AreEqual(0.13941049901558636, GetDoubleResult(ga, "BestQuality"));
-      Assert.AreEqual(5.7121443289014842, GetDoubleResult(ga, "CurrentAverageQuality"));
-      Assert.AreEqual(102.59400156249991, GetDoubleResult(ga, "CurrentWorstQuality"));
+      Assert.AreEqual(0.13775264138895371, GetDoubleResult(ga, "BestQuality"), 1E-8);
+      Assert.AreEqual(14.232802217120254, GetDoubleResult(ga, "CurrentAverageQuality"), 1E-8);
+      Assert.AreEqual(104.24339008411457, GetDoubleResult(ga, "CurrentWorstQuality"), 1E-8);
       Assert.AreEqual(100900, GetIntResult(ga, "EvaluatedSolutions"));
     }