source: branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEEvaluator.cs @ 10029

Last change on this file since 10029 was 10029, checked in by sawinkle, 9 years ago

#2109: added additional documentation and refactored code of GEEvaluator.cs

File size: 11.7 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.Data;
25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
26using HeuristicLab.Problems.ArtificialAnt;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Encodings.IntegerVectorEncoding;
32using System.Collections.Generic;
33using System.Linq;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Problems.GrammaticalEvolution {
37  [Item("GEArtificialAntEvaluator", "Evaluates an artificial ant solution, implemented in Grammatical Evolution.")]
38  [StorableClass]
39  public class GEEvaluator : SingleSuccessorOperator,
40    ISingleObjectiveEvaluator, ISymbolicExpressionTreeGrammarBasedOperator {
41
42    #region Parameter Properties
43    public ILookupParameter<DoubleValue> QualityParameter {
44      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
45    }
46    public ILookupParameter<IntegerVector> IntegerVectorParameter {
47      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
48    }
49    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
50      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
51    }
52    public ILookupParameter<BoolMatrix> WorldParameter {
53      get { return (ILookupParameter<BoolMatrix>)Parameters["World"]; }
54    }
55    public ILookupParameter<IntValue> MaxTimeStepsParameter {
56      get { return (ILookupParameter<IntValue>)Parameters["MaxTimeSteps"]; }
57    }
58    public IValueLookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionTreeGrammarParameter {
59      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionTreeGrammar"]; }
60    }
61    #endregion
62 
63    [StorableConstructor]
64    protected GEEvaluator(bool deserializing) : base(deserializing) { }
65    protected GEEvaluator(GEEvaluator original, Cloner cloner) : base(original, cloner) { }
66    public override IDeepCloneable Clone(Cloner cloner) { return new GEEvaluator(this, cloner); }
67    public GEEvaluator()
68      : base() {
69      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the evaluated artificial ant solution."));
70      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The artificial ant solution encoded as an integer vector genome."));
71      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The artificial ant solution encoded as a symbolic expression tree that should be evaluated"));
72      Parameters.Add(new LookupParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items."));
73      Parameters.Add(new LookupParameter<IntValue>("MaxTimeSteps", "The maximal number of time steps that the artificial ant should be simulated."));
74      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>("SymbolicExpressionTreeGrammar", "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
75    }
76
77    public sealed override IOperation Apply() {
78      SymbolicExpressionTree expression = MapIntegerVectorToSymbolicExpressionTree();
79      BoolMatrix world = WorldParameter.ActualValue;
80      IntValue maxTimeSteps = MaxTimeStepsParameter.ActualValue;
81 
82      AntInterpreter interpreter = new AntInterpreter();
83      interpreter.MaxTimeSteps   = maxTimeSteps.Value;
84      interpreter.World          = world;
85      interpreter.Expression     = expression;
86      interpreter.Run();
87
88      QualityParameter.ActualValue = new DoubleValue(interpreter.FoodEaten);
89      return null;
90    }
91   
92   
93    /// <summary>
94    /// Maps an integer vector to a symbolic expression tree, using a
95    /// genotype-to-phenotype mapper.
96    /// </summary>
97    /// <returns>solution tree</returns>
98    private SymbolicExpressionTree MapIntegerVectorToSymbolicExpressionTree() {
99     
100      ISymbolicExpressionGrammar grammar = SymbolicExpressionTreeGrammarParameter.ActualValue;
101      SymbolicExpressionTree     tree    = new SymbolicExpressionTree();
102      IntegerVector integerVectorGenome  = IntegerVectorParameter.ActualValue;
103      var rootNode  = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
104      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
105      rootNode.AddSubtree(startNode);
106      tree.Root = rootNode;
107     
108      int genotypeIndex    = 0;
109      int currSubtreeCount = 1;
110     
111      MapGenoToPhenoDepthFirstRec(startNode, integerVectorGenome,
112                                  grammar, integerVectorGenome.Length,
113                                  ref genotypeIndex, ref currSubtreeCount);
114     
115      SymbolicExpressionTreeParameter.ActualValue = tree;
116      return tree;
117    }
118   
119   
120    /// <summary>
121    /// Genotype-to-Phenotype mapper (recursive depth-first approach).
122    /// Appends maximum allowed children (non-terminal symbols) to
123    /// <paramref name="currentNode"/>, as long as <paramref name="currSubtreeCount"/>
124    /// doesn't exceed <paramref name="maxSubtreeCount"/>.
125    /// If at most <paramref name="maxSubtreeCount"/> subtrees were created,
126    /// each non-full node is filled with randomly chosen nodes
127    /// (non-terminal and terminal), and each non-terminal node is again filled with a terminal node.
128    /// </summary>
129    /// <param name="currentNode">current parent node</param>
130    /// <param name="integerVectorGenome">integer vector used for mapping</param>
131    /// <param name="grammar">grammar definition to determine the allowed child symbols for currentNode </param>
132    /// <param name="maxSubtreeCount">maximum allowed subtrees (= number of used genomes)</param>
133    /// <param name="genotypeIndex">current index in integer vector</param>
134    /// <param name="currSubtreeCount">number of already determined subtrees (filled or still incomplete)</param>
135    private void MapGenoToPhenoDepthFirstRec(ISymbolicExpressionTreeNode currentNode,
136                                             IntegerVector integerVectorGenome,
137                                             ISymbolicExpressionGrammar grammar,
138                                             int maxSubtreeCount,
139                                             ref int genotypeIndex,
140                                             ref int currSubtreeCount) {
141      if (currSubtreeCount < maxSubtreeCount) {
142     
143        var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
144       
145        if ((currSubtreeCount + newNode.Symbol.MaximumArity) > maxSubtreeCount) {
146          // TODO: maybe check, if there is any node, which fits in the tree yet
147          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));
148        } else {
149          currentNode.AddSubtree(newNode);
150          genotypeIndex++;
151          currSubtreeCount += newNode.Symbol.MaximumArity;
152       
153          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
154            MapGenoToPhenoDepthFirstRec(newNode, integerVectorGenome,
155                                        grammar, maxSubtreeCount,
156                                        ref genotypeIndex, ref currSubtreeCount);
157          }
158        }
159       
160      } else {
161        while (currentNode.Symbol.MaximumArity > currentNode.SubtreeCount) {
162          var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
163          currentNode.AddSubtree(newNode);
164          genotypeIndex++;
165          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
166            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));
167          }
168        }
169      }
170    }
171   
172   
173    /// <summary>
174    /// Randomly returns a terminal node for the given <paramref name="parentNode"/>.
175    /// (A terminal has got a minimum and maximum arity of 0.)
176    /// </summary>
177    /// <param name="parentNode">parent node for which a child node is returned randomly</param>
178    /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>
179    /// <returns>randomly chosen terminal node with arity 0</returns>
180    private ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
181                                                              ISymbolicExpressionGrammar  grammar) {
182      var possibleSymbolsList = from   s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
183                                where  s.MaximumArity == 0
184                                where  s.MinimumArity == 0
185                                select s;
186      // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen?
187      return possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();
188    }
189   
190   
191    /// <summary>
192    /// Utility method, which returns the number of elements of <paramref name="symbolList"/>.
193    /// </summary>
194    /// <param name="symbolList">enumerable symbol list to count the elements for</param>
195    /// <returns>number of elements in parameter symbolList</returns>
196    private int GetNumberOfAllowedChildSymbols(IEnumerable<ISymbol> symbolList) {
197      int count = 0;
198      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
199        while (enumerator.MoveNext()) {
200          count++;
201        }
202      }
203      return count;
204    }
205   
206   
207    /// <summary>
208    /// Returns a randomly chosen child node for the given <paramref name="parentNode"/>.
209    /// </summary>
210    /// <param name="parentNode">parent node to find a child node randomly for</param>
211    /// <param name="integerVectorGenome">integer vector to map to production rules</param>
212    /// <param name="grammar">grammar definition used to define the allowed child symbols</param>
213    /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>
214    /// <returns></returns>
215    private ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,
216                                                        IntegerVector integerVectorGenome,
217                                                        ISymbolicExpressionGrammar grammar,
218                                                        int genotypeIndex) {
219     
220      var symbolList    = grammar.GetAllowedChildSymbols(parentNode.Symbol);
221      int prodRuleCount = GetNumberOfAllowedChildSymbols(symbolList);
222      int prodRuleIndex = integerVectorGenome[genotypeIndex % integerVectorGenome.Length] % prodRuleCount;
223      int currentIndex  = 0;
224     
225      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
226        while (enumerator.MoveNext() && (currentIndex != prodRuleIndex)) {
227          currentIndex++;
228        }
229        return enumerator.Current.CreateTreeNode();
230      }
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.