1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Collections.Generic;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Encodings.IntegerVectorEncoding;


27  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


28  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


29  using HeuristicLab.Random;


30 


31  namespace HeuristicLab.Problems.GrammaticalEvolution {


32  /// <summary>


33  /// DepthFirstMapper


34  /// </summary>


35  [Item("DepthFirstMapper", "")]


36  [StorableClass]


37  public class DepthFirstMapper : GenotypeToPhenotypeMapper {


38 


39  [StorableConstructor]


40  protected DepthFirstMapper(bool deserializing) : base(deserializing) { }


41  protected DepthFirstMapper(DepthFirstMapper original, Cloner cloner) : base(original, cloner) { }


42  public DepthFirstMapper() : base() { }


43 


44  public override IDeepCloneable Clone(Cloner cloner) {


45  return new DepthFirstMapper(this, cloner);


46  }


47 


48 


49  /// <summary>


50  /// Maps a genotype (an integer vector) to a phenotype (a symbolic expression tree).


51  /// Depthfirst approach.


52  /// </summary>


53  /// <param name="grammar">grammar definition</param>


54  /// <param name="genotype">integer vector, which should be mapped to a tree</param>


55  /// <returns>phenotype (a symbolic expression tree)</returns>


56  public override SymbolicExpressionTree Map(ISymbolicExpressionGrammar grammar,


57  IntegerVector genotype) {


58 


59  SymbolicExpressionTree tree = new SymbolicExpressionTree();


60  var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();


61  if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(new MersenneTwister());


62  var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();


63  if (startNode.HasLocalParameters) startNode.ResetLocalParameters(new MersenneTwister());


64  rootNode.AddSubtree(startNode);


65  tree.Root = rootNode;


66 


67  //int genotypeIndex = 0;


68  //int currSubtreeCount = 1;


69  //MapDepthFirstRecursively(startNode, genotype,


70  // grammar, genotype.Length,


71  // ref genotypeIndex, ref currSubtreeCount,


72  // new MersenneTwister());


73 


74  MapDepthFirstIteratively(startNode, genotype, grammar,


75  genotype.Length, new MersenneTwister());


76  return tree;


77  }


78 


79 


80  /// <summary>


81  /// GenotypetoPhenotype mapper (recursive depthfirst approach).


82  /// Appends maximum allowed children (nonterminal symbols) to


83  /// <paramref name="currentNode"/>, as long as <paramref name="currSubtreeCount"/>


84  /// doesn't exceed <paramref name="maxSubtreeCount"/>.


85  /// If at most <paramref name="maxSubtreeCount"/> subtrees were created,


86  /// each nonfull node is filled with randomly chosen nodes


87  /// (nonterminal and terminal), and each nonterminal node is again filled with a terminal node.


88  /// </summary>


89  /// <param name="currentNode">current parent node</param>


90  /// <param name="genotype">integer vector, which should be mapped to a tree</param>


91  /// <param name="grammar">grammar to determine the allowed child symbols for currentNode </param>


92  /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>


93  /// <param name="genotypeIndex">current index in integer vector</param>


94  /// <param name="currSubtreeCount">number of already determined subtrees (filled or still incomplete)</param>


95  private void MapDepthFirstRecursively(ISymbolicExpressionTreeNode currentNode,


96  IntegerVector genotype,


97  ISymbolicExpressionGrammar grammar,


98  int maxSubtreeCount,


99  ref int genotypeIndex,


100  ref int currSubtreeCount,


101  IRandom random) {


102 


103  // TODO: check, if method calls of GetNewChildNode() and GetRandomTerminalNode() don't return null


104  if (currSubtreeCount < maxSubtreeCount) {


105 


106  var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random);


107 


108  if ((currSubtreeCount + newNode.Symbol.MinimumArity) > maxSubtreeCount) {


109  // TODO: maybe check, if there is any node, which fits in the tree yet


110  currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar, random));


111  } else {


112  currentNode.AddSubtree(newNode);


113  genotypeIndex++;


114  currSubtreeCount += newNode.Symbol.MinimumArity;


115 


116  while (newNode.Symbol.MinimumArity > newNode.SubtreeCount) {


117  MapDepthFirstRecursively(newNode, genotype,


118  grammar, maxSubtreeCount,


119  ref genotypeIndex, ref currSubtreeCount, random);


120  }


121  }


122 


123  } else {


124  while (currentNode.Symbol.MinimumArity > currentNode.SubtreeCount) {


125  var newNode = GetNewChildNode(currentNode, genotype, grammar, genotypeIndex, random);


126  currentNode.AddSubtree(newNode);


127  genotypeIndex++;


128  while (newNode.Symbol.MinimumArity > newNode.SubtreeCount) {


129  newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar, random));


130  }


131  }


132  }


133  }


134 


135 


136  /// <summary>


137  /// GenotypetoPhenotype mapper (iterative depthfirst approach).


138  /// </summary>


139  /// <param name="startNode">first node of the tree with arity 1</param>


140  /// <param name="genotype">integer vector, which should be mapped to a tree</param>


141  /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>


142  /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>


143  /// <param name="random">random number generator</param>


144  private void MapDepthFirstIteratively(ISymbolicExpressionTreeNode startNode,


145  IntegerVector genotype,


146  ISymbolicExpressionGrammar grammar,


147  int maxSubtreeCount, IRandom random) {


148 


149  Stack<Tuple<ISymbolicExpressionTreeNode, int>> stack


150  = new Stack<Tuple<ISymbolicExpressionTreeNode, int>>(); // tuples of <node, arity>


151 


152  int genotypeIndex = 0;


153  int currSubtreeCount = 1;


154 


155  stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));


156 


157  while ((currSubtreeCount < maxSubtreeCount) && (stack.Count > 0)) {


158 


159  // get next node from stack and repush it, if this node still has unhandled subtrees ...


160  Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();


161  if (current.Item2 > 1) {


162  stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2  1));


163  }


164 


165  var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);


166  int arity = SampleArity(random, newNode, maxSubtreeCount  currSubtreeCount);


167 


168  if (arity < 0) {


169  current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));


170  } else {


171  current.Item1.AddSubtree(newNode);


172  genotypeIndex++;


173  currSubtreeCount += arity;


174  if (arity > 0) {


175  // new node has subtrees so push it onto the stack


176  stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(newNode, arity));


177  }


178  }


179  }


180 


181  // maximum allowed subtree count was already reached, but there are still


182  // incomplete subtrees (nonterminal symbols) in the tree


183  // > fill them with terminal symbols


184  while (stack.Count > 0) {


185  Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();


186  if (current.Item2 > 1) {


187  stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2  1));


188  }


189  current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));


190  }


191  }


192  }


193  } 
