Changeset 8214 for branches/GP-MoveOperators

Timestamp:

07/04/12 16:23:35 (12 years ago)

Author:

gkronber

Message:

#1847: bug fixes and improvements discussed with andreas

Location:

branches/GP-MoveOperators

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMoveAbsoluteAttribute.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveMaker.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveTabuMaker.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs (modified) (10 diffs)

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMoveAbsoluteAttribute.cs

@@ -31 +31 @@
     public int[] Path { get; private set; }
 
+    [Storable]
+    public double[] PreviousOutput { get; private set; }
+
+    // for debugging
+    [Storable]
+    public double[] NewOutput { get; private set; }
+
     [StorableConstructor]
     protected ChangeNodeTypeMoveAbsoluteAttribute(bool deserializing) : base(deserializing) { }
@@ -36 +43 @@
       : base(original, cloner) {
       this.Path = (int[])original.Path.Clone();
+      this.PreviousOutput = original.PreviousOutput;
+      this.NewOutput = original.NewOutput;
     }
-    public ChangeNodeTypeMoveAbsoluteAttribute(int[] path, double moveQuality)
+    public ChangeNodeTypeMoveAbsoluteAttribute(int[] path, double moveQuality, double[] prevOutput, double[] newOutput)
       : base(moveQuality) {
       Path = path;
+      PreviousOutput = prevOutput;
+      NewOutput = newOutput;
     }
 

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Linq;
 using HeuristicLab.Common;
@@ -86 +87 @@
       OnlineLinearScalingParameterCalculator.Calculate(move.NewOutput, move.OriginalOutput, out alpha, out beta, out errorState);
 
+      // prevent scaling to a constant value
+      if (beta.IsAlmost(0.0)) beta = 10E-5;
+
       move.Alpha = alpha;
       move.Beta = beta;
 
-      // clone tree and parent
-      var cloner = new Cloner();
-      var clonedTree = cloner.Clone(move.Tree);
-      var clonedParent = cloner.Clone(move.Parent);
-      var clonedBranch = cloner.Clone(move.NewBranch);
-
-      clonedParent.RemoveSubtree(move.SubtreeIndex);
-      clonedParent.InsertSubtree(move.SubtreeIndex, Scale(clonedBranch, alpha, beta));
+      var oldBranch = move.Parent.GetSubtree(move.SubtreeIndex);
+      move.Parent.RemoveSubtree(move.SubtreeIndex);
+      move.Parent.InsertSubtree(move.SubtreeIndex, Scale(move.NewBranch, alpha, beta));
 
       var problemData = ProblemDataParameter.ActualValue;
@@ -103 +102 @@
       var fitnessPartition = FitnessCalculationPartitionParameter.ActualValue;
       var rows = Enumerable.Range(fitnessPartition.Start, fitnessPartition.End - fitnessPartition.Start);
-      var quality = evaluator.Evaluate(childContext, clonedTree, problemData, rows);
+      var quality = evaluator.Evaluate(childContext, move.Tree, problemData, rows);
+
+      // revert changes to tree
+      move.Parent.RemoveSubtree(move.SubtreeIndex);
+      move.Parent.InsertSubtree(move.SubtreeIndex, oldBranch);
 
       MoveQualityParameter.ActualValue = new DoubleValue(quality);

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveMaker.cs

@@ -86 +86 @@
 
     private ISymbolicExpressionTreeNode Scale(ISymbolicExpressionTreeNode node, double alpha, double beta) {
-      var constAlpha = (ConstantTreeNode)constant.CreateTreeNode();
-      var constBeta = (ConstantTreeNode)constant.CreateTreeNode();
-      constAlpha.Value = alpha;
-      constBeta.Value = beta;
-      var sum = add.CreateTreeNode();
-      var prod = mul.CreateTreeNode();
-      prod.AddSubtree(node); prod.AddSubtree(constBeta);
-      sum.AddSubtree(prod); sum.AddSubtree(constAlpha);
-      return sum;
+      var constNode = node as ConstantTreeNode;
+      if (constNode != null) {
+        constNode.Value = constNode.Value * beta + alpha;
+        return constNode;
+      }
+      var varNode = node as VariableTreeNode;
+      if (varNode != null) {
+        varNode.Weight = varNode.Weight * beta;
+        var constAlpha = (ConstantTreeNode)constant.CreateTreeNode();
+        constAlpha.Value = alpha;
+        var sum = add.CreateTreeNode();
+        sum.AddSubtree(varNode); sum.AddSubtree(constAlpha);
+        return sum;
+      }
+      if (node.Symbol is Addition && node.GetSubtree(0).Symbol is Multiplication &&
+        node.GetSubtree(1).Symbol is Constant && node.GetSubtree(0).GetSubtree(1).Symbol is Constant) {
+        var constAlpha = node.GetSubtree(1) as ConstantTreeNode;
+        var constBeta = node.GetSubtree(0).GetSubtree(1) as ConstantTreeNode;
+        constAlpha.Value = beta * constAlpha.Value + alpha;
+        constBeta.Value = constBeta.Value * beta;
+        return node;
+      } else {
+        var constAlpha = (ConstantTreeNode)constant.CreateTreeNode();
+        var constBeta = (ConstantTreeNode)constant.CreateTreeNode();
+        constAlpha.Value = alpha;
+        constBeta.Value = beta;
+        var sum = add.CreateTreeNode();
+        var prod = mul.CreateTreeNode();
+        prod.AddSubtree(node);
+        prod.AddSubtree(constBeta);
+        sum.AddSubtree(prod);
+        sum.AddSubtree(constAlpha);
+        return sum;
+      }
     }
   }

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs

@@ -109 +109 @@
               || maximization && moveQuality <= absTabuAttribute.MoveQuality
               || !maximization && moveQuality >= absTabuAttribute.MoveQuality) {
-          if (absTabuAttribute != null && absTabuAttribute.Path.Length == path.Count) {
+          if (absTabuAttribute.Path.Length == path.Count) {
             isTabu = true;
             for (int j = 0; j < path.Count; j++) {
@@ -116 +116 @@
                 break;
               }
+            }
+            if (isTabu) {
+              // check correlations
+              // R(prev, next)
+              // R(current, next)
+              // tabu = R(prev,next) > R(current,next)
+              // == the new move would be closer to the original than the previous move
+              OnlineCalculatorError error;
+              double rPrevNext = OnlinePearsonsRSquaredCalculator.Calculate(absTabuAttribute.PreviousOutput, move.NewOutput, out error);
+              if (error != OnlineCalculatorError.None) rPrevNext = 0.0;
+              double rCurrentNext = OnlinePearsonsRSquaredCalculator.Calculate(absTabuAttribute.PreviousOutput, move.OriginalOutput,
+                                                                               out error);
+              if (error != OnlineCalculatorError.None) rCurrentNext = 0.0;
+              isTabu = rPrevNext >= rCurrentNext;
             }
           }

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveTabuMaker.cs

@@ -55 +55 @@
       var move = ReplaceBranchMoveParameter.ActualValue;
       var tree = SymbolicExpressionTreeParameter.ActualValue;
-      double baseQuality = moveQuality;
-      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality; // we make an uphill move, the lower bound is the solution quality
+      double aspirationThreshold = moveQuality;
+      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) aspirationThreshold = quality; // if we make a bad move, the aspriation threshold is the solution quality
 
       List<int> path = new List<int>();
@@ -68 +68 @@
       }
       path.Reverse();
-      return new ChangeNodeTypeMoveAbsoluteAttribute(path.ToArray(), baseQuality);
+      return new ChangeNodeTypeMoveAbsoluteAttribute(path.ToArray(), aspirationThreshold, move.OriginalOutput, move.NewOutput);
     }
   }

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs

@@ -36 +36 @@
   [StorableClass]
   public class ReplaceBranchMultiMoveGenerator : SingleSuccessorOperator, IStochasticOperator, ISymbolicExpressionTreeMoveOperator, IMultiMoveGenerator,
-    ISymbolicDataAnalysisInterpreterOperator, ISymbolicExpressionTreeGrammarBasedOperator {
+    ISymbolicDataAnalysisInterpreterOperator, ISymbolicExpressionTreeGrammarBasedOperator, ISymbolicExpressionTreeSizeConstraintOperator {
     public ILookupParameter<IRandom> RandomParameter {
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
@@ -53 +53 @@
       get { return (ILookupParameter<IRegressionProblemData>)Parameters["ProblemData"]; }
     }
-
     public IntValue SampleSize {
       get { return SampleSizeParameter.Value; }
@@ -81 +80 @@
     }
 
-    private IList<ISymbolicExpressionTree> trees;
-    private IList<double[]> treeOutput;
+    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumSymbolicExpressionTreeDepth"]; }
+    }
+
+    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumSymbolicExpressionTreeLength"]; }
+    }
+
+    public IValueLookupParameter<IntValue> NeighbourhoodSizeParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["NeighbourhoodSize"]; }
+    }
+
+
+    private IList<ISymbolicExpressionTree> fragments;
+    private IList<double[]> fragmentOutput;
 
     [StorableConstructor]
@@ -101 +113 @@
       Parameters.Add(new ValueParameter<IntValue>("MaxReplacementBranchLength", new IntValue(8)));
       Parameters.Add(new ValueParameter<IntValue>("MaxReplacementBranchDepth", new IntValue(4)));
-    }
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeDepth"));
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength"));
+      Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
+    }
+
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      if (!Parameters.ContainsKey("MaximumSymbolicExpressionTreeDepth")) {
+        Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeDepth"));
+        Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength"));
+      }
+      if (!Parameters.ContainsKey("NeighbourhoodSize")) {
+        Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
+      }
+
+    }
+
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -108 +137 @@
 
     public override void ClearState() {
-      trees = null;
-      treeOutput = null;
+      fragments = null;
+      fragmentOutput = null;
       base.ClearState();
     }
     public override void InitializeState() {
-      trees = null;
-      treeOutput = null;
+      fragments = null;
+      fragmentOutput = null;
       base.InitializeState();
     }
@@ -120 +149 @@
     public override IOperation Apply() {
       var random = RandomParameter.ActualValue;
-      if (trees == null || treeOutput == null) {
+      if (fragments == null || fragmentOutput == null) {
         InitializeOperator();
       }
@@ -156 +185 @@
       var rows = ProblemDataParameter.ActualValue.TrainingIndices;
 
+      int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
+      int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
+      int neighbourhoodSize = NeighbourhoodSizeParameter.ActualValue.Value;
       while (count < n) {
         // select a random replacement point
@@ -164 +196 @@
         start.RemoveSubtree(0);
 
-        var bestTrees = new SortedList<double, Tuple<ISymbolicExpressionTree, double[]>>();
-        double bestSimilarity = 0;
+        var bestTrees = new SortedList<double, Tuple<ISymbolicExpressionTree, double[]>>(fragments.Count);
         // iterate over the whole pool of branches for replacement
-        for (int i = 0; i < trees.Count; i++) {
+        for (int i = 0; i < fragments.Count; i++) {
           // if the branch is allowed in the selected point
-          if (tree.Root.Grammar.IsAllowedChildSymbol(selected.parent.Symbol, trees[i].Root.GetSubtree(0).GetSubtree(0).Symbol, selected.i)) {
-            OnlineCalculatorError error;
-            // calculate the similarity
-            double similarity = OnlinePearsonsRSquaredCalculator.Calculate(output, treeOutput[i], out error);
-            if (error != OnlineCalculatorError.None) similarity = 0.0;
-
+          if (tree.Length - selected.parent.GetSubtree(selected.i).GetLength() + fragments[i].Length <= maxLength + 2 &&
+            tree.Root.GetBranchLevel(selected.parent) + fragments[i].Depth - 2 <= maxDepth + 2 &&
+            tree.Root.Grammar.IsAllowedChildSymbol(selected.parent.Symbol, fragments[i].Root.GetSubtree(0).GetSubtree(0).Symbol, selected.i)) {
+            double similarity;
+            if (neighbourhoodSize > 0) {
+              OnlineCalculatorError error;
+              // calculate the similarity
+              similarity = OnlinePearsonsRSquaredCalculator.Calculate(output, fragmentOutput[i], out error);
+              if (error != OnlineCalculatorError.None) similarity = 0.0;
+            } else {
+              // neighbourhoodSize = 0 => similarity is not considered
+              similarity = 0.0;
+            }
             // if we found a new bestSimilarity then keep the replacement branch in a sorted list (keep maximally the 30 best for this replacement point)
-            if (similarity > bestSimilarity && !similarity.IsAlmost(1.0)) {
-              bestSimilarity = similarity;
-              bestTrees.Add(similarity, Tuple.Create(trees[i], treeOutput[i]));
-              if (bestTrees.Count > 30)
+            if (!similarity.IsAlmost(1.0)) {
+              bestTrees.Add(similarity + random.NextDouble() * 1E-6, Tuple.Create(fragments[i], fragmentOutput[i]));
+              if (neighbourhoodSize > 0 && bestTrees.Count > neighbourhoodSize)
                 bestTrees.RemoveAt(0); // remove moves with small R² at the beginning
-
+              else if (neighbourhoodSize == 0 && bestTrees.Count > 1) {
+                bestTrees.RemoveAt(bestTrees.Count - 1);  // remove the last tree => only a random fragment is kept
+              }
             }
           }
-        }
-        // did not find a move better than similarity 0.0 => create a move to replace it with a random branch
-        // this is necessary to make it possible to replace branches that evaluate to NaN or infinity
-        if (bestTrees.Count == 0) {
-          int r = random.Next(trees.Count);
-          bestTrees.Add(0.0, Tuple.Create(trees[r], treeOutput[r]));
         }
         // yield moves (we need to add linear scaling parameters for the inserted tree)
@@ -215 +248 @@
       // create pool of random branches for replacement (no constants)
       // and evaluate the output
-      // only keep trees if the output does not contain invalid values
+      // only keep fragments if the output does not contain invalid values
       var n = ReplacementBranchesPoolSize.Value.Value;
       while (trees.Count < n) {
@@ -227 +260 @@
       // enable constants again
       constSym.InitialFrequency = oldConstFreq;
-      this.trees = trees;
-      this.treeOutput = treeOutput;
-    }
-
+      this.fragments = trees;
+      this.fragmentOutput = treeOutput;
+    }
   }
 }