Changeset 7105 for branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover.cs

Timestamp:

11/30/11 17:21:30 (12 years ago)

Author:

bburlacu

Message:

#1682: Implemented the ProbabilisticFunctionalCrossover.

File:

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

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

@@ -59 +59 @@
     public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
                                                 ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, T problemData, IEnumerable<int> rows, int maxDepth, int maxLength) {
-      List<CutPoint> crossoverPoints0 = new List<CutPoint>();
+      var crossoverPoints0 = new List<CutPoint>();
       parent0.Root.ForEachNodePostfix((n) => {
         if (n.Subtrees.Any() && n != parent0.Root)
@@ -65 +65 @@
             crossoverPoints0.Add(new CutPoint(n, child));
       });
-      CutPoint crossoverPoint0 = crossoverPoints0[random.Next(crossoverPoints0.Count)];
+      var 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>();
+      var allowedBranches = new List<ISymbolicExpressionTreeNode>();
       parent1.Root.ForEachNodePostfix((n) => {
         if (n.Subtrees.Any() && n != parent1.Root)
@@ -88 +88 @@
       var rootSymbol = new ProgramRootSymbol();
       var startSymbol = new StartSymbol();
-      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol);
+      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol); // this will change crossoverPoint0.Child.Parent
       IEnumerable<double> estimatedValues0 = interpreter.GetSymbolicExpressionTreeValues(tree0, dataset, rows);
       double min0 = estimatedValues0.Min();
       double max0 = estimatedValues0.Max();
+      crossoverPoint0.Child.Parent = crossoverPoint0.Parent; // restore correct parent 
 
-      List<double> weights = new List<double>();
+      var weights = new List<double>();
       foreach (var node in allowedBranches) {
+        var parent = node.Parent;
         var tree1 = CreateTreeFromNode(random, node, rootSymbol, startSymbol);
         IEnumerable<double> estimatedValues1 = interpreter.GetSymbolicExpressionTreeValues(tree1, dataset, rows);
         double min1 = estimatedValues1.Min();
         double max1 = estimatedValues1.Max();
-
-        double behavioralDistance = (Math.Abs(min0 - min1) + Math.Abs(max0 - max1)) / 2;
-
+        double behavioralDistance = (Math.Abs(min0 - min1) + Math.Abs(max0 - max1)) / 2; // this can be NaN of Infinity because some trees are crazy like exp(exp(exp(...))), we correct that below
         weights.Add(behavioralDistance);
+        node.Parent = parent; // restore correct node parent
       }
 
-      ISymbolicExpressionTreeNode selectedBranch = SelectRandomBranch(random, allowedBranches, weights);
+      // remove branches with an infinite or NaN behavioral distance
+      for (int i = 0; i != weights.Count; ++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)
+        return parent0;
+
+      ISymbolicExpressionTreeNode selectedBranch;
+      double sum = weights.Sum();
+      if (sum == 0.0)
+        selectedBranch = allowedBranches[0]; // just return the first, since we don't care (all weights are zero)
+      else {
+        // transform similarity distances into probabilities by normalizing and inverting the values
+        for (int i = 0; i != weights.Count; ++i)
+          weights[i] = (1 - weights[i] / sum);
+
+        selectedBranch = SelectRandomBranch(random, allowedBranches, weights);
+      }
       swap(crossoverPoint0, selectedBranch);
-
       return parent0;
     }
@@ -128 +149 @@
 
     private static ISymbolicExpressionTreeNode SelectRandomBranch(IRandom random, List<ISymbolicExpressionTreeNode> nodes, List<double> weights) {
-      // transform similarity distances into probabilities by normalizing and inverting the values
-      double sum = weights.Sum();
-      for (int i = 0; i != weights.Count; ++i)
-        weights[i] = (1 - weights[i] / sum);
       double r = weights.Sum() * random.NextDouble();
       for (int i = 0; i != nodes.Count; ++i) {
@@ -138 +155 @@
         r -= weights[i];
       }
-      return null;
+      return nodes.Last();
     }
   }