Changeset 8286 for branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4
- Timestamp:
- 07/11/12 16:43:09 (12 years ago)
- Location:
- branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs
r8214 r8286 20 20 #endregion 21 21 22 using System;23 22 using System.Linq; 24 23 using HeuristicLab.Common; -
branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs
r8214 r8286 55 55 get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; } 56 56 } 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"]; } 59 68 } 60 69 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; } 64 77 } 65 78 … … 73 86 Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The solution as symbolic expression tree.")); 74 87 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))); 76 90 Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem.")); 77 91 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")); 78 94 } 79 95 … … 87 103 var tree = SymbolicExpressionTreeParameter.ActualValue; 88 104 bool isTabu = true; 89 bool useAspiration = UseAspirationCriterion.Value; 105 bool useQualityAspiration = UseQualityAspirationCriterion.Value; 106 bool useSemanticAspiration = UseSemanticAspirationCriterion.Value; 90 107 bool maximization = MaximizationParameter.ActualValue.Value; 91 108 double moveQuality = MoveQualityParameter.ActualValue.Value; … … 103 120 104 121 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--) { 106 126 var tabuAttribute = tabuList[i]; 107 127 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++; 134 141 } 135 142 } 136 143 137 144 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; 138 151 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; 139 189 } 140 190 } -
branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs
r8214 r8286 91 91 get { return (IValueLookupParameter<IntValue>)Parameters["NeighbourhoodSize"]; } 92 92 } 93 93 public IValueLookupParameter<BoolValue> SemanticParameter { 94 get { return (IValueLookupParameter<BoolValue>)Parameters["Semantic"]; } 95 } 94 96 95 97 private IList<ISymbolicExpressionTree> fragments; … … 116 118 Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSymbolicExpressionTreeLength")); 117 119 Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5))); 120 Parameters.Add(new ValueLookupParameter<BoolValue>("Semantic", new BoolValue())); 118 121 } 119 122 … … 171 174 172 175 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 178 194 179 195 var root = (new ProgramRootSymbol()).CreateTreeNode(); … … 185 201 var rows = ProblemDataParameter.ActualValue.TrainingIndices; 186 202 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); 214 270 } 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); 224 273 } 225 274 } 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++; 232 285 } 233 286 }
Note: See TracChangeset
for help on using the changeset viewer.