Changeset 7522 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs

Timestamp:

02/24/12 17:30:16 (15 months ago)

Author:

bburlacu

Message:

#1772: Merged changes from trunk, rigged the TournamentSelector to track clones, improved tracking code.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

Files:

• . (modified) (1 prop)
• 3.4/Crossovers/SubtreeCrossover.cs (modified) (13 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs

@@ -36 +36 @@
   /// until a valid configuration is found.
   /// </summary>  
-  [Item("SubtreeCrossover", "An operator which performs subtree swapping crossover.")]
+  [Item("SubtreeSwappingCrossover", "An operator which performs subtree swapping crossover.")]
   [StorableClass]
-  public sealed class SubtreeCrossover : TracingSymbolicExpressionTreeCrossover, ISymbolicExpressionTreeSizeConstraintOperator {
+  public class SubtreeCrossover : TracingSymbolicExpressionTreeCrossover, ISymbolicExpressionTreeSizeConstraintOperator {
     private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
+
     #region Parameter Properties
     public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
@@ -65 +66 @@
     #endregion
     [StorableConstructor]
-    private SubtreeCrossover(bool deserializing) : base(deserializing) { }
-    private SubtreeCrossover(SubtreeCrossover original, Cloner cloner) : base(original, cloner) { }
+    protected SubtreeCrossover(bool deserializing) : base(deserializing) { }
+    protected SubtreeCrossover(SubtreeCrossover original, Cloner cloner) : base(original, cloner) { }
     public SubtreeCrossover()
       : base() {
@@ -78 +79 @@
     }
 
-    protected override ISymbolicExpressionTree Cross(IRandom random,
+    public override ISymbolicExpressionTree Crossover(IRandom random,
       ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
       return Cross(random, parent0, parent1, InternalCrossoverPointProbability.Value,
@@ -94 +95 @@
       // calculate the max length and depth that the inserted branch can have 
       int maxInsertedBranchLength = maxTreeLength - (parent0.Length - childLength);
-      int maxInsertedBranchDepth = maxTreeDepth - GetBranchLevel(parent0.Root, crossoverPoint0.Parent);
+      int maxInsertedBranchDepth = maxTreeDepth - parent0.Root.GetBranchLevel(crossoverPoint0.Parent);
 
       List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
       parent1.Root.ForEachNodePostfix((n) => {
         if (n.GetLength() <= maxInsertedBranchLength &&
-            n.GetDepth() <= maxInsertedBranchDepth &&
-            IsMatchingPointType(crossoverPoint0, n))
+            n.GetDepth() <= maxInsertedBranchDepth && crossoverPoint0.IsMatchingPointType(n))
           allowedBranches.Add(n);
       });
       // empty branch
-      if (IsMatchingPointType(crossoverPoint0, null)) allowedBranches.Add(null);
+      if (crossoverPoint0.IsMatchingPointType(null)) allowedBranches.Add(null);
 
       if (allowedBranches.Count == 0) {
@@ -128 +128 @@
     }
 
-    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.SubtreeCount &&
-          cutPoint.ChildIndex == parent.SubtreeCount - 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.SubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(n.Symbol) &&
-            n.SubtreeCount <= 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");
@@ -157 +133 @@
       List<CutPoint> leafCrossoverPoints = new List<CutPoint>();
       parent0.Root.ForEachNodePostfix((n) => {
-        if (n.Subtrees.Any() && n != parent0.Root) {
+        if (n.SubtreeCount > 0 && n != parent0.Root) {
           foreach (var child in n.Subtrees) {
             if (child.GetLength() <= maxBranchLength &&
                 child.GetDepth() <= maxBranchDepth) {
-              if (child.Subtrees.Any())
+              if (child.SubtreeCount > 0)
                 internalCrossoverPoints.Add(new CutPoint(n, child));
               else
@@ -167 +143 @@
             }
           }
+
           // add one additional extension point if the number of sub trees for the symbol is not full
           if (n.SubtreeCount < n.Grammar.GetMaximumSubtreeCount(n.Symbol)) {
@@ -173 +150 @@
           }
         }
-      });
+      }
+    );
 
       if (random.NextDouble() < internalNodeProbability) {
@@ -200 +178 @@
         // select internal node if possible
         allowedInternalBranches = (from branch in branches
-                                   where branch != null && branch.Subtrees.Any()
+                                   where branch != null && branch.SubtreeCount > 0
                                    select branch).ToList();
         if (allowedInternalBranches.Count > 0) {
@@ -207 +185 @@
           // no internal nodes allowed => select leaf nodes
           allowedLeafBranches = (from branch in branches
-                                 where branch == null || !branch.Subtrees.Any()
+                                 where branch == null || branch.SubtreeCount == 0
                                  select branch).ToList();
           return allowedLeafBranches.SelectRandom(random);
@@ -214 +192 @@
         // select leaf node if possible
         allowedLeafBranches = (from branch in branches
-                               where branch == null || !branch.Subtrees.Any()
+                               where branch == null || branch.SubtreeCount == 0
                                select branch).ToList();
         if (allowedLeafBranches.Count > 0) {
@@ -220 +198 @@
         } else {
           allowedInternalBranches = (from branch in branches
-                                     where branch != null && branch.Subtrees.Any()
+                                     where branch != null && branch.SubtreeCount > 0
                                      select branch).ToList();
           return allowedInternalBranches.SelectRandom(random);
@@ -226 +204 @@
       }
     }
-
-    private static int GetBranchLevel(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode point) {
-      if (root == point) return 0;
-      foreach (var subtree in root.Subtrees) {
-        int branchLevel = GetBranchLevel(subtree, point);
-        if (branchLevel < int.MaxValue) return 1 + branchLevel;
-      }
-      return int.MaxValue;
-    }
   }
 }