Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/26/08 18:21:23 (15 years ago)
Author:
gkronber
Message:

simplified StandardCrossOver to a simple sub-tree swapping crossover with max size and height constraints.
The old version should probably be revived as HL2StandardCrossover.

#393 (Refactor GP crossover operators to extract common code into the abstract base class GPCrossoverBase)

Location:
trunk/sources/HeuristicLab.GP/Recombination
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.GP/Recombination/GPCrossoverBase.cs

    r815 r832  
    6464        }
    6565
    66         IFunctionTree child = Cross(gardener, random, parent0, parent1);
     66        IFunctionTree child = Cross(scope, gardener, random, parent0, parent1);
    6767        Debug.Assert(gardener.IsValidTree(child));
    6868        IScope childScope = new Scope(i.ToString());
    … …  
    7676    }
    7777
    78     internal abstract IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1);
     78    internal abstract IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1);
    7979
    8080    private IFunctionTree TakeNextParent(IScope scope) {

  • trunk/sources/HeuristicLab.GP/Recombination/OnePointCrossOver.cs

    r815 r832  
    4949    }
    5050
    51     internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
     51    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
    5252      List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
    5353      GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);

  • trunk/sources/HeuristicLab.GP/Recombination/StandardCrossOver.cs

    r656 r832  
    3232
    3333namespace HeuristicLab.GP {
    34   public class StandardCrossOver : OperatorBase {
    35     private const int MAX_RECOMBINATION_TRIES = 20;
     34  public class StandardCrossOver : GPCrossoverBase {
     35    private const int MAX_RECOMBINATION_TRIES = 100;
     36
    3637    public override string Description {
    3738      get {
    … …  
    4445    public StandardCrossOver()
    4546      : base() {
    46       AddVariableInfo(new VariableInfo("Random", "Pseudo random number generator", typeof(MersenneTwister), VariableKind.In));
    47       AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
    4847      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    4948      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    50       AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.New));
    51       AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));
    52       AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));
    5349    }
    5450
    55     public override IOperation Apply(IScope scope) {
    56       MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    57       GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
     51    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
    5852      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    5953      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    6054
    61       TreeGardener gardener = new TreeGardener(random, opLibrary);
    62 
    63       if((scope.SubScopes.Count % 2) != 0)
    64         throw new InvalidOperationException("Number of parents is not even");
    65 
    66       CompositeOperation initOperations = new CompositeOperation();
    67 
    68       int children = scope.SubScopes.Count / 2;
    69       for(int i = 0; i < children; i++) {
    70         IScope parent1 = scope.SubScopes[0];
    71         scope.RemoveSubScope(parent1);
    72         IScope parent2 = scope.SubScopes[0];
    73         scope.RemoveSubScope(parent2);
    74         IScope child = new Scope(i.ToString());
    75         IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
    76         initOperations.AddOperation(childInitOperation);
    77         scope.AddSubScope(child);
    78       }
    79 
    80       return initOperations;
    81     }
    82 
    83     private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
    84       IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
    85       List<IFunctionTree> newBranches;
    86       IFunctionTree newTree = Cross(gardener, parent1, parent2,
    87         random, maxTreeSize, maxTreeHeight, out newBranches);
    88 
    89 
    90       int newTreeSize = newTree.Size;
    91       int newTreeHeight = newTree.Height;
    92       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
    93       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
    94       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
     55      // when tree0 is terminal then try to cross into tree1, when tree1 is also terminal just return tree0 unchanged.
     56      IFunctionTree newTree;
     57      if(tree0.SubTrees.Count > 0) {
     58        newTree = Cross(gardener, tree0, tree1, random, maxTreeSize, maxTreeHeight);
     59      } else if(tree1.SubTrees.Count > 0) {
     60        newTree = Cross(gardener, tree1, tree0, random, maxTreeSize, maxTreeHeight);
     61      } else newTree = tree0;
    9562
    9663      // check if the new tree is valid and if the height of is still in the allowed bounds (we are not so strict for the max-size)
    97       Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
    98       return gardener.CreateInitializationOperation(newBranches, child);
     64      Debug.Assert(gardener.IsValidTree(newTree) && newTree.Height <= maxTreeHeight && newTree.Size <= maxTreeSize);
     65      return newTree;
    9966    }
    10067
    10168
    102     private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {
    103       IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    104       int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
    105       int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
     69    private IFunctionTree Cross(TreeGardener gardener, IFunctionTree tree0, IFunctionTree tree1, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
     70      int tries = 0;
     71      List<IFunctionTree> allowedCrossoverPoints = null;
     72      IFunctionTree parent0;
     73      int replacedChildIndex;
     74      do {
     75        // select a random crossover point in the first parent tree0
     76        parent0 = null;
     77        while(parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
     78        // select a random branch to replace
     79        replacedChildIndex = random.Next(parent0.SubTrees.Count);
    10680
    107       IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
    108       int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;
    109       int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
     81        // calculate the max size and height that the inserted branch can have
     82        int maxInsertedBranchSize = maxTreeSize - (tree0.Size - parent0.SubTrees[replacedChildIndex].Size);
     83        int maxInsertedBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, parent0); // branchlevel is 1 if tree0==parent0
    11084
    111       if(tree0Size == 1 && tree1Size == 1) {
    112         return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
    113       } else {
    114         newBranches = new List<IFunctionTree>();
     85        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent0.Function, replacedChildIndex);
     86        allowedCrossoverPoints = GetPossibleCrossoverPoints(gardener, tree1, maxInsertedBranchSize, maxInsertedBranchHeight, allowedFunctions);
     87      } while(allowedCrossoverPoints.Count == 0 || tries++ > MAX_RECOMBINATION_TRIES);
    11588
    116         // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
    117         // in case both trees are higher than 1 we swap the trees with probability 50%
    118         if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
    119           IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
    120           int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
    121           int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
    122         }
     89      if(allowedCrossoverPoints.Count > 0) {
     90        IFunctionTree branch1 = allowedCrossoverPoints[random.Next(allowedCrossoverPoints.Count)];
    12391
    124         // save the roots because later on we change tree0 and tree1 while searching a valid tree configuration
    125         IFunctionTree root0 = tree0;
    126         IFunctionTree root1 = tree1;
    127         int root0Height = tree0Height;
    128         int root1Height = tree1Height;
    129         int rootSize = tree0Size;
    130 
    131         // select a random suboperators of the two trees at a random level
    132         int tree0Level = random.Next(root0Height - 1); // since we checked before that the height of tree0 is > 1 this is OK
    133         int tree1Level = random.Next(root1Height);
    134         tree0 = gardener.GetRandomBranch(tree0, tree0Level);
    135         tree1 = gardener.GetRandomBranch(tree1, tree1Level);
    136 
    137         // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
    138         tree1Size = tree1.Size;
    139         tree1Height = tree1.Height;
    140 
    141         List<int> possibleChildIndices = new List<int>();
    142 
    143         // Now tree0 is supposed to take tree1 as one if its children. If this is not possible,
    144         // then go down in either of the two trees as far as possible. If even then it is not possible
    145         // to merge the trees then throw an exception
    146         // find the list of allowed indices (regarding allowed sub-trees, maxTreeSize and maxTreeHeight)
    147         for(int i = 0; i < tree0.SubTrees.Count; i++) {
    148           int subTreeSize = tree0.SubTrees[i].Size;
    149 
    150           // the index is ok when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
    151           if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
    152             rootSize - subTreeSize + tree1Size < maxTreeSize &&
    153             tree0Level + tree1Height < maxTreeHeight) {
    154             possibleChildIndices.Add(i);
    155           }
    156         }
    157         int tries = 0;
    158         while(possibleChildIndices.Count == 0) {
    159           if(tries++ > MAX_RECOMBINATION_TRIES) {
    160             if(random.Next() > 0.5) return root1;
    161             else return root0;
    162           }
    163           // we couln't find a possible configuration given the current tree0 and tree1
    164           // possible reasons for this are:
    165           //  - tree1 is not allowed as sub-tree of tree0
    166           //  - appending tree1 as child of tree0 would create a tree that exceedes the maxTreeHeight
    167           //  - replacing any child of tree0 with tree1 woulde create a tree that exceedes the maxTeeSize
    168           // thus we just try until we find a valid configuration
    169 
    170           tree0Level = random.Next(root0Height - 1);
    171           tree1Level = random.Next(root1Height);
    172           tree0 = gardener.GetRandomBranch(root0, tree0Level);
    173           tree1 = gardener.GetRandomBranch(root1, tree1Level);
    174 
    175           // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
    176           tree1Size = tree1.Size;
    177           tree1Height = tree1.Height;
    178           // recalculate the list of possible indices
    179           possibleChildIndices.Clear();
    180           for(int i = 0; i < tree0.SubTrees.Count; i++) {
    181             int subTreeSize = tree0.SubTrees[i].Size;
    182 
    183             // when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
    184             // the index is ok
    185             if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
    186               rootSize - subTreeSize + tree1Size < maxTreeSize &&
    187               tree0Level + tree1Height < maxTreeHeight) {
    188               possibleChildIndices.Add(i);
    189             }
    190           }
    191         }
    192         // replace the existing sub-tree at a random index in tree0 with tree1
    193         int selectedIndex = possibleChildIndices[random.Next(possibleChildIndices.Count)];
    194         tree0.RemoveSubTree(selectedIndex);
    195         tree0.InsertSubTree(selectedIndex, tree1);
    196         return root0;
     92        // replace the branch in tree0 with the selected branch from tree1
     93        parent0.RemoveSubTree(replacedChildIndex);
     94        parent0.InsertSubTree(replacedChildIndex, branch1);
    19795      }
     96      return tree0;
    19897    }
    19998
    200 
    201     // take f and g and create a tree that has f and g as sub-trees
    202     // example
    203     //       O
    204     //      /|\
    205     //     g 2 f
    206     //
    207     private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
    208       newBranches = new List<IFunctionTree>();
    209       // determine the set of possible parent functions
    210       ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
    211       if(possibleParents.Count == 0) throw new InvalidProgramException();
    212       // and select a random one
    213       IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();
    214 
    215       int nSlots = Math.Max(2, parent.Function.MinArity);
    216       // determine which slot can take which sub-trees
    217       List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
    218       for(int slot = 0; slot < nSlots; slot++) {
    219         ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
    220         List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
    221         if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
    222         if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
    223         slots[slot] = allowedTrees;
     99    private List<IFunctionTree> GetPossibleCrossoverPoints(TreeGardener gardener, IFunctionTree tree, int maxInsertedBranchSize, int maxInsertedBranchHeight, IList<IFunction> allowedFunctions) {
     100      List<IFunctionTree> crossoverPoints = new List<IFunctionTree>();
     101      foreach(IFunctionTree possiblePoint in gardener.GetAllSubTrees(tree)) {
     102        if(allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.Size <= maxInsertedBranchSize && possiblePoint.Height <= maxInsertedBranchHeight)
     103          crossoverPoints.Add(possiblePoint);
    224104      }
    225       // fill the slots in the order of degrees of freedom
    226       int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
    227 
    228       // tmp arry to store the tree for each sub-tree slot of the parent
    229       IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
    230 
    231       // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
    232       for(int i = 0; i < slotSequence.Length; i++) {
    233         int slot = slotSequence[i];
    234         List<IFunctionTree> allowedTrees = slots[slot];
    235         // when neither f nor g fit into the slot => create a new random tree
    236         if(allowedTrees.Count() == 0) {
    237           var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
    238           selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);
    239           newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
    240         } else {
    241           // select randomly which tree to insert into this slot
    242           IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
    243           selectedFunctionTrees[slot] = selectedTree;
    244           // remove the tree that we used in this slot from following function-sets
    245           for(int j = i + 1; j < slotSequence.Length; j++) {
    246             int otherSlot = slotSequence[j];
    247             slots[otherSlot].Remove(selectedTree);
    248           }
    249         }
    250       }
    251       // actually append the sub-trees to the parent tree
    252       for(int i = 0; i < selectedFunctionTrees.Length; i++) {
    253         parent.InsertSubTree(i, selectedFunctionTrees[i]);
    254       }
    255 
    256       return parent;
     105      return crossoverPoints;
    257106    }
    258107  }

  • trunk/sources/HeuristicLab.GP/Recombination/UniformCrossover.cs

    r815 r832  
    5252    }
    5353
    54     internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
     54    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
    5555      List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
    5656      GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);
Note: See TracChangeset for help on using the changeset viewer.