Changeset 10228 for branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

Timestamp:

12/15/13 12:34:33 (11 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.

File:

• branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs (modified) (6 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));
+      }
+    }
   }
 }