Changeset 5916

Timestamp:

03/31/11 19:20:29 (13 years ago)

Author:

gkronber

Message:

#1418 changed crossover operator for symbolic expression trees to allow extensions and reductions of the number of subtrees for variable-arity symbols.

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4

Files:

• Crossovers/SubtreeCrossover.cs (modified) (9 diffs)
• CutPoint.cs (modified) (1 diff)

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

@@ -88 +88 @@
       double internalCrossoverPointProbability, int maxTreeLength, int maxTreeDepth) {
       // select a random crossover point in the first parent 
-      ISymbolicExpressionTreeNode crossoverPoint0;
-      int replacedSubtreeIndex;
-      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeLength, maxTreeDepth, out crossoverPoint0, out replacedSubtreeIndex);
-
+      CutPoint crossoverPoint0;
+      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeLength, maxTreeDepth, out crossoverPoint0);
+
+      int childLength = crossoverPoint0.Child != null ? crossoverPoint0.Child.GetLength() : 0;
       // calculate the max length and depth that the inserted branch can have 
-      int maxInsertedBranchLength = maxTreeLength - (parent0.Length - crossoverPoint0.GetSubtree(replacedSubtreeIndex).GetLength());
-      int maxInsertedBranchDepth = maxTreeDepth - GetBranchLevel(parent0.Root, crossoverPoint0);
+      int maxInsertedBranchLength = maxTreeLength - (parent0.Length - childLength);
+      int maxInsertedBranchDepth = maxTreeDepth - GetBranchLevel(parent0.Root, crossoverPoint0.Parent);
+
 
       List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
@@ -100 +101 @@
         if (n.GetLength() <= maxInsertedBranchLength &&
           n.GetDepth() <= maxInsertedBranchDepth &&
-          IsMatchingPointType(crossoverPoint0, replacedSubtreeIndex, n))
+          IsMatchingPointType(crossoverPoint0, n))
           allowedBranches.Add(n);
       });
+      // empty branch
+      if (IsMatchingPointType(crossoverPoint0, null)) allowedBranches.Add(null);
 
       if (allowedBranches.Count == 0) {
@@ -109 +112 @@
         var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
 
-        // manipulate the tree of parent0 in place
-        // replace the branch in tree0 with the selected branch from tree1
-        crossoverPoint0.RemoveSubtree(replacedSubtreeIndex);
-        crossoverPoint0.InsertSubtree(replacedSubtreeIndex, selectedBranch);
+        if (crossoverPoint0.Child != null) {
+          // manipulate the tree of parent0 in place
+          // replace the branch in tree0 with the selected branch from tree1
+          crossoverPoint0.Parent.RemoveSubtree(crossoverPoint0.ChildIndex);
+          if (selectedBranch != null) {
+            crossoverPoint0.Parent.InsertSubtree(crossoverPoint0.ChildIndex, selectedBranch);
+          }
+        } else {
+          // child is null (additional child should be added under the parent)
+          if (selectedBranch != null) {
+            crossoverPoint0.Parent.AddSubtree(selectedBranch);
+          }
+        }
         return parent0;
       }
     }
 
-    private static bool IsMatchingPointType(ISymbolicExpressionTreeNode parent, int replacedSubtreeIndex, ISymbolicExpressionTreeNode branch) {
-      // check syntax constraints of direct parent - child relation
-      if (!parent.Grammar.ContainsSymbol(branch.Symbol) ||
-          !parent.Grammar.IsAllowedChildSymbol(parent.Symbol, branch.Symbol, replacedSubtreeIndex)) return false;
-
-      bool result = true;
-      // check point type for the whole branch
-      branch.ForEachNodePostfix((n) => {
-        result =
-          result &&
-          parent.Grammar.ContainsSymbol(n.Symbol) &&
-          n.SubtreesCount >= parent.Grammar.GetMinimumSubtreeCount(n.Symbol) &&
-          n.SubtreesCount <= parent.Grammar.GetMaximumSubtreeCount(n.Symbol);
-      });
-      return result;
-    }
-
-    private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchLength, int maxBranchDepth, out ISymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {
+    private static bool IsMatchingPointType(CutPoint cutPoint, ISymbolicExpressionTreeNode newChild) {
+      var parent = cutPoint.Parent;
+      if (newChild == null) {
+        // make sure that one subtree can be removed and that only the last subtree is removed 
+        return parent.Grammar.GetMinimumSubtreeCount(parent.Symbol) < parent.SubtreesCount &&
+          cutPoint.ChildIndex == parent.SubtreesCount - 1;
+      } else {
+        // check syntax constraints of direct parent - child relation
+        if (!parent.Grammar.ContainsSymbol(newChild.Symbol) ||
+            !parent.Grammar.IsAllowedChildSymbol(parent.Symbol, newChild.Symbol, cutPoint.ChildIndex)) return false;
+
+        bool result = true;
+        // check point type for the whole branch
+        newChild.ForEachNodePostfix((n) => {
+          result =
+            result &&
+            parent.Grammar.ContainsSymbol(n.Symbol) &&
+            n.SubtreesCount >= parent.Grammar.GetMinimumSubtreeCount(n.Symbol) &&
+            n.SubtreesCount <= parent.Grammar.GetMaximumSubtreeCount(n.Symbol);
+        });
+        return result;
+      }
+    }
+
+    private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchLength, int maxBranchDepth, out CutPoint crossoverPoint) {
       if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
       List<CutPoint> internalCrossoverPoints = new List<CutPoint>();
@@ -149 +168 @@
             }
           }
+          // add one additional extension point if the number of sub trees for the symbol is not full
+          if (n.SubtreesCount < n.Grammar.GetMaximumSubtreeCount(n.Symbol)) {
+            // empty extension point
+            internalCrossoverPoints.Add(new CutPoint(n, n.SubtreesCount));
+          }
         }
       });
@@ -156 +180 @@
         if (internalCrossoverPoints.Count > 0) {
           // select internal crossover point or leaf
-          var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
-          crossoverPoint = selectedCrossoverPoint.Parent;
-          subtreeIndex = selectedCrossoverPoint.ChildIndex;
+          crossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
         } else {
           // otherwise select external node
-          var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
-          crossoverPoint = selectedCrossoverPoint.Parent;
-          subtreeIndex = selectedCrossoverPoint.ChildIndex;
+          crossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
         }
       } else if (leafCrossoverPoints.Count > 0) {
         // select from leaf crossover point if possible
-        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
-        crossoverPoint = selectedCrossoverPoint.Parent;
-        subtreeIndex = selectedCrossoverPoint.ChildIndex;
+        crossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
       } else {
         // otherwise select internal crossover point
-        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
-        crossoverPoint = selectedCrossoverPoint.Parent;
-        subtreeIndex = selectedCrossoverPoint.ChildIndex;
+        crossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
       }
     }
@@ -185 +201 @@
         // select internal node if possible
         allowedInternalBranches = (from branch in branches
-                                   where branch.Subtrees.Any()
+                                   where branch != null && branch.Subtrees.Any()
                                    select branch).ToList();
         if (allowedInternalBranches.Count > 0) {
@@ -192 +208 @@
           // no internal nodes allowed => select leaf nodes
           allowedLeafBranches = (from branch in branches
-                                 where !branch.Subtrees.Any()
+                                 where branch == null || !branch.Subtrees.Any()
                                  select branch).ToList();
           return allowedLeafBranches.SelectRandom(random);
@@ -199 +215 @@
         // select leaf node if possible
         allowedLeafBranches = (from branch in branches
-                               where !branch.Subtrees.Any()
+                               where branch == null || !branch.Subtrees.Any()
                                select branch).ToList();
         if (allowedLeafBranches.Count > 0) {
@@ -205 +221 @@
         } else {
           allowedInternalBranches = (from branch in branches
-                                     where branch.Subtrees.Any()
+                                     where branch != null && branch.Subtrees.Any()
                                      select branch).ToList();
           return allowedInternalBranches.SelectRandom(random);

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/CutPoint.cs

@@ -34 +34 @@
       this.childIndex = parent.IndexOfSubtree(child);
     }
+    public CutPoint(ISymbolicExpressionTreeNode parent, int childIndex) {
+      this.Parent = parent;
+      this.childIndex = childIndex;
+      this.Child = null;
+    }
   }
 }