Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.GrammaticalEvolution/3.4/Mappers/PIGEMapper.cs @ 15400

Last change on this file since 15400 was 14185, checked in by swagner, 8 years ago

#2526: Updated year of copyrights in license headers

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