Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.GP/Recombination/OnePointCrossOver.cs

    r707 r809  
    5656      TreeGardener gardener = new TreeGardener(random, opLibrary);
    5757
    58       if((scope.SubScopes.Count % 2) != 0)
     58      if ((scope.SubScopes.Count % 2) != 0)
    5959        throw new InvalidOperationException("Number of parents is not even");
    6060
    61       CompositeOperation initOperations = new CompositeOperation();
    62 
    63       int children = scope.SubScopes.Count / 2;
    64       for(int i = 0; i < children; i++) {
     61      int crossoverEvents = scope.SubScopes.Count / 2;
     62      for (int i = 0; i < crossoverEvents; i++) {
    6563        IScope parent1 = scope.SubScopes[0];
    6664        scope.RemoveSubScope(parent1);
    6765        IScope parent2 = scope.SubScopes[0];
    6866        scope.RemoveSubScope(parent2);
    69         IScope child = new Scope(i.ToString());
    70         IOperation childInitOperation = Cross(scope, random, gardener, parent1, parent2, child);
    71         initOperations.AddOperation(childInitOperation);
    72         scope.AddSubScope(child);
     67        IScope child0 = new Scope((i * 2).ToString());
     68        IScope child1 = new Scope((i * 2 + 1).ToString());
     69        Cross(scope, random, gardener, parent1, parent2, child0, child1);
     70        scope.AddSubScope(child0);
     71        scope.AddSubScope(child1);
    7372      }
    74 
    75       return initOperations;
    76     }
    77 
    78     private IOperation Cross(IScope scope, MersenneTwister random, TreeGardener gardener, IScope parent1, IScope parent2, IScope child) {
    79       IFunctionTree newTree = Cross(random, gardener, parent1, parent2);
    80 
    81       int newTreeSize = newTree.Size;
    82       int newTreeHeight = newTree.Height;
    83       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
    84       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
    85       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
    86 
    8773      return null;
    8874    }
    8975
     76    private void Cross(IScope scope, MersenneTwister random, TreeGardener gardener, IScope parent1, IScope parent2, IScope child0, IScope child1) {
     77      IFunctionTree newTree0;
     78      IFunctionTree newTree1;
     79      Cross(random, gardener, parent1, parent2, out newTree0, out newTree1);
    9080
    91     private IFunctionTree Cross(MersenneTwister random, TreeGardener gardener, IScope f, IScope g) {
     81      child0.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree0));
     82      child0.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTree0.Size)));
     83      child0.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTree0.Height)));
     84      child1.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree1));
     85      child1.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTree1.Size)));
     86      child1.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTree1.Height)));
     87    }
     88
     89
     90    private void Cross(MersenneTwister random, TreeGardener gardener, IScope f, IScope g, out IFunctionTree child0, out IFunctionTree child1) {
    9291      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    9392      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
     
    9897      int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
    9998
    100       List<IFunctionTree[]> allowedCrossOverPoints = GetCrossOverPoints(gardener, null, tree0, tree1);
    101       if(allowedCrossOverPoints.Count == 0) {
    102         if(random.NextDouble() < 0.5) return tree0; else return tree1;
     99      List<CrossoverPoint> allowedCrossOverPoints = GetCrossOverPoints(gardener, tree0, tree1);
     100      if (allowedCrossOverPoints.Count > 0) {
     101        CrossoverPoint crossOverPoint = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
     102        IFunctionTree parent0 = crossOverPoint.parent0;
     103        IFunctionTree parent1 = crossOverPoint.parent1;
     104        IFunctionTree branch0 = crossOverPoint.parent0.SubTrees[crossOverPoint.childIndex];
     105        IFunctionTree branch1 = crossOverPoint.parent1.SubTrees[crossOverPoint.childIndex];
     106        parent0.RemoveSubTree(crossOverPoint.childIndex);
     107        parent1.RemoveSubTree(crossOverPoint.childIndex);
     108        parent0.InsertSubTree(crossOverPoint.childIndex, branch1);
     109        parent1.InsertSubTree(crossOverPoint.childIndex, branch0);
    103110      }
    104       IFunctionTree[] crossOverPoints = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
    105       IFunctionTree parent = crossOverPoints[0];
    106       IFunctionTree replacedBranch = crossOverPoints[1];
    107       IFunctionTree insertedBranch = crossOverPoints[2];
    108       if(parent == null) return insertedBranch;
    109       else {
    110         int i = 0;
    111         while(parent.SubTrees[i] != replacedBranch) i++;
    112         parent.RemoveSubTree(i);
    113         parent.InsertSubTree(i, insertedBranch);
    114         return tree0;
     111
     112      if (random.NextDouble() < 0.5) {
     113        child0 = tree0;
     114        child1 = tree1;
     115      } else {
     116        child0 = tree1;
     117        child1 = tree0;
    115118      }
    116119    }
     120    class CrossoverPoint {
     121      public IFunctionTree parent0;
     122      public IFunctionTree parent1;
     123      public int childIndex;
     124    }
    117125
    118     private List<IFunctionTree[]> GetCrossOverPoints(TreeGardener gardener, IFunctionTree parent, IFunctionTree tree0, IFunctionTree tree1) {
    119       List<IFunctionTree[]> results = new List<IFunctionTree[]>();
    120       if(tree0.SubTrees.Count != tree1.SubTrees.Count) return results;
    121       // invariant arity - number of subtrees is equal in both trees
    122       for(int i = 0; i < tree0.SubTrees.Count; i++) {
    123         if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.SubTrees[i].Function)) {
    124           results.Add(new IFunctionTree[] { tree0, tree0.SubTrees[i], tree1.SubTrees[i]});
     126    private List<CrossoverPoint> GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1) {
     127      List<CrossoverPoint> results = new List<CrossoverPoint>();
     128      if (branch0.SubTrees.Count != branch1.SubTrees.Count) return results;
     129
     130      for (int i = 0; i < branch0.SubTrees.Count; i++) {
     131        // if the branches fit to the parent
     132        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function) &&
     133          gardener.GetAllowedSubFunctions(branch1.Function, i).Contains(branch0.SubTrees[i].Function)) {
     134          CrossoverPoint p = new CrossoverPoint();
     135          p.childIndex = i;
     136          p.parent0 = branch0;
     137          p.parent1 = branch1;
     138          results.Add(p);
    125139        }
    126         results.AddRange(GetCrossOverPoints(gardener, tree0, tree0.SubTrees[i], tree1.SubTrees[i]));
     140        results.AddRange(GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i]));
    127141      }
    128142      return results;
Note: See TracChangeset for help on using the changeset viewer.