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

Timestamp:

07/06/10 11:59:50 (14 years ago)

Author:

gkronber

Message:

Minor improvements concerning efficiency of symbolic expression tree encoding data structures and operators. #1073

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3

Files:

• Crossovers/CrossoverPoint.cs (added)
• Crossovers/SubtreeCrossover.cs (modified) (3 diffs)
• SymbolicExpressionTreeNode.cs (modified) (5 diffs)
• Symbols/ReadOnlySymbol.cs (modified) (1 diff)
• Symbols/StartSymbol.cs (modified) (1 diff)

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

@@ -67 +67 @@
       int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
 
-      var allowedBranches = (from branch in parent1.Root.IterateNodesPostfix()
-                             where branch.GetSize() < maxInsertedBranchSize
-                             where branch.GetHeight() < maxInsertedBranchHeight
-                             where IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, branch)
-                             select branch).ToList();
+      List<SymbolicExpressionTreeNode> allowedBranches = new List<SymbolicExpressionTreeNode>();
+      parent1.Root.ForEachNodePostfix((n) => {
+        if (n.GetSize() < maxInsertedBranchSize &&
+          n.GetHeight() < maxInsertedBranchHeight &&
+          IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, n))
+          allowedBranches.Add(n);
+      });
 
-      if (allowedBranches.Count() == 0) {
+      if (allowedBranches.Count == 0) {
         success = false;
         return parent0;
@@ -89 +91 @@
 
     private static bool IsMatchingPointType(SymbolicExpressionTreeNode parent, int replacedSubtreeIndex, SymbolicExpressionTreeNode branch) {
-      // check point type for the whole branch
-      foreach (var node in branch.IterateNodesPostfix()) {
-        if (!parent.Grammar.ContainsSymbol(node.Symbol)) return false;
-        else if (node.SubTrees.Count < parent.Grammar.GetMinSubtreeCount(node.Symbol)) return false;
-        else if (node.SubTrees.Count > parent.Grammar.GetMaxSubtreeCount(node.Symbol)) return false;
-      }
-
       // check syntax constraints of direct parent - child relation
       if (!parent.Grammar.IsAllowedChild(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
 
-      return true;
+      bool result = true;
+      // check point type for the whole branch
+      branch.ForEachNodePostfix((n) => {
+        result &= n.SubTrees.Count >= parent.Grammar.GetMinSubtreeCount(n.Symbol);
+        result &= n.SubTrees.Count <= parent.Grammar.GetMaxSubtreeCount(n.Symbol);
+        result &= parent.Grammar.ContainsSymbol(n.Symbol);
+      });
+      return result;
     }
 
     private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchSize, int maxBranchHeight, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {
-      var crossoverPoints = (from branch in parent0.Root.IterateNodesPostfix()
-                             where branch.SubTrees.Count > 0
-                             where branch != parent0.Root
-                             where branch.GetSize() < maxBranchSize
-                             where branch.GetHeight() < maxBranchHeight
-                             from index in Enumerable.Range(0, branch.SubTrees.Count)
-                             let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }
-                             select p).ToList();
-      var internalCrossoverPoints = (from p in crossoverPoints
-                                     where !p.IsLeaf
-                                     select p).ToList();
-      var leafCrossoverPoints = (from p in crossoverPoints
-                                 where p.IsLeaf
-                                 select p).ToList();
-      if (internalCrossoverPoints.Count == 0) {
+      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
+      List<CrossoverPoint> internalCrossoverPoints = new List<CrossoverPoint>();
+      List<CrossoverPoint> leafCrossoverPoints = new List<CrossoverPoint>();
+      parent0.Root.ForEachNodePostfix((n) => {
+        if (n.SubTrees.Count > 0 &&
+          n.GetSize() < maxBranchSize &&
+          n.GetHeight() < maxBranchHeight &&
+          n != parent0.Root
+          ) {
+          foreach (var child in n.SubTrees) {
+            if (child.SubTrees.Count > 0)
+              internalCrossoverPoints.Add(new CrossoverPoint(n, child));
+            else
+              leafCrossoverPoints.Add(new CrossoverPoint(n, child));
+          }
+        }
+      });
+      if (random.NextDouble() < internalNodeProbability) {
+        // select from internal node if possible
+        if (internalCrossoverPoints.Count > 0) {
+          // select internal crossover point or leaf
+          var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
+          crossoverPoint = selectedCrossoverPoint.Parent;
+          subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
+        } else {
+          // otherwise select external node
+          var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
+          crossoverPoint = selectedCrossoverPoint.Parent;
+          subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
+        }
+      } else if (leafCrossoverPoints.Count > 0) {
+        // select from leaf crossover point if possible
         var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
-        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
-        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
-      } else if (leafCrossoverPoints.Count == 0) {
-        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
-        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
-        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
-      } else if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {
-        // select internal crossover point or leaf
-        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
-        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
+        crossoverPoint = selectedCrossoverPoint.Parent;
         subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
       } else {
-        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
-        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
+        // otherwise select internal crossover point
+        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
+        crossoverPoint = selectedCrossoverPoint.Parent;
         subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
       }
@@ -139 +150 @@
     private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<SymbolicExpressionTreeNode> branches, double internalNodeProbability) {
       if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
-      var allowedInternalBranches = (from branch in branches
+      List<SymbolicExpressionTreeNode> allowedInternalBranches;
+      List<SymbolicExpressionTreeNode> allowedLeafBranches;
+      if (random.NextDouble() < internalNodeProbability) {
+        // select internal node if possible
+        allowedInternalBranches = (from branch in branches
+                                   where branch.SubTrees.Count > 0
+                                   select branch).ToList();
+        if (allowedInternalBranches.Count > 0) {
+          return allowedInternalBranches.SelectRandom(random);
+        } else {
+          // no internal nodes allowed => select leaf nodes
+          allowedLeafBranches = (from branch in branches
+                                 where branch.SubTrees.Count == 0
+                                 select branch).ToList();
+          return allowedLeafBranches.SelectRandom(random);
+        }
+      } else {
+        // select leaf node if possible
+        allowedLeafBranches = (from branch in branches
+                               where branch.SubTrees.Count == 0
+                               select branch).ToList();
+        if (allowedLeafBranches.Count > 0) {
+          return allowedLeafBranches.SelectRandom(random);
+        } else {
+          allowedInternalBranches = (from branch in branches
                                      where branch.SubTrees.Count > 0
                                      select branch).ToList();
-      var allowedLeafBranches = (from branch in branches
-                                 where branch.SubTrees.Count == 0
-                                 select branch).ToList();
-      if (allowedInternalBranches.Count == 0) {
-        return allowedLeafBranches.SelectRandom(random);
-      } else if (allowedLeafBranches.Count == 0) {
-        return allowedInternalBranches.SelectRandom(random);
-      } else if (random.NextDouble() < internalNodeProbability) {
-        // when leaf and internal nodes are possible then choose either a leaf or internal node with internalNodeProbability
-        return allowedInternalBranches.SelectRandom(random);
-      } else {
-        return allowedLeafBranches.SelectRandom(random);
+          return allowedInternalBranches.SelectRandom(random);
+        }
       }
     }

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

@@ -43 +43 @@
     private short size;
     private short height;
-    private List<SymbolicExpressionTreeNode> prefixForm;
-    private List<SymbolicExpressionTreeNode> postfixForm;
 
     public Symbol Symbol {
@@ -64 +62 @@
 
     public SymbolicExpressionTreeNode(Symbol symbol) {
-      subTrees = new List<SymbolicExpressionTreeNode>();
+      subTrees = new List<SymbolicExpressionTreeNode>(3);
       this.symbol = symbol;
     }
@@ -137 +135 @@
 
     public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix() {
-      if (prefixForm == null) {
-        prefixForm = new List<SymbolicExpressionTreeNode>(200);
-        ForEachNodePrefix(x => prefixForm.Add(x));
-      }
-      return prefixForm;
+      List<SymbolicExpressionTreeNode> list = new List<SymbolicExpressionTreeNode>();
+      ForEachNodePrefix((n) => list.Add(n));
+      return list;
     }
 
-    private void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
+    public void ForEachNodePrefix(Action<SymbolicExpressionTreeNode> a) {
       a(this);
       for (int i = 0; i < SubTrees.Count; i++) {
@@ -152 +148 @@
 
     public IEnumerable<SymbolicExpressionTreeNode> IterateNodesPostfix() {
-      if (postfixForm == null) {
-        postfixForm = new List<SymbolicExpressionTreeNode>(200);
-        ForEachNodePostfix(x => postfixForm.Add(x));
-      }
-      return postfixForm;
+      List<SymbolicExpressionTreeNode> list = new List<SymbolicExpressionTreeNode>();
+      ForEachNodePostfix((n) => list.Add(n));
+      return list;
     }
 
-    private void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
+    public void ForEachNodePostfix(Action<SymbolicExpressionTreeNode> a) {
       for (int i = 0; i < SubTrees.Count; i++) {
         SubTrees[i].ForEachNodePrefix(a);
@@ -190 +184 @@
     private void ResetCachedValues() {
       size = 0; height = 0;
-      prefixForm = null; postfixForm = null;
       if (parent != null) parent.ResetCachedValues();
     }

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

@@ -34 +34 @@
   [Item("ReadOnlySymbol", "Represents a symbol in a symbolic function tree that cannot be modified.")]
   public abstract class ReadOnlySymbol : Symbol {
-    #region Properties
-    [Storable]
-    private double initialFrequency;
-    public double InitialFrequency {
-      get { return initialFrequency; }
-      set { throw new NotSupportedException(); }
-    }
-    #endregion
+    //#region Properties
+    //[Storable]
+    //private double initialFrequency;
+    //public double InitialFrequency {
+    //  get { return initialFrequency; }
+    //  set { throw new NotSupportedException(); }
+    //}
+    //#endregion
 
     public override bool CanChangeName {

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

@@ -25 +25 @@
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols {
   [StorableClass]
-  [Item("StartSymbol", "Special symbol that represents the starting node of the result producing branch of a symbolic expression tree.")]
+  [Item(StartSymbol.StartSymbolName, StartSymbol.StartSymbolDescription)]
   public sealed class StartSymbol : ReadOnlySymbol {
+    public const string StartSymbolName = "StartSymbol";
+    public const string StartSymbolDescription = "Special symbol that represents the starting node of the result producing branch of a symbolic expression tree.";
+
+    public StartSymbol() : base(StartSymbol.StartSymbolName, StartSymbol.StartSymbolDescription) { }
+    [StorableConstructor]
+    private StartSymbol(bool deserializing) : base(deserializing) { }
 
     public override SymbolicExpressionTreeNode CreateTreeNode() {