Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/GP-MoveOperators/HeuristicLab.Optimization.Operators/3.3/TabuMaker.cs

    r7259 r8286  
    6565      ItemList<IItem> tabuList = TabuListParameter.ActualValue;
    6666      int tabuTenure = TabuTenureParameter.ActualValue.Value;
     67      if (tabuTenure > 0) {
     68        // overlength should always be zero
     69        int overlength = tabuList.Count - tabuTenure;
     70        // copy and remove from back for performance
     71        if (overlength >= 0) {
     72          for (int i = 0; i < tabuTenure - 1; i++)
     73            tabuList[i] = tabuList[i + overlength + 1];
     74          while (tabuList.Count >= tabuTenure)
     75            tabuList.RemoveAt(tabuList.Count - 1);
     76        }
    6777
    68       int overlength = tabuList.Count - tabuTenure;
    69       if (overlength >= 0) {
    70         for (int i = 0; i < tabuTenure - 1; i++)
    71           tabuList[i] = tabuList[i + overlength + 1];
    72         while (tabuList.Count >= tabuTenure)
    73           tabuList.RemoveAt(tabuList.Count - 1);
     78        tabuList.Add(GetTabuAttribute(MaximizationParameter.ActualValue.Value, QualityParameter.ActualValue.Value,
     79                                      MoveQualityParameter.ActualValue.Value));
    7480      }
    75 
    76       tabuList.Add(GetTabuAttribute(MaximizationParameter.ActualValue.Value, QualityParameter.ActualValue.Value, MoveQualityParameter.ActualValue.Value));
    7781      return base.Apply();
    7882    }
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs

    r8214 r8286  
    2020#endregion
    2121
    22 using System;
    2322using System.Linq;
    2423using HeuristicLab.Common;
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs

    r8214 r8286  
    5555      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    5656    }
    57     public ValueParameter<BoolValue> UseAspirationCriterionParameter {
    58       get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
     57    public ValueParameter<BoolValue> UseQualityAspirationCriterionParameter {
     58      get { return (ValueParameter<BoolValue>)Parameters["UseQualityAspirationCriterion"]; }
     59    }
     60    public ValueParameter<BoolValue> UseSemanticAspirationCriterionParameter {
     61      get { return (ValueParameter<BoolValue>)Parameters["UseSemanticAspirationCriterion"]; }
     62    }
     63    public ILookupParameter<DoubleValue> SemanticAspirationParameter {
     64      get { return (ILookupParameter<DoubleValue>)Parameters["SemanticAspirations"]; }
     65    }
     66    public ILookupParameter<DoubleValue> QualityAspirationParameter {
     67      get { return (ILookupParameter<DoubleValue>)Parameters["QualityAspirations"]; }
    5968    }
    6069
    61     public BoolValue UseAspirationCriterion {
    62       get { return UseAspirationCriterionParameter.Value; }
    63       set { UseAspirationCriterionParameter.Value = value; }
     70    public BoolValue UseQualityAspirationCriterion {
     71      get { return UseQualityAspirationCriterionParameter.Value; }
     72      set { UseQualityAspirationCriterionParameter.Value = value; }
     73    }
     74    public BoolValue UseSemanticAspirationCriterion {
     75      get { return UseSemanticAspirationCriterionParameter.Value; }
     76      set { UseSemanticAspirationCriterionParameter.Value = value; }
    6477    }
    6578
     
    7386      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The solution as symbolic expression tree."));
    7487      Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
    75       Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
     88      Parameters.Add(new ValueParameter<BoolValue>("UseQualityAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
     89      Parameters.Add(new ValueParameter<BoolValue>("UseSemanticAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
    7690      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
    7791      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
     92      Parameters.Add(new LookupParameter<DoubleValue>("SemanticAspirations"));
     93      Parameters.Add(new LookupParameter<DoubleValue>("QualityAspirations"));
    7894    }
    7995
     
    87103      var tree = SymbolicExpressionTreeParameter.ActualValue;
    88104      bool isTabu = true;
    89       bool useAspiration = UseAspirationCriterion.Value;
     105      bool useQualityAspiration = UseQualityAspirationCriterion.Value;
     106      bool useSemanticAspiration = UseSemanticAspirationCriterion.Value;
    90107      bool maximization = MaximizationParameter.ActualValue.Value;
    91108      double moveQuality = MoveQualityParameter.ActualValue.Value;
     
    103120
    104121      isTabu = false;
    105       for (int i = 0; i < tabuList.Count && isTabu == false; i++) {
     122      int semanticAspirations = 0;
     123      int qualityAspirations = 0;
     124      // run through the tabu list backwards so that we can break at the most recent relevant change
     125      for (int i = tabuList.Count - 1; i >= 0 && isTabu == false; i--) {
    106126        var tabuAttribute = tabuList[i];
    107127        var absTabuAttribute = tabuAttribute as ChangeNodeTypeMoveAbsoluteAttribute;
    108         if (!useAspiration
    109               || maximization && moveQuality <= absTabuAttribute.MoveQuality
    110               || !maximization && moveQuality >= absTabuAttribute.MoveQuality) {
    111           if (absTabuAttribute.Path.Length == path.Count) {
    112             isTabu = true;
    113             for (int j = 0; j < path.Count; j++) {
    114               if (absTabuAttribute.Path[j] != path[j]) {
    115                 isTabu = false;
    116                 break;
    117               }
    118             }
    119             if (isTabu) {
    120               // check correlations
    121               // R(prev, next)
    122               // R(current, next)
    123               // tabu = R(prev,next) > R(current,next)
    124               // == the new move would be closer to the original than the previous move
    125               OnlineCalculatorError error;
    126               double rPrevNext = OnlinePearsonsRSquaredCalculator.Calculate(absTabuAttribute.PreviousOutput, move.NewOutput, out error);
    127               if (error != OnlineCalculatorError.None) rPrevNext = 0.0;
    128               double rCurrentNext = OnlinePearsonsRSquaredCalculator.Calculate(absTabuAttribute.PreviousOutput, move.OriginalOutput,
    129                                                                                out error);
    130               if (error != OnlineCalculatorError.None) rCurrentNext = 0.0;
    131               isTabu = rPrevNext >= rCurrentNext;
    132             }
    133           }
     128        // three aspiration criteria
     129        if (useQualityAspiration && IsBetter(maximization, moveQuality, absTabuAttribute.MoveQuality)) {
     130          qualityAspirations++;
     131          continue;
     132        }
     133        if (BeginsWith(path, absTabuAttribute.Path))
     134          break; // not necessary to check the remainder of the tabu list
     135
     136        isTabu = IsSamePath(path, absTabuAttribute.Path);
     137        // check semantic aspiration criterion only afterwards because it is expansive to evaluate
     138        if (isTabu && useSemanticAspiration && IsLessSimilar(absTabuAttribute, move)) {
     139          isTabu = false;
     140          semanticAspirations++;
    134141        }
    135142      }
    136143
    137144      MoveTabuParameter.ActualValue = new BoolValue(isTabu);
     145      var semAsp = SemanticAspirationParameter.ActualValue ?? new DoubleValue();
     146      var qualAsp = QualityAspirationParameter.ActualValue ?? new DoubleValue();
     147      semAsp.Value += semanticAspirations;
     148      qualAsp.Value += qualityAspirations;
     149      SemanticAspirationParameter.ActualValue = semAsp;
     150      QualityAspirationParameter.ActualValue = qualAsp;
    138151      return base.Apply();
     152    }
     153
     154    // checks wether the path to the node is the same or the tabu path is a parent
     155    private bool IsSamePath(List<int> path, int[] tabuPath) {
     156      if (tabuPath.Length != path.Count) return false;
     157      for (int j = 0; j < tabuPath.Length; j++) {
     158        if (tabuPath[j] != path[j]) {
     159          return false;
     160        }
     161      }
     162      return true;
     163    }
     164
     165    private bool IsLessSimilar(ChangeNodeTypeMoveAbsoluteAttribute tabuAttribute, ReplaceBranchMove move) {
     166      // check correlations
     167      // R(prev, next)
     168      // R(current, next)
     169      // tabu = R(prev,next) > R(current,next)
     170      // == the new move would be closer to the original than the previous move
     171      OnlineCalculatorError error;
     172      double rPrevNext = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.NewOutput, out error);
     173      if (error != OnlineCalculatorError.None) rPrevNext = 0.0;
     174      double rPrevCurrent = OnlinePearsonsRSquaredCalculator.Calculate(tabuAttribute.PreviousOutput, move.OriginalOutput,
     175                                                                       out error);
     176      if (error != OnlineCalculatorError.None) rPrevCurrent = 0.0;
     177      return rPrevNext < rPrevCurrent;
     178    }
     179
     180    private bool BeginsWith(List<int> path, int[] prefix) {
     181      if (path.Count <= prefix.Length) return false;
     182      for (int j = 0; j < prefix.Length; j++)
     183        if (prefix[j] != path[j]) return false;
     184      return true;
     185    }
     186
     187    private bool IsBetter(bool maximization, double lhs, double rhs) {
     188      return maximization ? lhs > rhs : lhs < rhs;
    139189    }
    140190  }
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs

    r8214 r8286  
    9191      get { return (IValueLookupParameter<IntValue>)Parameters["NeighbourhoodSize"]; }
    9292    }
    93 
     93    public IValueLookupParameter<BoolValue> SemanticParameter {
     94      get { return (IValueLookupParameter<BoolValue>)Parameters["Semantic"]; }
     95    }
    9496
    9597    private IList<ISymbolicExpressionTree> fragments;
     
    116118      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength"));
    117119      Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
     120      Parameters.Add(new ValueLookupParameter<BoolValue>("Semantic", new BoolValue()));
    118121    }
    119122
     
    171174
    172175    public IEnumerable<ReplaceBranchMove> GenerateMoves(ISymbolicExpressionTree tree, IRandom random, int n) {
    173       int count = 0;
    174       var possibleChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
    175                               from i in Enumerable.Range(0, parent.SubtreeCount)
    176                               let currentChild = parent.GetSubtree(i)
    177                               select new { parent, i }).ToArray();
     176      int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
     177      int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
     178      var possibleInternalChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
     179                                      from i in Enumerable.Range(0, parent.SubtreeCount)
     180                                      let currentChild = parent.GetSubtree(i)
     181                                      where currentChild.SubtreeCount > 0
     182                                      where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
     183                                      where tree.Length - currentChild.GetLength() < maxLength
     184                                      select new CutPoint(parent, i)).ToArray();
     185
     186      var possibleLeaveChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
     187                                   from i in Enumerable.Range(0, parent.SubtreeCount)
     188                                   let currentChild = parent.GetSubtree(i)
     189                                   where currentChild.SubtreeCount == 0
     190                                   where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
     191                                   where tree.Length - 1 < maxLength
     192                                   select new CutPoint(parent, i)).ToArray();
     193
    178194
    179195      var root = (new ProgramRootSymbol()).CreateTreeNode();
     
    185201      var rows = ProblemDataParameter.ActualValue.TrainingIndices;
    186202
    187       int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
    188       int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
    189       int neighbourhoodSize = NeighbourhoodSizeParameter.ActualValue.Value;
    190       while (count < n) {
    191         // select a random replacement point
    192         var selected = possibleChildren[random.Next(possibleChildren.Length)];
    193         // evaluate
    194         start.AddSubtree(selected.parent.GetSubtree(selected.i));
    195         var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
    196         start.RemoveSubtree(0);
    197 
    198         var bestTrees = new SortedList<double, Tuple<ISymbolicExpressionTree, double[]>>(fragments.Count);
    199         // iterate over the whole pool of branches for replacement
    200         for (int i = 0; i < fragments.Count; i++) {
    201           // if the branch is allowed in the selected point
    202           if (tree.Length - selected.parent.GetSubtree(selected.i).GetLength() + fragments[i].Length <= maxLength + 2 &&
    203             tree.Root.GetBranchLevel(selected.parent) + fragments[i].Depth - 2 <= maxDepth + 2 &&
    204             tree.Root.Grammar.IsAllowedChildSymbol(selected.parent.Symbol, fragments[i].Root.GetSubtree(0).GetSubtree(0).Symbol, selected.i)) {
    205             double similarity;
    206             if (neighbourhoodSize > 0) {
    207               OnlineCalculatorError error;
    208               // calculate the similarity
    209               similarity = OnlinePearsonsRSquaredCalculator.Calculate(output, fragmentOutput[i], out error);
    210               if (error != OnlineCalculatorError.None) similarity = 0.0;
    211             } else {
    212               // neighbourhoodSize = 0 => similarity is not considered
    213               similarity = 0.0;
     203      bool semantic = SemanticParameter.ActualValue.Value;
     204
     205      // select a random replacement point
     206      CutPoint[] possibleChildren;
     207      if (random.NextDouble() < 0.9)
     208        possibleChildren = possibleInternalChildren;
     209      else possibleChildren = possibleLeaveChildren;
     210      var selected = possibleChildren[random.Next(possibleChildren.Length)];
     211      // evaluate
     212      start.AddSubtree(selected.Parent.GetSubtree(selected.ChildIndex));
     213      var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
     214      start.RemoveSubtree(0);
     215
     216      if (semantic) {
     217        return FindMostSimilarFragments(tree, maxLength, maxDepth, selected, random, n, output);
     218      } else {
     219        return FindRandomFragments(tree, maxLength, maxDepth, selected, random, n, output);
     220      }
     221    }
     222
     223    private IEnumerable<ReplaceBranchMove> FindRandomFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
     224  IRandom random, int maxNeighbours, double[] output) {
     225      var selectedFragments = new List<Tuple<ISymbolicExpressionTree, double[]>>(maxNeighbours);
     226      int treeLength = tree.Length;
     227      int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
     228      int parentBranchLevel = tree.Root.GetBranchLevel(selected.Parent);
     229      int iterations = 0;
     230      int maxIterations = maxNeighbours + 100;
     231      // select random fragments
     232      while (selectedFragments.Count < maxNeighbours && iterations++ < maxIterations) {
     233        int r = random.Next(fragments.Count);
     234        var selectedFragment = fragments[r];
     235        var selectedFragmentOutput = fragmentOutput[r];
     236        // if the branch is allowed in the selected point
     237        if (treeLength - removedFragementLength + selectedFragment.Length <= maxLength + 4 &&
     238          parentBranchLevel + selectedFragment.Depth - 2 <= maxDepth + 2 &&
     239          tree.Root.Grammar.IsAllowedChildSymbol(selected.Parent.Symbol, selectedFragment.Root.GetSubtree(0).GetSubtree(0).Symbol, selected.ChildIndex)) {
     240          selectedFragments.Add(Tuple.Create(selectedFragment, selectedFragmentOutput));
     241        }
     242      }
     243      // yield moves (we need to add linear scaling parameters for the inserted tree)
     244      return selectedFragments
     245        .Select(pair => new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0), output, pair.Item2));
     246    }
     247
     248    private IEnumerable<ReplaceBranchMove> FindMostSimilarFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
     249      IRandom random, int maxNeighbours, double[] output) {
     250      var bestTrees = new SortedList<double, List<Tuple<ISymbolicExpressionTree, double[]>>>(fragments.Count);
     251      int treeLength = tree.Length;
     252      int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
     253      int parentBranchLevel = tree.Root.GetBranchLevel(selected.Parent);
     254      // iterate over the whole pool of branches for replacement
     255      for (int i = 0; i < fragments.Count; i++) {
     256        // if the branch is allowed in the selected point
     257        if (treeLength - removedFragementLength + fragments[i].Length <= maxLength + 4 &&
     258          parentBranchLevel + fragments[i].Depth - 2 <= maxDepth + 2 &&
     259          tree.Root.Grammar.IsAllowedChildSymbol(selected.Parent.Symbol, fragments[i].Root.GetSubtree(0).GetSubtree(0).Symbol, selected.ChildIndex)) {
     260          OnlineCalculatorError error;
     261          // calculate the similarity
     262          double similarity = OnlinePearsonsRSquaredCalculator.Calculate(output, fragmentOutput[i], out error);
     263          similarity = Math.Round(similarity, 5);
     264          if (error != OnlineCalculatorError.None) similarity = 0.0;
     265          // if we found a new bestSimilarity then keep the replacement branch in a sorted list (keep maximally the n best for this replacement point)
     266          if (similarity < 1 && ((bestTrees.Count < maxNeighbours) || similarity > bestTrees.ElementAt(0).Key)) {
     267            if (!bestTrees.ContainsKey(similarity)) {
     268              var l = new List<Tuple<ISymbolicExpressionTree, double[]>>();
     269              bestTrees.Add(similarity, l);
    214270            }
    215             // if we found a new bestSimilarity then keep the replacement branch in a sorted list (keep maximally the 30 best for this replacement point)
    216             if (!similarity.IsAlmost(1.0)) {
    217               bestTrees.Add(similarity + random.NextDouble() * 1E-6, Tuple.Create(fragments[i], fragmentOutput[i]));
    218               if (neighbourhoodSize > 0 && bestTrees.Count > neighbourhoodSize)
    219                 bestTrees.RemoveAt(0); // remove moves with small R² at the beginning
    220               else if (neighbourhoodSize == 0 && bestTrees.Count > 1) {
    221                 bestTrees.RemoveAt(bestTrees.Count - 1);  // remove the last tree => only a random fragment is kept
    222               }
    223             }
     271            bestTrees[similarity].Add(Tuple.Create(fragments[i], fragmentOutput[i]));
     272            if (bestTrees.Count > maxNeighbours) bestTrees.RemoveAt(0);
    224273          }
    225274        }
    226         // yield moves (we need to add linear scaling parameters for the inserted tree)
    227         foreach (var pair in bestTrees.Values) {
    228           yield return
    229             new ReplaceBranchMove(tree, selected.parent, selected.i, pair.Item1.Root.GetSubtree(0).GetSubtree(0), output, pair.Item2);
    230           count++;
    231         }
     275      }
     276      int c = 0;
     277      // yield moves (we need to add linear scaling parameters for the inserted tree)
     278      while (c < maxNeighbours) {
     279        var l = bestTrees.ElementAt(c % bestTrees.Count).Value;
     280        var pair = l[random.Next(l.Count)];
     281        yield return
     282          new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0),
     283                                output, pair.Item2);
     284        c++;
    232285      }
    233286    }
Note: See TracChangeset for help on using the changeset viewer.