Changeset 809

Timestamp:

11/23/08 22:17:28 (16 years ago)

Author:

gkronber

Message:

implemented #387 (Onepoint crossover should generate two children each crossover event)

File:

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

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

@@ -56 +56 @@
       TreeGardener gardener = new TreeGardener(random, opLibrary);
 
-      if((scope.SubScopes.Count % 2) != 0)
+      if ((scope.SubScopes.Count % 2) != 0)
         throw new InvalidOperationException("Number of parents is not even");
 
-      CompositeOperation initOperations = new CompositeOperation();
-
-      int children = scope.SubScopes.Count / 2;
-      for(int i = 0; i < children; i++) {
+      int crossoverEvents = scope.SubScopes.Count / 2;
+      for (int i = 0; i < crossoverEvents; i++) {
         IScope parent1 = scope.SubScopes[0];
         scope.RemoveSubScope(parent1);
         IScope parent2 = scope.SubScopes[0];
         scope.RemoveSubScope(parent2);
-        IScope child = new Scope(i.ToString());
-        IOperation childInitOperation = Cross(scope, random, gardener, parent1, parent2, child);
-        initOperations.AddOperation(childInitOperation);
-        scope.AddSubScope(child);
+        IScope child0 = new Scope((i * 2).ToString());
+        IScope child1 = new Scope((i * 2 + 1).ToString());
+        Cross(scope, random, gardener, parent1, parent2, child0, child1);
+        scope.AddSubScope(child0);
+        scope.AddSubScope(child1);
       }
-
-      return initOperations;
-    }
-
-    private IOperation Cross(IScope scope, MersenneTwister random, TreeGardener gardener, IScope parent1, IScope parent2, IScope child) {
-      IFunctionTree newTree = Cross(random, gardener, parent1, parent2);
-
-      int newTreeSize = newTree.Size;
-      int newTreeHeight = newTree.Height;
-      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
-      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
-      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
-
       return null;
     }
 
+    private void Cross(IScope scope, MersenneTwister random, TreeGardener gardener, IScope parent1, IScope parent2, IScope child0, IScope child1) {
+      IFunctionTree newTree0;
+      IFunctionTree newTree1;
+      Cross(random, gardener, parent1, parent2, out newTree0, out newTree1);
 
-    private IFunctionTree Cross(MersenneTwister random, TreeGardener gardener, IScope f, IScope g) {
+      child0.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree0));
+      child0.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTree0.Size)));
+      child0.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTree0.Height)));
+      child1.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree1));
+      child1.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTree1.Size)));
+      child1.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTree1.Height)));
+    }
+
+
+    private void Cross(MersenneTwister random, TreeGardener gardener, IScope f, IScope g, out IFunctionTree child0, out IFunctionTree child1) {
       IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
       int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
@@ -98 +97 @@
       int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
 
-      List<IFunctionTree[]> allowedCrossOverPoints = GetCrossOverPoints(gardener, null, tree0, tree1);
-      if(allowedCrossOverPoints.Count == 0) {
-        if(random.NextDouble() < 0.5) return tree0; else return tree1;
+      List<CrossoverPoint> allowedCrossOverPoints = GetCrossOverPoints(gardener, tree0, tree1);
+      if (allowedCrossOverPoints.Count > 0) {
+        CrossoverPoint crossOverPoint = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
+        IFunctionTree parent0 = crossOverPoint.parent0;
+        IFunctionTree parent1 = crossOverPoint.parent1;
+        IFunctionTree branch0 = crossOverPoint.parent0.SubTrees[crossOverPoint.childIndex];
+        IFunctionTree branch1 = crossOverPoint.parent1.SubTrees[crossOverPoint.childIndex];
+        parent0.RemoveSubTree(crossOverPoint.childIndex);
+        parent1.RemoveSubTree(crossOverPoint.childIndex);
+        parent0.InsertSubTree(crossOverPoint.childIndex, branch1);
+        parent1.InsertSubTree(crossOverPoint.childIndex, branch0);
       }
-      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;
+
+      if (random.NextDouble() < 0.5) {
+        child0 = tree0;
+        child1 = tree1;
+      } else {
+        child0 = tree1;
+        child1 = tree0;
       }
     }
+    class CrossoverPoint {
+      public IFunctionTree parent0;
+      public IFunctionTree parent1;
+      public int childIndex;
+    }
 
-    private List<IFunctionTree[]> GetCrossOverPoints(TreeGardener gardener, IFunctionTree parent, IFunctionTree tree0, IFunctionTree tree1) {
-      List<IFunctionTree[]> results = new List<IFunctionTree[]>();
-      if(tree0.SubTrees.Count != tree1.SubTrees.Count) return results;
-      // invariant arity - number of subtrees is equal in both trees
-      for(int i = 0; i < tree0.SubTrees.Count; i++) {
-        if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.SubTrees[i].Function)) {
-          results.Add(new IFunctionTree[] { tree0, tree0.SubTrees[i], tree1.SubTrees[i]});
+    private List<CrossoverPoint> GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1) {
+      List<CrossoverPoint> results = new List<CrossoverPoint>();
+      if (branch0.SubTrees.Count != branch1.SubTrees.Count) return results;
+
+      for (int i = 0; i < branch0.SubTrees.Count; i++) {
+        // if the branches fit to the parent
+        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function) &&
+          gardener.GetAllowedSubFunctions(branch1.Function, i).Contains(branch0.SubTrees[i].Function)) {
+          CrossoverPoint p = new CrossoverPoint();
+          p.childIndex = i;
+          p.parent0 = branch0;
+          p.parent1 = branch1;
+          results.Add(p);
         }
-        results.AddRange(GetCrossOverPoints(gardener, tree0, tree0.SubTrees[i], tree1.SubTrees[i]));
+        results.AddRange(GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i]));
       }
       return results;