Changeset 10228 for branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution

Timestamp:

12/15/13 12:34:33 (10 years ago)

Author:

sawinkle

Message:

#2109: Updated DepthFirstMapper and abstract base class GenotypeToPhenotypeMapper:

• Added new method SampleArity() to GenotypeToPhenotypeMapper to determine a random arity for a given node, depending on a maximum allowed arity.
• Replaced the recursive depth-first mapping approach by a iterative one, which uses a stack of <node, arity> tuples. The recursive approach only generated trees with very small subtrees depending on the minimumArity of each node. Now, the iterative one uses the SampleArity() method and pushes/pops the <node, arity> tuples from/to the used stack. Therefore, it is not necessary to only allow the minimumArity, but also to deal with arbitrarily sampled arities per node.

Location:

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers

Files:

• DepthFirstMapper.cs (modified) (6 diffs)
• GenotypeToPhenotypeMapper.cs (modified) (5 diffs)

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -63 +65 @@
       tree.Root = rootNode;
 
-      int genotypeIndex = 0;
-      int currSubtreeCount = 1;
+      //int genotypeIndex = 0;
+      //int currSubtreeCount = 1;
+      //MapDepthFirstRecursively(startNode, genotype,
+      //                         grammar, genotype.Length,
+      //                         ref genotypeIndex, ref currSubtreeCount,
+      //                         new MersenneTwister());
 
-      MapDepthFirstRecursively(startNode, genotype,
-                               grammar, genotype.Length,
-                               ref genotypeIndex, ref currSubtreeCount);
-
+      MapDepthFirstIteratively(startNode, genotype, grammar,
+                               genotype.Length, new MersenneTwister());
       return tree;
     }
@@ -85 +89 @@
     /// <param name="currentNode">current parent node</param>
     /// <param name="genotype">integer vector, which should be mapped to a tree</param>
-    /// <param name="grammar">grammar definition to determine the allowed child symbols for currentNode </param>
+    /// <param name="grammar">grammar to determine the allowed child symbols for currentNode </param>
     /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
     /// <param name="genotypeIndex">current index in integer vector</param>
@@ -94 +98 @@
                                           int maxSubtreeCount,
                                           ref int genotypeIndex,
-                                          ref int currSubtreeCount) {
+                                          ref int currSubtreeCount,
+                                          IRandom random) {
+
+      // TODO: check, if method calls of GetNewChildNode() and GetRandomTerminalNode() don't return null
       if (currSubtreeCount < maxSubtreeCount) {
 
-        var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex);
+        var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random);
 
         if ((currSubtreeCount + newNode.Symbol.MinimumArity) > maxSubtreeCount) {
           // TODO: maybe check, if there is any node, which fits in the tree yet
-          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));
+          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar, random));
         } else {
           currentNode.AddSubtree(newNode);
@@ -110 +117 @@
             MapDepthFirstRecursively(newNode, genotype,
                                      grammar, maxSubtreeCount,
-                                     ref genotypeIndex, ref currSubtreeCount);
+                                     ref genotypeIndex, ref currSubtreeCount, random);
           }
         }
@@ -116 +123 @@
       } else {
         while (currentNode.Symbol.MinimumArity > currentNode.SubtreeCount) {
-          var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex);
+          var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random);
           currentNode.AddSubtree(newNode);
           genotypeIndex++;
           while (newNode.Symbol.MinimumArity > newNode.SubtreeCount) {
-            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));
+            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar, random));
           }
         }
       }
     }
+
+
+    /// <summary>
+    /// Genotype-to-Phenotype mapper (iterative depth-first approach).
+    /// </summary>
+    /// <param name="startNode">first node of the tree with arity 1</param>
+    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
+    /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
+    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
+    /// <param name="random">random number generator</param>
+    private void MapDepthFirstIteratively(ISymbolicExpressionTreeNode startNode,
+                                          IntegerVector genotype,
+                                          ISymbolicExpressionGrammar grammar,
+                                          int maxSubtreeCount, IRandom random) {
+
+      Stack<Tuple<ISymbolicExpressionTreeNode, int>> stack
+        = new Stack<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity>
+
+      int genotypeIndex = 0;
+      int currSubtreeCount = 1;
+
+      stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));
+
+      while ((currSubtreeCount < maxSubtreeCount) && (stack.Count > 0)) {
+
+        // get next node from stack and re-push it, if this node still has unhandled subtrees ...
+        Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();
+        if (current.Item2 > 1) {
+          stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2 - 1));
+        }
+
+        var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
+        int arity = SampleArity(random, newNode, maxSubtreeCount - currSubtreeCount);
+
+        if (arity < 0) {
+          current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
+        } else {
+          current.Item1.AddSubtree(newNode);
+          genotypeIndex++;
+          currSubtreeCount += arity;
+          if (arity > 0) {
+            // new node has subtrees so push it onto the stack 
+            stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity));
+          }
+        }
+      }
+
+      // maximum allowed subtree count was already reached, but there are still
+      // incomplete subtrees (non-terminal symbols) in the tree
+      // -> fill them with terminal symbols
+      while (stack.Count > 0) {
+        Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();
+        if (current.Item2 > 1) {
+          stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2 - 1));
+        }
+        current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
+      }
+    }
   }
 }

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/GenotypeToPhenotypeMapper.cs

@@ -23 +23 @@
 using System.Linq;
 using HeuristicLab.Common;
+using HeuristicLab.Core;
 using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.GrammaticalEvolution.Mappers;
-using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GrammaticalEvolution {
@@ -48 +48 @@
     /// </summary>
     /// <param name="parentNode">parent node for which a child node is returned randomly</param>
-    /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>
-    /// <returns>randomly chosen terminal node with arity 0</returns>
+    /// <param name="grammar">grammar to determine the allowed child symbols for parentNode</param>
+    /// <param name="random">random number generator</param>
+    /// <returns>randomly chosen terminal node with arity 0 or null, if no terminal node exists</returns>
     protected ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
-                                                              ISymbolicExpressionGrammar grammar) {
+                                                                ISymbolicExpressionGrammar grammar,
+                                                                IRandom random) {
       // only select specific symbols, which can be interpreted ...
       var possibleSymbolsList = (from s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
@@ -58 +60 @@
                                  where s.MinimumArity == 0
                                  select s).ToList();
-      // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen?
-      var newNode = possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();
-      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(new MersenneTwister());
+
+      // no terminal node exists for the given parent node
+      if (possibleSymbolsList.Count() < 1) return null;
+
+      var newNode = possibleSymbolsList.SelectRandom(random).CreateTreeNode();
+      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);
       return newNode;
     }
@@ -70 +75 @@
     /// <param name="parentNode">parent node to find a child node randomly for</param>
     /// <param name="genotype">integer vector, which should be mapped to a tree</param>
-    /// <param name="grammar">grammar definition used to define the allowed child symbols</param>
+    /// <param name="grammar">grammar used to define the allowed child symbols</param>
     /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>
-    /// <returns>randomly chosen child node for parentNode</returns>
+    /// <param name="random">random number generator</param>
+    /// <returns>randomly chosen child node or null, if no child node exits</returns>
     protected ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,
                                                           IntegerVector genotype,
                                                           ISymbolicExpressionGrammar grammar,
-                                                          int genotypeIndex) {
+                                                          int genotypeIndex,
+                                                          IRandom random) {
 
       // only select specific symbols, which can be interpreted ...
@@ -82 +89 @@
                                          where s.InitialFrequency > 0.0
                                          select s).ToList();
+
       int prodRuleCount = symbolList.Count();
+
+      // no child node exists for the given parent node
+      if (prodRuleCount < 1) return null;
+
       int prodRuleIndex = genotype[genotypeIndex % genotype.Length] % prodRuleCount;
 
       var newNode = symbolList.ElementAt(prodRuleIndex).CreateTreeNode();
-      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(new MersenneTwister());
+      if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);
       return newNode;
+    }
+
+
+    /// <summary>
+    /// Randomly determines an arity for the given node.
+    /// </summary>
+    /// <param name="random">random number generator</param>
+    /// <param name="node">node, for which a random arity is determined</param>
+    /// <param name="maxAllowedArity">the resulting arity must not exceed this maximum arity</param>
+    /// <returns>random arity in the interval [minArity, maxArity] of the node or
+    ///          -1, if minArity exceeds maxAllowedArity</returns>
+    protected int SampleArity(IRandom random,
+                              ISymbolicExpressionTreeNode node,
+                              int maxAllowedArity) {
+      int minArity = node.Symbol.MinimumArity;
+      int maxArity = node.Symbol.MaximumArity;
+
+      if (maxAllowedArity < maxArity) {
+        maxArity = maxAllowedArity;
+      }
+
+      if (maxAllowedArity < minArity) {
+        return -1;
+      }
+
+      if (minArity == maxArity) {
+        return minArity;
+      }
+
+      return random.Next(minArity, maxArity);
     }
   }