Changeset 5411

Timestamp:

02/03/11 13:47:16 (14 years ago)

Author:

gkronber

Message:

Improved test cases for symbolic expression tree encoding and fixed minor bugs. #1336

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3

Files:

• ArchitectureManipulators/SubroutineDeleter.cs (modified) (2 diffs)
• EnumerableExtensions.cs (modified) (2 diffs)
• SymbolicExpressionTreeNode.cs (modified) (3 diffs)
• Tests/AllArchitectureAlteringOperatorsTest.cs (modified) (4 diffs)
• Tests/ArgumentCreaterTest.cs (modified) (2 diffs)
• Tests/Grammars.cs (modified) (1 diff)
• Tests/SubtreeCrossoverTest.cs (modified) (1 diff)
• Tests/Util.cs (modified) (2 diffs)

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

@@ -28 +28 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
@@ -97 +98 @@
         // deletion by random regeneration
         SymbolicExpressionTreeNode replacementTree = null;
-        // TODO: should weight symbols by tickets
-        var selectedSymbol = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).SelectRandom(random);
+        var allowedSymbolsList = invocationCutPoint.Parent.GetAllowedSymbols(invocationCutPoint.ReplacedChildIndex).ToList();
+        var weights = allowedSymbolsList.Select(s => s.InitialFrequency);
+        var selectedSymbol = allowedSymbolsList.SelectRandom(weights, random);
 
         int minPossibleSize = invocationCutPoint.Parent.Grammar.GetMinExpressionLength(selectedSymbol);

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

@@ -23 +23 @@
 using System.Linq;
 using HeuristicLab.Core;
+using System;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
@@ -35 +36 @@
       }
     }
+    public static T SelectRandom<T>(this IEnumerable<T> xs, IEnumerable<double> weights, IRandom random) {
+      var list = xs as IList<T>;
+      var weightsList = weights as IList<double>;
+      if (list == null) {
+        list = xs.ToList();
+      }
+      if (weightsList == null) {
+        weightsList = weights.ToList();
+      }
+      if (list.Count != weightsList.Count) throw new ArgumentException("Number of elements in enumerations doesn't match.");
+      if (list.Count == 0) throw new ArgumentException("Enumeration is empty", "xs");
+
+      double sum = weightsList.Sum();
+      double r = random.NextDouble() * sum;
+      double agg = 0;
+      for (int i = 0; i < list.Count; i++) {
+        agg += weightsList[i];
+        if (agg > r) return list[i];
+      }
+      // should never happen
+      throw new InvalidOperationException();
+    }
   }
 }

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

@@ -37 +37 @@
 
     // cached values to prevent unnecessary tree iterations
-    private short size;
-    private short height;
+    private ushort size;
+    private ushort height;
 
     public Symbol Symbol {
@@ -106 +106 @@
         if (SubTrees != null) {
           for (int i = 0; i < SubTrees.Count; i++) {
-            checked { size += (short)SubTrees[i].GetSize(); }
+            checked { size += (ushort)SubTrees[i].GetSize(); }
           }
         }
@@ -117 +117 @@
       else {
         if (SubTrees != null) {
-          for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (short)SubTrees[i].GetHeight());
+          for (int i = 0; i < SubTrees.Count; i++) height = Math.Max(height, (ushort)SubTrees[i].GetHeight());
         }
         height++;

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

@@ -80 +80 @@
             bool success = false;
             op.ModifyArchitecture(random, selectedTree, grammar, maxTreeSize, maxTreeHeigth, maxDefuns, maxArgs, out success);
-            if (!success) failedEvents++;
+            if (!success) failedEvents++; // architecture manipulation might fail
             Util.IsValid(selectedTree);
             newTrees.Add(selectedTree);
@@ -93 +93 @@
             bool success;
             newTrees.Add(SubtreeCrossover.Cross(random, par0, par1, 0.9, MAX_TREE_SIZE, MAX_TREE_HEIGHT, out success));
-            Assert.IsTrue(success);
+            Assert.IsTrue(success); // crossover must succeed
           }
         }
@@ -102 +102 @@
       Console.WriteLine("AllArchitectureAlteringOperators: " + Environment.NewLine +
         "Operations / s: ~" + Math.Round(1000.0 / (msPerOperation)) + "operations / s)" + Environment.NewLine +
-        "Failed events: " + failedEvents / (double)(POPULATION_SIZE * N_ITERATIONS) + "%" + Environment.NewLine +
+        "Failed events: " + failedEvents * 100.0 / (double)(POPULATION_SIZE * N_ITERATIONS * 2.0) + "%" + Environment.NewLine +
         Util.GetSizeDistributionString(trees, 200, 5) + Environment.NewLine +
         Util.GetFunctionDistributionString(trees) + Environment.NewLine +
@@ -108 +108 @@
         Util.GetTerminalDistributionString(trees) + Environment.NewLine
         );
+
+      Assert.IsTrue(failedEvents * 100.0 / (POPULATION_SIZE * N_ITERATIONS * 2.0) < 25.0); // 75% of architecture operations must succeed
+      Assert.IsTrue(Math.Round(1000.0 / (msPerOperation)) > 1000); // must achieve more than 1000 ops per second
     }
   }

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

@@ -56 +56 @@
       var grammar = Grammars.CreateArithmeticAndAdfGrammar();
       var random = new MersenneTwister(31415);
+      int failedOps = 0;
       for (int i = 0; i < POPULATION_SIZE; i++) {
         SymbolicExpressionTree tree;
@@ -61 +62 @@
           tree = ProbabilisticTreeCreator.Create(random, grammar, MAX_TREE_SIZE, MAX_TREE_HEIGHT, 3, 3);
         } while (!TreeHasAdfWithParameter(tree, 3));
-        var success = ArgumentCreater.CreateNewArgument(random, tree, grammar, 10000, 100, 3, 3);
-        Assert.IsTrue(success);
+        var success = ArgumentCreater.CreateNewArgument(random, tree, grammar, 60000, 100, 3, 3);
+        if (!success) failedOps++;
         Util.IsValid(tree);
         trees.Add(tree);
       }
+      // difficult to make sure that create argument operations succeed because trees are macro-expanded can potentially become very big 
+      // => just test if only a small proportion fails
+      Assert.IsTrue(failedOps < POPULATION_SIZE * 0.01 ); // only 1% may fail
       Console.WriteLine("ArgumentCreator: " + Environment.NewLine +
+        "Failed operations: " + failedOps * 100.0 / POPULATION_SIZE + " %" + Environment.NewLine +
         Util.GetSizeDistributionString(trees, 200, 20) + Environment.NewLine +
         Util.GetFunctionDistributionString(trees) + Environment.NewLine +

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

@@ -79 +79 @@
         var mul = new Multiplication();
         var div = new Division();
+        div.InitialFrequency = 0.0; // disable division symbol
         var terminal = new Terminal();
 

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

@@ -86 +86 @@
         Util.GetTerminalDistributionString(trees) + Environment.NewLine
         );
+
+      Assert.IsTrue(Math.Round(1000.0 / (msPerCrossoverEvent)) > 2000); // must achieve more than 2000 x-overs/s
     }
   }

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

@@ -130 +130 @@
       }
       //Assert.AreEqual(tree.Root.Symbol, tree.Root.Grammar.StartSymbol);
-      //foreach (var subtree in tree.Root.SubTrees)
-      //  Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
+      foreach (var subtree in tree.Root.SubTrees)
+        Assert.AreNotSame(subtree.Grammar, tree.Root.Grammar);
       IsValid(tree.Root);
     }
@@ -141 +141 @@
       Assert.IsTrue(treeNode.SubTrees.Count >= treeNode.Grammar.GetMinSubtreeCount(matchingSymbol));
       Assert.IsTrue(treeNode.SubTrees.Count <= treeNode.Grammar.GetMaxSubtreeCount(matchingSymbol));
+      Assert.AreNotEqual(0.0, matchingSymbol.InitialFrequency); // check that no deactivated symbols occur in the tree
       for (int i = 0; i < treeNode.SubTrees.Count; i++) {
         Assert.IsTrue(treeNode.GetAllowedSymbols(i).Select(x => x.Name).Contains(treeNode.SubTrees[i].Symbol.Name));