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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Problems.ArtificialAnt;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.GrammaticalEvolution {
  [Item("GEArtificialAntEvaluator", "Evaluates an artificial ant solution, implemented in Grammatical Evolution.")]
  [StorableClass]
  public class GEEvaluator : SingleSuccessorOperator,
    ISingleObjectiveEvaluator, ISymbolicExpressionTreeGrammarBasedOperator {

    // TODO: replace these horrible global variables ...
    private static int genotypeIndex    = 0;
    private static int currSubtreeCount = 1;
    
    #region Parameter Properties
    public ILookupParameter<DoubleValue> QualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    public ILookupParameter<IntegerVector> IntegerVectorParameter {
      get { return (ILookupParameter<IntegerVector>)Parameters["IntegerVector"]; }
    }
    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
    }
    public ILookupParameter<BoolMatrix> WorldParameter {
      get { return (ILookupParameter<BoolMatrix>)Parameters["World"]; }
    }
    public ILookupParameter<IntValue> MaxTimeStepsParameter {
      get { return (ILookupParameter<IntValue>)Parameters["MaxTimeSteps"]; }
    }
    public IValueLookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionTreeGrammarParameter {
      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionTreeGrammar"]; }
    }
    #endregion
  
    [StorableConstructor]
    protected GEEvaluator(bool deserializing) : base(deserializing) { }
    protected GEEvaluator(GEEvaluator original, Cloner cloner) : base(original, cloner) { }
    public override IDeepCloneable Clone(Cloner cloner) { return new GEEvaluator(this, cloner); }
    public GEEvaluator()
      : base() {
      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the evaluated artificial ant solution."));
      Parameters.Add(new LookupParameter<IntegerVector>("IntegerVector", "The artificial ant solution encoded as an integer vector genome."));
      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The artificial ant solution encoded as a symbolic expression tree that should be evaluated"));
      Parameters.Add(new LookupParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items."));
      Parameters.Add(new LookupParameter<IntValue>("MaxTimeSteps", "The maximal number of time steps that the artificial ant should be simulated."));
      Parameters.Add(new ValueLookupParameter<ISymbolicExpressionGrammar>("SymbolicExpressionTreeGrammar", "The tree grammar that defines the correct syntax of symbolic expression trees that should be created."));
    }

    public sealed override IOperation Apply() {
      SymbolicExpressionTree expression = MapIntegerVectorToSymbolicExpressionTree();
      BoolMatrix world = WorldParameter.ActualValue;
      IntValue maxTimeSteps = MaxTimeStepsParameter.ActualValue;
 
      AntInterpreter interpreter = new AntInterpreter();
      interpreter.MaxTimeSteps   = maxTimeSteps.Value;
      interpreter.World          = world;
      interpreter.Expression     = expression;
      interpreter.Run();

      QualityParameter.ActualValue = new DoubleValue(interpreter.FoodEaten);
      return null;
    }
    
    
    /// <summary>
    /// Genotype-to-Phenotype mapper (depth-first approach).
    /// </summary>
    /// <returns>solution tree</returns>
    private SymbolicExpressionTree MapIntegerVectorToSymbolicExpressionTree() {
      
      ISymbolicExpressionGrammar grammar = SymbolicExpressionTreeGrammarParameter.ActualValue;
      SymbolicExpressionTree     tree    = new SymbolicExpressionTree();
      IntegerVector integerVectorGenome  = IntegerVectorParameter.ActualValue;
      var rootNode  = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
      rootNode.AddSubtree(startNode);
      tree.Root = rootNode;
      
      genotypeIndex    = 0;
      currSubtreeCount = 1;
      
      MapGenoToPhenoDepthFirstRec(startNode, integerVectorGenome,
                                  grammar, integerVectorGenome.Length);
     
      SymbolicExpressionTreeParameter.ActualValue = tree;
      return tree;
    }
    
    
    private void MapGenoToPhenoDepthFirstRec(ISymbolicExpressionTreeNode currentNode,
                                             IntegerVector integerVectorGenome,
                                             ISymbolicExpressionGrammar grammar,
                                             int maxSubtreeCount) {
      if (currSubtreeCount < maxSubtreeCount) {
      
        var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
        
        if ((currSubtreeCount + newNode.Symbol.MaximumArity) > maxSubtreeCount) {
          // TODO: maybe check, if there is any node, which fits in the tree yet
          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));
        } else {
          currentNode.AddSubtree(newNode);
          genotypeIndex++;
          currSubtreeCount += newNode.Symbol.MaximumArity;
        
          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
            MapGenoToPhenoDepthFirstRec(newNode, integerVectorGenome, 
                                        grammar, maxSubtreeCount);
          }
        }
        
      } else {
        while (currentNode.Symbol.MaximumArity > currentNode.SubtreeCount) {
          var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
          currentNode.AddSubtree(newNode);
          genotypeIndex++;
          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));
          }
        }
      }
    }
    
    
    /// <summary>
    /// Randomly returns a terminal node for the given parentNode.
    /// (A terminal has got a minimum and maximum arity of 0.)
    /// </summary>
    /// <param name="parentNode">parent node for which a child node is returned randomly</param>
    /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>
    /// <returns>randomly chosen terminal node with arity 0</returns>
    private ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
                                                              ISymbolicExpressionGrammar  grammar) {
      var possibleSymbolsList = from   s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
                                where  s.MaximumArity == 0
                                where  s.MinimumArity == 0
                                select s;
      // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen? 
      return possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();
    }
    
    
    /// <summary>
    /// Utility method, which returns the number of elements of the parameter symbolList.
    /// </summary>
    /// <param name="symbolList">enumerable symbol list to count the elements for</param>
    /// <returns>number of elements in parameter symbolList</returns>
    private int GetNumberOfAllowedChildSymbols(IEnumerable<ISymbol> symbolList) {
      int count = 0;
      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
        while (enumerator.MoveNext()) {
          count++;
        }
      }
      return count;
    }
    
    
    /// <summary>
    /// Returns a randomly chosen child node for the given parentNode.
    /// </summary>
    /// <param name="parentNode">parent node to find a child node randomly for</param>
    /// <param name="integerVectorGenome">integer vector to map to production rules</param>
    /// <param name="grammar">grammar definition used to define the allowed child symbols</param>
    /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>
    /// <returns></returns>
    private ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,
                                                        IntegerVector integerVectorGenome,
                                                        ISymbolicExpressionGrammar grammar,
                                                        int genotypeIndex) {
      
      var symbolList    = grammar.GetAllowedChildSymbols(parentNode.Symbol);
      int prodRuleCount = GetNumberOfAllowedChildSymbols(symbolList);
      int prodRuleIndex = integerVectorGenome[genotypeIndex] % prodRuleCount;
      int currentIndex  = 0;
      
      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
        while (enumerator.MoveNext() && (currentIndex != prodRuleIndex)) {
          currentIndex++;
        }
        return enumerator.Current.CreateTreeNode();
      }
    }
  }
}