Changeset 8286

Timestamp:

07/11/12 16:43:09 (12 years ago)

Author:

gkronber

Message:

#1847 experimental changes to try to get TS to work

Location:

branches/GP-MoveOperators

Files:

• HeuristicLab.Optimization.Operators/3.3/TabuMaker.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs (modified) (4 diffs)

branches/GP-MoveOperators/HeuristicLab.Optimization.Operators/3.3/TabuMaker.cs

@@ -65 +65 @@
       ItemList<IItem> tabuList = TabuListParameter.ActualValue;
       int tabuTenure = TabuTenureParameter.ActualValue.Value;
+      if (tabuTenure > 0) {
+        // overlength should always be zero
+        int overlength = tabuList.Count - tabuTenure;
+        // copy and remove from back for performance
+        if (overlength >= 0) {
+          for (int i = 0; i < tabuTenure - 1; i++)
+            tabuList[i] = tabuList[i + overlength + 1];
+          while (tabuList.Count >= tabuTenure)
+            tabuList.RemoveAt(tabuList.Count - 1);
+        }
 
-      int overlength = tabuList.Count - tabuTenure;
-      if (overlength >= 0) {
-        for (int i = 0; i < tabuTenure - 1; i++)
-          tabuList[i] = tabuList[i + overlength + 1];
-        while (tabuList.Count >= tabuTenure)
-          tabuList.RemoveAt(tabuList.Count - 1);
+        tabuList.Add(GetTabuAttribute(MaximizationParameter.ActualValue.Value, QualityParameter.ActualValue.Value,
+                                      MoveQualityParameter.ActualValue.Value));
       }
-
-      tabuList.Add(GetTabuAttribute(MaximizationParameter.ActualValue.Value, QualityParameter.ActualValue.Value, MoveQualityParameter.ActualValue.Value));
       return base.Apply();
     }

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

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Linq;
 using HeuristicLab.Common;

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

@@ -55 +55 @@
       get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
     }
-    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
-      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
+    public ValueParameter<BoolValue> UseQualityAspirationCriterionParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseQualityAspirationCriterion"]; }
+    }
+    public ValueParameter<BoolValue> UseSemanticAspirationCriterionParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseSemanticAspirationCriterion"]; }
+    }
+    public ILookupParameter<DoubleValue> SemanticAspirationParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["SemanticAspirations"]; }
+    }
+    public ILookupParameter<DoubleValue> QualityAspirationParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["QualityAspirations"]; }
     }
 
-    public BoolValue UseAspirationCriterion {
-      get { return UseAspirationCriterionParameter.Value; }
-      set { UseAspirationCriterionParameter.Value = value; }
+    public BoolValue UseQualityAspirationCriterion {
+      get { return UseQualityAspirationCriterionParameter.Value; }
+      set { UseQualityAspirationCriterionParameter.Value = value; }
+    }
+    public BoolValue UseSemanticAspirationCriterion {
+      get { return UseSemanticAspirationCriterionParameter.Value; }
+      set { UseSemanticAspirationCriterionParameter.Value = value; }
     }
 
@@ -73 +86 @@
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The solution as symbolic expression tree."));
       Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
-      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<BoolValue>("UseQualityAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
+      Parameters.Add(new ValueParameter<BoolValue>("UseSemanticAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
       Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
+      Parameters.Add(new LookupParameter<DoubleValue>("SemanticAspirations"));
+      Parameters.Add(new LookupParameter<DoubleValue>("QualityAspirations"));
     }
 
@@ -87 +103 @@
       var tree = SymbolicExpressionTreeParameter.ActualValue;
       bool isTabu = true;
-      bool useAspiration = UseAspirationCriterion.Value;
+      bool useQualityAspiration = UseQualityAspirationCriterion.Value;
+      bool useSemanticAspiration = UseSemanticAspirationCriterion.Value;
       bool maximization = MaximizationParameter.ActualValue.Value;
       double moveQuality = MoveQualityParameter.ActualValue.Value;
@@ -103 +120 @@
 
       isTabu = false;
-      for (int i = 0; i < tabuList.Count && isTabu == false; i++) {
+      int semanticAspirations = 0;
+      int qualityAspirations = 0;
+      // run through the tabu list backwards so that we can break at the most recent relevant change
+      for (int i = tabuList.Count - 1; i >= 0 && isTabu == false; i--) {
         var tabuAttribute = tabuList[i];
         var absTabuAttribute = tabuAttribute as ChangeNodeTypeMoveAbsoluteAttribute;
-        if (!useAspiration
-              || maximization && moveQuality <= absTabuAttribute.MoveQuality
-              || !maximization && moveQuality >= absTabuAttribute.MoveQuality) {
-          if (absTabuAttribute.Path.Length == path.Count) {
-            isTabu = true;
-            for (int j = 0; j < path.Count; j++) {
-              if (absTabuAttribute.Path[j] != path[j]) {
-                isTabu = false;
-                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;
-            }
-          }
+        // three aspiration criteria
+        if (useQualityAspiration && IsBetter(maximization, moveQuality, absTabuAttribute.MoveQuality)) {
+          qualityAspirations++;
+          continue;
+        }
+        if (BeginsWith(path, absTabuAttribute.Path))
+          break; // not necessary to check the remainder of the tabu list
+
+        isTabu = IsSamePath(path, absTabuAttribute.Path);
+        // check semantic aspiration criterion only afterwards because it is expansive to evaluate
+        if (isTabu && useSemanticAspiration && IsLessSimilar(absTabuAttribute, move)) {
+          isTabu = false;
+          semanticAspirations++;
         }
       }
 
       MoveTabuParameter.ActualValue = new BoolValue(isTabu);
+      var semAsp = SemanticAspirationParameter.ActualValue ?? new DoubleValue();
+      var qualAsp = QualityAspirationParameter.ActualValue ?? new DoubleValue();
+      semAsp.Value += semanticAspirations;
+      qualAsp.Value += qualityAspirations;
+      SemanticAspirationParameter.ActualValue = semAsp;
+      QualityAspirationParameter.ActualValue = qualAsp;
       return base.Apply();
+    }
+
+    // checks wether the path to the node is the same or the tabu path is a parent
+    private bool IsSamePath(List<int> path, int[] tabuPath) {
+      if (tabuPath.Length != path.Count) return false;
+      for (int j = 0; j < tabuPath.Length; j++) {
+        if (tabuPath[j] != path[j]) {
+          return false;
+        }
+      }
+      return true;
+    }
+
+    private bool IsLessSimilar(ChangeNodeTypeMoveAbsoluteAttribute tabuAttribute, ReplaceBranchMove move) {
+      // 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(tabuAttribute.PreviousOutput, move.NewOutput, out error);
+      if (error != OnlineCalculatorError.None) rPrevNext = 0.0;
+      double rPrevCurrent = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.OriginalOutput,
+                                                                       out error);
+      if (error != OnlineCalculatorError.None) rPrevCurrent = 0.0;
+      return rPrevNext < rPrevCurrent;
+    }
+
+    private bool BeginsWith(List<int> path, int[] prefix) {
+      if (path.Count <= prefix.Length) return false;
+      for (int j = 0; j < prefix.Length; j++)
+        if (prefix[j] != path[j]) return false;
+      return true;
+    }
+
+    private bool IsBetter(bool maximization, double lhs, double rhs) {
+      return maximization ? lhs > rhs : lhs < rhs;
     }
   }

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

@@ -91 +91 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["NeighbourhoodSize"]; }
     }
-
+    public IValueLookupParameter<BoolValue> SemanticParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Semantic"]; }
+    }
 
     private IList<ISymbolicExpressionTree> fragments;
@@ -116 +118 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength"));
       Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Semantic", new BoolValue()));
     }
 
@@ -171 +174 @@
 
     public IEnumerable<ReplaceBranchMove> GenerateMoves(ISymbolicExpressionTree tree, IRandom random, int n) {
-      int count = 0;
-      var possibleChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
-                              from i in Enumerable.Range(0, parent.SubtreeCount)
-                              let currentChild = parent.GetSubtree(i)
-                              select new { parent, i }).ToArray();
+      int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
+      int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
+      var possibleInternalChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
+                                      from i in Enumerable.Range(0, parent.SubtreeCount)
+                                      let currentChild = parent.GetSubtree(i)
+                                      where currentChild.SubtreeCount > 0
+                                      where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
+                                      where tree.Length - currentChild.GetLength() < maxLength
+                                      select new CutPoint(parent, i)).ToArray();
+
+      var possibleLeaveChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
+                                   from i in Enumerable.Range(0, parent.SubtreeCount)
+                                   let currentChild = parent.GetSubtree(i)
+                                   where currentChild.SubtreeCount == 0
+                                   where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
+                                   where tree.Length - 1 < maxLength
+                                   select new CutPoint(parent, i)).ToArray();
+
 
       var root = (new ProgramRootSymbol()).CreateTreeNode();
@@ -185 +201 @@
       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
-        var selected = possibleChildren[random.Next(possibleChildren.Length)];
-        // evaluate 
-        start.AddSubtree(selected.parent.GetSubtree(selected.i));
-        var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
-        start.RemoveSubtree(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 < fragments.Count; i++) {
-          // if the branch is allowed in the selected point
-          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;
+      bool semantic = SemanticParameter.ActualValue.Value;
+
+      // select a random replacement point
+      CutPoint[] possibleChildren;
+      if (random.NextDouble() < 0.9)
+        possibleChildren = possibleInternalChildren;
+      else possibleChildren = possibleLeaveChildren;
+      var selected = possibleChildren[random.Next(possibleChildren.Length)];
+      // evaluate 
+      start.AddSubtree(selected.Parent.GetSubtree(selected.ChildIndex));
+      var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
+      start.RemoveSubtree(0);
+
+      if (semantic) {
+        return FindMostSimilarFragments(tree, maxLength, maxDepth, selected, random, n, output);
+      } else {
+        return FindRandomFragments(tree, maxLength, maxDepth, selected, random, n, output);
+      }
+    }
+
+    private IEnumerable<ReplaceBranchMove> FindRandomFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
+  IRandom random, int maxNeighbours, double[] output) {
+      var selectedFragments = new List<Tuple<ISymbolicExpressionTree, double[]>>(maxNeighbours);
+      int treeLength = tree.Length;
+      int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
+      int parentBranchLevel = tree.Root.GetBranchLevel(selected.Parent);
+      int iterations = 0;
+      int maxIterations = maxNeighbours + 100;
+      // select random fragments
+      while (selectedFragments.Count < maxNeighbours && iterations++ < maxIterations) {
+        int r = random.Next(fragments.Count);
+        var selectedFragment = fragments[r];
+        var selectedFragmentOutput = fragmentOutput[r];
+        // if the branch is allowed in the selected point
+        if (treeLength - removedFragementLength + selectedFragment.Length <= maxLength + 4 &&
+          parentBranchLevel + selectedFragment.Depth - 2 <= maxDepth + 2 &&
+          tree.Root.Grammar.IsAllowedChildSymbol(selected.Parent.Symbol, selectedFragment.Root.GetSubtree(0).GetSubtree(0).Symbol, selected.ChildIndex)) {
+          selectedFragments.Add(Tuple.Create(selectedFragment, selectedFragmentOutput));
+        }
+      }
+      // yield moves (we need to add linear scaling parameters for the inserted tree)
+      return selectedFragments
+        .Select(pair => new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0), output, pair.Item2));
+    }
+
+    private IEnumerable<ReplaceBranchMove> FindMostSimilarFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
+      IRandom random, int maxNeighbours, double[] output) {
+      var bestTrees = new SortedList<double, List<Tuple<ISymbolicExpressionTree, double[]>>>(fragments.Count);
+      int treeLength = tree.Length;
+      int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
+      int parentBranchLevel = tree.Root.GetBranchLevel(selected.Parent);
+      // iterate over the whole pool of branches for replacement
+      for (int i = 0; i < fragments.Count; i++) {
+        // if the branch is allowed in the selected point
+        if (treeLength - removedFragementLength + fragments[i].Length <= maxLength + 4 &&
+          parentBranchLevel + fragments[i].Depth - 2 <= maxDepth + 2 &&
+          tree.Root.Grammar.IsAllowedChildSymbol(selected.Parent.Symbol, fragments[i].Root.GetSubtree(0).GetSubtree(0).Symbol, selected.ChildIndex)) {
+          OnlineCalculatorError error;
+          // calculate the similarity
+          double similarity = OnlinePearsonsRSquaredCalculator.Calculate(output, fragmentOutput[i], out error);
+          similarity = Math.Round(similarity, 5);
+          if (error != OnlineCalculatorError.None) similarity = 0.0;
+          // if we found a new bestSimilarity then keep the replacement branch in a sorted list (keep maximally the n best for this replacement point)
+          if (similarity < 1 && ((bestTrees.Count < maxNeighbours) || similarity > bestTrees.ElementAt(0).Key)) {
+            if (!bestTrees.ContainsKey(similarity)) {
+              var l = new List<Tuple<ISymbolicExpressionTree, double[]>>();
+              bestTrees.Add(similarity, l);
             }
-            // 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.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
-              }
-            }
+            bestTrees[similarity].Add(Tuple.Create(fragments[i], fragmentOutput[i]));
+            if (bestTrees.Count > maxNeighbours) bestTrees.RemoveAt(0);
           }
         }
-        // yield moves (we need to add linear scaling parameters for the inserted tree)
-        foreach (var pair in bestTrees.Values) {
-          yield return
-            new ReplaceBranchMove(tree, selected.parent, selected.i, pair.Item1.Root.GetSubtree(0).GetSubtree(0), output, pair.Item2);
-          count++;
-        }
+      }
+      int c = 0;
+      // yield moves (we need to add linear scaling parameters for the inserted tree)
+      while (c < maxNeighbours) {
+        var l = bestTrees.ElementAt(c % bestTrees.Count).Value;
+        var pair = l[random.Next(l.Count)];
+        yield return
+          new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0),
+                                output, pair.Item2);
+        c++;
       }
     }