Changeset 7109

Timestamp:

12/01/11 17:15:28 (12 years ago)

Author:

bburlacu

Message:

#1693: Implemented the context-aware crossover.

File:

• branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs (modified) (2 diffs)

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs

@@ -32 +32 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
 
-  [Item("ContextAwareCrossover", "An operator which performs subtree swapping in a deterministic way: it checks all possible cross points in the second parent with the aim of creating the best possible offspring.")]
+  [Item("ContextAwareCrossover", "A crossover operator which deterministically choses the best insertion point for a randomly selected node.")]
   public sealed class SymbolicDataAnalysisExpressionContextAwareCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
     [StorableConstructor]
@@ -56 +56 @@
     /// <summary>
     /// Takes two parent individuals P0 and P1. 
-    /// Randomly choose a node i from the first parent, then test all nodes j from the second parent to determine the best child that would be obtained by swapping i for j.
+    /// Randomly choose a node i from the second parent, then test all possible crossover points from the first parent to determine the best location for i to be inserted.
     /// </summary>
     public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, IExecutionContext context,
                                                 ISymbolicDataAnalysisSingleObjectiveEvaluator<T> evaluator, T problemData, IEnumerable<int> rows, int maxDepth, int maxLength) {
-      List<CutPoint> crossoverPoints0 = new List<CutPoint>();
+      // randomly choose a node from the second parent
+      var possibleChildren = new List<ISymbolicExpressionTreeNode>();
+      parent1.Root.ForEachNodePostfix((n) => {
+        if (n.Subtrees.Any() && n != parent0.Root)
+          foreach (var child in n.Subtrees)
+            possibleChildren.Add(child);
+      });
+      var selectedChild = possibleChildren[random.Next(possibleChildren.Count)];
+      var crossoverPoints = new List<CutPoint>();
+      var qualities = new List<Tuple<CutPoint, double>>();
+
       parent0.Root.ForEachNodePostfix((n) => {
         if (n.Subtrees.Any() && n != parent0.Root)
-          foreach (var child in n.Subtrees)
-            crossoverPoints0.Add(new CutPoint(n, child));
-      });
-      CutPoint crossoverPoint0 = crossoverPoints0[random.Next(crossoverPoints0.Count)];
-      int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
-      int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
-
-      List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
-      parent1.Root.ForEachNodePostfix((n) => {
-        if (n.Subtrees.Any() && n != parent1.Root)
-          foreach (var child in n.Subtrees)
-            if (crossoverPoint0.IsMatchingPointType(child) && (child.GetDepth() + level <= maxDepth) && (child.GetLength() + length <= maxLength))
-              allowedBranches.Add(child);
+          foreach (var child in n.Subtrees) {
+            var crossoverPoint = new CutPoint(n, child);
+            int totalDepth = parent0.Root.GetBranchLevel(child) + selectedChild.GetDepth();
+            int totalLength = parent0.Root.GetLength() - child.GetLength() + selectedChild.GetLength();
+            if (crossoverPoint.IsMatchingPointType(selectedChild) && totalDepth <= maxDepth && totalLength <= maxLength) {
+              crossoverPoints.Add(crossoverPoint);
+            }
+          }
       });
 
-      // check if empty branch is allowed
-      if (crossoverPoint0.IsMatchingPointType(null)) allowedBranches.Add(null);
+      if (crossoverPoints.Any()) {
+        // this loop will perform two swap operations per each crossover point
+        foreach (var crossoverPoint in crossoverPoints) {
+          // save the old parent so we can restore it later
+          var parent = selectedChild.Parent;
+          // perform a swap and check the quality of the solution
+          swap(crossoverPoint, selectedChild);
+          double quality = evaluator.Evaluate(context, parent0, problemData, rows);
+          qualities.Add(new Tuple<CutPoint, double>(crossoverPoint, quality));
+          // restore the correct parent
+          selectedChild.Parent = parent;
+          // swap the replaced subtree back into the tree so that the structure is preserved
+          swap(crossoverPoint, crossoverPoint.Child);
+        }
 
-      if (allowedBranches.Count == 0)
-        return parent0;
-
-      var dataset = problemData.Dataset;
-
-      // create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
-      ISymbolicExpressionTreeNode selectedBranch = null;
-
-      var nodeQualities = new List<Tuple<ISymbolicExpressionTreeNode, double>>();
-
-      foreach (var node in allowedBranches) {
-        swap(crossoverPoint0, node);
-        double quality = evaluator.Evaluate(context, parent0, problemData, rows);
-        nodeQualities.Add(new Tuple<ISymbolicExpressionTreeNode, double>(node, quality));
+        qualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
+        var crossoverPoint0 = evaluator.Maximization ? qualities.Last().Item1 : qualities.First().Item1;
+        // swap the node that would create the best offspring
+        // this last swap makes a total of (2 * crossoverPoints.Count() + 1) swap operations.
+        swap(crossoverPoint0, selectedChild);
       }
-
-      nodeQualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
-
-      if (evaluator.Maximization)
-        selectedBranch = nodeQualities.Last().Item1;
-      else
-        selectedBranch = nodeQualities.First().Item1;
-
-      // swap the node that would create the best offspring
-      swap(crossoverPoint0, selectedBranch);
 
       return parent0;