#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 .
*/
#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 QualityParameter {
get { return (ILookupParameter)Parameters["Quality"]; }
}
public ILookupParameter IntegerVectorParameter {
get { return (ILookupParameter)Parameters["IntegerVector"]; }
}
public ILookupParameter SymbolicExpressionTreeParameter {
get { return (ILookupParameter)Parameters["SymbolicExpressionTree"]; }
}
public ILookupParameter WorldParameter {
get { return (ILookupParameter)Parameters["World"]; }
}
public ILookupParameter MaxTimeStepsParameter {
get { return (ILookupParameter)Parameters["MaxTimeSteps"]; }
}
public IValueLookupParameter SymbolicExpressionTreeGrammarParameter {
get { return (IValueLookupParameter)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("Quality", "The quality of the evaluated artificial ant solution."));
Parameters.Add(new LookupParameter("IntegerVector", "The artificial ant solution encoded as an integer vector genome."));
Parameters.Add(new LookupParameter("SymbolicExpressionTree", "The artificial ant solution encoded as a symbolic expression tree that should be evaluated"));
Parameters.Add(new LookupParameter("World", "The world for the artificial ant with scattered food items."));
Parameters.Add(new LookupParameter("MaxTimeSteps", "The maximal number of time steps that the artificial ant should be simulated."));
Parameters.Add(new ValueLookupParameter("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;
}
///
/// Genotype-to-Phenotype mapper (depth-first approach).
///
/// solution tree
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));
}
}
}
}
///
/// Randomly returns a terminal node for the given parentNode.
/// (A terminal has got a minimum and maximum arity of 0.)
///
/// parent node for which a child node is returned randomly
/// grammar definition to determine the allowed child symbols for parentNode
/// randomly chosen terminal node with arity 0
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();
}
///
/// Utility method, which returns the number of elements of the parameter symbolList.
///
/// enumerable symbol list to count the elements for
/// number of elements in parameter symbolList
private int GetNumberOfAllowedChildSymbols(IEnumerable symbolList) {
int count = 0;
using (IEnumerator enumerator = symbolList.GetEnumerator()) {
while (enumerator.MoveNext()) {
count++;
}
}
return count;
}
///
/// Returns a randomly chosen child node for the given parentNode.
///
/// parent node to find a child node randomly for
/// integer vector to map to production rules
/// grammar definition used to define the allowed child symbols
/// index in the integer vector; can be greater than vector length
///
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 enumerator = symbolList.GetEnumerator()) {
while (enumerator.MoveNext() && (currentIndex != prodRuleIndex)) {
currentIndex++;
}
return enumerator.Current.CreateTreeNode();
}
}
}
}