Changeset 4106 for trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

Timestamp:

07/26/10 16:18:45 (14 years ago)

Author:

gkronber

Message:

Fixed bugs in SubtreeCrossover, ArgumentCreater and ArgumentDuplicater and updated unit tests for symbolic expression tree operators. #1103

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3

Files:

• ArchitectureManipulators/ArgumentCreater.cs (modified) (1 diff)
• ArchitectureManipulators/ArgumentDuplicater.cs (modified) (2 diffs)
• Crossovers/SubtreeCrossover.cs (modified) (2 diffs)
• SymbolicExpressionTreeNode.cs (modified) (9 diffs)
• SymbolicExpressionTreeTopLevelNode.cs (modified) (1 diff)
• Symbols/InvokeFunction.cs (modified) (1 diff)
• Tests/Grammars.cs (modified) (2 diffs)
• Tests/ProbabilisticTreeCreaterTest.cs (modified) (1 diff)
• Tests/Util.cs (modified) (3 diffs)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentCreater.cs

@@ -83 +83 @@
       selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedChildIndex);
       selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedChildIndex, newArgNode);
+
       // find all invocations of the selected ADF and attach a cloned version of the replaced branch (with all argument-nodes expanded)
       var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                            where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
                             select node;
-      foreach (var invocationNode in invocationNodes) {
-        // append a new argument branch after expanding all argument nodes
-        var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
-        clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
-        invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
+      // do this repeatedly until no matching invocations are found      
+      while (invocationNodes.Count() > 0) {
+        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
+        foreach (var invocationNode in invocationNodes) {
+          // append a new argument branch after expanding all argument nodes
+          var clonedBranch = (SymbolicExpressionTreeNode)replacedBranch.Clone();
+          clonedBranch = ReplaceArgumentsInBranch(clonedBranch, invocationNode.SubTrees);
+          invocationNode.InsertSubTree(newArgumentIndex, clonedBranch);
+          newlyAddedBranches.Add(clonedBranch);
+        }
+        invocationNodes = from newlyAddedBranch in newlyAddedBranches
+                          from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
+                          where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                          where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
+                          select node;
       }
       // increase expected number of arguments of function defining branch

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/ArgumentDuplicater.cs

@@ -25 +25 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
@@ -80 +81 @@
       var invocationNodes = from node in symbolicExpressionTree.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
                             where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                            where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
                             select node;
-      foreach (var invokeNode in invocationNodes) {
-        var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
-        var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
-        invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
+      // do this repeatedly until no matching invocations are found      
+      while (invocationNodes.Count() > 0) {
+        List<SymbolicExpressionTreeNode> newlyAddedBranches = new List<SymbolicExpressionTreeNode>();
+        foreach (var invokeNode in invocationNodes) {
+          var argumentBranch = invokeNode.SubTrees[selectedArgumentSymbol.ArgumentIndex];
+          var clonedArgumentBranch = (SymbolicExpressionTreeNode)argumentBranch.Clone();
+          invokeNode.InsertSubTree(newArgumentIndex, clonedArgumentBranch);
+          newlyAddedBranches.Add(clonedArgumentBranch);
+        }
+        invocationNodes = from newlyAddedBranch in newlyAddedBranches
+                          from node in newlyAddedBranch.IterateNodesPrefix().OfType<InvokeFunctionTreeNode>()
+                          where node.Symbol.FunctionName == selectedDefunBranch.FunctionName
+                          where node.SubTrees.Count == selectedDefunBranch.NumberOfArguments
+                          select node;
       }
       // register the new argument symbol and increase the number of arguments of the ADF

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

@@ -90 +90 @@
     private static bool IsMatchingPointType(SymbolicExpressionTreeNode parent, int replacedSubtreeIndex, SymbolicExpressionTreeNode branch) {
       // check syntax constraints of direct parent - child relation
-      if (!parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
+      if (!parent.Grammar.ContainsSymbol(branch.Symbol) ||
+          !parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
 
       bool result = true;
@@ -97 +98 @@
         result =
           result &&
+          parent.Grammar.ContainsSymbol(n.Symbol) &&
           n.SubTrees.Count >= parent.Grammar.GetMinSubtreeCount(n.Symbol) &&
-          n.SubTrees.Count <= parent.Grammar.GetMaxSubtreeCount(n.Symbol) &&
-          parent.Grammar.ContainsSymbol(n.Symbol);
+          n.SubTrees.Count <= parent.Grammar.GetMaxSubtreeCount(n.Symbol);
       });
       return result;

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

@@ -51 +51 @@
     }
 
-    public SymbolicExpressionTreeNode() {
+    internal SymbolicExpressionTreeNode() {
       // don't allocate subtrees list here!
       // because we don't want to allocate it in terminal nodes
@@ -85 +85 @@
     }
 
-    internal virtual ISymbolicExpressionGrammar Grammar {
+    public virtual ISymbolicExpressionGrammar Grammar {
       get { return parent.Grammar; }
       set { throw new NotSupportedException("Grammar can be set only for SymbolicExpressionTreeTopLevelNodes."); }
@@ -94 +94 @@
       else {
         size = 1;
-        for (int i = 0; i < SubTrees.Count; i++) size += (short)SubTrees[i].GetSize();
+        if (SubTrees != null) {
+          for (int i = 0; i < SubTrees.Count; i++) size += (short)SubTrees[i].GetSize();
+        }
         return size;
       }
@@ -102 +104 @@
       if (height > 0) return height;
       else {
-        for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
+        if (SubTrees != null) {
+          for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
+        }
         height++;
         return height;
@@ -112 +116 @@
 
     public virtual void AddSubTree(SymbolicExpressionTreeNode tree) {
-      subTrees.Add(tree);
+      SubTrees.Add(tree);
       tree.Parent = this;
       ResetCachedValues();
@@ -118 +122 @@
 
     public virtual void InsertSubTree(int index, SymbolicExpressionTreeNode tree) {
-      subTrees.Insert(index, tree);
+      SubTrees.Insert(index, tree);
       tree.Parent = this;
       ResetCachedValues();
@@ -124 +128 @@
 
     public virtual void RemoveSubTree(int index) {
-      subTrees[index].Parent = null;
-      subTrees.RemoveAt(index);
+      SubTrees[index].Parent = null;
+      SubTrees.RemoveAt(index);
       ResetCachedValues();
     }
@@ -137 +141 @@
     public void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
       a(this);
-      for (int i = 0; i < SubTrees.Count; i++) {
-        SubTrees[i].ForEachNodePrefix(a);
+      if (SubTrees != null) {
+        for (int i = 0; i < SubTrees.Count; i++) {
+          SubTrees[i].ForEachNodePrefix(a);
+        }
       }
     }
@@ -149 +155 @@
 
     public void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
-      for (int i = 0; i < SubTrees.Count; i++) {
-        SubTrees[i].ForEachNodePrefix(a);
+      if (SubTrees != null) {
+        for (int i = 0; i < SubTrees.Count; i++) {
+          SubTrees[i].ForEachNodePostfix(a);
+        }
       }
       a(this);

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeTopLevelNode.cs

@@ -37 +37 @@
     [Storable]
     private ISymbolicExpressionGrammar grammar;
-    internal override ISymbolicExpressionGrammar Grammar {
+    public override ISymbolicExpressionGrammar Grammar {
       get { return grammar; }
       set { grammar = value; }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Symbols/InvokeFunction.cs

@@ -32 +32 @@
   public sealed class InvokeFunction : ReadOnlySymbol {
     public const string InvokeFunctionName = "InvokeFunction";
-    public const string InvokeFunctionDescription = "Symbol that the invokation of another function.";
+    public const string InvokeFunctionDescription = "Symbol that the invocation of another function.";
     public override bool CanChangeName {
       get {

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Grammars.cs

@@ -26 +26 @@
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
   public static class Grammars {
-    private class Addition : Symbol { }
-    private class Subtraction : Symbol { }
-    private class Multiplication : Symbol { }
-    private class Division : Symbol { }
-    private class Terminal : Symbol { }
+    private class Addition : Symbol { public Addition() : base("Addition", "") { } }
+    private class Subtraction : Symbol { public Subtraction() : base("Subtraction", "") { } }
+    private class Multiplication : Symbol { public Multiplication() : base("Multiplication", "") { } }
+    private class Division : Symbol { public Division() : base("Division", "") { } }
+    private class Terminal : Symbol { public Terminal() : base("Terminal", "") { } }
 
     private class SimpleArithmeticGrammar : DefaultSymbolicExpressionGrammar {
@@ -89 +89 @@
       return g;
     }
-
-    public static void HasValidAdfGrammars(SymbolicExpressionTree tree) {
-      //Assert.AreEqual(tree.Root.Grammar.Symbols.Count(), 8);
-      //Assert.AreEqual(tree.Root.GetAllowedSymbols(0).Count(), 1); // only the start symbol is allowed
-      //// we allow 3 ADF branches
-      //Assert.AreEqual(tree.Root.GetAllowedSymbols(1).Count(), 1); // only the defun branch is allowed
-      //Assert.AreEqual(tree.Root.GetAllowedSymbols(2).Count(), 1); // only the defun symbol is allowed
-      //Assert.AreEqual(tree.Root.GetAllowedSymbols(3).Count(), 1); // only the defun symbol is allowed
-      //foreach (var subtree in tree.Root.SubTrees) {
-      //  // check consistency of each sub-tree grammar independently
-      //  var allowedSymbols = subtree.GetAllowedSymbols(0);
-      //  int numberOfAllowedSymbols = allowedSymbols.Count();
-      //  foreach (var parent in allowedSymbols) {
-      //    for (int argIndex = 0; argIndex < subtree.Grammar.GetMaxSubtreeCount(parent); argIndex++) {
-      //      var allowedChildren = from child in subtree.Grammar.Symbols
-      //                            where subtree.Grammar.IsAllowedChild(parent, child, argIndex)
-      //                            select child;
-      //      Assert.AreEqual(numberOfAllowedSymbols, allowedChildren.Count());
-      //    }
-      //  }
-      //}
-    }
-
   }
 }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/ProbabilisticTreeCreaterTest.cs

@@ -76 +76 @@
       for (int i = 0; i < POPULATION_SIZE; i++) {
         var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
-        Grammars.HasValidAdfGrammars(tree);
         Util.IsValid(tree);
         randomTrees.Add(tree);

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Tests/Util.cs

@@ -26 +26 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._3.Tests {
@@ -114 +115 @@
 
     public static void IsValid(SymbolicExpressionTree tree) {
-      Grammars.HasValidAdfGrammars(tree);
+      foreach (var defunTreeNode in tree.Root.SubTrees.OfType<DefunTreeNode>()) {
+        int arity = defunTreeNode.NumberOfArguments;
+        var invoke = new InvokeFunction(defunTreeNode.FunctionName);
+        foreach (var otherRootNode in tree.Root.SubTrees) {
+          if (otherRootNode.Grammar.ContainsSymbol(invoke)) {
+            Assert.IsTrue(otherRootNode.Grammar.GetMinSubtreeCount(invoke) == arity);
+            Assert.IsTrue(otherRootNode.Grammar.GetMaxSubtreeCount(invoke) == arity);
+          }
+        }
+      }
       //Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol);
       //foreach (var subtree in tree.Root.SubTrees)
@@ -122 +132 @@
 
     public static void IsValid(SymbolicExpressionTreeNode treeNode) {
-      //var matchingSymbol = (from symb in treeNode.Grammar.Symbols
-      //                      where symb.Name == treeNode.Symbol.Name
-      //                      select symb).SingleOrDefault();
-      //Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
-      //Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
+      var matchingSymbol = (from symb in treeNode.Grammar.Symbols
+                            where symb.Name == treeNode.Symbol.Name
+                            select symb).SingleOrDefault();
+      Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
+      Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
       for (int i = 0; i < treeNode.SubTrees.Count; i++) {
         Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));