[2] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using System;
|
---|
| 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Text;
|
---|
| 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Constraints;
|
---|
| 27 | using System.Diagnostics;
|
---|
| 28 | using HeuristicLab.Data;
|
---|
| 29 | using System.Linq;
|
---|
| 30 | using HeuristicLab.Random;
|
---|
| 31 | using HeuristicLab.Operators;
|
---|
| 32 | using HeuristicLab.Selection;
|
---|
[155] | 33 | using HeuristicLab.Functions;
|
---|
| 34 | using System.Collections;
|
---|
[2] | 35 |
|
---|
| 36 | namespace HeuristicLab.StructureIdentification {
|
---|
| 37 | internal class TreeGardener {
|
---|
| 38 | private IRandom random;
|
---|
[155] | 39 | private GPOperatorLibrary funLibrary;
|
---|
| 40 | private List<IFunction> functions;
|
---|
[179] | 41 |
|
---|
[155] | 42 | private List<IFunction> terminals;
|
---|
| 43 | internal IList<IFunction> Terminals {
|
---|
[179] | 44 | get { return terminals; }
|
---|
[2] | 45 | }
|
---|
[179] | 46 |
|
---|
[155] | 47 | private List<IFunction> allFunctions;
|
---|
| 48 | internal IList<IFunction> AllFunctions {
|
---|
[179] | 49 | get { return allFunctions; }
|
---|
[2] | 50 | }
|
---|
| 51 |
|
---|
[180] | 52 | #region constructors
|
---|
[155] | 53 | internal TreeGardener(IRandom random, GPOperatorLibrary funLibrary) {
|
---|
[2] | 54 | this.random = random;
|
---|
[155] | 55 | this.funLibrary = funLibrary;
|
---|
| 56 | this.allFunctions = new List<IFunction>();
|
---|
| 57 | terminals = new List<IFunction>();
|
---|
| 58 | functions = new List<IFunction>();
|
---|
[2] | 59 | // init functions and terminals based on constraints
|
---|
[179] | 60 | foreach(IFunction fun in funLibrary.Group.Operators) {
|
---|
[2] | 61 | int maxA, minA;
|
---|
[155] | 62 | GetMinMaxArity(fun, out minA, out maxA);
|
---|
[179] | 63 | if(maxA == 0) {
|
---|
[155] | 64 | terminals.Add(fun);
|
---|
[179] | 65 | allFunctions.Add(fun);
|
---|
[2] | 66 | } else {
|
---|
[155] | 67 | functions.Add(fun);
|
---|
[179] | 68 | allFunctions.Add(fun);
|
---|
[2] | 69 | }
|
---|
| 70 | }
|
---|
| 71 | }
|
---|
[180] | 72 | #endregion
|
---|
[2] | 73 |
|
---|
| 74 | #region random initialization
|
---|
[180] | 75 | /// <summary>
|
---|
| 76 | /// Creates a random balanced tree with a maximal size and height. When the max-height or max-size are 1 it will return a random terminal.
|
---|
| 77 | /// In other cases it will return either a terminal (tree of size 1) or any other tree with a function in it's root (at least height 2).
|
---|
| 78 | /// </summary>
|
---|
| 79 | /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
|
---|
| 80 | /// <param name="maxTreeHeight">Maximal height of the tree.</param>
|
---|
| 81 | /// <returns></returns>
|
---|
[179] | 82 | internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
|
---|
[202] | 83 | IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
|
---|
[448] | 84 | IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeHeight - 1);
|
---|
[202] | 85 | return tree;
|
---|
[179] | 86 | }
|
---|
| 87 |
|
---|
[180] | 88 | /// <summary>
|
---|
| 89 | /// Creates a random (unbalanced) tree with a maximal size and height. When the max-height or max-size are 1 it will return a random terminal.
|
---|
| 90 | /// In other cases it will return either a terminal (tree of size 1) or any other tree with a function in it's root (at least height 2).
|
---|
| 91 | /// </summary>
|
---|
| 92 | /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
|
---|
| 93 | /// <param name="maxTreeHeight">Maximal height of the tree.</param>
|
---|
| 94 | /// <returns></returns>
|
---|
[179] | 95 | internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
|
---|
[202] | 96 | IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
|
---|
[448] | 97 | IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeHeight - 1);
|
---|
[202] | 98 | return tree;
|
---|
[179] | 99 | }
|
---|
| 100 |
|
---|
[286] | 101 | internal IFunctionTree PTC2(IRandom random, int size, int maxDepth) {
|
---|
[449] | 102 | return PTC2(random, GetRandomRoot(size, maxDepth), size, maxDepth);
|
---|
| 103 | }
|
---|
| 104 |
|
---|
| 105 | internal IFunctionTree PTC2(IRandom random, IFunction rootF, int size, int maxDepth) {
|
---|
[452] | 106 | IFunctionTree root = rootF.GetTreeNode();
|
---|
| 107 | if(size <= 1 || maxDepth <= 1) return root;
|
---|
[286] | 108 | List<object[]> list = new List<object[]>();
|
---|
| 109 | int currentSize = 1;
|
---|
[444] | 110 | int totalListMinSize = 0;
|
---|
[286] | 111 | int minArity;
|
---|
| 112 | int maxArity;
|
---|
| 113 | GetMinMaxArity(root.Function, out minArity, out maxArity);
|
---|
| 114 | if(maxArity >= size) {
|
---|
| 115 | maxArity = size;
|
---|
| 116 | }
|
---|
| 117 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
[444] | 118 | totalListMinSize += GetMinimalTreeSize(root.Function) - 1;
|
---|
| 119 | for(int i = 0; i < actualArity; i++) {
|
---|
[286] | 120 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
| 121 | root.AddSubTree(null);
|
---|
[444] | 122 | list.Add(new object[] { root, i, 2 });
|
---|
[286] | 123 | }
|
---|
| 124 |
|
---|
[444] | 125 | while(list.Count > 0 && totalListMinSize + currentSize < size) {
|
---|
[286] | 126 | int randomIndex = random.Next(list.Count);
|
---|
| 127 | object[] nextExtension = list[randomIndex];
|
---|
| 128 | list.RemoveAt(randomIndex);
|
---|
| 129 | IFunctionTree parent = (IFunctionTree)nextExtension[0];
|
---|
| 130 | int a = (int)nextExtension[1];
|
---|
| 131 | int d = (int)nextExtension[2];
|
---|
| 132 | if(d == maxDepth) {
|
---|
| 133 | parent.RemoveSubTree(a);
|
---|
[444] | 134 | IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
|
---|
| 135 | parent.InsertSubTree(a, branch); // insert a smallest possible tree
|
---|
| 136 | currentSize += branch.Size;
|
---|
[448] | 137 | totalListMinSize -= branch.Size;
|
---|
[286] | 138 | } else {
|
---|
[444] | 139 | IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(
|
---|
| 140 | f => !IsTerminal(f) && GetMinimalTreeHeight(f) + (d - 1) <= maxDepth).ToArray());
|
---|
[286] | 141 | IFunctionTree newTree = selectedFunction.GetTreeNode();
|
---|
| 142 | parent.RemoveSubTree(a);
|
---|
| 143 | parent.InsertSubTree(a, newTree);
|
---|
[444] | 144 | currentSize++;
|
---|
| 145 | totalListMinSize--;
|
---|
[286] | 146 |
|
---|
| 147 | GetMinMaxArity(selectedFunction, out minArity, out maxArity);
|
---|
| 148 | if(maxArity >= size) {
|
---|
| 149 | maxArity = size;
|
---|
| 150 | }
|
---|
| 151 | actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 152 | for(int i = 0; i < actualArity; i++) {
|
---|
| 153 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
| 154 | newTree.AddSubTree(null);
|
---|
| 155 | list.Add(new object[] { newTree, i, d + 1 });
|
---|
| 156 | }
|
---|
[444] | 157 | totalListMinSize += GetMinimalTreeSize(newTree.Function) - 1;
|
---|
[286] | 158 | }
|
---|
| 159 | }
|
---|
| 160 | while(list.Count > 0) {
|
---|
| 161 | int randomIndex = random.Next(list.Count);
|
---|
| 162 | object[] nextExtension = list[randomIndex];
|
---|
| 163 | list.RemoveAt(randomIndex);
|
---|
| 164 | IFunctionTree parent = (IFunctionTree)nextExtension[0];
|
---|
| 165 | int a = (int)nextExtension[1];
|
---|
| 166 | int d = (int)nextExtension[2];
|
---|
| 167 | parent.RemoveSubTree(a);
|
---|
[452] | 168 | parent.InsertSubTree(a,
|
---|
| 169 | CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1)); // append a tree with minimal possible height
|
---|
[286] | 170 | }
|
---|
| 171 | return root;
|
---|
| 172 | }
|
---|
| 173 |
|
---|
[180] | 174 | /// <summary>
|
---|
| 175 | /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height.
|
---|
| 176 | /// </summary>
|
---|
| 177 | /// <param name="allowedFunctions">Set of allowed functions.</param>
|
---|
| 178 | /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
|
---|
| 179 | /// <param name="maxTreeHeight">Maximal height of the tree.</param>
|
---|
| 180 | /// <returns>New random unbalanced tree</returns>
|
---|
[163] | 181 | internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
|
---|
[181] | 182 | // get the minimal needed height based on allowed functions and extend the max-height if necessary
|
---|
[448] | 183 | int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeHeight(f)).Min();
|
---|
[179] | 184 | if(minTreeHeight > maxTreeHeight)
|
---|
[2] | 185 | maxTreeHeight = minTreeHeight;
|
---|
[181] | 186 | // get the minimal needed size based on allowed functions and extend the max-size if necessary
|
---|
[444] | 187 | int minTreeSize = allowedFunctions.Select(f => GetMinimalTreeSize(f)).Min();
|
---|
[179] | 188 | if(minTreeSize > maxTreeSize)
|
---|
[2] | 189 | maxTreeSize = minTreeSize;
|
---|
| 190 |
|
---|
[181] | 191 | // select a random value for the size and height
|
---|
[2] | 192 | int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
|
---|
| 193 | int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
|
---|
| 194 |
|
---|
[181] | 195 | // filter the set of allowed functions and select only from those that fit into the given maximal size and height limits
|
---|
[444] | 196 | IFunction[] possibleFunctions = allowedFunctions.Where(f => GetMinimalTreeHeight(f) <= treeHeight &&
|
---|
| 197 | GetMinimalTreeSize(f) <= treeSize).ToArray();
|
---|
[182] | 198 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[2] | 199 |
|
---|
[181] | 200 | // build the tree
|
---|
[202] | 201 | IFunctionTree root;
|
---|
[452] | 202 | root = PTC2(random, selectedFunction, maxTreeSize, maxTreeHeight);
|
---|
[2] | 203 | return root;
|
---|
| 204 | }
|
---|
| 205 |
|
---|
[155] | 206 | internal CompositeOperation CreateInitializationOperation(ICollection<IFunctionTree> trees, IScope scope) {
|
---|
[2] | 207 | // needed for the parameter shaking operation
|
---|
| 208 | CompositeOperation initializationOperation = new CompositeOperation();
|
---|
| 209 | Scope tempScope = new Scope("Temp. initialization scope");
|
---|
| 210 |
|
---|
[429] | 211 | var parametricTrees = trees.Where(t => t.Function.GetVariable(FunctionBase.INITIALIZATION) != null);
|
---|
[179] | 212 | foreach(IFunctionTree tree in parametricTrees) {
|
---|
[2] | 213 | // enqueue an initialization operation for each operator with local variables
|
---|
[429] | 214 | IOperator initialization = (IOperator)tree.Function.GetVariable(FunctionBase.INITIALIZATION).Value;
|
---|
[2] | 215 | Scope initScope = new Scope();
|
---|
| 216 | // copy the local variables into a temporary scope used for initialization
|
---|
[179] | 217 | foreach(IVariable variable in tree.LocalVariables) {
|
---|
[155] | 218 | initScope.AddVariable(variable);
|
---|
[2] | 219 | }
|
---|
| 220 | tempScope.AddSubScope(initScope);
|
---|
| 221 | initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
|
---|
| 222 | }
|
---|
| 223 | Scope backupScope = new Scope("backup");
|
---|
[179] | 224 | foreach(Scope subScope in scope.SubScopes) {
|
---|
[2] | 225 | backupScope.AddSubScope(subScope);
|
---|
| 226 | }
|
---|
| 227 | scope.AddSubScope(tempScope);
|
---|
| 228 | scope.AddSubScope(backupScope);
|
---|
| 229 | // add an operation to remove the temporary scopes
|
---|
| 230 | initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
|
---|
| 231 | return initializationOperation;
|
---|
| 232 | }
|
---|
| 233 | #endregion
|
---|
| 234 |
|
---|
| 235 | #region tree information gathering
|
---|
[155] | 236 | internal IFunctionTree GetRandomParentNode(IFunctionTree tree) {
|
---|
| 237 | List<IFunctionTree> parentNodes = new List<IFunctionTree>();
|
---|
[2] | 238 |
|
---|
| 239 | // add null for the parent of the root node
|
---|
| 240 | parentNodes.Add(null);
|
---|
| 241 |
|
---|
[155] | 242 | TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
|
---|
[179] | 243 | if(possibleParentNode.SubTrees.Count > 0) {
|
---|
[155] | 244 | parentNodes.Add(possibleParentNode);
|
---|
[2] | 245 | }
|
---|
| 246 | });
|
---|
| 247 |
|
---|
| 248 | return parentNodes[random.Next(parentNodes.Count)];
|
---|
| 249 | }
|
---|
| 250 |
|
---|
[155] | 251 | internal ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
|
---|
| 252 | List<IFunctionTree> allTrees = new List<IFunctionTree>();
|
---|
| 253 | TreeForEach(root, t => { allTrees.Add(t); });
|
---|
| 254 | return allTrees;
|
---|
[2] | 255 | }
|
---|
| 256 |
|
---|
| 257 | /// <summary>
|
---|
[155] | 258 | /// returns the height level of branch in the tree
|
---|
| 259 | /// if the branch == tree => 1
|
---|
| 260 | /// if branch is in the sub-trees of tree => 2
|
---|
[2] | 261 | /// ...
|
---|
[155] | 262 | /// if branch is not found => -1
|
---|
[2] | 263 | /// </summary>
|
---|
[155] | 264 | /// <param name="tree">root of the function tree to process</param>
|
---|
| 265 | /// <param name="branch">branch that is searched in the tree</param>
|
---|
[2] | 266 | /// <returns></returns>
|
---|
[155] | 267 | internal int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
|
---|
| 268 | return GetBranchLevelHelper(tree, branch, 1);
|
---|
[2] | 269 | }
|
---|
| 270 |
|
---|
[155] | 271 | // 'tail-recursive' helper
|
---|
| 272 | private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
|
---|
[179] | 273 | if(branch == tree) return level;
|
---|
[2] | 274 |
|
---|
[179] | 275 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
[155] | 276 | int result = GetBranchLevelHelper(subTree, branch, level + 1);
|
---|
[179] | 277 | if(result != -1) return result;
|
---|
[2] | 278 | }
|
---|
| 279 |
|
---|
| 280 | return -1;
|
---|
| 281 | }
|
---|
| 282 |
|
---|
[155] | 283 | internal bool IsValidTree(IFunctionTree tree) {
|
---|
[451] | 284 | SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
|
---|
| 285 | analyzer.AllPossibleOperators = AllFunctions.Cast<IOperator>().ToArray<IOperator>();
|
---|
| 286 | for(int i = 0; i < tree.SubTrees.Count; i++) {
|
---|
| 287 | if(!analyzer.GetAllowedOperators(tree.Function, i).Contains(tree.SubTrees[i].Function)) return false;
|
---|
| 288 | }
|
---|
| 289 |
|
---|
[155] | 290 | foreach(IConstraint constraint in tree.Function.Constraints) {
|
---|
| 291 | if(constraint is NumberOfSubOperatorsConstraint) {
|
---|
| 292 | int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data;
|
---|
| 293 | int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data;
|
---|
[179] | 294 | if(tree.SubTrees.Count < min || tree.SubTrees.Count > max)
|
---|
[155] | 295 | return false;
|
---|
| 296 | }
|
---|
[2] | 297 | }
|
---|
[155] | 298 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
| 299 | if(!IsValidTree(subTree)) return false;
|
---|
| 300 | }
|
---|
[2] | 301 | return true;
|
---|
| 302 | }
|
---|
| 303 |
|
---|
[155] | 304 | // returns a random branch from the specified level in the tree
|
---|
| 305 | internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
|
---|
[179] | 306 | if(level == 0) return tree;
|
---|
[155] | 307 | List<IFunctionTree> branches = GetBranchesAtLevel(tree, level);
|
---|
| 308 | return branches[random.Next(branches.Count)];
|
---|
[2] | 309 | }
|
---|
| 310 | #endregion
|
---|
| 311 |
|
---|
[179] | 312 | #region function information (arity, allowed childs and parents)
|
---|
[155] | 313 | internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
|
---|
| 314 | List<IFunction> result = new List<IFunction>();
|
---|
[179] | 315 | foreach(IFunction f in functions) {
|
---|
| 316 | if(IsPossibleParent(f, list)) {
|
---|
[155] | 317 | result.Add(f);
|
---|
[2] | 318 | }
|
---|
| 319 | }
|
---|
| 320 | return result;
|
---|
| 321 | }
|
---|
| 322 |
|
---|
[155] | 323 | private bool IsPossibleParent(IFunction f, List<IFunction> children) {
|
---|
[2] | 324 | int minArity;
|
---|
| 325 | int maxArity;
|
---|
[155] | 326 | GetMinMaxArity(f, out minArity, out maxArity);
|
---|
[2] | 327 |
|
---|
| 328 | // note: we can't assume that the operators in the children list have different types!
|
---|
| 329 |
|
---|
| 330 | // when the maxArity of this function is smaller than the list of operators that
|
---|
| 331 | // should be included as sub-operators then it can't be a parent
|
---|
[179] | 332 | if(maxArity < children.Count()) {
|
---|
[2] | 333 | return false;
|
---|
| 334 | }
|
---|
| 335 | int nSlots = Math.Max(minArity, children.Count);
|
---|
| 336 |
|
---|
| 337 | SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
|
---|
[155] | 338 | analyzer.AllPossibleOperators = children.Cast<IOperator>().ToArray<IOperator>();
|
---|
[2] | 339 |
|
---|
[155] | 340 | List<HashSet<IFunction>> slotSets = new List<HashSet<IFunction>>();
|
---|
[2] | 341 |
|
---|
[155] | 342 | // we iterate through all slots for sub-trees and calculate the set of
|
---|
| 343 | // allowed functions for this slot.
|
---|
[2] | 344 | // we only count those slots that can hold at least one of the children that we should combine
|
---|
[179] | 345 | for(int slot = 0; slot < nSlots; slot++) {
|
---|
[155] | 346 | HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>());
|
---|
[179] | 347 | if(functionSet.Count() > 0) {
|
---|
[155] | 348 | slotSets.Add(functionSet);
|
---|
[2] | 349 | }
|
---|
| 350 | }
|
---|
| 351 |
|
---|
| 352 | // ok at the end of this operation we know how many slots of the parent can actually
|
---|
| 353 | // hold one of our children.
|
---|
| 354 | // if the number of slots is smaller than the number of children we can be sure that
|
---|
[155] | 355 | // we can never combine all children as sub-trees of the function and thus the function
|
---|
[2] | 356 | // can't be a parent.
|
---|
[179] | 357 | if(slotSets.Count() < children.Count()) {
|
---|
[2] | 358 | return false;
|
---|
| 359 | }
|
---|
| 360 |
|
---|
| 361 | // finally we sort the sets by size and beginning from the first set select one
|
---|
[155] | 362 | // function for the slot and thus remove it as possible sub-tree from the remaining sets.
|
---|
| 363 | // when we can successfully assign all available children to a slot the function is a valid parent
|
---|
| 364 | // when only a subset of all children can be assigned to slots the function is no valid parent
|
---|
[2] | 365 | slotSets.Sort((p, q) => p.Count() - q.Count());
|
---|
| 366 |
|
---|
| 367 | int assignments = 0;
|
---|
[179] | 368 | for(int i = 0; i < slotSets.Count() - 1; i++) {
|
---|
| 369 | if(slotSets[i].Count > 0) {
|
---|
[155] | 370 | IFunction selected = slotSets[i].ElementAt(0);
|
---|
[2] | 371 | assignments++;
|
---|
[179] | 372 | for(int j = i + 1; j < slotSets.Count(); j++) {
|
---|
[2] | 373 | slotSets[j].Remove(selected);
|
---|
| 374 | }
|
---|
| 375 | }
|
---|
| 376 | }
|
---|
| 377 |
|
---|
| 378 | // sanity check
|
---|
[179] | 379 | if(assignments > children.Count) throw new InvalidProgramException();
|
---|
[2] | 380 | return assignments == children.Count - 1;
|
---|
| 381 | }
|
---|
[179] | 382 | internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
|
---|
| 383 | List<IFunction> parents = new List<IFunction>();
|
---|
| 384 | foreach(IFunction function in functions) {
|
---|
| 385 | ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
|
---|
| 386 | if(allowedSubFunctions.Contains(child)) {
|
---|
| 387 | parents.Add(function);
|
---|
| 388 | }
|
---|
| 389 | }
|
---|
| 390 | return parents;
|
---|
| 391 | }
|
---|
| 392 | internal bool IsTerminal(IFunction f) {
|
---|
| 393 | int minArity;
|
---|
| 394 | int maxArity;
|
---|
| 395 | GetMinMaxArity(f, out minArity, out maxArity);
|
---|
| 396 | return minArity == 0 && maxArity == 0;
|
---|
| 397 | }
|
---|
| 398 | internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
|
---|
| 399 | if(f == null) {
|
---|
| 400 | return allFunctions;
|
---|
| 401 | } else {
|
---|
[431] | 402 | SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
|
---|
[433] | 403 | analyzer.AllPossibleOperators = AllFunctions.Cast<IOperator>().ToArray<IOperator>();
|
---|
[179] | 404 | List<IFunction> result = new List<IFunction>();
|
---|
[431] | 405 | foreach(IFunction function in analyzer.GetAllowedOperators(f, index)) {
|
---|
[179] | 406 | result.Add(function);
|
---|
| 407 | }
|
---|
| 408 | return result;
|
---|
| 409 | }
|
---|
| 410 | }
|
---|
| 411 | internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) {
|
---|
| 412 | foreach(IConstraint constraint in f.Constraints) {
|
---|
| 413 | NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
|
---|
| 414 | if(theConstraint != null) {
|
---|
| 415 | minArity = theConstraint.MinOperators.Data;
|
---|
| 416 | maxArity = theConstraint.MaxOperators.Data;
|
---|
| 417 | return;
|
---|
| 418 | }
|
---|
| 419 | }
|
---|
| 420 | // the default arity is 2
|
---|
| 421 | minArity = 2;
|
---|
| 422 | maxArity = 2;
|
---|
| 423 | }
|
---|
| 424 | #endregion
|
---|
| 425 |
|
---|
| 426 | #region private utility methods
|
---|
[202] | 427 | private IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
|
---|
[180] | 428 | if(maxTreeHeight == 1 || maxTreeSize == 1) {
|
---|
[182] | 429 | IFunction selectedTerminal = RandomSelect(terminals);
|
---|
[202] | 430 | return selectedTerminal;
|
---|
[180] | 431 | } else {
|
---|
[284] | 432 | IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
[180] | 433 | GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
|
---|
[182] | 434 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[202] | 435 | return selectedFunction;
|
---|
[180] | 436 | }
|
---|
| 437 | }
|
---|
[179] | 438 |
|
---|
[448] | 439 |
|
---|
| 440 | private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) {
|
---|
| 441 | if(maxTreeHeight == 0) return parent.GetTreeNode();
|
---|
[180] | 442 | int minArity;
|
---|
| 443 | int maxArity;
|
---|
[202] | 444 | GetMinMaxArity(parent, out minArity, out maxArity);
|
---|
[180] | 445 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 446 | if(actualArity > 0) {
|
---|
[202] | 447 | IFunctionTree parentTree = parent.GetTreeNode();
|
---|
[180] | 448 | for(int i = 0; i < actualArity; i++) {
|
---|
[448] | 449 | IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight).ToArray();
|
---|
[182] | 450 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[448] | 451 | IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
|
---|
[202] | 452 | parentTree.InsertSubTree(i, newSubTree);
|
---|
[180] | 453 | }
|
---|
[202] | 454 | return parentTree;
|
---|
[180] | 455 | }
|
---|
[202] | 456 | return parent.GetTreeNode();
|
---|
[180] | 457 | }
|
---|
| 458 |
|
---|
[448] | 459 |
|
---|
[180] | 460 | // NOTE: this method doesn't build fully balanced trees because we have constraints on the
|
---|
| 461 | // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
|
---|
[448] | 462 | private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) {
|
---|
| 463 | if(maxTreeHeight == 0) return parent.GetTreeNode();
|
---|
[180] | 464 | int minArity;
|
---|
| 465 | int maxArity;
|
---|
[202] | 466 | GetMinMaxArity(parent, out minArity, out maxArity);
|
---|
[180] | 467 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 468 | if(actualArity > 0) {
|
---|
[202] | 469 | IFunctionTree parentTree = parent.GetTreeNode();
|
---|
[180] | 470 | for(int i = 0; i < actualArity; i++) {
|
---|
[448] | 471 | // first try to find a function that fits into the maxHeight limit
|
---|
[450] | 472 | IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
[199] | 473 | !IsTerminal(f)).ToArray();
|
---|
| 474 | // no possible function found => extend function set to terminals
|
---|
| 475 | if(possibleFunctions.Length == 0) {
|
---|
[202] | 476 | possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => IsTerminal(f)).ToArray();
|
---|
[199] | 477 | IFunction selectedTerminal = RandomSelect(possibleFunctions);
|
---|
[189] | 478 | IFunctionTree newTree = selectedTerminal.GetTreeNode();
|
---|
[202] | 479 | parentTree.InsertSubTree(i, newTree);
|
---|
[180] | 480 | } else {
|
---|
[182] | 481 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[448] | 482 | IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxTreeHeight - 1);
|
---|
[202] | 483 | parentTree.InsertSubTree(i, newTree);
|
---|
[180] | 484 | }
|
---|
| 485 | }
|
---|
[202] | 486 | return parentTree;
|
---|
[180] | 487 | }
|
---|
[202] | 488 | return parent.GetTreeNode();
|
---|
[180] | 489 | }
|
---|
| 490 |
|
---|
[179] | 491 | private int GetMinimalTreeHeight(IOperator op) {
|
---|
| 492 | return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
|
---|
| 493 | }
|
---|
| 494 |
|
---|
| 495 | private int GetMinimalTreeSize(IOperator op) {
|
---|
| 496 | return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
|
---|
| 497 | }
|
---|
| 498 |
|
---|
| 499 | private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
|
---|
| 500 | action(tree);
|
---|
| 501 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
| 502 | TreeForEach(subTree, action);
|
---|
| 503 | }
|
---|
| 504 | }
|
---|
| 505 |
|
---|
| 506 | private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) {
|
---|
| 507 | if(level == 1) return new List<IFunctionTree>(tree.SubTrees);
|
---|
| 508 |
|
---|
| 509 | List<IFunctionTree> branches = new List<IFunctionTree>();
|
---|
| 510 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
[444] | 511 | if(subTree.Height >= level - 1)
|
---|
| 512 | branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
|
---|
[179] | 513 | }
|
---|
| 514 | return branches;
|
---|
| 515 | }
|
---|
| 516 |
|
---|
[182] | 517 | private IFunction RandomSelect(IList<IFunction> functionSet) {
|
---|
| 518 | double[] accumulatedTickets = new double[functionSet.Count];
|
---|
| 519 | double ticketAccumulator = 0;
|
---|
| 520 | int i = 0;
|
---|
| 521 | // precalculate the slot-sizes
|
---|
| 522 | foreach(IFunction function in functionSet) {
|
---|
| 523 | ticketAccumulator += ((DoubleData)function.GetVariable(GPOperatorLibrary.TICKETS).Value).Data;
|
---|
| 524 | accumulatedTickets[i] = ticketAccumulator;
|
---|
| 525 | i++;
|
---|
| 526 | }
|
---|
| 527 | // throw ball
|
---|
| 528 | double r = random.NextDouble() * ticketAccumulator;
|
---|
| 529 | // find the slot that has been hit
|
---|
| 530 | for(i = 0; i < accumulatedTickets.Length; i++) {
|
---|
| 531 | if(r < accumulatedTickets[i]) return functionSet[i];
|
---|
| 532 | }
|
---|
| 533 | // sanity check
|
---|
| 534 | throw new InvalidProgramException(); // should never happen
|
---|
| 535 | }
|
---|
[179] | 536 |
|
---|
| 537 | #endregion
|
---|
| 538 |
|
---|
[2] | 539 | }
|
---|
| 540 | }
|
---|