Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/24/08 23:59:29 (16 years ago)
Author:
gkronber
Message:
  • removed combination of two terminals to a tree and with this the initialization routine for new branches.
  • fixed an 'off-by-one' bug in the calculation of maximal branch heights.

#391 (Review and improve implementation of SizeFair and LangdonHomologous crossover operators)

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r656 r814  
    6464      TreeGardener gardener = new TreeGardener(random, opLibrary);
    6565
    66       if((scope.SubScopes.Count % 2) != 0)
     66      if ((scope.SubScopes.Count % 2) != 0)
    6767        throw new InvalidOperationException("Number of parents is not even");
    6868
    69       CompositeOperation initOperations = new CompositeOperation();
    70 
    7169      int children = scope.SubScopes.Count / 2;
    72       for(int i = 0; i < children; i++) {
     70      for (int i = 0; i < children; i++) {
    7371        IScope parent1 = scope.SubScopes[0];
    7472        scope.RemoveSubScope(parent1);
    … …  
    7674        scope.RemoveSubScope(parent2);
    7775        IScope child = new Scope(i.ToString());
    78         IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
    79         initOperations.AddOperation(childInitOperation);
     76        Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
    8077        scope.AddSubScope(child);
    8178      }
    8279
    83       return initOperations;
     80      return null;
    8481    }
    8582
    86     private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
     83    private void Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
    8784      IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
    88       List<IFunctionTree> newBranches;
    8985      IFunctionTree newTree = Cross(gardener, parent1, parent2,
    90         random, maxTreeSize, maxTreeHeight, out newBranches);
     86        random, maxTreeSize, maxTreeHeight);
    9187
     88      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
     89      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTree.Size)));
     90      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTree.Height)));
    9291
    93       int newTreeSize = newTree.Size;
    94       int newTreeHeight = newTree.Height;
    95       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
    96       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
    97       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
    98 
    99       // 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)
    100       Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
    101       return gardener.CreateInitializationOperation(newBranches, child);
     92      // check if the new tree is valid and the height and size are still in the allowed bounds
     93      Debug.Assert(gardener.IsValidTree(newTree) && newTree.Height <= maxTreeHeight && newTree.Size <= maxTreeSize);
    10294    }
    10395
    10496
    105     private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {
     97    private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
    10698      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    10799      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
    … …  
    112104      int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
    113105
    114       if(tree0Size == 1 && tree1Size == 1) {
    115         return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
     106      // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
     107      // in case both trees are higher than 1 we swap the trees with probability 50%
     108      if (tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
     109        IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
     110        int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
     111        int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
     112      }
     113
     114      // select a random suboperator of the 'receiving' tree
     115      IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
     116      int removedBranchIndex;
     117      IFunctionTree removedBranch;
     118      IList<IFunction> allowedFunctions;
     119      if (crossoverPoint == null) {
     120        removedBranchIndex = 0;
     121        removedBranch = tree0;
     122        allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    116123      } else {
    117         newBranches = new List<IFunctionTree>();
     124        removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
     125        removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
     126        allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
     127      }
     128      int removedBranchSize = removedBranch.Size;
     129      int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
     130      int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
     131      IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
    118132
    119         // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
    120         // in case both trees are higher than 1 we swap the trees with probability 50%
    121         if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
    122           IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
    123           int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
    124           int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
     133      int tries = 0;
     134      while (insertedBranch == null) {
     135        if (tries++ > MAX_RECOMBINATION_TRIES) {
     136          if (random.Next() > 0.5) return tree1;
     137          else return tree0;
    125138        }
    126139
    127         // select a random suboperator of the 'receiving' tree
    128         IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
    129         int removedBranchIndex;
    130         IFunctionTree removedBranch;
    131         IList<IFunction> allowedFunctions;
    132         if(crossoverPoint == null) {
     140        // retry with a different crossoverPoint       
     141        crossoverPoint = gardener.GetRandomParentNode(tree0);
     142        if (crossoverPoint == null) {
    133143          removedBranchIndex = 0;
    134144          removedBranch = tree0;
    … …  
    139149          allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    140150        }
    141         int removedBranchSize = removedBranch.Size;
    142         int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
    143         int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch);
    144         IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
    145 
    146         int tries = 0;
    147         while(insertedBranch == null) {
    148           if(tries++ > MAX_RECOMBINATION_TRIES) {
    149             if(random.Next() > 0.5) return tree1;
    150             else return tree0;
    151           }
    152 
    153           // retry with a different crossoverPoint       
    154           crossoverPoint = gardener.GetRandomParentNode(tree0);
    155           if(crossoverPoint == null) {
    156             removedBranchIndex = 0;
    157             removedBranch = tree0;
    158             allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    159           } else {
    160             removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
    161             removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
    162             allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    163           }
    164           removedBranchSize = removedBranch.Size;
    165           maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
    166           maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
    167           insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
    168         }
    169         if(crossoverPoint != null) {
    170           // replace the branch below the crossoverpoint with the selected branch from root1
    171           crossoverPoint.RemoveSubTree(removedBranchIndex);
    172           crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
    173           return tree0;
    174         } else {
    175           return insertedBranch;
    176         }
     151        removedBranchSize = removedBranch.Size;
     152        maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
     153        maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
     154        insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
     155      }
     156      if (crossoverPoint != null) {
     157        // replace the branch below the crossoverpoint with the selected branch from root1
     158        crossoverPoint.RemoveSubTree(removedBranchIndex);
     159        crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
     160        return tree0;
     161      } else {
     162        return insertedBranch;
    177163      }
    178164    }
    … …  
    186172      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
    187173
    188       if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
    189         if(equalLengthBranches.Count() == 0) {
     174      if (shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
     175        if (equalLengthBranches.Count() == 0) {
    190176          return null;
    191177        } else {
    … …  
    199185
    200186        double r = random.NextDouble();
    201         if(r < pLonger) {
     187        if (r < pLonger) {
    202188          return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
    203         } else if(r < pLonger + pShorter) {
     189        } else if (r < pLonger + pShorter) {
    204190          return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
    205191        } else {
    … …  
    208194      }
    209195    }
    210 
    211 
    212     // take f and g and create a tree that has f and g as sub-trees
    213     // example
    214     //       O
    215     //      /|\
    216     //     g 2 f
    217     //
    218     private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
    219       newBranches = new List<IFunctionTree>();
    220       // determine the set of possible parent functions
    221       ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
    222       if(possibleParents.Count == 0) throw new InvalidProgramException();
    223       // and select a random one
    224       IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();
    225 
    226       int nSlots = Math.Max(2, parent.Function.MinArity);
    227       // determine which slot can take which sub-trees
    228       List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
    229       for(int slot = 0; slot < nSlots; slot++) {
    230         ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
    231         List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
    232         if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
    233         if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
    234         slots[slot] = allowedTrees;
    235       }
    236       // fill the slots in the order of degrees of freedom
    237       int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
    238 
    239       // tmp arry to store the tree for each sub-tree slot of the parent
    240       IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
    241 
    242       // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
    243       for(int i = 0; i < slotSequence.Length; i++) {
    244         int slot = slotSequence[i];
    245         List<IFunctionTree> allowedTrees = slots[slot];
    246         // when neither f nor g fit into the slot => create a new random tree
    247         if(allowedTrees.Count() == 0) {
    248           var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
    249           selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);
    250           newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
    251         } else {
    252           // select randomly which tree to insert into this slot
    253           IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
    254           selectedFunctionTrees[slot] = selectedTree;
    255           // remove the tree that we used in this slot from following function-sets
    256           for(int j = i + 1; j < slotSequence.Length; j++) {
    257             int otherSlot = slotSequence[j];
    258             slots[otherSlot].Remove(selectedTree);
    259           }
    260         }
    261       }
    262       // actually append the sub-trees to the parent tree
    263       for(int i = 0; i < selectedFunctionTrees.Length; i++) {
    264         parent.InsertSubTree(i, selectedFunctionTrees[i]);
    265       }
    266 
    267       return parent;
    268     }
    269196  }
    270197}
Note: See TracChangeset for help on using the changeset viewer.