- Timestamp:
- 04/24/08 14:10:03 (16 years ago)
- Location:
- trunk/sources/HeuristicLab.StructureIdentification
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.StructureIdentification/Manipulation/DeleteSubTreeManipulation.cs
r163 r179 59 59 // => return a new minimal random tree 60 60 if(parent == null) { 61 IFunctionTree newTree = gardener.Create RandomTree(1, 1, false);61 IFunctionTree newTree = gardener.CreateBalancedRandomTree(1, 1); 62 62 // check if the tree is ok 63 63 if(!gardener.IsValidTree(newTree)) { -
trunk/sources/HeuristicLab.StructureIdentification/RandomTreeCreator.cs
r155 r179 59 59 IFunctionTree root; 60 60 if(random.NextDouble() <= balancedTreesRate) { 61 root = gardener.Create RandomTree(treeSize, treeHeight, true);61 root = gardener.CreateBalancedRandomTree(treeSize, treeHeight); 62 62 } else { 63 root = gardener.Create RandomTree(treeSize, treeHeight, false);63 root = gardener.CreateBalancedRandomTree(treeSize, treeHeight); 64 64 } 65 65 -
trunk/sources/HeuristicLab.StructureIdentification/TreeGardener.cs
r167 r179 39 39 private GPOperatorLibrary funLibrary; 40 40 private List<IFunction> functions; 41 41 42 private List<IFunction> terminals; 42 43 43 internal IList<IFunction> Terminals { 44 get { return terminals.AsReadOnly(); } 45 } 44 get { return terminals; } 45 } 46 46 47 private List<IFunction> allFunctions; 47 48 48 internal IList<IFunction> AllFunctions { 49 get { return allFunctions .AsReadOnly(); }49 get { return allFunctions; } 50 50 } 51 51 … … 57 57 functions = new List<IFunction>(); 58 58 // init functions and terminals based on constraints 59 foreach 59 foreach(IFunction fun in funLibrary.Group.Operators) { 60 60 int maxA, minA; 61 61 GetMinMaxArity(fun, out minA, out maxA); 62 if 62 if(maxA == 0) { 63 63 terminals.Add(fun); 64 allFunctions.Add(fun); 64 65 } else { 65 66 functions.Add(fun); 66 } 67 } 68 allFunctions.AddRange(functions); 69 allFunctions.AddRange(terminals); 67 allFunctions.Add(fun); 68 } 69 } 70 70 } 71 71 72 72 #region random initialization 73 internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) { 74 if(maxTreeHeight == 1 || maxTreeSize == 1) { 75 IFunction selectedTerminal = terminals[random.Next(terminals.Count())]; 76 return new FunctionTree(selectedTerminal); 77 } else { 78 IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight && 79 GetMinimalTreeSize(f) <= maxTreeSize).ToArray(); 80 IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)]; 81 FunctionTree root = new FunctionTree(selectedFunction); 82 MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1); 83 return root; 84 } 85 } 86 87 internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) { 88 IFunction[] possibleFunctions = allFunctions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight && 89 GetMinimalTreeSize(f) <= maxTreeSize).ToArray(); 90 IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)]; 91 FunctionTree root = new FunctionTree(selectedFunction); 92 MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1); 93 return root; 94 } 95 73 96 internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) { 74 97 // default is non-balanced trees 75 return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false); 76 } 98 return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false); 99 } 100 77 101 internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) { 78 102 79 103 int minTreeHeight = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data).Min(); 80 if 104 if(minTreeHeight > maxTreeHeight) 81 105 maxTreeHeight = minTreeHeight; 82 106 83 107 int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min(); 84 if 108 if(minTreeSize > maxTreeSize) 85 109 maxTreeSize = minTreeSize; 86 110 … … 95 119 } 96 120 97 internal IFunctionTree CreateRandomTree(int maxTreeSize, int maxTreeHeight, bool balanceTrees) {98 if (balanceTrees) {99 if (maxTreeHeight == 1 || maxTreeSize==1) {100 IFunction selectedTerminal = terminals[random.Next(terminals.Count())];101 return new FunctionTree(selectedTerminal);102 } else {103 IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&104 GetMinimalTreeSize(f) <= maxTreeSize).ToArray();105 IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];106 FunctionTree root = new FunctionTree(selectedFunction);107 MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);108 return root;109 }110 111 } else {112 IFunction[] possibleFunctions = allFunctions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&113 GetMinimalTreeSize(f) <= maxTreeSize).ToArray();114 IFunction selectedFunction = possibleFunctions[random.Next(possibleFunctions.Length)];115 FunctionTree root = new FunctionTree(selectedFunction);116 MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1);117 return root;118 }119 }120 121 121 internal IFunctionTree CreateRandomTree(IFunction rootFunction, int maxTreeSize, int maxTreeHeight, bool balanceTrees) { 122 122 IFunctionTree root = new FunctionTree(rootFunction); 123 if 123 if(balanceTrees) { 124 124 MakeBalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1); 125 125 } else { 126 126 MakeUnbalancedTree(root, maxTreeSize - 1, maxTreeHeight - 1); 127 127 } 128 if 128 if(GetTreeSize(root) > maxTreeSize || 129 129 GetTreeHeight(root) > maxTreeHeight) { 130 130 throw new InvalidProgramException(); … … 133 133 } 134 134 135 136 135 private void MakeUnbalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) { 137 if 136 if(maxTreeHeight == 0 || maxTreeSize == 0) return; 138 137 int minArity; 139 138 int maxArity; 140 139 GetMinMaxArity(parent.Function, out minArity, out maxArity); 141 if 140 if(maxArity >= maxTreeSize) { 142 141 maxArity = maxTreeSize; 143 142 } 144 143 int actualArity = random.Next(minArity, maxArity + 1); 145 if 144 if(actualArity > 0) { 146 145 int maxSubTreeSize = maxTreeSize / actualArity; 147 for 146 for(int i = 0; i < actualArity; i++) { 148 147 IFunction[] possibleFunctions = GetAllowedSubFunctions(parent.Function, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight && 149 148 GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray(); … … 159 158 // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree 160 159 private void MakeBalancedTree(IFunctionTree parent, int maxTreeSize, int maxTreeHeight) { 161 if 160 if(maxTreeHeight == 0 || maxTreeSize == 0) return; // should never happen anyway 162 161 int minArity; 163 162 int maxArity; 164 163 GetMinMaxArity(parent.Function, out minArity, out maxArity); 165 if 164 if(maxArity >= maxTreeSize) { 166 165 maxArity = maxTreeSize; 167 166 } 168 167 int actualArity = random.Next(minArity, maxArity + 1); 169 if 168 if(actualArity > 0) { 170 169 int maxSubTreeSize = maxTreeSize / actualArity; 171 for 172 if 170 for(int i = 0; i < actualArity; i++) { 171 if(maxTreeHeight == 1 || maxSubTreeSize == 1) { 173 172 IFunction[] possibleTerminals = GetAllowedSubFunctions(parent.Function, i).Where( 174 173 f => GetMinimalTreeHeight(f) <= maxTreeHeight && … … 199 198 var parametricTrees = trees.Where(t => t.Function.GetVariable(GPOperatorLibrary.INITIALIZATION) != null); 200 199 201 foreach 200 foreach(IFunctionTree tree in parametricTrees) { 202 201 // enqueue an initialization operation for each operator with local variables 203 202 IOperator initialization = (IOperator)tree.Function.GetVariable(GPOperatorLibrary.INITIALIZATION).Value; … … 205 204 206 205 // copy the local variables into a temporary scope used for initialization 207 foreach 206 foreach(IVariable variable in tree.LocalVariables) { 208 207 initScope.AddVariable(variable); 209 208 } … … 214 213 215 214 Scope backupScope = new Scope("backup"); 216 foreach 215 foreach(Scope subScope in scope.SubScopes) { 217 216 backupScope.AddSubScope(subScope); 218 217 } … … 233 232 234 233 internal int GetTreeHeight(IFunctionTree tree) { 235 if 234 if(tree.SubTrees.Count == 0) return 1; 236 235 return 1 + tree.SubTrees.Max(f => GetTreeHeight(f)); 237 236 } … … 244 243 245 244 TreeForEach(tree, delegate(IFunctionTree possibleParentNode) { 246 if 245 if(possibleParentNode.SubTrees.Count > 0) { 247 246 parentNodes.Add(possibleParentNode); 248 247 } … … 250 249 251 250 return parentNodes[random.Next(parentNodes.Count)]; 252 }253 254 internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {255 if (f == null) {256 return allFunctions;257 } else {258 ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;259 List<IFunction> result = new List<IFunction>();260 foreach(IFunction function in (ItemList)slotList[index]) {261 result.Add(function);262 }263 return result;264 }265 }266 internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) {267 foreach (IConstraint constraint in f.Constraints) {268 NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;269 if (theConstraint != null) {270 minArity = theConstraint.MinOperators.Data;271 maxArity = theConstraint.MaxOperators.Data;272 return;273 }274 }275 // the default arity is 2276 minArity = 2;277 maxArity = 2;278 }279 internal bool IsTerminal(IFunction f) {280 int minArity;281 int maxArity;282 GetMinMaxArity(f, out minArity, out maxArity);283 return minArity == 0 && maxArity == 0;284 }285 286 internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {287 List<IFunction> parents = new List<IFunction>();288 foreach (IFunction function in functions) {289 ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);290 if (allowedSubFunctions.Contains(child)) {291 parents.Add(function);292 }293 }294 return parents;295 251 } 296 252 … … 317 273 // 'tail-recursive' helper 318 274 private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) { 319 if 320 321 foreach 275 if(branch == tree) return level; 276 277 foreach(IFunctionTree subTree in tree.SubTrees) { 322 278 int result = GetBranchLevelHelper(subTree, branch, level + 1); 323 if 279 if(result != -1) return result; 324 280 } 325 281 … … 332 288 int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data; 333 289 int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data; 334 if(tree.SubTrees.Count < min || tree.SubTrees.Count > max) 290 if(tree.SubTrees.Count < min || tree.SubTrees.Count > max) 335 291 return false; 336 292 } … … 344 300 // returns a random branch from the specified level in the tree 345 301 internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) { 346 if 302 if(level == 0) return tree; 347 303 List<IFunctionTree> branches = GetBranchesAtLevel(tree, level); 348 304 return branches[random.Next(branches.Count)]; … … 350 306 #endregion 351 307 352 #region private utility methods 353 354 private int GetMinimalTreeHeight(IOperator op) { 355 return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data; 356 } 357 358 private int GetMinimalTreeSize(IOperator op) { 359 return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data; 360 } 361 362 private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) { 363 action(tree); 364 foreach (IFunctionTree subTree in tree.SubTrees) { 365 TreeForEach(subTree, action); 366 } 367 } 368 369 private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) { 370 if (level == 1) return new List<IFunctionTree>(tree.SubTrees); 371 372 List<IFunctionTree> branches = new List<IFunctionTree>(); 373 foreach (IFunctionTree subTree in tree.SubTrees) { 374 branches.AddRange(GetBranchesAtLevel(subTree, level - 1)); 375 } 376 return branches; 377 } 378 379 380 #endregion 381 308 #region function information (arity, allowed childs and parents) 382 309 internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) { 383 310 List<IFunction> result = new List<IFunction>(); 384 foreach 385 if 311 foreach(IFunction f in functions) { 312 if(IsPossibleParent(f, list)) { 386 313 result.Add(f); 387 314 } … … 399 326 // when the maxArity of this function is smaller than the list of operators that 400 327 // should be included as sub-operators then it can't be a parent 401 if 328 if(maxArity < children.Count()) { 402 329 return false; 403 330 } … … 412 339 // allowed functions for this slot. 413 340 // we only count those slots that can hold at least one of the children that we should combine 414 for 341 for(int slot = 0; slot < nSlots; slot++) { 415 342 HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>()); 416 if 343 if(functionSet.Count() > 0) { 417 344 slotSets.Add(functionSet); 418 345 } … … 424 351 // we can never combine all children as sub-trees of the function and thus the function 425 352 // can't be a parent. 426 if 353 if(slotSets.Count() < children.Count()) { 427 354 return false; 428 355 } … … 435 362 436 363 int assignments = 0; 437 for 438 if 364 for(int i = 0; i < slotSets.Count() - 1; i++) { 365 if(slotSets[i].Count > 0) { 439 366 IFunction selected = slotSets[i].ElementAt(0); 440 367 assignments++; 441 for 368 for(int j = i + 1; j < slotSets.Count(); j++) { 442 369 slotSets[j].Remove(selected); 443 370 } … … 446 373 447 374 // sanity check 448 if 375 if(assignments > children.Count) throw new InvalidProgramException(); 449 376 return assignments == children.Count - 1; 450 377 } 378 internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) { 379 List<IFunction> parents = new List<IFunction>(); 380 foreach(IFunction function in functions) { 381 ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex); 382 if(allowedSubFunctions.Contains(child)) { 383 parents.Add(function); 384 } 385 } 386 return parents; 387 } 388 internal bool IsTerminal(IFunction f) { 389 int minArity; 390 int maxArity; 391 GetMinMaxArity(f, out minArity, out maxArity); 392 return minArity == 0 && maxArity == 0; 393 } 394 internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) { 395 if(f == null) { 396 return allFunctions; 397 } else { 398 ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value; 399 List<IFunction> result = new List<IFunction>(); 400 foreach(IFunction function in (ItemList)slotList[index]) { 401 result.Add(function); 402 } 403 return result; 404 } 405 } 406 internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) { 407 foreach(IConstraint constraint in f.Constraints) { 408 NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint; 409 if(theConstraint != null) { 410 minArity = theConstraint.MinOperators.Data; 411 maxArity = theConstraint.MaxOperators.Data; 412 return; 413 } 414 } 415 // the default arity is 2 416 minArity = 2; 417 maxArity = 2; 418 } 419 #endregion 420 421 #region private utility methods 422 423 private int GetMinimalTreeHeight(IOperator op) { 424 return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data; 425 } 426 427 private int GetMinimalTreeSize(IOperator op) { 428 return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data; 429 } 430 431 private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) { 432 action(tree); 433 foreach(IFunctionTree subTree in tree.SubTrees) { 434 TreeForEach(subTree, action); 435 } 436 } 437 438 private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) { 439 if(level == 1) return new List<IFunctionTree>(tree.SubTrees); 440 441 List<IFunctionTree> branches = new List<IFunctionTree>(); 442 foreach(IFunctionTree subTree in tree.SubTrees) { 443 branches.AddRange(GetBranchesAtLevel(subTree, level - 1)); 444 } 445 return branches; 446 } 447 448 449 #endregion 450 451 451 } 452 452 }
Note: See TracChangeset
for help on using the changeset viewer.