Changeset 8214


Ignore:
Timestamp:
07/04/12 16:23:35 (10 years ago)
Author:
gkronber
Message:

#1847: bug fixes and improvements discussed with andreas

Location:
branches/GP-MoveOperators
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMoveAbsoluteAttribute.cs

    r7832 r8214  
    3131    public int[] Path { get; private set; }
    3232
     33    [Storable]
     34    public double[] PreviousOutput { get; private set; }
     35
     36    // for debugging
     37    [Storable]
     38    public double[] NewOutput { get; private set; }
     39
    3340    [StorableConstructor]
    3441    protected ChangeNodeTypeMoveAbsoluteAttribute(bool deserializing) : base(deserializing) { }
     
    3643      : base(original, cloner) {
    3744      this.Path = (int[])original.Path.Clone();
     45      this.PreviousOutput = original.PreviousOutput;
     46      this.NewOutput = original.NewOutput;
    3847    }
    39     public ChangeNodeTypeMoveAbsoluteAttribute(int[] path, double moveQuality)
     48    public ChangeNodeTypeMoveAbsoluteAttribute(int[] path, double moveQuality, double[] prevOutput, double[] newOutput)
    4049      : base(moveQuality) {
    4150      Path = path;
     51      PreviousOutput = prevOutput;
     52      NewOutput = newOutput;
    4253    }
    4354
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs

    r8207 r8214  
    2020#endregion
    2121
     22using System;
    2223using System.Linq;
    2324using HeuristicLab.Common;
     
    8687      OnlineLinearScalingParameterCalculator.Calculate(move.NewOutput, move.OriginalOutput, out alpha, out beta, out errorState);
    8788
     89      // prevent scaling to a constant value
     90      if (beta.IsAlmost(0.0)) beta = 10E-5;
     91
    8892      move.Alpha = alpha;
    8993      move.Beta = beta;
    9094
    91       // clone tree and parent
    92       var cloner = new Cloner();
    93       var clonedTree = cloner.Clone(move.Tree);
    94       var clonedParent = cloner.Clone(move.Parent);
    95       var clonedBranch = cloner.Clone(move.NewBranch);
    96 
    97       clonedParent.RemoveSubtree(move.SubtreeIndex);
    98       clonedParent.InsertSubtree(move.SubtreeIndex, Scale(clonedBranch, alpha, beta));
     95      var oldBranch = move.Parent.GetSubtree(move.SubtreeIndex);
     96      move.Parent.RemoveSubtree(move.SubtreeIndex);
     97      move.Parent.InsertSubtree(move.SubtreeIndex, Scale(move.NewBranch, alpha, beta));
    9998
    10099      var problemData = ProblemDataParameter.ActualValue;
     
    103102      var fitnessPartition = FitnessCalculationPartitionParameter.ActualValue;
    104103      var rows = Enumerable.Range(fitnessPartition.Start, fitnessPartition.End - fitnessPartition.Start);
    105       var quality = evaluator.Evaluate(childContext, clonedTree, problemData, rows);
     104      var quality = evaluator.Evaluate(childContext, move.Tree, problemData, rows);
     105
     106      // revert changes to tree
     107      move.Parent.RemoveSubtree(move.SubtreeIndex);
     108      move.Parent.InsertSubtree(move.SubtreeIndex, oldBranch);
    106109
    107110      MoveQualityParameter.ActualValue = new DoubleValue(quality);
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveMaker.cs

    r8207 r8214  
    8686
    8787    private ISymbolicExpressionTreeNode Scale(ISymbolicExpressionTreeNode node, double alpha, double beta) {
    88       var constAlpha = (ConstantTreeNode)constant.CreateTreeNode();
    89       var constBeta = (ConstantTreeNode)constant.CreateTreeNode();
    90       constAlpha.Value = alpha;
    91       constBeta.Value = beta;
    92       var sum = add.CreateTreeNode();
    93       var prod = mul.CreateTreeNode();
    94       prod.AddSubtree(node); prod.AddSubtree(constBeta);
    95       sum.AddSubtree(prod); sum.AddSubtree(constAlpha);
    96       return sum;
     88      var constNode = node as ConstantTreeNode;
     89      if (constNode != null) {
     90        constNode.Value = constNode.Value * beta + alpha;
     91        return constNode;
     92      }
     93      var varNode = node as VariableTreeNode;
     94      if (varNode != null) {
     95        varNode.Weight = varNode.Weight * beta;
     96        var constAlpha = (ConstantTreeNode)constant.CreateTreeNode();
     97        constAlpha.Value = alpha;
     98        var sum = add.CreateTreeNode();
     99        sum.AddSubtree(varNode); sum.AddSubtree(constAlpha);
     100        return sum;
     101      }
     102      if (node.Symbol is Addition && node.GetSubtree(0).Symbol is Multiplication &&
     103        node.GetSubtree(1).Symbol is Constant && node.GetSubtree(0).GetSubtree(1).Symbol is Constant) {
     104        var constAlpha = node.GetSubtree(1) as ConstantTreeNode;
     105        var constBeta = node.GetSubtree(0).GetSubtree(1) as ConstantTreeNode;
     106        constAlpha.Value = beta * constAlpha.Value + alpha;
     107        constBeta.Value = constBeta.Value * beta;
     108        return node;
     109      } else {
     110        var constAlpha = (ConstantTreeNode)constant.CreateTreeNode();
     111        var constBeta = (ConstantTreeNode)constant.CreateTreeNode();
     112        constAlpha.Value = alpha;
     113        constBeta.Value = beta;
     114        var sum = add.CreateTreeNode();
     115        var prod = mul.CreateTreeNode();
     116        prod.AddSubtree(node);
     117        prod.AddSubtree(constBeta);
     118        sum.AddSubtree(prod);
     119        sum.AddSubtree(constAlpha);
     120        return sum;
     121      }
    97122    }
    98123  }
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs

    r8206 r8214  
    109109              || maximization && moveQuality <= absTabuAttribute.MoveQuality
    110110              || !maximization && moveQuality >= absTabuAttribute.MoveQuality) {
    111           if (absTabuAttribute != null && absTabuAttribute.Path.Length == path.Count) {
     111          if (absTabuAttribute.Path.Length == path.Count) {
    112112            isTabu = true;
    113113            for (int j = 0; j < path.Count; j++) {
     
    116116                break;
    117117              }
     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;
    118132            }
    119133          }
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveTabuMaker.cs

    r8206 r8214  
    5555      var move = ReplaceBranchMoveParameter.ActualValue;
    5656      var tree = SymbolicExpressionTreeParameter.ActualValue;
    57       double baseQuality = moveQuality;
    58       if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality; // we make an uphill move, the lower bound is the solution quality
     57      double aspirationThreshold = moveQuality;
     58      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) aspirationThreshold = quality; // if we make a bad move, the aspriation threshold is the solution quality
    5959
    6060      List<int> path = new List<int>();
     
    6868      }
    6969      path.Reverse();
    70       return new ChangeNodeTypeMoveAbsoluteAttribute(path.ToArray(), baseQuality);
     70      return new ChangeNodeTypeMoveAbsoluteAttribute(path.ToArray(), aspirationThreshold, move.OriginalOutput, move.NewOutput);
    7171    }
    7272  }
  • branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs

    r8207 r8214  
    3636  [StorableClass]
    3737  public class ReplaceBranchMultiMoveGenerator : SingleSuccessorOperator, IStochasticOperator, ISymbolicExpressionTreeMoveOperator, IMultiMoveGenerator,
    38     ISymbolicDataAnalysisInterpreterOperator, ISymbolicExpressionTreeGrammarBasedOperator {
     38    ISymbolicDataAnalysisInterpreterOperator, ISymbolicExpressionTreeGrammarBasedOperator, ISymbolicExpressionTreeSizeConstraintOperator {
    3939    public ILookupParameter<IRandom> RandomParameter {
    4040      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     
    5353      get { return (ILookupParameter<IRegressionProblemData>)Parameters["ProblemData"]; }
    5454    }
    55 
    5655    public IntValue SampleSize {
    5756      get { return SampleSizeParameter.Value; }
     
    8180    }
    8281
    83     private IList<ISymbolicExpressionTree> trees;
    84     private IList<double[]> treeOutput;
     82    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
     83      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumSymbolicExpressionTreeDepth"]; }
     84    }
     85
     86    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
     87      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumSymbolicExpressionTreeLength"]; }
     88    }
     89
     90    public IValueLookupParameter<IntValue> NeighbourhoodSizeParameter {
     91      get { return (IValueLookupParameter<IntValue>)Parameters["NeighbourhoodSize"]; }
     92    }
     93
     94
     95    private IList<ISymbolicExpressionTree> fragments;
     96    private IList<double[]> fragmentOutput;
    8597
    8698    [StorableConstructor]
     
    101113      Parameters.Add(new ValueParameter<IntValue>("MaxReplacementBranchLength", new IntValue(8)));
    102114      Parameters.Add(new ValueParameter<IntValue>("MaxReplacementBranchDepth", new IntValue(4)));
    103     }
     115      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeDepth"));
     116      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength"));
     117      Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
     118    }
     119
     120
     121    [StorableHook(HookType.AfterDeserialization)]
     122    private void AfterDeserialization() {
     123      if (!Parameters.ContainsKey("MaximumSymbolicExpressionTreeDepth")) {
     124        Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeDepth"));
     125        Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength"));
     126      }
     127      if (!Parameters.ContainsKey("NeighbourhoodSize")) {
     128        Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
     129      }
     130
     131    }
     132
    104133
    105134    public override IDeepCloneable Clone(Cloner cloner) {
     
    108137
    109138    public override void ClearState() {
    110       trees = null;
    111       treeOutput = null;
     139      fragments = null;
     140      fragmentOutput = null;
    112141      base.ClearState();
    113142    }
    114143    public override void InitializeState() {
    115       trees = null;
    116       treeOutput = null;
     144      fragments = null;
     145      fragmentOutput = null;
    117146      base.InitializeState();
    118147    }
     
    120149    public override IOperation Apply() {
    121150      var random = RandomParameter.ActualValue;
    122       if (trees == null || treeOutput == null) {
     151      if (fragments == null || fragmentOutput == null) {
    123152        InitializeOperator();
    124153      }
     
    156185      var rows = ProblemDataParameter.ActualValue.TrainingIndices;
    157186
     187      int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
     188      int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
     189      int neighbourhoodSize = NeighbourhoodSizeParameter.ActualValue.Value;
    158190      while (count < n) {
    159191        // select a random replacement point
     
    164196        start.RemoveSubtree(0);
    165197
    166         var bestTrees = new SortedList<double, Tuple<ISymbolicExpressionTree, double[]>>();
    167         double bestSimilarity = 0;
     198        var bestTrees = new SortedList<double, Tuple<ISymbolicExpressionTree, double[]>>(fragments.Count);
    168199        // iterate over the whole pool of branches for replacement
    169         for (int i = 0; i < trees.Count; i++) {
     200        for (int i = 0; i < fragments.Count; i++) {
    170201          // if the branch is allowed in the selected point
    171           if (tree.Root.Grammar.IsAllowedChildSymbol(selected.parent.Symbol, trees[i].Root.GetSubtree(0).GetSubtree(0).Symbol, selected.i)) {
    172             OnlineCalculatorError error;
    173             // calculate the similarity
    174             double similarity = OnlinePearsonsRSquaredCalculator.Calculate(output, treeOutput[i], out error);
    175             if (error != OnlineCalculatorError.None) similarity = 0.0;
    176 
     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;
     214            }
    177215            // if we found a new bestSimilarity then keep the replacement branch in a sorted list (keep maximally the 30 best for this replacement point)
    178             if (similarity > bestSimilarity && !similarity.IsAlmost(1.0)) {
    179               bestSimilarity = similarity;
    180               bestTrees.Add(similarity, Tuple.Create(trees[i], treeOutput[i]));
    181               if (bestTrees.Count > 30)
     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)
    182219                bestTrees.RemoveAt(0); // remove moves with small R² at the beginning
    183 
     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              }
    184223            }
    185224          }
    186         }
    187         // did not find a move better than similarity 0.0 => create a move to replace it with a random branch
    188         // this is necessary to make it possible to replace branches that evaluate to NaN or infinity
    189         if (bestTrees.Count == 0) {
    190           int r = random.Next(trees.Count);
    191           bestTrees.Add(0.0, Tuple.Create(trees[r], treeOutput[r]));
    192225        }
    193226        // yield moves (we need to add linear scaling parameters for the inserted tree)
     
    215248      // create pool of random branches for replacement (no constants)
    216249      // and evaluate the output
    217       // only keep trees if the output does not contain invalid values
     250      // only keep fragments if the output does not contain invalid values
    218251      var n = ReplacementBranchesPoolSize.Value.Value;
    219252      while (trees.Count < n) {
     
    227260      // enable constants again
    228261      constSym.InitialFrequency = oldConstFreq;
    229       this.trees = trees;
    230       this.treeOutput = treeOutput;
    231     }
    232 
     262      this.fragments = trees;
     263      this.fragmentOutput = treeOutput;
     264    }
    233265  }
    234266}
Note: See TracChangeset for help on using the changeset viewer.