Changeset 666 for trunk/sources/HeuristicLab.GP/Recombination

Timestamp:

10/15/08 00:48:18 (16 years ago)

Author:

gkronber

Message:

fixed #305 (Implementation of GP onepoint crossover doesn't match description as given in FoGP)

File:

• trunk/sources/HeuristicLab.GP/Recombination/OnePointCrossOver.cs (modified) (6 diffs)

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

@@ -45 +45 @@
       : base() {
       AddVariableInfo(new VariableInfo("Random", "Pseudo random number generator", typeof(MersenneTwister), VariableKind.In));
-      AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
-      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
-      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
       AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.New));
-      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));
-      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));
+      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.New));
+      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.New));
     }
 
     public override IOperation Apply(IScope scope) {
       MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
-      GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
-      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
-      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
-
-      TreeGardener gardener = new TreeGardener(random, opLibrary);
 
       if((scope.SubScopes.Count % 2) != 0)
@@ -73 +65 @@
         scope.RemoveSubScope(parent2);
         IScope child = new Scope(i.ToString());
-        IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
+        IOperation childInitOperation = Cross(scope, random, parent1, parent2, child);
         initOperations.AddOperation(childInitOperation);
         scope.AddSubScope(child);
@@ -81 +73 @@
     }
 
-    private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
-      IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
-      IFunctionTree newTree = Cross(gardener, parent1, parent2,
-        random, maxTreeSize, maxTreeHeight);
+    private IOperation Cross(IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
+      IFunctionTree newTree = Cross(random, parent1, parent2);
 
       int newTreeSize = newTree.Size;
@@ -92 +82 @@
       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
 
-      // 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)
-      Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
       return null;
     }
 
 
-    private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
+    private IFunctionTree Cross(MersenneTwister random, IScope f, IScope g) {
       IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
       int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
@@ -107 +95 @@
       int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
 
-      if(tree0Size == 1 && tree1Size == 1) {
-        return CombineTerminals(gardener, tree0, tree1, random);
-      } else {
-        // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
-        // in case both trees are higher than 1 we swap the trees with probability 50%
-        if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
-          IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
-          int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
-          int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
-        }
-
-        List<IFunctionTree[]> allowedCrossOverPoints = GetCrossOverPoints(null, tree0, tree1);
-        if(allowedCrossOverPoints.Count == 0) {
-          if(random.NextDouble() < 0.5) return tree0; else return tree1;
-        }
-        IFunctionTree[] crossOverPoints = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
-        IFunctionTree parent = crossOverPoints[0];
-        IFunctionTree replacedBranch = crossOverPoints[1];
-        IFunctionTree insertedBranch = crossOverPoints[2];
-        if(parent == null) return insertedBranch;
-        else {
-          int i = 0;
-          while(parent.SubTrees[i] != replacedBranch) i++;
-          parent.RemoveSubTree(i);
-          parent.InsertSubTree(i, insertedBranch);
-          return tree0;
-        }
+      List<IFunctionTree[]> allowedCrossOverPoints = GetCrossOverPoints(null, tree0, tree1);
+      if(allowedCrossOverPoints.Count == 0) {
+        if(random.NextDouble() < 0.5) return tree0; else return tree1;
+      }
+      IFunctionTree[] crossOverPoints = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
+      IFunctionTree parent = crossOverPoints[0];
+      IFunctionTree replacedBranch = crossOverPoints[1];
+      IFunctionTree insertedBranch = crossOverPoints[2];
+      if(parent == null) return insertedBranch;
+      else {
+        int i = 0;
+        while(parent.SubTrees[i] != replacedBranch) i++;
+        parent.RemoveSubTree(i);
+        parent.InsertSubTree(i, insertedBranch);
+        return tree0;
       }
     }
@@ -139 +115 @@
     private List<IFunctionTree[]> GetCrossOverPoints(IFunctionTree parent, IFunctionTree tree0, IFunctionTree tree1) {
       List<IFunctionTree[]> results = new List<IFunctionTree[]>();
-      if(tree0.Function != tree1.Function) return results;
+      if(tree0.SubTrees.Count != tree1.SubTrees.Count) return results;
+      // invariant arity - number of subtrees is equal in both trees
 
-      int maxArity = Math.Min(tree0.SubTrees.Count, tree1.SubTrees.Count);
-      for(int i = 0; i < maxArity; i++) {
+      results.Add(new IFunctionTree[] { parent, tree0, tree1 });
+      for(int i = 0; i < tree0.SubTrees.Count; i++) {
         results.AddRange(GetCrossOverPoints(tree0, tree0.SubTrees[i], tree1.SubTrees[i]));
       }
-      if(results.Count == 0) results.Add(new IFunctionTree[] { parent, tree0, tree1 });
       return results;
-    }
-
-    private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random) {
-      if(random.NextDouble() < 0.5) return f; else return g;
     }
   }