Changeset 2566 for trunk/sources/HeuristicLab.GP/3.3
- Timestamp:
- 12/21/09 16:14:40 (15 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.GP/3.3/TreeGardener.cs
r2222 r2566 51 51 functions = new List<IFunction>(); 52 52 // init functions and terminals based on constraints 53 foreach (IFunction fun in funLibrary.Functions) {54 if (fun.MaxSubTrees == 0) {53 foreach (IFunction fun in funLibrary.Functions) { 54 if (fun.MaxSubTrees == 0) { 55 55 terminals.Add(fun); 56 56 allFunctions.Add(fun); … … 112 112 list.Add(new object[] { root, i, 2 }); 113 113 } 114 115 while (list.Count > 0 && totalListMinSize + currentSize < size) { 116 int randomIndex = random.Next(list.Count); 117 object[] nextExtension = list[randomIndex]; 118 list.RemoveAt(randomIndex); 119 IFunctionTree parent = (IFunctionTree)nextExtension[0]; 120 int a = (int)nextExtension[1]; 121 int d = (int)nextExtension[2]; 122 if (d == maxDepth) { 123 parent.RemoveSubTree(a); 124 IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1); 125 parent.InsertSubTree(a, branch); // insert a smallest possible tree 126 currentSize += branch.GetSize(); 127 totalListMinSize -= branch.GetSize(); 128 } else { 129 IFunction selectedFunction = TreeGardener.RandomSelect(random, GetAllowedSubFunctions(parent.Function, a).Where( 130 f => !TreeGardener.IsTerminal(f) && f.MinTreeHeight + (d - 1) <= maxDepth).ToArray()); 131 IFunctionTree newTree = selectedFunction.GetTreeNode(); 132 parent.RemoveSubTree(a); 133 parent.InsertSubTree(a, newTree); 134 currentSize++; 135 totalListMinSize--; 136 137 minArity = selectedFunction.MinSubTrees; 138 maxArity = selectedFunction.MaxSubTrees; 139 if (maxArity >= size) { 140 maxArity = size; 114 if (IsRecursiveExpansionPossible(root.Function)) { 115 while (list.Count > 0 && totalListMinSize + currentSize < size) { 116 int randomIndex = random.Next(list.Count); 117 object[] nextExtension = list[randomIndex]; 118 list.RemoveAt(randomIndex); 119 IFunctionTree parent = (IFunctionTree)nextExtension[0]; 120 int a = (int)nextExtension[1]; 121 int d = (int)nextExtension[2]; 122 if (d == maxDepth) { 123 parent.RemoveSubTree(a); 124 IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1); 125 parent.InsertSubTree(a, branch); // insert a smallest possible tree 126 currentSize += branch.GetSize(); 127 totalListMinSize -= branch.GetSize(); 128 } else { 129 IFunction selectedFunction = TreeGardener.RandomSelect(random, GetAllowedSubFunctions(parent.Function, a).Where( 130 f => IsRecursiveExpansionPossible(f) && f.MinTreeHeight + (d - 1) <= maxDepth).ToArray()); 131 IFunctionTree newTree = selectedFunction.GetTreeNode(); 132 parent.RemoveSubTree(a); 133 parent.InsertSubTree(a, newTree); 134 currentSize++; 135 totalListMinSize--; 136 137 minArity = selectedFunction.MinSubTrees; 138 maxArity = selectedFunction.MaxSubTrees; 139 if (maxArity >= size) { 140 maxArity = size; 141 } 142 actualArity = random.Next(minArity, maxArity + 1); 143 for (int i = 0; i < actualArity; i++) { 144 // insert a dummy sub-tree and add the pending extension to the list 145 newTree.AddSubTree(null); 146 list.Add(new object[] { newTree, i, d + 1 }); 147 } 148 totalListMinSize += newTree.Function.MinTreeSize - 1; 141 149 } 142 actualArity = random.Next(minArity, maxArity + 1);143 for (int i = 0; i < actualArity; i++) {144 // insert a dummy sub-tree and add the pending extension to the list145 newTree.AddSubTree(null);146 list.Add(new object[] { newTree, i, d + 1 });147 }148 totalListMinSize += newTree.Function.MinTreeSize - 1;149 150 } 150 151 } … … 162 163 return root; 163 164 } 164 165 166 private bool IsRecursiveExpansionPossible(IFunction parent) { 167 return FindCycle(parent, new Stack<IFunction>()); 168 } 169 170 private Dictionary<IFunction, bool> inCycle = new Dictionary<IFunction, bool>(); 171 private bool FindCycle(IFunction parent, Stack<IFunction> parentChain) { 172 if (inCycle.ContainsKey(parent)) { 173 return inCycle[parent]; 174 } else if (IsTerminal(parent)) { 175 inCycle[parent] = false; 176 return false; 177 } else if (parentChain.Contains(parent)) { 178 inCycle[parent] = true; 179 return true; 180 } else { 181 parentChain.Push(parent); 182 bool result = false; 183 // all slot indexes 184 for (int i = 0; i < parent.MaxSubTrees; i++) { 185 foreach (IFunction subFunction in GetAllowedSubFunctions(parent, i)) { 186 result |= FindCycle(subFunction, parentChain); 187 } 188 } 189 190 parentChain.Pop(); 191 inCycle[parent] = result; 192 return result; 193 } 194 } 195 165 196 /// <summary> 166 197 /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height. … … 173 204 // get the minimal needed height based on allowed functions and extend the max-height if necessary 174 205 int minTreeHeight = allowedFunctions.Select(f => f.MinTreeHeight).Min(); 175 if (minTreeHeight > maxTreeHeight)206 if (minTreeHeight > maxTreeHeight) 176 207 maxTreeHeight = minTreeHeight; 177 208 // get the minimal needed size based on allowed functions and extend the max-size if necessary 178 209 int minTreeSize = allowedFunctions.Select(f => f.MinTreeSize).Min(); 179 if (minTreeSize > maxTreeSize)210 if (minTreeSize > maxTreeSize) 180 211 maxTreeSize = minTreeSize; 181 212 … … 204 235 205 236 TreeForEach(tree, delegate(IFunctionTree possibleParentNode) { 206 if (possibleParentNode.SubTrees.Count > 0) {237 if (possibleParentNode.SubTrees.Count > 0) { 207 238 parentNodes.Add(possibleParentNode); 208 239 } … … 234 265 // 'tail-recursive' helper 235 266 private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) { 236 if (branch == tree) return level;237 238 foreach (IFunctionTree subTree in tree.SubTrees) {267 if (branch == tree) return level; 268 269 foreach (IFunctionTree subTree in tree.SubTrees) { 239 270 int result = GetBranchLevelHelper(subTree, branch, level + 1); 240 if (result != -1) return result;271 if (result != -1) return result; 241 272 } 242 273 … … 245 276 246 277 public bool IsValidTree(IFunctionTree tree) { 247 for (int i = 0; i < tree.SubTrees.Count; i++) {248 if (!tree.Function.GetAllowedSubFunctions(i).Contains(tree.SubTrees[i].Function)) return false;249 } 250 251 if (tree.SubTrees.Count < tree.Function.MinSubTrees || tree.SubTrees.Count > tree.Function.MaxSubTrees)278 for (int i = 0; i < tree.SubTrees.Count; i++) { 279 if (!tree.Function.GetAllowedSubFunctions(i).Contains(tree.SubTrees[i].Function)) return false; 280 } 281 282 if (tree.SubTrees.Count < tree.Function.MinSubTrees || tree.SubTrees.Count > tree.Function.MaxSubTrees) 252 283 return false; 253 foreach (IFunctionTree subTree in tree.SubTrees) {254 if (!IsValidTree(subTree)) return false;284 foreach (IFunctionTree subTree in tree.SubTrees) { 285 if (!IsValidTree(subTree)) return false; 255 286 } 256 287 return true; … … 259 290 // returns a random branch from the specified level in the tree 260 291 public IFunctionTree GetRandomBranch(IFunctionTree tree, int level) { 261 if (level == 0) return tree;292 if (level == 0) return tree; 262 293 List<IFunctionTree> branches = new List<IFunctionTree>(); 263 294 GetBranchesAtLevel(tree, level, branches); … … 269 300 internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) { 270 301 List<IFunction> result = new List<IFunction>(); 271 foreach (IFunction f in functions) {272 if (IsPossibleParent(f, list)) {302 foreach (IFunction f in functions) { 303 if (IsPossibleParent(f, list)) { 273 304 result.Add(f); 274 305 } … … 284 315 // when the maxArity of this function is smaller than the list of operators that 285 316 // should be included as sub-operators then it can't be a parent 286 if (maxArity < children.Count()) {317 if (maxArity < children.Count()) { 287 318 return false; 288 319 } … … 294 325 // allowed functions for this slot. 295 326 // we only count those slots that can hold at least one of the children that we should combine 296 for (int slot = 0; slot < nSlots; slot++) {327 for (int slot = 0; slot < nSlots; slot++) { 297 328 HashSet<IFunction> functionSet = new HashSet<IFunction>(f.GetAllowedSubFunctions(slot)); 298 if (functionSet.Count() > 0) {329 if (functionSet.Count() > 0) { 299 330 slotSets.Add(functionSet); 300 331 } … … 306 337 // we can never combine all children as sub-trees of the function and thus the function 307 338 // can't be a parent. 308 if (slotSets.Count() < children.Count()) {339 if (slotSets.Count() < children.Count()) { 309 340 return false; 310 341 } … … 317 348 318 349 int assignments = 0; 319 for (int i = 0; i < slotSets.Count() - 1; i++) {320 if (slotSets[i].Count > 0) {350 for (int i = 0; i < slotSets.Count() - 1; i++) { 351 if (slotSets[i].Count > 0) { 321 352 IFunction selected = slotSets[i].ElementAt(0); 322 353 assignments++; 323 for (int j = i + 1; j < slotSets.Count(); j++) {354 for (int j = i + 1; j < slotSets.Count(); j++) { 324 355 slotSets[j].Remove(selected); 325 356 } … … 328 359 329 360 // sanity check 330 if (assignments > children.Count) throw new InvalidProgramException();361 if (assignments > children.Count) throw new InvalidProgramException(); 331 362 return assignments == children.Count - 1; 332 363 } 333 364 public IList<IFunction> GetAllowedParents(IFunction child, int childIndex) { 334 365 List<IFunction> parents = new List<IFunction>(); 335 foreach (IFunction function in functions) {366 foreach (IFunction function in functions) { 336 367 ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex); 337 if (allowedSubFunctions.Contains(child)) {368 if (allowedSubFunctions.Contains(child)) { 338 369 parents.Add(function); 339 370 } … … 345 376 } 346 377 public ICollection<IFunction> GetAllowedSubFunctions(IFunction f, int index) { 347 if (f == null) {378 if (f == null) { 348 379 return allFunctions; 349 380 } else { … … 355 386 #region private utility methods 356 387 public IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) { 357 if (maxTreeHeight == 1 || maxTreeSize == 1) {388 if (maxTreeHeight == 1 || maxTreeSize == 1) { 358 389 IFunction selectedTerminal = RandomSelect(terminals); 359 390 return selectedTerminal; 360 391 } else { 361 IFunction[] possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight && 362 f.MinTreeSize <= maxTreeSize).ToArray(); 363 IFunction selectedFunction = RandomSelect(possibleFunctions); 364 return selectedFunction; 392 int minExpandableTreeSize = (from f in functions 393 where IsRecursiveExpansionPossible(f) 394 select f.MinTreeSize).Min(); 395 int minExpandableTreeHeight = (from f in functions 396 where IsRecursiveExpansionPossible(f) 397 select f.MinTreeHeight).Min(); 398 IFunction[] possibleFunctions; 399 if (maxTreeSize < minExpandableTreeSize || maxTreeHeight < minExpandableTreeHeight) { 400 possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight && 401 f.MinTreeSize <= maxTreeSize).ToArray(); 402 } else { 403 possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight && 404 f.MinTreeSize <= maxTreeSize && IsRecursiveExpansionPossible(f)).ToArray(); 405 } 406 return RandomSelect(possibleFunctions); 365 407 } 366 408 } … … 368 410 369 411 private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) { 370 if (maxTreeHeight == 0) return parent.GetTreeNode();412 if (maxTreeHeight == 0) return parent.GetTreeNode(); 371 413 int minArity = parent.MinSubTrees; 372 414 int maxArity = parent.MaxSubTrees; 373 415 int actualArity = random.Next(minArity, maxArity + 1); 374 if (actualArity > 0) {416 if (actualArity > 0) { 375 417 IFunctionTree parentTree = parent.GetTreeNode(); 376 for (int i = 0; i < actualArity; i++) {418 for (int i = 0; i < actualArity; i++) { 377 419 IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight).ToArray(); 378 420 IFunction selectedFunction = RandomSelect(possibleFunctions); … … 389 431 // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree 390 432 private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) { 391 if (maxTreeHeight == 0) return parent.GetTreeNode();433 if (maxTreeHeight == 0) return parent.GetTreeNode(); 392 434 int minArity = parent.MinSubTrees; 393 435 int maxArity = parent.MaxSubTrees; 394 436 int actualArity = random.Next(minArity, maxArity + 1); 395 if (actualArity > 0) {437 if (actualArity > 0) { 396 438 IFunctionTree parentTree = parent.GetTreeNode(); 397 for (int i = 0; i < actualArity; i++) {439 for (int i = 0; i < actualArity; i++) { 398 440 // first try to find a function that fits into the maxHeight limit 399 441 IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight && 400 442 !IsTerminal(f)).ToArray(); 401 443 // no possible function found => extend function set to terminals 402 if (possibleFunctions.Length == 0) {444 if (possibleFunctions.Length == 0) { 403 445 possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => IsTerminal(f)).ToArray(); 404 446 IFunction selectedTerminal = RandomSelect(possibleFunctions); … … 418 460 private static void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) { 419 461 action(tree); 420 foreach (IFunctionTree subTree in tree.SubTrees) {462 foreach (IFunctionTree subTree in tree.SubTrees) { 421 463 TreeForEach(subTree, action); 422 464 } … … 424 466 425 467 private static void GetBranchesAtLevel(IFunctionTree tree, int level, List<IFunctionTree> result) { 426 if (level == 1) result.AddRange(tree.SubTrees);427 foreach (IFunctionTree subTree in tree.SubTrees) {428 if (subTree.GetHeight() >= level - 1)468 if (level == 1) result.AddRange(tree.SubTrees); 469 foreach (IFunctionTree subTree in tree.SubTrees) { 470 if (subTree.GetHeight() >= level - 1) 429 471 GetBranchesAtLevel(subTree, level - 1, result); 430 472 }
Note: See TracChangeset
for help on using the changeset viewer.