Free cookie consent management tool by TermsFeed Policy Generator

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

Ignore:
Timestamp:
12/15/13 12:34:33 (10 years ago)
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:
1 edited

Unmodified
Added
Removed
• ## branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

 r10075 #endregion using System; using System.Collections.Generic; using HeuristicLab.Common; using HeuristicLab.Core; 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; } /// current parent node /// integer vector, which should be mapped to a tree /// grammar definition to determine the allowed child symbols for currentNode /// grammar to determine the allowed child symbols for currentNode /// maximum allowed subtrees (= number of used genomes) /// current index in integer vector 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); MapDepthFirstRecursively(newNode, genotype, grammar, maxSubtreeCount, ref genotypeIndex, ref currSubtreeCount); ref genotypeIndex, ref currSubtreeCount, random); } } } 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)); } } } } /// /// Genotype-to-Phenotype mapper (iterative depth-first approach). /// /// first node of the tree with arity 1 /// integer vector, which should be mapped to a tree /// grammar to determine the allowed child symbols for each node /// maximum allowed subtrees (= number of used genomes) /// random number generator private void MapDepthFirstIteratively(ISymbolicExpressionTreeNode startNode, IntegerVector genotype, ISymbolicExpressionGrammar grammar, int maxSubtreeCount, IRandom random) { Stack> stack = new Stack>(); // tuples of int genotypeIndex = 0; int currSubtreeCount = 1; stack.Push(new Tuple(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 current = stack.Pop(); if (current.Item2 > 1) { stack.Push(new Tuple(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(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 current = stack.Pop(); if (current.Item2 > 1) { stack.Push(new Tuple(current.Item1, current.Item2 - 1)); } current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random)); } } } }
Note: See TracChangeset for help on using the changeset viewer.