Changeset 10022

Timestamp:

10/03/13 22:47:11 (11 years ago)

Author:

sawinkle

Message:

#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

Location:

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution

Files:

• GEArtificialAntProblem.cs (modified) (5 diffs)
• GEEvaluator.cs (modified) (5 diffs)
• HeuristicLab.Problems.GrammaticalEvolution-3.3.csproj (modified) (1 diff)

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEArtificialAntProblem.cs

@@ -86 +86 @@
       get { return (IValueParameter<IntValue>)Parameters["MaximumExpressionLength"]; }
     }
-    public IValueParameter<IntValue> MaxExpressionDepthParameter {
-      get { return (IValueParameter<IntValue>)Parameters["MaximumExpressionDepth"]; }
-    }
     public IValueParameter<IntValue> MaxFunctionDefinitionsParameter {
       get { return (IValueParameter<IntValue>)Parameters["MaximumFunctionDefinitions"]; }
@@ -104 +101 @@
       get { return (IValueParameter<IntMatrix>)Parameters["Bounds"]; }
     }
-    
     #endregion
 
@@ -119 +115 @@
       get { return MaxExpressionLengthParameter.Value; }
       set { MaxExpressionLengthParameter.Value = value; }
-    }
-    public IntValue MaxExpressionDepth {
-      get { return MaxExpressionDepthParameter.Value; }
-      set { MaxExpressionDepthParameter.Value = value; }
     }
     public IntValue MaxFunctionDefinitions {
@@ -174 +166 @@
       : base(new GEEvaluator(), new UniformRandomIntegerVectorCreator()) {
       BoolMatrix world = new BoolMatrix(santaFeAntTrail);
-      Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(100)));
-      Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionDepth", "Maximal depth of the expression to control the artificial ant.", new IntValue(10)));
+      Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(30)));
       Parameters.Add(new ValueParameter<IntValue>("MaximumFunctionDefinitions", "Maximal number of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
       Parameters.Add(new ValueParameter<IntValue>("MaximumFunctionArguments", "Maximal number of arguments of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
@@ -181 +172 @@
       Parameters.Add(new ValueParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items.", world));
       Parameters.Add(new ValueParameter<IntValue>("MaximumTimeSteps", "The number of time steps the artificial ant has available to collect all food items.", new IntValue(600)));
-      IntMatrix m = new IntMatrix(1,2);
-      m[0,0] = 1;
-      m[0,1] = 10;
-      Parameters.Add(new ValueParameter<IntMatrix>("Bounds", "", m));
+      IntMatrix m = new IntMatrix(new int[,]{{0,100}});
+      Parameters.Add(new ValueParameter<IntMatrix>("Bounds", "The integer number range in which the single genomes of a genotype are created.", m));
       
       Maximization.Value = true;

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEEvaluator.cs

@@ -30 +30 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Encodings.IntegerVectorEncoding;
+using System.Collections.Generic;
+using System.Linq;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GrammaticalEvolution {
@@ -37 +40 @@
     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 {
@@ -56 +63 @@
       get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionTreeGrammar"]; }
     }
-  #endregion
-    
+    #endregion
+  
     [StorableConstructor]
     protected GEEvaluator(bool deserializing) : base(deserializing) { }
@@ -73 +80 @@
 
     public sealed override IOperation Apply() {
-      SymbolicExpressionTree expression = ConvertIntegerVectorToSymbolicExpressionTree(SymbolicExpressionTreeGrammarParameter.ActualValue);
+      SymbolicExpressionTree expression = MapIntegerVectorToSymbolicExpressionTree();
       BoolMatrix world = WorldParameter.ActualValue;
       IntValue maxTimeSteps = MaxTimeStepsParameter.ActualValue;
@@ -89 +96 @@
     
     /// <summary>
-    /// Genotype-to-Phenotype mapper.
-    /// </summary>
-    /// <param name="grammar">grammar definition used to guide the mapping process</param>
+    /// Genotype-to-Phenotype mapper (depth-first approach).
+    /// </summary>
     /// <returns>solution tree</returns>
-    public SymbolicExpressionTree ConvertIntegerVectorToSymbolicExpressionTree(ISymbolicExpressionGrammar grammar) {
-      SymbolicExpressionTree tree = new SymbolicExpressionTree();
-      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
-      // if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
-      rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
+    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();
-      startNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
-      // if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
       rootNode.AddSubtree(startNode);
-      // PTC2(random, startNode, maxTreeLength, maxTreeDepth);
       tree.Root = rootNode;
-      var moveNode = grammar.GetSymbol("Move").CreateTreeNode();
-      startNode.AddSubtree(moveNode);
+      
+      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();
+      }
+    }
   }
 }

branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution-3.3.csproj

@@ -151 +151 @@
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.ArtificialAnt-3.4.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Random-3.3">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core">