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 HeuristicLab.Common;


23  using HeuristicLab.Core;


24  using HeuristicLab.Encodings.IntegerVectorEncoding;


25  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


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


27 


28  namespace HeuristicLab.Problems.GrammaticalEvolution {


29  /// <summary>


30  /// DepthFirstMapper


31  /// </summary>


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


33  [StorableClass]


34  public class DepthFirstMapper : GenotypeToPhenotypeMapper {


35 


36  [StorableConstructor]


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


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


39  public DepthFirstMapper() : base() { }


40 


41  public override IDeepCloneable Clone(Cloner cloner) {


42  return new DepthFirstMapper(this, cloner);


43  }


44 


45 


46  /// <summary>


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


48  /// Depthfirst approach.


49  /// </summary>


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


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


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


53  public override SymbolicExpressionTree Map(ISymbolicExpressionGrammar grammar,


54  IntegerVector genotype) {


55 


56  SymbolicExpressionTree tree = new SymbolicExpressionTree();


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


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


59  rootNode.AddSubtree(startNode);


60  tree.Root = rootNode;


61 


62  int genotypeIndex = 0;


63  int currSubtreeCount = 1;


64 


65  MapDepthFirstRecursively(startNode, genotype,


66  grammar, genotype.Length,


67  ref genotypeIndex, ref currSubtreeCount);


68 


69  return tree;


70  }


71 


72 


73  /// <summary>


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


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


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


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


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


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


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


81  /// </summary>


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


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


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


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


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


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


88  private void MapDepthFirstRecursively(ISymbolicExpressionTreeNode currentNode,


89  IntegerVector genotype,


90  ISymbolicExpressionGrammar grammar,


91  int maxSubtreeCount,


92  ref int genotypeIndex,


93  ref int currSubtreeCount) {


94  if (currSubtreeCount < maxSubtreeCount) {


95 


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


97 


98  if ((currSubtreeCount + newNode.Symbol.MaximumArity) > maxSubtreeCount) {


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


100  currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));


101  } else {


102  currentNode.AddSubtree(newNode);


103  genotypeIndex++;


104  currSubtreeCount += newNode.Symbol.MaximumArity;


105 


106  while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {


107  MapDepthFirstRecursively(newNode, genotype,


108  grammar, maxSubtreeCount,


109  ref genotypeIndex, ref currSubtreeCount);


110  }


111  }


112 


113  } else {


114  while (currentNode.Symbol.MaximumArity > currentNode.SubtreeCount) {


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


116  currentNode.AddSubtree(newNode);


117  genotypeIndex++;


118  while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {


119  newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));


120  }


121  }


122  }


123  }


124  }


125  } 
