Changeset 1196


Ignore:
Timestamp:
02/02/09 12:45:08 (12 years ago)
Author:
gkronber
Message:

fixed #479 (Crossover operators create trees that are larger than the allowed max size)

Location:
branches/CEDMA-Refactoring-Ticket419/HeuristicLab.GP/Recombination
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • branches/CEDMA-Refactoring-Ticket419/HeuristicLab.GP/Recombination/OnePointCrossOver.cs

    r832 r1196  
    3636  /// W. B. Langdon and R. Poli.  Foundations of Genetic Programming. Springer-Verlag, 2002.
    3737  /// </summary>
    38   public class OnePointCrossOver : GPCrossoverBase {
     38  public class OnePointCrossOver : SizeConstrictedGPCrossoverBase {
    3939    // internal data structure to represent crossover points
    4040    private class CrossoverPoint {
     
    4545    public override string Description {
    4646      get {
    47         return @"";
     47        return @"One point crossover for trees as described in W. B. Langdon and R. Poli. Foundations of Genetic Programming. Springer-Verlag, 2002.";
    4848      }
    4949    }
    5050
    51     internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
     51    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
    5252      List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
    53       GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);
     53      GetCrossOverPoints(gardener, tree0, tree1, maxTreeSize - tree0.Size, allowedCrossOverPoints);
    5454      if (allowedCrossOverPoints.Count > 0) {
    5555        CrossoverPoint crossOverPoint = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
     
    6262    }
    6363
    64     private void GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1, List<CrossoverPoint> crossoverPoints) {
     64    private void GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1, int maxNewNodes, List<CrossoverPoint> crossoverPoints) {
    6565      if (branch0.SubTrees.Count != branch1.SubTrees.Count) return;
    6666
    6767      for (int i = 0; i < branch0.SubTrees.Count; i++) {
    6868        // if the current branch can be attached as a sub-tree to branch0
    69         if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function)) {
     69        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function) &&
     70           branch1.SubTrees[i].Size - branch0.SubTrees[i].Size <= maxNewNodes) {
    7071          CrossoverPoint p = new CrossoverPoint();
    7172          p.childIndex = i;
     
    7475          crossoverPoints.Add(p);
    7576        }
    76         GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i], crossoverPoints);
     77        GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i], maxNewNodes, crossoverPoints);
    7778      }
    7879    }
  • branches/CEDMA-Refactoring-Ticket419/HeuristicLab.GP/Recombination/SizeConstrictedGPCrossoverBase.cs

    r835 r1196  
    3232
    3333namespace HeuristicLab.GP {
    34   public abstract class SizeConstrictedGPCrossoverBase : GPCrossoverBase{
     34  public abstract class SizeConstrictedGPCrossoverBase : GPCrossoverBase {
     35
     36    private int MaxRecombinationTries { get { return 20; } }
     37
    3538    public SizeConstrictedGPCrossoverBase()
    3639      : base() {
     
    4548      // when tree0 is terminal then try to cross into tree1, when tree1 is also terminal just return tree0 unchanged.
    4649      IFunctionTree newTree;
    47       if (tree0.SubTrees.Count > 0) {
    48         newTree = Cross(gardener, random, tree0, tree1, maxTreeSize, maxTreeHeight);
    49       } else if (tree1.SubTrees.Count > 0) {
    50         newTree = Cross(gardener, random, tree1, tree0, maxTreeSize, maxTreeHeight);
    51       } else newTree = tree0;
    52 
    53       // check if the size and height of the new tree are still within the allowed bounds
    54       Debug.Assert(newTree.Height <= maxTreeHeight);
    55       Debug.Assert(newTree.Size <= maxTreeSize);
     50      int tries = 0;
     51      do {
     52        if (tree0.SubTrees.Count > 0) {
     53          newTree = Cross(gardener, random, (IFunctionTree)tree0.Clone(), (IFunctionTree)tree1.Clone(), maxTreeSize, maxTreeHeight);
     54        } else if (tree1.SubTrees.Count > 0) {
     55          newTree = Cross(gardener, random, (IFunctionTree)tree1.Clone(), (IFunctionTree)tree0.Clone(), maxTreeSize, maxTreeHeight);
     56        } else newTree = tree0;
     57        if (tries++ > MaxRecombinationTries)
     58          throw new InvalidOperationException("Couldn't recombine parents to create a valid child not larger than " + maxTreeSize + " and not higher than " + maxTreeHeight + ".");
     59      } while (newTree.Size > maxTreeSize || newTree.Height > maxTreeHeight);
    5660      return newTree;
    5761    }
  • branches/CEDMA-Refactoring-Ticket419/HeuristicLab.GP/Recombination/SizeFairCrossOver.cs

    r835 r1196  
    3939  /// </summary>
    4040  public class SizeFairCrossOver : SizeConstrictedGPCrossoverBase {
    41     private const int MAX_RECOMBINATION_TRIES = 20;
     41    private int MaxRecombinationTries { get { return 20; } }
    4242    // private data structure for crossover points
    4343    protected class CrossoverPoint {
     
    5757        removedBranchIndex = random.Next(parent.SubTrees.Count);
    5858        insertedBranch = GetReplacementBranch(random, gardener, tree0, parent, removedBranchIndex, tree1, maxTreeSize, maxTreeHeight);
    59       } while (insertedBranch == null && tries++ < MAX_RECOMBINATION_TRIES);
     59      } while (insertedBranch == null && tries++ < MaxRecombinationTries);
    6060
    6161      if (insertedBranch != null) {
     
    139139      for (int i = 0; i < root.SubTrees.Count; i++) {
    140140        GetTrail(root.SubTrees[i], branch, trail);
    141         if (trail.Count>0) {
     141        if (trail.Count > 0) {
    142142          trail.Add(i);
    143143          return;
  • branches/CEDMA-Refactoring-Ticket419/HeuristicLab.GP/Recombination/StandardCrossOver.cs

    r1064 r1196  
    3333namespace HeuristicLab.GP {
    3434  public class StandardCrossOver : SizeConstrictedGPCrossoverBase {
    35     private const int MAX_RECOMBINATION_TRIES = 20;
     35    private int MaxRecombinationTries { get { return 20; } }
    3636
    3737    public override string Description {
     
    5252        // select a random crossover point in the first parent tree0
    5353        parent0 = null;
    54         while(parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
     54        while (parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
    5555        // select a random branch to replace
    5656        replacedChildIndex = random.Next(parent0.SubTrees.Count);
     
    6262        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent0.Function, replacedChildIndex);
    6363        allowedCrossoverPoints = GetPossibleCrossoverPoints(gardener, tree1, maxInsertedBranchSize, maxInsertedBranchHeight, allowedFunctions);
    64       } while(allowedCrossoverPoints.Count == 0 && tries++ < MAX_RECOMBINATION_TRIES);
     64      } while (allowedCrossoverPoints.Count == 0 && tries++ < MaxRecombinationTries);
    6565
    66       if(allowedCrossoverPoints.Count > 0) {
     66      if (allowedCrossoverPoints.Count > 0) {
    6767        IFunctionTree branch1 = allowedCrossoverPoints[random.Next(allowedCrossoverPoints.Count)];
    6868
     
    7676    private List<IFunctionTree> GetPossibleCrossoverPoints(TreeGardener gardener, IFunctionTree tree, int maxInsertedBranchSize, int maxInsertedBranchHeight, IList<IFunction> allowedFunctions) {
    7777      List<IFunctionTree> crossoverPoints = new List<IFunctionTree>();
    78       foreach(IFunctionTree possiblePoint in gardener.GetAllSubTrees(tree)) {
    79         if(allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.Size <= maxInsertedBranchSize && possiblePoint.Height <= maxInsertedBranchHeight)
     78      foreach (IFunctionTree possiblePoint in gardener.GetAllSubTrees(tree)) {
     79        if (allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.Size <= maxInsertedBranchSize && possiblePoint.Height <= maxInsertedBranchHeight)
    8080          crossoverPoints.Add(possiblePoint);
    8181      }
  • branches/CEDMA-Refactoring-Ticket419/HeuristicLab.GP/Recombination/UniformCrossover.cs

    r832 r1196  
    3737  /// In Proceedings of Genetic Programming '98, Madison, Wisconsin, 1998.
    3838  /// </summary>
    39   public class UniformCrossover : GPCrossoverBase {
     39  public class UniformCrossover : SizeConstrictedGPCrossoverBase {
    4040    // internal datastructure to represent crossover points
    4141    private class CrossoverPoint {
     
    5252    }
    5353
    54     internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
     54    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
    5555      List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
    5656      GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);
Note: See TracChangeset for help on using the changeset viewer.