Changeset 5567

Timestamp:

02/28/11 17:11:56 (14 years ago)

Author:

gkronber

Message:

#1418 improved ChangeNodeTypeManipulation operator to make unit test succeed.

Location:

branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4

Files:

• Manipulators/ChangeNodeTypeManipulation.cs (modified) (2 diffs)
• Tests/ChangeNodeTypeManipulationTest.cs (modified) (3 diffs)
• Tests/Grammars.cs (modified) (2 diffs)

branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs

@@ -46 +46 @@
 
     public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
+      // select any node as parent (except the root node)
+      var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
+                                let subtreeCount = parent.SubTrees.Count()
+                                from subtreeIndex in Enumerable.Range(0, subtreeCount)
+                                let subtree = parent.GetSubTree(subtreeIndex)
+                                let existingSubtreeCount = subtree.SubTrees.Count()
+                                // find possible symbols for the node (also considering the existing branches below it)
+                                let allowedSymbols = (from symbol in parent.Grammar.GetAllowedSymbols(parent.Symbol, subtreeIndex)
+                                                      // do not replace the existing symbol with itself
+                                                      where symbol.Name != subtree.Symbol.Name
+                                                      where existingSubtreeCount <= parent.Grammar.GetMaxSubtreeCount(symbol)
+                                                      where existingSubtreeCount >= parent.Grammar.GetMinSubtreeCount(symbol)
+                                                      // keep only symbols that are still possible considering the existing sub-trees
+                                                      where (from existingSubtreeIndex in Enumerable.Range(0, existingSubtreeCount)
+                                                             let existingSubtree = subtree.GetSubTree(existingSubtreeIndex)
+                                                             select parent.Grammar.IsAllowedChild(symbol, existingSubtree.Symbol, existingSubtreeIndex))
+                                                             .All(x => x == true)
+                                                      select symbol)
+                                                      .ToList()
+                                where allowedSymbols.Count() > 0
+                                select new { Parent = parent, Child = subtree, Index = subtreeIndex, AllowedSymbols = allowedSymbols })
+                               .ToList();
+      if (manipulationPoints.Count == 0) { return; }
+      var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
 
-      // select any node as parent (except the root node)
-      var manipulationPoint = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
-                               from subtree in parent.SubTrees
-                               select new { Parent = parent, Node = subtree, Index = parent.IndexOfSubTree(subtree) })
-                               .SelectRandom(random);
-      int subTreeCount = manipulationPoint.Node.SubTrees.Count();
-      // find possible symbols for the node (also considering the existing branches below it)
-      var allowedSymbols = from symbol in manipulationPoint.Parent.Grammar.GetAllowedSymbols(manipulationPoint.Parent.Symbol, manipulationPoint.Index)
-                           where subTreeCount <= manipulationPoint.Node.Grammar.GetMaxSubtreeCount(symbol)
-                           where subTreeCount >= manipulationPoint.Node.Grammar.GetMinSubtreeCount(symbol)
-                           select symbol;
-
-      if (allowedSymbols.Count() == 0) {
-        return;
-      }
-      var node = manipulationPoint.Node;
-      // keep only symbols that are still possible considering the existing sub-trees
-      var constrainedSymbols = (from symbol in allowedSymbols
-                                let disallowedSubtrees =
-                                      from subtree in node.SubTrees
-                                      where !node.Grammar.IsAllowedChild(symbol, subtree.Symbol, node.IndexOfSubTree(subtree))
-                                      select subtree
-                                where disallowedSubtrees.Count() == 0
-                                select symbol)
-                               .ToList();
-      if (constrainedSymbols.Count() == 0) {
-        return;
-      }
-      var weights = constrainedSymbols.Select(s => s.InitialFrequency).ToList();
-      var newSymbol =  constrainedSymbols.SelectRandom(weights, random);
+      var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
+      var newSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
 
       // replace the old node with the new node
@@ -82 +78 @@
       if (newNode.HasLocalParameters)
         newNode.ResetLocalParameters(random);
-      foreach (var subtree in node.SubTrees)
+      foreach (var subtree in selectedManipulationPoint.Child.SubTrees)
         newNode.AddSubTree(subtree);
-      manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index);
-      manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, newNode);
+      selectedManipulationPoint.Parent.RemoveSubTree(selectedManipulationPoint.Index);
+      selectedManipulationPoint.Parent.InsertSubTree(selectedManipulationPoint.Index, newNode);
     }
   }

branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Tests/ChangeNodeTypeManipulationTest.cs

@@ -53 +53 @@
       var grammar = Grammars.CreateArithmeticAndAdfGrammar();
       var random = new MersenneTwister(31415);
+      int failedEvents = 0;
       for (int i = 0; i < POPULATION_SIZE; i++) {
         var tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_LENGTH, MAX_TREE_DEPTH, 3, 3);
@@ -58 +59 @@
         ChangeNodeTypeManipulation.ChangeNodeType(random, tree);
         string manipulatedTree = formatter.Format(tree);
-        Assert.IsFalse(originalTree == manipulatedTree);
+        if (originalTree == manipulatedTree) failedEvents++;
         Util.IsValid(tree);
         trees.Add(tree);
       }
       Console.WriteLine("ChangeNodeTypeManipulation: " + Environment.NewLine +
+        "Failed events: " + failedEvents * 100.0 / POPULATION_SIZE + " %" + Environment.NewLine +
         Util.GetSizeDistributionString(trees, 105, 5) + Environment.NewLine +
         Util.GetFunctionDistributionString(trees) + Environment.NewLine +
@@ -68 +70 @@
         Util.GetTerminalDistributionString(trees) + Environment.NewLine
         );
+      Assert.IsTrue(failedEvents * 100.0 / POPULATION_SIZE < 5.0); // only max 5% failed mutations are allowed
     }
   }

branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Tests/Grammars.cs

@@ -23 +23 @@
 using HeuristicLab.Common;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding_3._4.Tests {
@@ -59 +60 @@
       public override IDeepCloneable Clone(Cloner cloner) {
         return new Terminal(this, cloner);
+      }
+
+      public override ISymbolicExpressionTreeNode CreateTreeNode() {
+        return new TerminalNode(this);
+      }
+    }
+
+    private class TerminalNode : SymbolicExpressionTreeTerminalNode {
+      public override bool HasLocalParameters { get { return true; } }
+      private double value;
+      protected TerminalNode(TerminalNode original, Cloner cloner)
+        : base(original, cloner) {
+        this.value = original.value;
+      }
+      [StorableConstructor]
+      protected TerminalNode(bool deserializing) : base(deserializing) { }
+      public TerminalNode(Terminal symbol) : base(symbol) { }
+
+      public override IDeepCloneable Clone(Cloner cloner) {
+        return new TerminalNode(this, cloner);
+      }
+      public override void ResetLocalParameters(Core.IRandom random) {
+        base.ResetLocalParameters(random);
+        value = random.NextDouble();
+      }
+      public override void ShakeLocalParameters(Core.IRandom random, double shakingFactor) {
+        base.ShakeLocalParameters(random, shakingFactor);
+        value = random.NextDouble();
+      }
+      public override string ToString() {
+        return value.ToString("E4");
       }
     }