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

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

#2109:

  • Removed the parameters MaxFunctionDefinitions and MaxFunctionArguments from GEArtificialAntProblem.cs, because automatically defined functions (adf) won't be supported by the Grammatical Evolution implementation of the Artificial Ant problem.
  • Switched from SharpDevelop to Visual Studio 2012 and installed 'Productivity Power Tools 2012'. This extension includes the options 'Format Document on save' and 'Remove and Sort Usings on save', so that some usings were deleted, sorted and the formating changed slightly. Furthermore 'Visual Studio 2010 text editor settings.vssettings' were included.
  • Added new folders ArtificialAnt and Symbolic to separate the files for the ArtificialAnt problem and the Symbolic Regression problem (single objective).
File size: 5.6 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;
27
28namespace 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    /// Depth-first 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    /// Genotype-to-Phenotype mapper (recursive depth-first approach).
75    /// Appends maximum allowed children (non-terminal 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 non-full node is filled with randomly chosen nodes
80    /// (non-terminal and terminal), and each non-terminal 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}
Note: See TracBrowser for help on using the repository browser.