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

Timestamp:

07/06/10 11:59:50 (15 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/Crossovers

Files:

• CrossoverPoint.cs (added)
• SubtreeCrossover.cs (modified) (3 diffs)

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);
+        }
       }
     }