1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022015 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  * Author: Sabine Winkler


21  */


22  #endregion


23 


24  using System.Collections.Generic;


25  using System.Linq;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.IntegerVectorEncoding;


30  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


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


32  using HeuristicLab.Problems.GrammaticalEvolution.Mappers;


33  using HeuristicLab.Random;


34 


35  namespace HeuristicLab.Problems.GrammaticalEvolution {


36  /// <summary>


37  /// Abstract base class for GenotypeToPhenotypeMappers


38  /// </summary>


39  public abstract class GenotypeToPhenotypeMapper : IntegerVectorOperator, IGenotypeToPhenotypeMapper {


40 


41  [StorableConstructor]


42  protected GenotypeToPhenotypeMapper(bool deserializing) : base(deserializing) { }


43  protected GenotypeToPhenotypeMapper(GenotypeToPhenotypeMapper original, Cloner cloner) : base(original, cloner) { }


44  protected GenotypeToPhenotypeMapper() : base() { }


45 


46  public abstract SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,


47  ISymbolicExpressionGrammar grammar,


48  IntegerVector genotype);


49 


50  /// <summary>


51  /// Randomly returns a terminal node for the given <paramref name="parentNode"/>.


52  /// (A terminal has got a minimum and maximum arity of 0.)


53  /// </summary>


54  /// <param name="parentNode">parent node for which a child node is returned randomly</param>


55  /// <param name="grammar">grammar to determine the allowed child symbols for parentNode</param>


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


57  /// <returns>randomly chosen terminal node with arity 0 or null, if no terminal node exists</returns>


58  protected ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,


59  ISymbolicExpressionGrammar grammar,


60  IRandom random) {


61  // only select specific symbols, which can be interpreted ...


62  var possibleSymbolsList = (from s in grammar.GetAllowedChildSymbols(parentNode.Symbol)


63  where s.InitialFrequency > 0.0


64  where s.MaximumArity == 0


65  where s.MinimumArity == 0


66  select s).ToList();


67 


68  // no terminal node exists for the given parent node


69  if (!possibleSymbolsList.Any()) return null;


70 


71  var newNode = possibleSymbolsList.SampleRandom(random).CreateTreeNode();


72  if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);


73  return newNode;


74  }


75 


76 


77  /// <summary>


78  /// Returns a randomly chosen child node for the given <paramref name="parentNode"/>.


79  /// </summary>


80  /// <param name="parentNode">parent node to find a child node randomly for</param>


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


82  /// <param name="grammar">grammar used to define the allowed child symbols</param>


83  /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>


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


85  /// <returns>randomly chosen child node or null, if no child node exits</returns>


86  protected ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,


87  IntegerVector genotype,


88  ISymbolicExpressionGrammar grammar,


89  int genotypeIndex,


90  IRandom random) {


91 


92  // only select specific symbols, which can be interpreted ...


93  IEnumerable<ISymbol> symbolList = (from s in grammar.GetAllowedChildSymbols(parentNode.Symbol)


94  where s.InitialFrequency > 0.0


95  select s).ToList();


96 


97  int prodRuleCount = symbolList.Count();


98 


99  // no child node exists for the given parent node


100  if (prodRuleCount < 1) return null;


101 


102  // genotypeIndex % genotype.Length, if wrapping is allowed


103  int prodRuleIndex = genotype[genotypeIndex] % prodRuleCount;


104 


105  var newNode = symbolList.ElementAt(prodRuleIndex).CreateTreeNode();


106  if (newNode.HasLocalParameters) newNode.ResetLocalParameters(random);


107  return newNode;


108  }


109 


110 


111  /// <summary>


112  /// Randomly determines an arity for the given node.


113  /// </summary>


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


115  /// <param name="node">node, for which a random arity is determined</param>


116  /// <param name="grammar">symbolic expression grammar to use</param>


117  /// <returns>random arity in the interval [minArity, maxArity]</returns>


118  protected int SampleArity(IRandom random,


119  ISymbolicExpressionTreeNode node,


120  ISymbolicExpressionGrammar grammar) {


121 


122  int minArity = grammar.GetMinimumSubtreeCount(node.Symbol);


123  int maxArity = grammar.GetMaximumSubtreeCount(node.Symbol);


124 


125  if (minArity == maxArity) {


126  return minArity;


127  }


128 


129  return random.Next(minArity, maxArity);


130  }


131  }


132  }

