Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/03/09 12:26:42 (15 years ago)
Author:
gkronber
Message:

Merged changes from GP-refactoring branch back into the trunk #713.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.GP/3.3/TreeGardener.cs

    r1529 r2222  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Text;
    2524using HeuristicLab.Core;
    26 using HeuristicLab.Constraints;
    27 using System.Diagnostics;
    28 using HeuristicLab.Data;
    2925using System.Linq;
    30 using HeuristicLab.Random;
    31 using HeuristicLab.Operators;
    3226using System.Collections;
    33 using HeuristicLab.Selection;
     27using HeuristicLab.GP.Interfaces;
    3428
    3529namespace HeuristicLab.GP {
    36   internal class TreeGardener {
     30  public class TreeGardener {
    3731    private IRandom random;
    38     private GPOperatorLibrary funLibrary;
     32    private FunctionLibrary funLibrary;
    3933    private List<IFunction> functions;
    4034
    4135    private List<IFunction> terminals;
    42     internal IList<IFunction> Terminals {
     36    public IList<IFunction> Terminals {
    4337      get { return terminals; }
    4438    }
    4539
    4640    private List<IFunction> allFunctions;
    47     internal IList<IFunction> AllFunctions {
     41    public IList<IFunction> AllFunctions {
    4842      get { return allFunctions; }
    4943    }
    5044
    5145    #region constructors
    52     internal TreeGardener(IRandom random, GPOperatorLibrary funLibrary) {
     46    public TreeGardener(IRandom random, FunctionLibrary funLibrary) {
    5347      this.random = random;
    5448      this.funLibrary = funLibrary;
    … …  
    5751      functions = new List<IFunction>();
    5852      // init functions and terminals based on constraints
    59       foreach(IFunction fun in funLibrary.Group.Operators) {
    60         if(fun.MaxArity == 0) {
     53      foreach(IFunction fun in funLibrary.Functions) {
     54        if(fun.MaxSubTrees == 0) {
    6155          terminals.Add(fun);
    6256          allFunctions.Add(fun);
    … …  
    7771    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
    7872    /// <returns></returns>
    79     internal IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
     73    public IFunctionTree CreateBalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
    8074      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
    8175      IFunctionTree tree = MakeBalancedTree(rootFunction, maxTreeHeight - 1);
    … …  
    9084    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
    9185    /// <returns></returns>
    92     internal IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
     86    public IFunctionTree CreateUnbalancedRandomTree(int maxTreeSize, int maxTreeHeight) {
    9387      IFunction rootFunction = GetRandomRoot(maxTreeSize, maxTreeHeight);
    9488      IFunctionTree tree = MakeUnbalancedTree(rootFunction, maxTreeHeight - 1);
    … …  
    9690    }
    9791
    98     internal IFunctionTree PTC2(IRandom random, int size, int maxDepth) {
    99       return PTC2(random, GetRandomRoot(size, maxDepth), size, maxDepth);
    100     }
    101 
    102     internal IFunctionTree PTC2(IRandom random, IFunction rootF, int size, int maxDepth) {
    103       IFunctionTree root = rootF.GetTreeNode();
    104       if(size <= 1 || maxDepth <= 1) return root;
     92    public IFunctionTree PTC2(int size, int maxDepth) {
     93      return PTC2(GetRandomRoot(size, maxDepth), size, maxDepth);
     94    }
     95
     96    private IFunctionTree PTC2(IFunction rootFunction, int size, int maxDepth) {
     97      IFunctionTree root = rootFunction.GetTreeNode();
     98      if (size <= 1 || maxDepth <= 1) return root;
    10599      List<object[]> list = new List<object[]>();
    106100      int currentSize = 1;
    107101      int totalListMinSize = 0;
    108       int minArity = root.Function.MinArity;
    109       int maxArity = root.Function.MaxArity;
    110       if(maxArity >= size) {
     102      int minArity = root.Function.MinSubTrees;
     103      int maxArity = root.Function.MaxSubTrees;
     104      if (maxArity >= size) {
    111105        maxArity = size;
    112106      }
    113107      int actualArity = random.Next(minArity, maxArity + 1);
    114       totalListMinSize += GetMinimalTreeSize(root.Function) - 1;
    115       for(int i = 0; i < actualArity; i++) {
     108      totalListMinSize += root.Function.MinTreeSize - 1;
     109      for (int i = 0; i < actualArity; i++) {
    116110        // insert a dummy sub-tree and add the pending extension to the list
    117111        root.AddSubTree(null);
    … …  
    119113      }
    120114
    121       while(list.Count > 0 && totalListMinSize + currentSize < size) {
     115      while (list.Count > 0 && totalListMinSize + currentSize < size) {
    122116        int randomIndex = random.Next(list.Count);
    123117        object[] nextExtension = list[randomIndex];
    … …  
    126120        int a = (int)nextExtension[1];
    127121        int d = (int)nextExtension[2];
    128         if(d == maxDepth) {
     122        if (d == maxDepth) {
    129123          parent.RemoveSubTree(a);
    130124          IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
    131125          parent.InsertSubTree(a, branch); // insert a smallest possible tree
    132           currentSize += branch.Size;
    133           totalListMinSize -= branch.Size;
     126          currentSize += branch.GetSize();
     127          totalListMinSize -= branch.GetSize();
    134128        } else {
    135           IFunction selectedFunction = RandomSelect(GetAllowedSubFunctions(parent.Function, a).Where(
    136             f => !IsTerminal(f) && GetMinimalTreeHeight(f) + (d - 1) <= maxDepth).ToArray());
     129          IFunction selectedFunction = TreeGardener.RandomSelect(random, GetAllowedSubFunctions(parent.Function, a).Where(
     130            f => !TreeGardener.IsTerminal(f) && f.MinTreeHeight + (d - 1) <= maxDepth).ToArray());
    137131          IFunctionTree newTree = selectedFunction.GetTreeNode();
    138132          parent.RemoveSubTree(a);
    … …  
    141135          totalListMinSize--;
    142136
    143           minArity = selectedFunction.MinArity;
    144           maxArity = selectedFunction.MaxArity;
    145           if(maxArity >= size) {
     137          minArity = selectedFunction.MinSubTrees;
     138          maxArity = selectedFunction.MaxSubTrees;
     139          if (maxArity >= size) {
    146140            maxArity = size;
    147141          }
    148142          actualArity = random.Next(minArity, maxArity + 1);
    149           for(int i = 0; i < actualArity; i++) {
     143          for (int i = 0; i < actualArity; i++) {
    150144            // insert a dummy sub-tree and add the pending extension to the list
    151145            newTree.AddSubTree(null);
    152146            list.Add(new object[] { newTree, i, d + 1 });
    153147          }
    154           totalListMinSize += GetMinimalTreeSize(newTree.Function) - 1;
    155         }
    156       }
    157       while(list.Count > 0) {
     148          totalListMinSize += newTree.Function.MinTreeSize - 1;
     149        }
     150      }
     151      while (list.Count > 0) {
    158152        int randomIndex = random.Next(list.Count);
    159153        object[] nextExtension = list[randomIndex];
    … …  
    168162      return root;
    169163    }
    170 
     164 
    171165    /// <summary>
    172166    /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height.
    … …  
    176170    /// <param name="maxTreeHeight">Maximal height of the tree.</param>
    177171    /// <returns>New random unbalanced tree</returns>
    178     internal IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
     172    public IFunctionTree CreateRandomTree(ICollection<IFunction> allowedFunctions, int maxTreeSize, int maxTreeHeight) {
    179173      // get the minimal needed height based on allowed functions and extend the max-height if necessary
    180       int minTreeHeight = allowedFunctions.Select(f => GetMinimalTreeHeight(f)).Min();
     174      int minTreeHeight = allowedFunctions.Select(f => f.MinTreeHeight).Min();
    181175      if(minTreeHeight > maxTreeHeight)
    182176        maxTreeHeight = minTreeHeight;
    183177      // get the minimal needed size based on allowed functions and extend the max-size if necessary
    184       int minTreeSize = allowedFunctions.Select(f => GetMinimalTreeSize(f)).Min();
     178      int minTreeSize = allowedFunctions.Select(f => f.MinTreeSize).Min();
    185179      if(minTreeSize > maxTreeSize)
    186180        maxTreeSize = minTreeSize;
    … …  
    191185
    192186      // filter the set of allowed functions and select only from those that fit into the given maximal size and height limits
    193       IFunction[] possibleFunctions = allowedFunctions.Where(f => GetMinimalTreeHeight(f) <= treeHeight &&
    194         GetMinimalTreeSize(f) <= treeSize).ToArray();
     187      IFunction[] possibleFunctions = allowedFunctions.Where(f => f.MinTreeHeight <= treeHeight &&
     188        f.MinTreeSize <= treeSize).ToArray();
    195189      IFunction selectedFunction = RandomSelect(possibleFunctions);
    196190
    197191      // build the tree
    198192      IFunctionTree root;
    199       root = PTC2(random, selectedFunction, maxTreeSize, maxTreeHeight);
     193      root = PTC2(selectedFunction, maxTreeSize, maxTreeHeight);
    200194      return root;
    201195    }
    202 
    203     internal CompositeOperation CreateInitializationOperation(ICollection<IFunctionTree> trees, IScope scope) {
    204       // needed for the parameter shaking operation
    205       CompositeOperation initializationOperation = new CompositeOperation();
    206       Scope tempScope = new Scope("Temp. initialization scope");
    207 
    208       var parametricTrees = trees.Where(t => t.Function.GetVariable(FunctionBase.INITIALIZATION) != null);
    209       foreach(IFunctionTree tree in parametricTrees) {
    210         // enqueue an initialization operation for each operator with local variables
    211         IOperator initialization = (IOperator)tree.Function.GetVariable(FunctionBase.INITIALIZATION).Value;
    212         Scope initScope = new Scope();
    213         // copy the local variables into a temporary scope used for initialization
    214         foreach(IVariable variable in tree.LocalVariables) {
    215           initScope.AddVariable(variable);
    216         }
    217         tempScope.AddSubScope(initScope);
    218         initializationOperation.AddOperation(new AtomicOperation(initialization, initScope));
    219       }
    220       Scope backupScope = new Scope("backup");
    221       foreach(Scope subScope in scope.SubScopes) {
    222         backupScope.AddSubScope(subScope);
    223       }
    224       scope.AddSubScope(tempScope);
    225       scope.AddSubScope(backupScope);
    226       // add an operation to remove the temporary scopes       
    227       initializationOperation.AddOperation(new AtomicOperation(new RightReducer(), scope));
    228       return initializationOperation;
    229     }
    230196    #endregion
    231197
    232198    #region tree information gathering
    233     internal IFunctionTree GetRandomParentNode(IFunctionTree tree) {
     199    public IFunctionTree GetRandomParentNode(IFunctionTree tree) {
    234200      List<IFunctionTree> parentNodes = new List<IFunctionTree>();
    235201
    … …  
    246212    }
    247213
    248     internal ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
     214    public static ICollection<IFunctionTree> GetAllSubTrees(IFunctionTree root) {
    249215      List<IFunctionTree> allTrees = new List<IFunctionTree>();
    250216      TreeForEach(root, t => { allTrees.Add(t); });
    … …  
    262228    /// <param name="branch">branch that is searched in the tree</param>
    263229    /// <returns></returns>
    264     internal int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
     230    public int GetBranchLevel(IFunctionTree tree, IFunctionTree branch) {
    265231      return GetBranchLevelHelper(tree, branch, 1);
    266232    }
    … …  
    278244    }
    279245
    280     internal bool IsValidTree(IFunctionTree tree) {
     246    public bool IsValidTree(IFunctionTree tree) {
    281247      for(int i = 0; i < tree.SubTrees.Count; i++) {
    282         if(!tree.Function.AllowedSubFunctions(i).Contains(tree.SubTrees[i].Function)) return false;
    283       }
    284 
    285       if(tree.SubTrees.Count < tree.Function.MinArity || tree.SubTrees.Count > tree.Function.MaxArity)
     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)
    286252        return false;
    287253      foreach(IFunctionTree subTree in tree.SubTrees) {
    … …  
    292258
    293259    // returns a random branch from the specified level in the tree
    294     internal IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
     260    public IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
    295261      if(level == 0) return tree;
    296262      List<IFunctionTree> branches = new List<IFunctionTree>();
    … …  
    312278
    313279    private bool IsPossibleParent(IFunction f, List<IFunction> children) {
    314       int minArity = f.MinArity;
    315       int maxArity = f.MaxArity;
     280      int minArity = f.MinSubTrees;
     281      int maxArity = f.MaxSubTrees;
    316282      // note: we can't assume that the operators in the children list have different types!
    317283
    … …  
    329295      // we only count those slots that can hold at least one of the children that we should combine
    330296      for(int slot = 0; slot < nSlots; slot++) {
    331         HashSet<IFunction> functionSet = new HashSet<IFunction>(f.AllowedSubFunctions(slot));
     297        HashSet<IFunction> functionSet = new HashSet<IFunction>(f.GetAllowedSubFunctions(slot));
    332298        if(functionSet.Count() > 0) {
    333299          slotSets.Add(functionSet);
    … …  
    365331      return assignments == children.Count - 1;
    366332    }
    367     internal IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
     333    public IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
    368334      List<IFunction> parents = new List<IFunction>();
    369335      foreach(IFunction function in functions) {
    … …  
    375341      return parents;
    376342    }
    377     internal bool IsTerminal(IFunction f) {
    378       return f.MinArity == 0 && f.MaxArity == 0;
    379     }
    380     internal IList<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
     343    public static bool IsTerminal(IFunction f) {
     344      return f.MinSubTrees == 0 && f.MaxSubTrees == 0;
     345    }
     346    public ICollection<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
    381347      if(f == null) {
    382348        return allFunctions;
    383349      } else {
    384         return f.AllowedSubFunctions(index);
     350        return f.GetAllowedSubFunctions(index);
    385351      }
    386352    }
    … …  
    388354
    389355    #region private utility methods
    390     private IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
     356    public IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
    391357      if(maxTreeHeight == 1 || maxTreeSize == 1) {
    392358        IFunction selectedTerminal = RandomSelect(terminals);
    393359        return selectedTerminal;
    394360      } else {
    395         IFunction[] possibleFunctions = functions.Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
    396           GetMinimalTreeSize(f) <= maxTreeSize).ToArray();
     361        IFunction[] possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight &&
     362          f.MinTreeSize <= maxTreeSize).ToArray();
    397363        IFunction selectedFunction = RandomSelect(possibleFunctions);
    398364        return selectedFunction;
    … …  
    403369    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) {
    404370      if(maxTreeHeight == 0) return parent.GetTreeNode();
    405       int minArity = parent.MinArity;
    406       int maxArity = parent.MaxArity;
     371      int minArity = parent.MinSubTrees;
     372      int maxArity = parent.MaxSubTrees;
    407373      int actualArity = random.Next(minArity, maxArity + 1);
    408374      if(actualArity > 0) {
    409375        IFunctionTree parentTree = parent.GetTreeNode();
    410376        for(int i = 0; i < actualArity; i++) {
    411           IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight).ToArray();
     377          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight).ToArray();
    412378          IFunction selectedFunction = RandomSelect(possibleFunctions);
    413379          IFunctionTree newSubTree = MakeUnbalancedTree(selectedFunction, maxTreeHeight - 1);
    … …  
    424390    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) {
    425391      if(maxTreeHeight == 0) return parent.GetTreeNode();
    426       int minArity = parent.MinArity;
    427       int maxArity = parent.MaxArity;
     392      int minArity = parent.MinSubTrees;
     393      int maxArity = parent.MaxSubTrees;
    428394      int actualArity = random.Next(minArity, maxArity + 1);
    429395      if(actualArity > 0) {
    … …  
    431397        for(int i = 0; i < actualArity; i++) {
    432398          // first try to find a function that fits into the maxHeight limit
    433           IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => GetMinimalTreeHeight(f) <= maxTreeHeight &&
     399          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight &&
    434400            !IsTerminal(f)).ToArray();
    435401          // no possible function found => extend function set to terminals
    … …  
    450416    }
    451417
    452     private int GetMinimalTreeHeight(IOperator op) {
    453       return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data;
    454     }
    455 
    456     private int GetMinimalTreeSize(IOperator op) {
    457       return ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data;
    458     }
    459 
    460     private void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
     418    private static void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
    461419      action(tree);
    462420      foreach(IFunctionTree subTree in tree.SubTrees) {
    … …  
    465423    }
    466424
    467     private void GetBranchesAtLevel(IFunctionTree tree, int level, List<IFunctionTree> result) {
     425    private static void GetBranchesAtLevel(IFunctionTree tree, int level, List<IFunctionTree> result) {
    468426      if(level == 1) result.AddRange(tree.SubTrees);
    469427      foreach(IFunctionTree subTree in tree.SubTrees) {
    470         if(subTree.Height >= level - 1)
     428        if(subTree.GetHeight() >= level - 1)
    471429          GetBranchesAtLevel(subTree, level - 1, result);
    472430      }
    … …  
    474432
    475433    private IFunction RandomSelect(IList<IFunction> functionSet) {
     434      return RandomSelect(random, functionSet);
     435    }
     436
     437    public static IFunction RandomSelect(IRandom random, IList<IFunction> functionSet) {
    476438      double[] accumulatedTickets = new double[functionSet.Count];
    477439      double ticketAccumulator = 0;
    478440      int i = 0;
    479441      // precalculate the slot-sizes
    480       foreach(IFunction function in functionSet) {
    481         ticketAccumulator += ((DoubleData)function.GetVariable(GPOperatorLibrary.TICKETS).Value).Data;
     442      foreach (IFunction function in functionSet) {
     443        ticketAccumulator += function.Tickets;
    482444        accumulatedTickets[i] = ticketAccumulator;
    483445        i++;
    … …  
    486448      double r = random.NextDouble() * ticketAccumulator;
    487449      // find the slot that has been hit
    488       for(i = 0; i < accumulatedTickets.Length; i++) {
    489         if(r < accumulatedTickets[i]) return functionSet[i];
     450      for (i = 0; i < accumulatedTickets.Length; i++) {
     451        if (r < accumulatedTickets[i]) return functionSet[i];
    490452      }
    491453      // sanity check
Note: See TracChangeset for help on using the changeset viewer.