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  using HeuristicLab.Random;


28 


29  namespace HeuristicLab.Problems.GrammaticalEvolution {


30  /// <summary>


31  /// DepthFirstMapper


32  /// </summary>


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


34  [StorableClass]


35  public class DepthFirstMapper : GenotypeToPhenotypeMapper {


36 


37  [StorableConstructor]


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


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


40  public DepthFirstMapper() : base() { }


41 


42  public override IDeepCloneable Clone(Cloner cloner) {


43  return new DepthFirstMapper(this, cloner);


44  }


45 


46 


47  /// <summary>


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


49  /// Depthfirst approach.


50  /// </summary>


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


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


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


54  public override SymbolicExpressionTree Map(ISymbolicExpressionGrammar grammar,


55  IntegerVector genotype) {


56 


57  SymbolicExpressionTree tree = new SymbolicExpressionTree();


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


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


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


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


62  rootNode.AddSubtree(startNode);


63  tree.Root = rootNode;


64 


65  int genotypeIndex = 0;


66  int currSubtreeCount = 1;


67 


68  MapDepthFirstRecursively(startNode, genotype,


69  grammar, genotype.Length,


70  ref genotypeIndex, ref currSubtreeCount);


71 


72  return tree;


73  }


74 


75 


76  /// <summary>


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


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


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


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


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


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


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


84  /// </summary>


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


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


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


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


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


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


91  private void MapDepthFirstRecursively(ISymbolicExpressionTreeNode currentNode,


92  IntegerVector genotype,


93  ISymbolicExpressionGrammar grammar,


94  int maxSubtreeCount,


95  ref int genotypeIndex,


96  ref int currSubtreeCount) {


97  if (currSubtreeCount < maxSubtreeCount) {


98 


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


100 


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


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


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


104  } else {


105  currentNode.AddSubtree(newNode);


106  genotypeIndex++;


107  currSubtreeCount += newNode.Symbol.MinimumArity;


108 


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


110  MapDepthFirstRecursively(newNode, genotype,


111  grammar, maxSubtreeCount,


112  ref genotypeIndex, ref currSubtreeCount);


113  }


114  }


115 


116  } else {


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


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


119  currentNode.AddSubtree(newNode);


120  genotypeIndex++;


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


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


123  }


124  }


125  }


126  }


127  }


128  } 
