source: branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs @ 10075

Last change on this file since 10075 was 10075, checked in by sawinkle, 7 years ago

#2109:

  • For each newly created node, ResetLocalParameters() has to be called, if possible. Otherwise 'Variable' symbols won't be initialized correctly. (E.g. internal ValueName is null and causes exceptions.)
  • Method MapDepthFirstRecursively() of DepthFirstMapper.cs checks subtree boundaries by using the MinimumArity instead of the MaximumArity. Otherwise e.g. adding the 'Addition' symbol will cause very short trees, because this symbol has got a MaximumArity of 255! This would cause, that the tree is immediately full, after insertion of one 'Addition' symbol, if the genotype length is e.g. just 100.
  • Several bug fixes.
  • Unresolved issues:
    • Changes in the selected grammar are not taken into account during a run (e.g. 'Addition' symbols will be inserted into the tree, although its checkbox was unchecked previously).
    • Exception, if a division by zero is tried.
    • Wrapping mechanism.
File size: 5.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Encodings.IntegerVectorEncoding;
25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27using HeuristicLab.Random;
28
29namespace 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    /// Depth-first 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    /// Genotype-to-Phenotype mapper (recursive depth-first approach).
78    /// Appends maximum allowed children (non-terminal 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 non-full node is filled with randomly chosen nodes
83    /// (non-terminal and terminal), and each non-terminal 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}
Note: See TracBrowser for help on using the repository browser.