Changeset 1197

Timestamp:

02/02/09 12:47:48 (16 years ago)

Author:

gkronber

Message:

merged fix for #479 (Crossover operators create trees that are larger than the allowed max size) (r1196) to trunk

Location:

trunk/sources/HeuristicLab.GP/Recombination

Files:

• OnePointCrossOver.cs (modified) (4 diffs)
• SizeConstrictedGPCrossoverBase.cs (modified) (2 diffs)
• SizeFairCrossOver.cs (modified) (3 diffs)
• StandardCrossOver.cs (modified) (4 diffs)
• UniformCrossover.cs (modified) (2 diffs)

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

@@ -36 +36 @@
   /// W. B. Langdon and R. Poli.  Foundations of Genetic Programming. Springer-Verlag, 2002.
   /// </summary>
-  public class OnePointCrossOver : GPCrossoverBase {
+  public class OnePointCrossOver : SizeConstrictedGPCrossoverBase {
     // internal data structure to represent crossover points
     private class CrossoverPoint {
@@ -45 +45 @@
     public override string Description {
       get {
-        return @"";
+        return @"One point crossover for trees as described in W. B. Langdon and R. Poli. Foundations of Genetic Programming. Springer-Verlag, 2002.";
       }
     }
 
-    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
+    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
       List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
-      GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);
+      GetCrossOverPoints(gardener, tree0, tree1, maxTreeSize - tree0.Size, allowedCrossOverPoints);
       if (allowedCrossOverPoints.Count > 0) {
         CrossoverPoint crossOverPoint = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
@@ -62 +62 @@
     }
 
-    private void GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1, List<CrossoverPoint> crossoverPoints) {
+    private void GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1, int maxNewNodes, List<CrossoverPoint> crossoverPoints) {
       if (branch0.SubTrees.Count != branch1.SubTrees.Count) return;
 
       for (int i = 0; i < branch0.SubTrees.Count; i++) {
         // if the current branch can be attached as a sub-tree to branch0
-        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function)) {
+        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function) &&
+           branch1.SubTrees[i].Size - branch0.SubTrees[i].Size <= maxNewNodes) {
           CrossoverPoint p = new CrossoverPoint();
           p.childIndex = i;
@@ -74 +75 @@
           crossoverPoints.Add(p);
         }
-        GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i], crossoverPoints);
+        GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i], maxNewNodes, crossoverPoints);
       }
     }

trunk/sources/HeuristicLab.GP/Recombination/SizeConstrictedGPCrossoverBase.cs

@@ -32 +32 @@
 
 namespace HeuristicLab.GP {
-  public abstract class SizeConstrictedGPCrossoverBase : GPCrossoverBase{
+  public abstract class SizeConstrictedGPCrossoverBase : GPCrossoverBase {
+
+    private int MaxRecombinationTries { get { return 20; } }
+
     public SizeConstrictedGPCrossoverBase()
       : base() {
@@ -45 +48 @@
       // when tree0 is terminal then try to cross into tree1, when tree1 is also terminal just return tree0 unchanged.
       IFunctionTree newTree;
-      if (tree0.SubTrees.Count > 0) {
-        newTree = Cross(gardener, random, tree0, tree1, maxTreeSize, maxTreeHeight);
-      } else if (tree1.SubTrees.Count > 0) {
-        newTree = Cross(gardener, random, tree1, tree0, maxTreeSize, maxTreeHeight);
-      } else newTree = tree0;
-
-      // check if the size and height of the new tree are still within the allowed bounds
-      Debug.Assert(newTree.Height <= maxTreeHeight);
-      Debug.Assert(newTree.Size <= maxTreeSize);
+      int tries = 0;
+      do {
+        if (tree0.SubTrees.Count > 0) {
+          newTree = Cross(gardener, random, (IFunctionTree)tree0.Clone(), (IFunctionTree)tree1.Clone(), maxTreeSize, maxTreeHeight);
+        } else if (tree1.SubTrees.Count > 0) {
+          newTree = Cross(gardener, random, (IFunctionTree)tree1.Clone(), (IFunctionTree)tree0.Clone(), maxTreeSize, maxTreeHeight);
+        } else newTree = tree0;
+        if (tries++ > MaxRecombinationTries)
+          throw new InvalidOperationException("Couldn't recombine parents to create a valid child not larger than " + maxTreeSize + " and not higher than " + maxTreeHeight + ".");
+      } while (newTree.Size > maxTreeSize || newTree.Height > maxTreeHeight);
       return newTree;
     }

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

@@ -39 +39 @@
   /// </summary>
   public class SizeFairCrossOver : SizeConstrictedGPCrossoverBase {
-    private const int MAX_RECOMBINATION_TRIES = 20;
+    private int MaxRecombinationTries { get { return 20; } }
     // private data structure for crossover points
     protected class CrossoverPoint {
@@ -57 +57 @@
         removedBranchIndex = random.Next(parent.SubTrees.Count);
         insertedBranch = GetReplacementBranch(random, gardener, tree0, parent, removedBranchIndex, tree1, maxTreeSize, maxTreeHeight);
-      } while (insertedBranch == null && tries++ < MAX_RECOMBINATION_TRIES);
+      } while (insertedBranch == null && tries++ < MaxRecombinationTries);
 
       if (insertedBranch != null) {
@@ -139 +139 @@
       for (int i = 0; i < root.SubTrees.Count; i++) {
         GetTrail(root.SubTrees[i], branch, trail);
-        if (trail.Count>0) {
+        if (trail.Count > 0) {
           trail.Add(i);
           return;

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

@@ -33 +33 @@
 namespace HeuristicLab.GP {
   public class StandardCrossOver : SizeConstrictedGPCrossoverBase {
-    private const int MAX_RECOMBINATION_TRIES = 20;
+    private int MaxRecombinationTries { get { return 20; } }
 
     public override string Description {
@@ -52 +52 @@
         // select a random crossover point in the first parent tree0
         parent0 = null;
-        while(parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
+        while (parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
         // select a random branch to replace
         replacedChildIndex = random.Next(parent0.SubTrees.Count);
@@ -62 +62 @@
         IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent0.Function, replacedChildIndex);
         allowedCrossoverPoints = GetPossibleCrossoverPoints(gardener, tree1, maxInsertedBranchSize, maxInsertedBranchHeight, allowedFunctions);
-      } while(allowedCrossoverPoints.Count == 0 && tries++ < MAX_RECOMBINATION_TRIES);
+      } while (allowedCrossoverPoints.Count == 0 && tries++ < MaxRecombinationTries);
 
-      if(allowedCrossoverPoints.Count > 0) {
+      if (allowedCrossoverPoints.Count > 0) {
         IFunctionTree branch1 = allowedCrossoverPoints[random.Next(allowedCrossoverPoints.Count)];
 
@@ -76 +76 @@
     private List<IFunctionTree> GetPossibleCrossoverPoints(TreeGardener gardener, IFunctionTree tree, int maxInsertedBranchSize, int maxInsertedBranchHeight, IList<IFunction> allowedFunctions) {
       List<IFunctionTree> crossoverPoints = new List<IFunctionTree>();
-      foreach(IFunctionTree possiblePoint in gardener.GetAllSubTrees(tree)) {
-        if(allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.Size <= maxInsertedBranchSize && possiblePoint.Height <= maxInsertedBranchHeight)
+      foreach (IFunctionTree possiblePoint in gardener.GetAllSubTrees(tree)) {
+        if (allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.Size <= maxInsertedBranchSize && possiblePoint.Height <= maxInsertedBranchHeight)
           crossoverPoints.Add(possiblePoint);
       }

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

@@ -37 +37 @@
   /// In Proceedings of Genetic Programming '98, Madison, Wisconsin, 1998.
   /// </summary>
-  public class UniformCrossover : GPCrossoverBase {
+  public class UniformCrossover : SizeConstrictedGPCrossoverBase {
     // internal datastructure to represent crossover points
     private class CrossoverPoint {
@@ -52 +52 @@
     }
 
-    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
+    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
       List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
       GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);