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

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

#2109:

  • simplified GEArtificialAntProblem and removed some unused code (e.g. parameter MaximumExpressionDepth is not necessary for an IntegerVector)
  • extended GEEvaluator to perform a complete, recursive Genotype-To-Phenotype mapping (depth-first approach); currently no "wrapping" of the integer vector is possible; a full tree with the maximum possible nodes filled in is generated, dependent on the integer vector; the Interpreter, Analysers and other classes get reused
File size: 10.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 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    // TODO: replace these horrible global variables ...
43    private static int genotypeIndex    = 0;
44    private static int currSubtreeCount = 1;
45   
46    #region Parameter Properties
47    public ILookupParameter<DoubleValue> QualityParameter {
48      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
49    }
50    public ILookupParameter<IntegerVector> IntegerVectorParameter {
51      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
52    }
53    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
54      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
55    }
56    public ILookupParameter<BoolMatrix> WorldParameter {
57      get { return (ILookupParameter<BoolMatrix>)Parameters["World"]; }
58    }
59    public ILookupParameter<IntValue> MaxTimeStepsParameter {
60      get { return (ILookupParameter<IntValue>)Parameters["MaxTimeSteps"]; }
61    }
62    public IValueLookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionTreeGrammarParameter {
63      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionTreeGrammar"]; }
64    }
65    #endregion
66 
67    [StorableConstructor]
68    protected GEEvaluator(bool deserializing) : base(deserializing) { }
69    protected GEEvaluator(GEEvaluator original, Cloner cloner) : base(original, cloner) { }
70    public override IDeepCloneable Clone(Cloner cloner) { return new GEEvaluator(this, cloner); }
71    public GEEvaluator()
72      : base() {
73      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the evaluated artificial ant solution."));
74      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The artificial ant solution encoded as an integer vector genome."));
75      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The artificial ant solution encoded as a symbolic expression tree that should be evaluated"));
76      Parameters.Add(new LookupParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items."));
77      Parameters.Add(new LookupParameter<IntValue>("MaxTimeSteps", "The maximal number of time steps that the artificial ant should be simulated."));
78      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>("SymbolicExpressionTreeGrammar", "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
79    }
80
81    public sealed override IOperation Apply() {
82      SymbolicExpressionTree expression = MapIntegerVectorToSymbolicExpressionTree();
83      BoolMatrix world = WorldParameter.ActualValue;
84      IntValue maxTimeSteps = MaxTimeStepsParameter.ActualValue;
85 
86      AntInterpreter interpreter = new AntInterpreter();
87      interpreter.MaxTimeSteps   = maxTimeSteps.Value;
88      interpreter.World          = world;
89      interpreter.Expression     = expression;
90      interpreter.Run();
91
92      QualityParameter.ActualValue = new DoubleValue(interpreter.FoodEaten);
93      return null;
94    }
95   
96   
97    /// <summary>
98    /// Genotype-to-Phenotype mapper (depth-first approach).
99    /// </summary>
100    /// <returns>solution tree</returns>
101    private SymbolicExpressionTree MapIntegerVectorToSymbolicExpressionTree() {
102     
103      ISymbolicExpressionGrammar grammar = SymbolicExpressionTreeGrammarParameter.ActualValue;
104      SymbolicExpressionTree     tree    = new SymbolicExpressionTree();
105      IntegerVector integerVectorGenome  = IntegerVectorParameter.ActualValue;
106      var rootNode  = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
107      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
108      rootNode.AddSubtree(startNode);
109      tree.Root = rootNode;
110     
111      genotypeIndex    = 0;
112      currSubtreeCount = 1;
113     
114      MapGenoToPhenoDepthFirstRec(startNode, integerVectorGenome,
115                                  grammar, integerVectorGenome.Length);
116     
117      SymbolicExpressionTreeParameter.ActualValue = tree;
118      return tree;
119    }
120   
121   
122    private void MapGenoToPhenoDepthFirstRec(ISymbolicExpressionTreeNode currentNode,
123                                             IntegerVector integerVectorGenome,
124                                             ISymbolicExpressionGrammar grammar,
125                                             int maxSubtreeCount) {
126      if (currSubtreeCount < maxSubtreeCount) {
127     
128        var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
129       
130        if ((currSubtreeCount + newNode.Symbol.MaximumArity) > maxSubtreeCount) {
131          // TODO: maybe check, if there is any node, which fits in the tree yet
132          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));
133        } else {
134          currentNode.AddSubtree(newNode);
135          genotypeIndex++;
136          currSubtreeCount += newNode.Symbol.MaximumArity;
137       
138          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
139            MapGenoToPhenoDepthFirstRec(newNode, integerVectorGenome,
140                                        grammar, maxSubtreeCount);
141          }
142        }
143       
144      } else {
145        while (currentNode.Symbol.MaximumArity > currentNode.SubtreeCount) {
146          var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
147          currentNode.AddSubtree(newNode);
148          genotypeIndex++;
149          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
150            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));
151          }
152        }
153      }
154    }
155   
156   
157    /// <summary>
158    /// Randomly returns a terminal node for the given parentNode.
159    /// (A terminal has got a minimum and maximum arity of 0.)
160    /// </summary>
161    /// <param name="parentNode">parent node for which a child node is returned randomly</param>
162    /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>
163    /// <returns>randomly chosen terminal node with arity 0</returns>
164    private ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
165                                                              ISymbolicExpressionGrammar  grammar) {
166      var possibleSymbolsList = from   s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
167                                where  s.MaximumArity == 0
168                                where  s.MinimumArity == 0
169                                select s;
170      // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen?
171      return possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();
172    }
173   
174   
175    /// <summary>
176    /// Utility method, which returns the number of elements of the parameter symbolList.
177    /// </summary>
178    /// <param name="symbolList">enumerable symbol list to count the elements for</param>
179    /// <returns>number of elements in parameter symbolList</returns>
180    private int GetNumberOfAllowedChildSymbols(IEnumerable<ISymbol> symbolList) {
181      int count = 0;
182      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
183        while (enumerator.MoveNext()) {
184          count++;
185        }
186      }
187      return count;
188    }
189   
190   
191    /// <summary>
192    /// Returns a randomly chosen child node for the given parentNode.
193    /// </summary>
194    /// <param name="parentNode">parent node to find a child node randomly for</param>
195    /// <param name="integerVectorGenome">integer vector to map to production rules</param>
196    /// <param name="grammar">grammar definition used to define the allowed child symbols</param>
197    /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>
198    /// <returns></returns>
199    private ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,
200                                                        IntegerVector integerVectorGenome,
201                                                        ISymbolicExpressionGrammar grammar,
202                                                        int genotypeIndex) {
203     
204      var symbolList    = grammar.GetAllowedChildSymbols(parentNode.Symbol);
205      int prodRuleCount = GetNumberOfAllowedChildSymbols(symbolList);
206      int prodRuleIndex = integerVectorGenome[genotypeIndex] % prodRuleCount;
207      int currentIndex  = 0;
208     
209      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
210        while (enumerator.MoveNext() && (currentIndex != prodRuleIndex)) {
211          currentIndex++;
212        }
213        return enumerator.Current.CreateTreeNode();
214      }
215    }
216  }
217}
Note: See TracBrowser for help on using the repository browser.