Changeset 7494 for branches/HeuristicLab.Crossovers

Timestamp:

02/21/12 10:57:40 (12 years ago)

Author:

bburlacu

Message:

#1682: * Moved Swap method into base class

• Simplified selection of allowed branches
• Replaced while loop with a more simple reversed for loop

Location:

branches/HeuristicLab.Crossovers/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers

Files:

• SymbolicDataAnalysisExpressionCrossover.cs (modified) (1 diff)
• SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover.cs (modified) (7 diffs)

branches/HeuristicLab.Crossovers/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionCrossover.cs

@@ -149 +149 @@
       return rows.Where(i => i < testPartitionStart || testPartitionEnd <= i);
     }
+
+    protected static void Swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
+      if (crossoverPoint.Child != null) {
+        // manipulate the tree of parent0 in place
+        // replace the branch in tree0 with the selected branch from tree1
+        crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);
+        if (selectedBranch != null) {
+          crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);
+        }
+      } else {
+        // child is null (additional child should be added under the parent)
+        if (selectedBranch != null) {
+          crossoverPoint.Parent.AddSubtree(selectedBranch);
+        }
+      }
+    }
   }
 }

branches/HeuristicLab.Crossovers/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover.cs

@@ -30 +30 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
 
-  [Item("ProbabilisticFunctionalCrossover", "An operator which performs subtree swapping based on the behavioral similarity between subtrees.")]
+  [Item("ProbabilisticFunctionalCrossover", "An operator which performs subtree swapping based on the behavioral similarity between subtrees:\n" +
+                                            "- Take two parent individuals P0 and P1\n" +
+                                            "- Randomly choose a node N from P0\n" +
+                                            "- For each matching node M from P1, calculate the behavioral distance:\n" +
+                                            "\t\tD(N,M) = 0.5 * ( abs(max(N) - max(M)) + abs(min(N) - min(M)) )\n" +
+                                            "- Make a probabilistic weighted choice of node M from P1, based on the inversed and normalized behavioral distance")]
   public sealed class SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
     [StorableConstructor]
@@ -38 +43 @@
     public SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover()
       : base() {
+      Name = "ProbabilisticFunctionalCrossover";
     }
     public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T>(this, cloner); }
@@ -53 +59 @@
     /// Randomly choose a node i from the first parent, then for each matching node j from the second parent, calculate the behavioral distance based on the range:
     /// d(i,j) = 0.5 * ( abs(max(i) - max(j)) + abs(min(i) - min(j)) ).
-    /// Next, assign probabilities for the selection of the second cross point based on the inversed and normalized behavioral distance and
-    /// choose the second crosspoint via a random weighted selection procedure.
+    /// Next, assign probabilities for the selection of a node j based on the inversed and normalized behavioral distance, then make a random weighted choice.
     /// </summary>
     public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
@@ -60 +65 @@
       var crossoverPoints0 = new List<CutPoint>();
       parent0.Root.ForEachNodePostfix((n) => {
-        if (n.Subtrees.Any() && n != parent0.Root)
-          crossoverPoints0.AddRange(from s in n.Subtrees
-                                    select new CutPoint(n, s));
+        // the if clauses prevent the root or the startnode from being selected, although the startnode can be the parent of the node being swapped.
+        if (n.Parent != null && n.Parent != parent0.Root) {
+          crossoverPoints0.Add(new CutPoint(n.Parent, n));
+        }
       });
       var crossoverPoint0 = crossoverPoints0.SelectRandom(random);
@@ -70 +76 @@
       var allowedBranches = new List<ISymbolicExpressionTreeNode>();
       parent1.Root.ForEachNodePostfix((n) => {
-        if (n.Subtrees.Any() && n != parent1.Root)
-          allowedBranches.AddRange(from s in n.Subtrees
-                                   where crossoverPoint0.IsMatchingPointType(s) && s.GetDepth() + level <= maxDepth && s.GetLength() + length <= maxLength
-                                   select s);
+        if (n.Parent != null && n.Parent != parent1.Root) {
+          if (n.GetDepth() + level <= maxDepth && n.GetLength() + length <= maxLength && crossoverPoint0.IsMatchingPointType(n))
+            allowedBranches.Add(n);
+        }
       });
 
@@ -107 +113 @@
 
       // remove branches with an infinite or NaN behavioral distance
-      int count = weights.Count, idx = 0;
-      while (idx < count) {
-        if (Double.IsNaN(weights[idx]) || Double.IsInfinity(weights[idx])) {
-          weights.RemoveAt(idx);
-          allowedBranches.RemoveAt(idx);
-          --count;
-        } else {
-          ++idx;
+      for (int i = weights.Count - 1; i >= 0; --i) {
+        if (Double.IsNaN(weights[i]) || Double.IsInfinity(weights[i])) {
+          weights.RemoveAt(i);
+          allowedBranches.RemoveAt(i);
         }
       }
-
       // check if there are any allowed branches left
       if (allowedBranches.Count == 0)
@@ -139 +140 @@
         selectedBranch = allowedBranches.SelectRandom(weights, random);
       }
-      swap(crossoverPoint0, selectedBranch);
+      Swap(crossoverPoint0, selectedBranch);
       return parent0;
-    }
-
-    private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
-      if (crossoverPoint.Child != null) {
-        // manipulate the tree of parent0 in place
-        // replace the branch in tree0 with the selected branch from tree1
-        crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);
-        if (selectedBranch != null) {
-          crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);
-        }
-      } else {
-        // child is null (additional child should be added under the parent)
-        if (selectedBranch != null) {
-          crossoverPoint.Parent.AddSubtree(selectedBranch);
-        }
-      }
     }
   }