Free cookie consent management tool by TermsFeed Policy Generator

Changeset 814 for trunk


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)

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

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.GP/Recombination/LangdonHomologousCrossOver.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;
    84     }
    85 
    86     private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
     80      return null;
     81    }
     82
     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);
    91 
    92 
    93       int newTreeSize = newTree.Size;
    94       int newTreeHeight = newTree.Height;
     86        random, maxTreeSize, maxTreeHeight);
     87
    9588      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);
    102     }
    103 
    104 
    105     private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {
     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)));
     91
     92      // check if the new tree is valid and if the size and height are still in the allowed bounds
     93      Debug.Assert(gardener.IsValidTree(newTree) && newTree.Height <= maxTreeHeight && newTree.Size <= maxTreeSize);
     94    }
     95
     96    private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
    10697      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    10798      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
    … …  
    112103      int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
    113104
    114       if(tree0Size == 1 && tree1Size == 1) {
    115         return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
     105      // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
     106      // in case both trees are higher than 1 we swap the trees with probability 50%
     107      if (tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
     108        IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
     109        int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
     110        int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
     111      }
     112
     113      // select a random suboperator of the 'receiving' tree
     114      IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
     115      int removedBranchIndex;
     116      IFunctionTree removedBranch;
     117      IList<IFunction> allowedFunctions;
     118      if (crossoverPoint == null) {
     119        removedBranchIndex = 0;
     120        removedBranch = tree0;
     121        allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    116122      } else {
    117         newBranches = new List<IFunctionTree>();
    118 
    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;
    125         }
    126 
    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) {
     123        removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
     124        removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
     125        allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
     126      }
     127      int removedBranchSize = removedBranch.Size;
     128      int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
     129      int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
     130      List<int> removedBranchThread = GetThread(removedBranch, tree0);
     131      IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchThread, removedBranchSize, maxBranchSize, maxBranchHeight);
     132
     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;
     138        }
     139
     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         List<int> removedBranchThread = GetThread(removedBranch, tree0);
    145         IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchThread, removedBranchSize, maxBranchSize, maxBranchHeight);
    146 
    147         int tries = 0;
    148         while(insertedBranch == null) {
    149           if(tries++ > MAX_RECOMBINATION_TRIES) {
    150             if(random.Next() > 0.5) return tree1;
    151             else return tree0;
    152           }
    153 
    154           // retry with a different crossoverPoint       
    155           crossoverPoint = gardener.GetRandomParentNode(tree0);
    156           if(crossoverPoint == null) {
    157             removedBranchIndex = 0;
    158             removedBranch = tree0;
    159             allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    160           } else {
    161             removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
    162             removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
    163             allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    164           }
    165           removedBranchSize = removedBranch.Size;
    166           maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
    167           maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
    168           removedBranchThread = GetThread(removedBranch, tree0);
    169           insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchThread, removedBranchSize, maxBranchSize, maxBranchHeight);
    170         }
    171         if(crossoverPoint != null) {
    172           // replace the branch below the crossoverpoint with the selected branch from root1
    173           crossoverPoint.RemoveSubTree(removedBranchIndex);
    174           crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
    175           return tree0;
    176         } else {
    177           return insertedBranch;
    178         }
     151        removedBranchSize = removedBranch.Size;
     152        maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
     153        maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
     154        removedBranchThread = GetThread(removedBranch, tree0);
     155        insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchThread, removedBranchSize, maxBranchSize, maxBranchHeight);
     156      }
     157      if (crossoverPoint != null) {
     158        // replace the branch below the crossoverpoint with the selected branch from root1
     159        crossoverPoint.RemoveSubTree(removedBranchIndex);
     160        crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
     161        return tree0;
     162      } else {
     163        return insertedBranch;
    179164      }
    180165    }
    … …  
    188173      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
    189174
    190       if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
    191         if(equalLengthBranches.Count() == 0) {
     175      if (shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
     176        if (equalLengthBranches.Count() == 0) {
    192177          return null;
    193178        } else {
    … …  
    201186
    202187        double r = random.NextDouble();
    203         if(r < pLonger) {
     188        if (r < pLonger) {
    204189          return longerBranches.OrderBy(t => MatchingSteps(removedBranchThread, t.Thread)).Last().Tree;
    205         } else if(r < pLonger + pShorter) {
     190        } else if (r < pLonger + pShorter) {
    206191          return shorterBranches.OrderBy(t => MatchingSteps(removedBranchThread, t.Thread)).Last().Tree;
    207192        } else {
    … …  
    213198    private int MatchingSteps(List<int> removedBranchThread, List<int> list) {
    214199      int n = Math.Min(removedBranchThread.Count, list.Count);
    215       for(int i = 0; i < n; i++) if(removedBranchThread[i] != list[i]) return i;
     200      for (int i = 0; i < n; i++) if (removedBranchThread[i] != list[i]) return i;
    216201      return n;
    217202    }
    … …  
    219204    private List<int> GetThread(IFunctionTree t, IFunctionTree tree) {
    220205      List<int> thread = new List<int>();
    221       for(int i = 0; i < tree.SubTrees.Count; i++) {
    222         if(t == tree.SubTrees[i]) {
     206      for (int i = 0; i < tree.SubTrees.Count; i++) {
     207        if (t == tree.SubTrees[i]) {
    223208          thread.Add(i);
    224209          return thread;
    225210        } else {
    226211          thread.AddRange(GetThread(t, tree.SubTrees[i]));
    227           if(thread.Count > 0) {
     212          if (thread.Count > 0) {
    228213            thread.Insert(0, i);
    229214            return thread;
    … …  
    233218      return thread;
    234219    }
    235 
    236 
    237     // take f and g and create a tree that has f and g as sub-trees
    238     // example
    239     //       O
    240     //      /|\
    241     //     g 2 f
    242     //
    243     private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
    244       newBranches = new List<IFunctionTree>();
    245       // determine the set of possible parent functions
    246       ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
    247       if(possibleParents.Count == 0) throw new InvalidProgramException();
    248       // and select a random one
    249       IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();
    250 
    251       int nSlots = Math.Max(2, parent.Function.MinArity);
    252       // determine which slot can take which sub-trees
    253       List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
    254       for(int slot = 0; slot < nSlots; slot++) {
    255         ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
    256         List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
    257         if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
    258         if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
    259         slots[slot] = allowedTrees;
    260       }
    261       // fill the slots in the order of degrees of freedom
    262       int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
    263 
    264       // tmp arry to store the tree for each sub-tree slot of the parent
    265       IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
    266 
    267       // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
    268       for(int i = 0; i < slotSequence.Length; i++) {
    269         int slot = slotSequence[i];
    270         List<IFunctionTree> allowedTrees = slots[slot];
    271         // when neither f nor g fit into the slot => create a new random tree
    272         if(allowedTrees.Count() == 0) {
    273           var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
    274           selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);
    275           newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
    276         } else {
    277           // select randomly which tree to insert into this slot
    278           IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
    279           selectedFunctionTrees[slot] = selectedTree;
    280           // remove the tree that we used in this slot from following function-sets
    281           for(int j = i + 1; j < slotSequence.Length; j++) {
    282             int otherSlot = slotSequence[j];
    283             slots[otherSlot].Remove(selectedTree);
    284           }
    285         }
    286       }
    287       // actually append the sub-trees to the parent tree
    288       for(int i = 0; i < selectedFunctionTrees.Length; i++) {
    289         parent.InsertSubTree(i, selectedFunctionTrees[i]);
    290       }
    291 
    292       return parent;
    293     }
    294220  }
    295221}

  • 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.