Changeset 10229


Ignore:
Timestamp:
12/15/13 15:56:42 (6 years ago)
Author:
sawinkle
Message:

#2109: Implemented a DepthFirstMapper, which works similarly to the DepthFirstMapper, but uses a queue to enable a breath-first tree creation.

Location:
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers
Files:
2 edited

Legend:

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

    r10068 r10229  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using HeuristicLab.Common;
    2325using HeuristicLab.Core;
     
    2527using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2628using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     29using HeuristicLab.Random;
    2730
    2831namespace HeuristicLab.Problems.GrammaticalEvolution {
     
    3033  /// BreathFirstMapper
    3134  /// </summary>
    32   [Item("BreathFirstMapper", "")]
     35  [Item("BreathFirstMapper", "Resolves the non-terminal symbols of the resulting phenotypic syntax tree in a breath-first manner.")]
    3336  [StorableClass]
    3437  public class BreathFirstMapper : GenotypeToPhenotypeMapper {
     
    6063      tree.Root = rootNode;
    6164
    62       // TODO
     65      MapBreathFirstIteratively(startNode, genotype, grammar,
     66                                genotype.Length, new MersenneTwister());
    6367
    6468      return tree;
    6569    }
     70
     71    /// <summary>
     72    /// Genotype-to-Phenotype mapper (iterative breath-first approach, by using a queue -> FIFO).
     73    /// </summary>
     74    /// <param name="startNode">first node of the tree with arity 1</param>
     75    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
     76    /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
     77    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
     78    /// <param name="random">random number generator</param>
     79    private void MapBreathFirstIteratively(ISymbolicExpressionTreeNode startNode,
     80                                          IntegerVector genotype,
     81                                          ISymbolicExpressionGrammar grammar,
     82                                          int maxSubtreeCount, IRandom random) {
     83
     84      Queue<Tuple<ISymbolicExpressionTreeNode, int>> queue
     85        = new Queue<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity>
     86
     87      int genotypeIndex = 0;
     88      int currSubtreeCount = 1;
     89
     90      queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));
     91
     92      while ((currSubtreeCount < maxSubtreeCount) && (queue.Count > 0)) {
     93
     94        Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();
     95
     96        // foreach subtree of the current node, create a new node and enqueue it, if it is no terminal node
     97        for (int i = 0; i < current.Item2; ++i) {
     98
     99          var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
     100          int arity = SampleArity(random, newNode, maxSubtreeCount - currSubtreeCount);
     101
     102          if (arity < 0) {
     103            current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
     104          } else {
     105            current.Item1.AddSubtree(newNode);
     106            genotypeIndex++;
     107            currSubtreeCount += arity;
     108            if (arity > 0) {
     109              // new node has subtrees so enqueue the node
     110              queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity));
     111            }
     112          }
     113        }
     114      }
     115
     116      // maximum allowed subtree count was already reached, but there are still
     117      // incomplete subtrees (non-terminal symbols) in the tree
     118      // -> fill them with terminal symbols
     119      while (queue.Count > 0) {
     120        Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();
     121        for (int i = 0; i < current.Item2; ++i) {
     122          current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
     123        }
     124      }
     125    }
    66126  }
    67127}
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

    r10228 r10229  
    3333  /// DepthFirstMapper
    3434  /// </summary>
    35   [Item("DepthFirstMapper", "")]
     35  [Item("DepthFirstMapper", "Resolves the non-terminal symbols of the resulting phenotypic syntax tree in a depth-first manner.")]
    3636  [StorableClass]
    3737  public class DepthFirstMapper : GenotypeToPhenotypeMapper {
     
    135135
    136136    /// <summary>
    137     /// Genotype-to-Phenotype mapper (iterative depth-first approach).
     137    /// Genotype-to-Phenotype mapper (iterative depth-first approach, by using a stack -> LIFO).
    138138    /// </summary>
    139139    /// <param name="startNode">first node of the tree with arity 1</param>
Note: See TracChangeset for help on using the changeset viewer.