#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(); } } } }