[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);
|
---|
| 84 | IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
| 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);
|
---|
| 97 | IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
| 98 | return tree;
|
---|
[179] | 99 | }
|
---|
| 100 |
|
---|
[286] | 101 | internal IFunctionTree PTC2(IRandom random, int size, int maxDepth) {
|
---|
| 102 | if(size == 1) return RandomSelect(terminals).GetTreeNode();
|
---|
| 103 | List<object[]> list = new List<object[]>();
|
---|
| 104 | IFunctionTree root = GetRandomRoot(size, maxDepth).GetTreeNode();
|
---|
| 105 | int currentSize = 1;
|
---|
| 106 | int minArity;
|
---|
| 107 | int maxArity;
|
---|
| 108 | GetMinMaxArity(root.Function, out minArity, out maxArity);
|
---|
| 109 | if(maxArity >= size) {
|
---|
| 110 | maxArity = size;
|
---|
| 111 | }
|
---|
| 112 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 113 | for(int i=0;i<actualArity;i++) {
|
---|
| 114 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
| 115 | root.AddSubTree(null);
|
---|
| 116 | list.Add(new object[] {root, i, 2});
|
---|
| 117 | }
|
---|
| 118 |
|
---|
| 119 | while(list.Count > 0 && list.Count + currentSize < size) {
|
---|
| 120 | int randomIndex = random.Next(list.Count);
|
---|
| 121 | object[] nextExtension = list[randomIndex];
|
---|
| 122 | list.RemoveAt(randomIndex);
|
---|
| 123 | IFunctionTree parent = (IFunctionTree)nextExtension[0];
|
---|
| 124 | int a = (int)nextExtension[1];
|
---|
| 125 | int d = (int)nextExtension[2];
|
---|
| 126 | if(d == maxDepth) {
|
---|
| 127 | parent.RemoveSubTree(a);
|
---|
[288] | 128 | parent.InsertSubTree(a, RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(f => IsTerminal(f)).ToArray()).GetTreeNode());
|
---|
[286] | 129 | } else {
|
---|
[289] | 130 | IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(
|
---|
| 131 | f => !IsTerminal(f) && GetMinimalTreeHeight(f) + (d-1) <= maxDepth).ToArray());
|
---|
[286] | 132 | IFunctionTree newTree = selectedFunction.GetTreeNode();
|
---|
| 133 | parent.RemoveSubTree(a);
|
---|
| 134 | parent.InsertSubTree(a, newTree);
|
---|
| 135 |
|
---|
| 136 | GetMinMaxArity(selectedFunction, out minArity, out maxArity);
|
---|
| 137 | if(maxArity >= size) {
|
---|
| 138 | maxArity = size;
|
---|
| 139 | }
|
---|
| 140 | actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 141 | for(int i = 0; i < actualArity; i++) {
|
---|
| 142 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
| 143 | newTree.AddSubTree(null);
|
---|
| 144 | list.Add(new object[] { newTree, i, d + 1 });
|
---|
| 145 | }
|
---|
| 146 | }
|
---|
| 147 | currentSize++;
|
---|
| 148 | }
|
---|
| 149 | while(list.Count > 0) {
|
---|
| 150 | int randomIndex = random.Next(list.Count);
|
---|
| 151 | object[] nextExtension = list[randomIndex];
|
---|
| 152 | list.RemoveAt(randomIndex);
|
---|
| 153 | IFunctionTree parent = (IFunctionTree)nextExtension[0];
|
---|
| 154 | int a = (int)nextExtension[1];
|
---|
| 155 | int d = (int)nextExtension[2];
|
---|
| 156 | parent.RemoveSubTree(a);
|
---|
[289] | 157 | parent.InsertSubTree(a, CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1)); // append a tree with minimal possible height
|
---|
[286] | 158 | }
|
---|
| 159 | return root;
|
---|
| 160 | }
|
---|
| 161 |
|
---|
[180] | 162 | /// <summary>
|
---|
| 163 | /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height.
|
---|
| 164 | /// </summary>
|
---|
| 165 | /// <param name="allowedFunctions">Set of allowed functions.</param>
|
---|
| 166 | /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
|
---|
| 167 | /// <param name="maxTreeHeight">Maximal height of the tree.</param>
|
---|
| 168 | /// <returns>New random unbalanced tree</returns>
|
---|
[163] | 169 | internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
|
---|
| 170 | // default is non-balanced trees
|
---|
[179] | 171 | return CreateRandomTree(allowedFunctions, maxTreeSize, maxTreeHeight, false);
|
---|
[163] | 172 | }
|
---|
[179] | 173 |
|
---|
[180] | 174 | /// <summary>
|
---|
[181] | 175 | /// Selects a random function from allowedFunctions and creates a (un)balanced random tree with maximal size and height.
|
---|
| 176 | /// Max-size and max-height are not accepted as hard constraints, if all functions in the set of allowed functions would
|
---|
| 177 | /// lead to a bigger tree then the limits are automatically extended to guarantee that we can build a tree.
|
---|
[180] | 178 | /// </summary>
|
---|
| 179 | /// <param name="allowedFunctions">Set of allowed functions.</param>
|
---|
| 180 | /// <param name="maxTreeSize">Maximal size of the tree (number of nodes).</param>
|
---|
| 181 | /// <param name="maxTreeHeight">Maximal height of the tree.</param>
|
---|
| 182 | /// <param name="balanceTrees">Flag determining whether the tree should be balanced or not.</param>
|
---|
| 183 | /// <returns>New random tree</returns>
|
---|
[155] | 184 | internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight, bool balanceTrees) {
|
---|
[181] | 185 | // get the minimal needed height based on allowed functions and extend the max-height if necessary
|
---|
[155] | 186 | int minTreeHeight = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data).Min();
|
---|
[179] | 187 | if(minTreeHeight > maxTreeHeight)
|
---|
[2] | 188 | maxTreeHeight = minTreeHeight;
|
---|
[181] | 189 | // get the minimal needed size based on allowed functions and extend the max-size if necessary
|
---|
[155] | 190 | int minTreeSize = allowedFunctions.Select(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data).Min();
|
---|
[179] | 191 | if(minTreeSize > maxTreeSize)
|
---|
[2] | 192 | maxTreeSize = minTreeSize;
|
---|
| 193 |
|
---|
[181] | 194 | // select a random value for the size and height
|
---|
[2] | 195 | int treeHeight = random.Next(minTreeHeight, maxTreeHeight + 1);
|
---|
| 196 | int treeSize = random.Next(minTreeSize, maxTreeSize + 1);
|
---|
| 197 |
|
---|
[181] | 198 | // filter the set of allowed functions and select only from those that fit into the given maximal size and height limits
|
---|
[155] | 199 | IFunction[] possibleFunctions = allowedFunctions.Where(f => ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data <= treeHeight &&
|
---|
| 200 | ((IntData)f.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data <= treeSize).ToArray();
|
---|
[182] | 201 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[2] | 202 |
|
---|
[181] | 203 | // build the tree
|
---|
[202] | 204 | IFunctionTree root;
|
---|
[179] | 205 | if(balanceTrees) {
|
---|
[202] | 206 | root = MakeBalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
[2] | 207 | } else {
|
---|
[202] | 208 | root = MakeUnbalancedTree(selectedFunction, maxTreeSize - 1, maxTreeHeight - 1);
|
---|
[2] | 209 | }
|
---|
| 210 | return root;
|
---|
| 211 | }
|
---|
| 212 |
|
---|
[155] | 213 | internal CompositeOperation CreateInitializationOperation(ICollection<IFunctionTree> trees, IScope scope) {
|
---|
[2] | 214 | // needed for the parameter shaking operation
|
---|
| 215 | CompositeOperation initializationOperation = new CompositeOperation();
|
---|
| 216 | Scope tempScope = new Scope("Temp. initialization scope");
|
---|
| 217 |
|
---|
[155] | 218 | var parametricTrees = trees.Where(t => t.Function.GetVariable(GPOperatorLibrary.INITIALIZATION) != null);
|
---|
[179] | 219 | foreach(IFunctionTree tree in parametricTrees) {
|
---|
[2] | 220 | // enqueue an initialization operation for each operator with local variables
|
---|
[155] | 221 | IOperator initialization = (IOperator)tree.Function.GetVariable(GPOperatorLibrary.INITIALIZATION).Value;
|
---|
[2] | 222 | Scope initScope = new Scope();
|
---|
| 223 | // copy the local variables into a temporary scope used for initialization
|
---|
[179] | 224 | foreach(IVariable variable in tree.LocalVariables) {
|
---|
[155] | 225 | initScope.AddVariable(variable);
|
---|
[2] | 226 | }
|
---|
| 227 | tempScope.AddSubScope(initScope);
|
---|
| 228 | initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
|
---|
| 229 | }
|
---|
| 230 | Scope backupScope = new Scope("backup");
|
---|
[179] | 231 | foreach(Scope subScope in scope.SubScopes) {
|
---|
[2] | 232 | backupScope.AddSubScope(subScope);
|
---|
| 233 | }
|
---|
| 234 | scope.AddSubScope(tempScope);
|
---|
| 235 | scope.AddSubScope(backupScope);
|
---|
| 236 | // add an operation to remove the temporary scopes
|
---|
| 237 | initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
|
---|
| 238 | return initializationOperation;
|
---|
| 239 | }
|
---|
| 240 | #endregion
|
---|
| 241 |
|
---|
| 242 | #region tree information gathering
|
---|
[155] | 243 | internal int GetTreeSize(IFunctionTree tree) {
|
---|
| 244 | return 1 + tree.SubTrees.Sum(f => GetTreeSize(f));
|
---|
[2] | 245 | }
|
---|
| 246 |
|
---|
[155] | 247 | internal int GetTreeHeight(IFunctionTree tree) {
|
---|
[179] | 248 | if(tree.SubTrees.Count == 0) return 1;
|
---|
[155] | 249 | return 1 + tree.SubTrees.Max(f => GetTreeHeight(f));
|
---|
[2] | 250 | }
|
---|
| 251 |
|
---|
[155] | 252 | internal IFunctionTree GetRandomParentNode(IFunctionTree tree) {
|
---|
| 253 | List<IFunctionTree> parentNodes = new List<IFunctionTree>();
|
---|
[2] | 254 |
|
---|
| 255 | // add null for the parent of the root node
|
---|
| 256 | parentNodes.Add(null);
|
---|
| 257 |
|
---|
[155] | 258 | TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
|
---|
[179] | 259 | if(possibleParentNode.SubTrees.Count > 0) {
|
---|
[155] | 260 | parentNodes.Add(possibleParentNode);
|
---|
[2] | 261 | }
|
---|
| 262 | });
|
---|
| 263 |
|
---|
| 264 | return parentNodes[random.Next(parentNodes.Count)];
|
---|
| 265 | }
|
---|
| 266 |
|
---|
[155] | 267 | internal ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
|
---|
| 268 | List<IFunctionTree> allTrees = new List<IFunctionTree>();
|
---|
| 269 | TreeForEach(root, t => { allTrees.Add(t); });
|
---|
| 270 | return allTrees;
|
---|
[2] | 271 | }
|
---|
| 272 |
|
---|
| 273 | /// <summary>
|
---|
[155] | 274 | /// returns the height level of branch in the tree
|
---|
| 275 | /// if the branch == tree => 1
|
---|
| 276 | /// if branch is in the sub-trees of tree => 2
|
---|
[2] | 277 | /// ...
|
---|
[155] | 278 | /// if branch is not found => -1
|
---|
[2] | 279 | /// </summary>
|
---|
[155] | 280 | /// <param name="tree">root of the function tree to process</param>
|
---|
| 281 | /// <param name="branch">branch that is searched in the tree</param>
|
---|
[2] | 282 | /// <returns></returns>
|
---|
[155] | 283 | internal int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
|
---|
| 284 | return GetBranchLevelHelper(tree, branch, 1);
|
---|
[2] | 285 | }
|
---|
| 286 |
|
---|
[155] | 287 | // 'tail-recursive' helper
|
---|
| 288 | private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
|
---|
[179] | 289 | if(branch == tree) return level;
|
---|
[2] | 290 |
|
---|
[179] | 291 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
[155] | 292 | int result = GetBranchLevelHelper(subTree, branch, level + 1);
|
---|
[179] | 293 | if(result != -1) return result;
|
---|
[2] | 294 | }
|
---|
| 295 |
|
---|
| 296 | return -1;
|
---|
| 297 | }
|
---|
| 298 |
|
---|
[155] | 299 | internal bool IsValidTree(IFunctionTree tree) {
|
---|
| 300 | foreach(IConstraint constraint in tree.Function.Constraints) {
|
---|
| 301 | if(constraint is NumberOfSubOperatorsConstraint) {
|
---|
| 302 | int max = ((NumberOfSubOperatorsConstraint)constraint).MaxOperators.Data;
|
---|
| 303 | int min = ((NumberOfSubOperatorsConstraint)constraint).MinOperators.Data;
|
---|
[179] | 304 | if(tree.SubTrees.Count < min || tree.SubTrees.Count > max)
|
---|
[155] | 305 | return false;
|
---|
| 306 | }
|
---|
[2] | 307 | }
|
---|
[155] | 308 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
| 309 | if(!IsValidTree(subTree)) return false;
|
---|
| 310 | }
|
---|
[2] | 311 | return true;
|
---|
| 312 | }
|
---|
| 313 |
|
---|
[155] | 314 | // returns a random branch from the specified level in the tree
|
---|
| 315 | internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
|
---|
[179] | 316 | if(level == 0) return tree;
|
---|
[155] | 317 | List<IFunctionTree> branches = GetBranchesAtLevel(tree, level);
|
---|
| 318 | return branches[random.Next(branches.Count)];
|
---|
[2] | 319 | }
|
---|
| 320 | #endregion
|
---|
| 321 |
|
---|
[179] | 322 | #region function information (arity, allowed childs and parents)
|
---|
[155] | 323 | internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
|
---|
| 324 | List<IFunction> result = new List<IFunction>();
|
---|
[179] | 325 | foreach(IFunction f in functions) {
|
---|
| 326 | if(IsPossibleParent(f, list)) {
|
---|
[155] | 327 | result.Add(f);
|
---|
[2] | 328 | }
|
---|
| 329 | }
|
---|
| 330 | return result;
|
---|
| 331 | }
|
---|
| 332 |
|
---|
[155] | 333 | private bool IsPossibleParent(IFunction f, List<IFunction> children) {
|
---|
[2] | 334 | int minArity;
|
---|
| 335 | int maxArity;
|
---|
[155] | 336 | GetMinMaxArity(f, out minArity, out maxArity);
|
---|
[2] | 337 |
|
---|
| 338 | // note: we can't assume that the operators in the children list have different types!
|
---|
| 339 |
|
---|
| 340 | // when the maxArity of this function is smaller than the list of operators that
|
---|
| 341 | // should be included as sub-operators then it can't be a parent
|
---|
[179] | 342 | if(maxArity < children.Count()) {
|
---|
[2] | 343 | return false;
|
---|
| 344 | }
|
---|
| 345 | int nSlots = Math.Max(minArity, children.Count);
|
---|
| 346 |
|
---|
| 347 | SubOperatorsConstraintAnalyser analyzer = new SubOperatorsConstraintAnalyser();
|
---|
[155] | 348 | analyzer.AllPossibleOperators = children.Cast<IOperator>().ToArray<IOperator>();
|
---|
[2] | 349 |
|
---|
[155] | 350 | List<HashSet<IFunction>> slotSets = new List<HashSet<IFunction>>();
|
---|
[2] | 351 |
|
---|
[155] | 352 | // we iterate through all slots for sub-trees and calculate the set of
|
---|
| 353 | // allowed functions for this slot.
|
---|
[2] | 354 | // we only count those slots that can hold at least one of the children that we should combine
|
---|
[179] | 355 | for(int slot = 0; slot < nSlots; slot++) {
|
---|
[155] | 356 | HashSet<IFunction> functionSet = new HashSet<IFunction>(analyzer.GetAllowedOperators(f, slot).Cast<IFunction>());
|
---|
[179] | 357 | if(functionSet.Count() > 0) {
|
---|
[155] | 358 | slotSets.Add(functionSet);
|
---|
[2] | 359 | }
|
---|
| 360 | }
|
---|
| 361 |
|
---|
| 362 | // ok at the end of this operation we know how many slots of the parent can actually
|
---|
| 363 | // hold one of our children.
|
---|
| 364 | // if the number of slots is smaller than the number of children we can be sure that
|
---|
[155] | 365 | // we can never combine all children as sub-trees of the function and thus the function
|
---|
[2] | 366 | // can't be a parent.
|
---|
[179] | 367 | if(slotSets.Count() < children.Count()) {
|
---|
[2] | 368 | return false;
|
---|
| 369 | }
|
---|
| 370 |
|
---|
| 371 | // finally we sort the sets by size and beginning from the first set select one
|
---|
[155] | 372 | // function for the slot and thus remove it as possible sub-tree from the remaining sets.
|
---|
| 373 | // when we can successfully assign all available children to a slot the function is a valid parent
|
---|
| 374 | // when only a subset of all children can be assigned to slots the function is no valid parent
|
---|
[2] | 375 | slotSets.Sort((p, q) => p.Count() - q.Count());
|
---|
| 376 |
|
---|
| 377 | int assignments = 0;
|
---|
[179] | 378 | for(int i = 0; i < slotSets.Count() - 1; i++) {
|
---|
| 379 | if(slotSets[i].Count > 0) {
|
---|
[155] | 380 | IFunction selected = slotSets[i].ElementAt(0);
|
---|
[2] | 381 | assignments++;
|
---|
[179] | 382 | for(int j = i + 1; j < slotSets.Count(); j++) {
|
---|
[2] | 383 | slotSets[j].Remove(selected);
|
---|
| 384 | }
|
---|
| 385 | }
|
---|
| 386 | }
|
---|
| 387 |
|
---|
| 388 | // sanity check
|
---|
[179] | 389 | if(assignments > children.Count) throw new InvalidProgramException();
|
---|
[2] | 390 | return assignments == children.Count - 1;
|
---|
| 391 | }
|
---|
[179] | 392 | internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
|
---|
| 393 | List<IFunction> parents = new List<IFunction>();
|
---|
| 394 | foreach(IFunction function in functions) {
|
---|
| 395 | ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
|
---|
| 396 | if(allowedSubFunctions.Contains(child)) {
|
---|
| 397 | parents.Add(function);
|
---|
| 398 | }
|
---|
| 399 | }
|
---|
| 400 | return parents;
|
---|
| 401 | }
|
---|
| 402 | internal bool IsTerminal(IFunction f) {
|
---|
| 403 | int minArity;
|
---|
| 404 | int maxArity;
|
---|
| 405 | GetMinMaxArity(f, out minArity, out maxArity);
|
---|
| 406 | return minArity == 0 && maxArity == 0;
|
---|
| 407 | }
|
---|
| 408 | internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
|
---|
| 409 | if(f == null) {
|
---|
| 410 | return allFunctions;
|
---|
| 411 | } else {
|
---|
| 412 | ItemList slotList = (ItemList)f.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
|
---|
| 413 | List<IFunction> result = new List<IFunction>();
|
---|
| 414 | foreach(IFunction function in (ItemList)slotList[index]) {
|
---|
| 415 | result.Add(function);
|
---|
| 416 | }
|
---|
| 417 | return result;
|
---|
| 418 | }
|
---|
| 419 | }
|
---|
| 420 | internal void GetMinMaxArity(IFunction f, out int minArity, out int maxArity) {
|
---|
| 421 | foreach(IConstraint constraint in f.Constraints) {
|
---|
| 422 | NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
|
---|
| 423 | if(theConstraint != null) {
|
---|
| 424 | minArity = theConstraint.MinOperators.Data;
|
---|
| 425 | maxArity = theConstraint.MaxOperators.Data;
|
---|
| 426 | return;
|
---|
| 427 | }
|
---|
| 428 | }
|
---|
| 429 | // the default arity is 2
|
---|
| 430 | minArity = 2;
|
---|
| 431 | maxArity = 2;
|
---|
| 432 | }
|
---|
| 433 | #endregion
|
---|
| 434 |
|
---|
| 435 | #region private utility methods
|
---|
[202] | 436 | private IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
|
---|
[180] | 437 | if(maxTreeHeight == 1 || maxTreeSize == 1) {
|
---|
[182] | 438 | IFunction selectedTerminal = RandomSelect(terminals);
|
---|
[202] | 439 | return selectedTerminal;
|
---|
[180] | 440 | } else {
|
---|
[284] | 441 | IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
[180] | 442 | GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
|
---|
[182] | 443 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[202] | 444 | return selectedFunction;
|
---|
[180] | 445 | }
|
---|
| 446 | }
|
---|
[179] | 447 |
|
---|
[202] | 448 | private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
|
---|
| 449 | if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
|
---|
[180] | 450 | int minArity;
|
---|
| 451 | int maxArity;
|
---|
[202] | 452 | GetMinMaxArity(parent, out minArity, out maxArity);
|
---|
[180] | 453 | if(maxArity >= maxTreeSize) {
|
---|
| 454 | maxArity = maxTreeSize;
|
---|
| 455 | }
|
---|
| 456 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 457 | if(actualArity > 0) {
|
---|
[202] | 458 | IFunctionTree parentTree = parent.GetTreeNode();
|
---|
[180] | 459 | int maxSubTreeSize = maxTreeSize / actualArity;
|
---|
| 460 | for(int i = 0; i < actualArity; i++) {
|
---|
[202] | 461 | IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
[180] | 462 | GetMinimalTreeSize(f) <= maxSubTreeSize).ToArray();
|
---|
[182] | 463 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[202] | 464 | IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
|
---|
| 465 | parentTree.InsertSubTree(i, newSubTree);
|
---|
[180] | 466 | }
|
---|
[202] | 467 | return parentTree;
|
---|
[180] | 468 | }
|
---|
[202] | 469 | return parent.GetTreeNode();
|
---|
[180] | 470 | }
|
---|
| 471 |
|
---|
| 472 | // NOTE: this method doesn't build fully balanced trees because we have constraints on the
|
---|
| 473 | // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
|
---|
[202] | 474 | private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeSize, int maxTreeHeight) {
|
---|
| 475 | if(maxTreeHeight == 0 || maxTreeSize == 0) return parent.GetTreeNode();
|
---|
[180] | 476 | int minArity;
|
---|
| 477 | int maxArity;
|
---|
[202] | 478 | GetMinMaxArity(parent, out minArity, out maxArity);
|
---|
[180] | 479 | if(maxArity >= maxTreeSize) {
|
---|
| 480 | maxArity = maxTreeSize;
|
---|
| 481 | }
|
---|
| 482 | int actualArity = random.Next(minArity, maxArity + 1);
|
---|
| 483 | if(actualArity > 0) {
|
---|
[202] | 484 | IFunctionTree parentTree = parent.GetTreeNode();
|
---|
[180] | 485 | int maxSubTreeSize = maxTreeSize / actualArity;
|
---|
| 486 | for(int i = 0; i < actualArity; i++) {
|
---|
[199] | 487 | // first try to find a function that fits into the maxHeight and maxSize limits
|
---|
[202] | 488 | IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(
|
---|
[199] | 489 | f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
|
---|
| 490 | GetMinimalTreeSize(f) <= maxSubTreeSize &&
|
---|
| 491 | !IsTerminal(f)).ToArray();
|
---|
| 492 | // no possible function found => extend function set to terminals
|
---|
| 493 | if(possibleFunctions.Length == 0) {
|
---|
[202] | 494 | possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => IsTerminal(f)).ToArray();
|
---|
[199] | 495 | IFunction selectedTerminal = RandomSelect(possibleFunctions);
|
---|
[189] | 496 | IFunctionTree newTree = selectedTerminal.GetTreeNode();
|
---|
[202] | 497 | parentTree.InsertSubTree(i, newTree);
|
---|
[180] | 498 | } else {
|
---|
[182] | 499 | IFunction selectedFunction = RandomSelect(possibleFunctions);
|
---|
[202] | 500 | IFunctionTree newTree = MakeBalancedTree(selectedFunction, maxSubTreeSize - 1, maxTreeHeight - 1);
|
---|
| 501 | parentTree.InsertSubTree(i, newTree);
|
---|
[180] | 502 | }
|
---|
| 503 | }
|
---|
[202] | 504 | return parentTree;
|
---|
[180] | 505 | }
|
---|
[202] | 506 | return parent.GetTreeNode();
|
---|
[180] | 507 | }
|
---|
| 508 |
|
---|
[179] | 509 | private int GetMinimalTreeHeight(IOperator op) {
|
---|
| 510 | return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
|
---|
| 511 | }
|
---|
| 512 |
|
---|
| 513 | private int GetMinimalTreeSize(IOperator op) {
|
---|
| 514 | return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
|
---|
| 515 | }
|
---|
| 516 |
|
---|
| 517 | private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
|
---|
| 518 | action(tree);
|
---|
| 519 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
| 520 | TreeForEach(subTree, action);
|
---|
| 521 | }
|
---|
| 522 | }
|
---|
| 523 |
|
---|
| 524 | private List<IFunctionTree> GetBranchesAtLevel(IFunctionTree tree, int level) {
|
---|
| 525 | if(level == 1) return new List<IFunctionTree>(tree.SubTrees);
|
---|
| 526 |
|
---|
| 527 | List<IFunctionTree> branches = new List<IFunctionTree>();
|
---|
| 528 | foreach(IFunctionTree subTree in tree.SubTrees) {
|
---|
| 529 | branches.AddRange(GetBranchesAtLevel(subTree, level - 1));
|
---|
| 530 | }
|
---|
| 531 | return branches;
|
---|
| 532 | }
|
---|
| 533 |
|
---|
[182] | 534 | private IFunction RandomSelect(IList<IFunction> functionSet) {
|
---|
| 535 | double[] accumulatedTickets = new double[functionSet.Count];
|
---|
| 536 | double ticketAccumulator = 0;
|
---|
| 537 | int i = 0;
|
---|
| 538 | // precalculate the slot-sizes
|
---|
| 539 | foreach(IFunction function in functionSet) {
|
---|
| 540 | ticketAccumulator += ((DoubleData)function.GetVariable(GPOperatorLibrary.TICKETS).Value).Data;
|
---|
| 541 | accumulatedTickets[i] = ticketAccumulator;
|
---|
| 542 | i++;
|
---|
| 543 | }
|
---|
| 544 | // throw ball
|
---|
| 545 | double r = random.NextDouble() * ticketAccumulator;
|
---|
| 546 | // find the slot that has been hit
|
---|
| 547 | for(i = 0; i < accumulatedTickets.Length; i++) {
|
---|
| 548 | if(r < accumulatedTickets[i]) return functionSet[i];
|
---|
| 549 | }
|
---|
| 550 | // sanity check
|
---|
| 551 | throw new InvalidProgramException(); // should never happen
|
---|
| 552 | }
|
---|
[179] | 553 |
|
---|
| 554 | #endregion
|
---|
| 555 |
|
---|
[2] | 556 | }
|
---|
| 557 | }
|
---|