Changeset 7497 for branches/HeuristicLab.Crossovers/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers

Timestamp:

02/21/12 11:08:58 (13 years ago)

Author:

bburlacu

Message:

#1682:

• Added names and detailed descriptions to all crossover operators
• Minor code improvements (selection of allowed branches and cutpoints)

Location:

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

Files:

• MultiSymbolicDataAnalysisExpressionCrossover.cs (modified) (1 diff)
• SymbolicDataAnalysisExpressionDepthConstrainedCrossover.cs (modified) (5 diffs)
• SymbolicDataAnalysisExpressionDeterministicBestCrossover.cs (modified) (5 diffs)

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

@@ -108 +108 @@
       Operators = checkedItemList;
       Operators_ItemsAdded(this, new CollectionItemsChangedEventArgs<IndexedItem<ISymbolicExpressionTreeCrossover>>(Operators.CheckedItems));
+      Name = "MultiSymbolicDataAnalysisExpressionCrossover";
     }
 

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

@@ -32 +32 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
 
-  [Item("DepthConstrainedCrossover", "An operator which performs subtree swapping within a specific depth range.")]
+  [Item("DepthConstrainedCrossover", "An operator which performs subtree swapping within a specific depth range. The range parameter controls the crossover behavior:\n" +
+                                     "- HighLevel (upper 25% of the tree)\n" +
+                                     "- Standard (mid 50% of the tree)\n" +
+                                     "- LowLevel (lower 25% of the tree)")]
   public sealed class SymbolicDataAnalysisExpressionDepthConstrainedCrossover<T> :
     SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
@@ -60 +63 @@
       DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.Standard)).AsReadOnly());
       DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.LowLevel)).AsReadOnly());
+      Name = "DepthConstrainedCrossover";
     }
     public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionDepthConstrainedCrossover<T>(this, cloner); }
@@ -83 +87 @@
     /// <returns></returns>
     public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, int maxDepth, int maxLength, string mode) {
-      int depth = parent0.Root.GetDepth() - 1; // subtract 1 because the tree levels are counted from 0 
+      int depth = parent0.Root.GetDepth() - 1; // substract 1 because the tree levels are counted from 0 
       var depthRange = new IntRange();
       const int depthOffset = 2; // skip the first 2 levels (root + startNode)
@@ -118 +122 @@
 
       var allowedBranches = (from s in GetNodesAtDepth(parent1, depthRange)
-                             where
-                               crossoverPoint0.IsMatchingPointType(s) &&
-                               s.GetDepth() + level <= maxDepth &&
-                               s.GetLength() + length <= maxLength
+                             where s.GetDepth() + level <= maxDepth
+                             where s.GetLength() + length <= maxLength
+                             where crossoverPoint0.IsMatchingPointType(s)
                              select s).ToList();
       if (allowedBranches.Count == 0) return parent0;
       var selectedBranch = allowedBranches.SelectRandom(random);
-      swap(crossoverPoint0, selectedBranch);
+      Swap(crossoverPoint0, selectedBranch);
       return parent0;
     }
@@ -136 +139 @@
              where depth <= depthRange.End
              select node;
-
-      //var list = new List<Tuple<ISymbolicExpressionTreeNode, int>> { new Tuple<ISymbolicExpressionTreeNode, int>(root, 0) };
-      //int offset = 0;
-      //int level = 0;
-      //while (level < range.End) {
-      //  ++level;
-      //  int count = list.Count;
-      //  for (int i = offset; i != count; ++i) {
-      //    if (list[i].Item1.Subtrees.Any())
-      //      list.AddRange(from s in list[i].Item1.Subtrees select new Tuple<ISymbolicExpressionTreeNode, int>(s, level));
-      //  }
-      //  offset = count;
-      //}
-      //// taking advantage of the fact that the list is already sorted by level
-      //for (int i = list.Count - 1; i >= 0; --i) {
-      //  if (list[i].Item2 >= range.Start)
-      //    yield return list[i].Item1;
-      //  else break;
-      //}
-    }
-
-    private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
-      // perform the actual swap
-      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/SymbolicDataAnalysisExpressionDeterministicBestCrossover.cs

@@ -30 +30 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
 
-  [Item("DeterministicBestCrossover", "An operator which performs subtree swapping in a deterministic way, by choosing the best subtree to be swapped in a certain position.")]
+  [Item("DeterministicBestCrossover", "An operator which performs subtree swapping by choosing the best subtree to be swapped in a certain position:\n" +
+                                      "- Take two parent individuals P0 and P1\n" +
+                                      "- Randomly choose a crossover point C from P0\n" +
+                                      "- Test all nodes from P1 to determine the one that produces the best child when inserted at place C in P0")]
   public sealed class SymbolicDataAnalysisExpressionDeterministicBestCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
     [StorableConstructor]
@@ -62 +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));
+        if (n.Parent != null && n.Parent != parent0.Root)
+          crossoverPoints0.Add(new CutPoint(n.Parent, n));
       });
       CutPoint crossoverPoint0 = crossoverPoints0.SelectRandom(random);
@@ -71 +74 @@
       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);
+        }
       });
 
@@ -89 +92 @@
       foreach (var node in allowedBranches) {
         var parent = node.Parent;
-        swap(crossoverPoint0, node); // the swap will set the nodes parent to crossoverPoint0.Parent
+        Swap(crossoverPoint0, node); // the swap will set the nodes parent to crossoverPoint0.Parent
         double quality = evaluator.Evaluate(context, parent0, problemData, rows);
-        swap(crossoverPoint0, originalChild); // swap the child back (so that the next swap will not affect the currently swapped node from parent1)
+        Swap(crossoverPoint0, originalChild); // swap the child back (so that the next swap will not affect the currently swapped node from parent1)
         nodeQualities.Add(new Tuple<ISymbolicExpressionTreeNode, double>(node, quality));
         node.Parent = parent; // restore correct parent
@@ -108 +111 @@
 
       // swap the node that would create the best offspring
-      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);
-        }
-      }
     }
   }