Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/PIGEMapper.cs @ 10328

Last change on this file since 10328 was 10328, checked in by sawinkle, 10 years ago

#2109:

  • Added method comments + refactoring.
  • Implemented RandomMapper.
  • Changed InitialTreeLength (genotype length) of Symbolic Regression problem from 25 to 30, equally to the Artificial Ant problem with also 30.
File size: 7.3 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 System.Collections.Generic;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.IntegerVectorEncoding;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Problems.GrammaticalEvolution {
31
32  /// <summary>
33  /// Position Independent (PI) Grammatical Evolution Mapper
34  /// -----------------------------------------------------------------------------------
35  /// Standard GE mappers:
36  ///   Rule = Codon Value % Number Of Rules
37  ///   
38  /// 𝜋GE:
39  ///   𝜋GE codons consist of (nont, rule) tuples, where nont may be one value from an "order"
40  ///   integer vector and rule may be one value from a "content" integer vector.
41  ///   
42  ///   Order:   NT   = nont % Num. NT      ... determines, which non-terminal to expand next
43  ///   Content: Rule = rule % Num. Rules   ... rule determination as with standard GE mappers
44  ///
45  /// Four mutation and crossover strategies possible:
46  ///  * Order-only:    only "order" vector is modified, "content" vector is fixed (1:0),
47  ///                   worst result according to [2]
48  ///  * Content-only:  only "content" vector is modified, "order" vector is fixed (0:1),
49  ///                   best result according to [2]
50  ///  * 𝜋GE:           genetic operators are applied equally (1:1),
51  ///  * Content:Order: genetic operators are applied unequally (e.g. 2:1 or 1:2),
52  ///
53  /// Here, the "content-only" strategy is implemented, as it is the best solution according to [2]
54  /// and it does not require much to change in the problem and evaluator classes.
55  ///
56  /// </summary>
57  /// <remarks>
58  /// Described in
59  ///
60  /// [1] Michael O’Neill et al. 𝜋Grammatical Evolution. In: GECCO 2004.
61  /// Vol. 3103. LNCS. Heidelberg: Springer-Verlag Berlin, 2004, pp. 617–629.
62  /// url: http://dynamics.org/Altenberg/UH_ICS/EC_REFS/GP_REFS/GECCO/2004/31030617.pdf.
63  ///
64  /// [2] David Fagan et al. Investigating Mapping Order in πGE. IEEE, 2010
65  /// url: http://ncra.ucd.ie/papers/pigeWCCI2010.pdf
66  /// </remarks>
67  [Item("PIGEMapper", "Position Independent (PI) Grammatical Evolution Mapper")]
68  [StorableClass]
69  public class PIGEMapper : GenotypeToPhenotypeMapper {
70
71    private IntegerVector nontVector;
72
73    public IntegerVector NontVector {
74      get { return nontVector; }
75      set { nontVector = value; }
76    }
77
78    private IntegerVector GetNontVector(IRandom random, IntMatrix bounds, int length) {
79      IntegerVector v = new IntegerVector(length);
80      v.Randomize(random, bounds);
81      return v;
82    }
83
84    [StorableConstructor]
85    protected PIGEMapper(bool deserializing) : base(deserializing) { }
86    protected PIGEMapper(PIGEMapper original, Cloner cloner) : base(original, cloner) { }
87    public PIGEMapper() : base() { }
88
89    public override IDeepCloneable Clone(Cloner cloner) {
90      return new PIGEMapper(this, cloner);
91    }
92
93
94    /// <summary>
95    /// Maps a genotype (an integer vector) to a phenotype (a symbolic expression tree).
96    /// PIGE approach.
97    /// </summary>
98    /// <param name="random">random number generator</param>
99    /// <param name="bounds">integer number range for genomes (codons) of the nont vector</param>
100    /// <param name="length">length of the nont vector to create</param>
101    /// <param name="grammar">grammar definition</param>
102    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
103    /// <returns>phenotype (a symbolic expression tree)</returns>
104    public override SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
105                                               ISymbolicExpressionGrammar grammar,
106                                               IntegerVector genotype) {
107
108      SymbolicExpressionTree tree = new SymbolicExpressionTree();
109      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
110      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
111      rootNode.AddSubtree(startNode);
112      tree.Root = rootNode;
113
114      if (NontVector == null) {
115        NontVector = GetNontVector(random, bounds, length);
116      }
117
118      MapPIGEIteratively(startNode, genotype, grammar,
119                         genotype.Length, random);
120
121      return tree;
122    }
123
124
125    /// <summary>
126    /// Genotype-to-Phenotype mapper (iterative 𝜋GE approach, using a list of not expanded nonTerminals).
127    /// </summary>
128    /// <param name="startNode">first node of the tree with arity 1</param>
129    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
130    /// <param name="grammar">grammar to determine the allowed child symbols for each node</param>
131    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
132    /// <param name="random">random number generator</param>
133    private void MapPIGEIteratively(ISymbolicExpressionTreeNode startNode,
134                                    IntegerVector genotype,
135                                    ISymbolicExpressionGrammar grammar,
136                                    int maxSubtreeCount, IRandom random) {
137
138      List<ISymbolicExpressionTreeNode> nonTerminals = new List<ISymbolicExpressionTreeNode>();
139
140      int genotypeIndex = 0;
141      nonTerminals.Add(startNode);
142
143      while (nonTerminals.Count > 0) {
144
145        if (genotypeIndex >= maxSubtreeCount) {
146          // if all genomes were used, only add terminal nodes to the remaining subtrees
147          ISymbolicExpressionTreeNode current = nonTerminals[0];
148          nonTerminals.RemoveAt(0);
149          current.AddSubtree(GetRandomTerminalNode(current, grammar, random));
150        } else {
151          // Order:   NT   = nont % Num. NT
152          int nt = NontVector[genotypeIndex] % nonTerminals.Count;
153          ISymbolicExpressionTreeNode current = nonTerminals[nt];
154          nonTerminals.RemoveAt(nt);
155
156          // Content: Rule = rule % Num. Rules
157          ISymbolicExpressionTreeNode newNode = GetNewChildNode(current, genotype, grammar, genotypeIndex, random);
158          int arity = SampleArity(random, newNode, grammar);
159
160          current.AddSubtree(newNode);
161          genotypeIndex++;
162          // new node has subtrees, so add "arity" number of copies of this node to the nonTerminals list
163          for (int i = 0; i < arity; ++i) {
164            nonTerminals.Add(newNode);
165          }
166        }
167      }
168    }
169  }
170}
Note: See TracBrowser for help on using the repository browser.