Free cookie consent management tool by TermsFeed Policy Generator

Changeset 666


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

Legend:

Unmodified
Added
Removed

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

    r656 r666  
    4545      : base() {
    4646      AddVariableInfo(new VariableInfo("Random", "Pseudo random number generator", typeof(MersenneTwister), VariableKind.In));
    47       AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
    48       AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    49       AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    5047      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.New));
    51       AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));
    52       AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));
     48      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.In | VariableKind.New));
     49      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.In | VariableKind.New));
    5350    }
    5451
    5552    public override IOperation Apply(IScope scope) {
    5653      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    57       GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    58       int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    59       int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    60 
    61       TreeGardener gardener = new TreeGardener(random, opLibrary);
    6254
    6355      if((scope.SubScopes.Count % 2) != 0)
    … …  
    7365        scope.RemoveSubScope(parent2);
    7466        IScope child = new Scope(i.ToString());
    75         IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
     67        IOperation childInitOperation = Cross(scope, random, parent1, parent2, child);
    7668        initOperations.AddOperation(childInitOperation);
    7769        scope.AddSubScope(child);
    … …  
    8173    }
    8274
    83     private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
    84       IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
    85       IFunctionTree newTree = Cross(gardener, parent1, parent2,
    86         random, maxTreeSize, maxTreeHeight);
     75    private IOperation Cross(IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
     76      IFunctionTree newTree = Cross(random, parent1, parent2);
    8777
    8878      int newTreeSize = newTree.Size;
    … …  
    9282      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
    9383
    94       // 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)
    95       Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
    9684      return null;
    9785    }
    9886
    9987
    100     private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
     88    private IFunctionTree Cross(MersenneTwister random, IScope f, IScope g) {
    10189      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    10290      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
    … …  
    10795      int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
    10896
    109       if(tree0Size == 1 && tree1Size == 1) {
    110         return CombineTerminals(gardener, tree0, tree1, random);
    111       } else {
    112         // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
    113         // in case both trees are higher than 1 we swap the trees with probability 50%
    114         if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
    115           IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
    116           int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
    117           int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
    118         }
    119 
    120         List<IFunctionTree[]> allowedCrossOverPoints = GetCrossOverPoints(null, tree0, tree1);
    121         if(allowedCrossOverPoints.Count == 0) {
    122           if(random.NextDouble() < 0.5) return tree0; else return tree1;
    123         }
    124         IFunctionTree[] crossOverPoints = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
    125         IFunctionTree parent = crossOverPoints[0];
    126         IFunctionTree replacedBranch = crossOverPoints[1];
    127         IFunctionTree insertedBranch = crossOverPoints[2];
    128         if(parent == null) return insertedBranch;
    129         else {
    130           int i = 0;
    131           while(parent.SubTrees[i] != replacedBranch) i++;
    132           parent.RemoveSubTree(i);
    133           parent.InsertSubTree(i, insertedBranch);
    134           return tree0;
    135         }
     97      List<IFunctionTree[]> allowedCrossOverPoints = GetCrossOverPoints(null, tree0, tree1);
     98      if(allowedCrossOverPoints.Count == 0) {
     99        if(random.NextDouble() < 0.5) return tree0; else return tree1;
     100      }
     101      IFunctionTree[] crossOverPoints = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
     102      IFunctionTree parent = crossOverPoints[0];
     103      IFunctionTree replacedBranch = crossOverPoints[1];
     104      IFunctionTree insertedBranch = crossOverPoints[2];
     105      if(parent == null) return insertedBranch;
     106      else {
     107        int i = 0;
     108        while(parent.SubTrees[i] != replacedBranch) i++;
     109        parent.RemoveSubTree(i);
     110        parent.InsertSubTree(i, insertedBranch);
     111        return tree0;
    136112      }
    137113    }
    … …  
    139115    private List<IFunctionTree[]> GetCrossOverPoints(IFunctionTree parent, IFunctionTree tree0, IFunctionTree tree1) {
    140116      List<IFunctionTree[]> results = new List<IFunctionTree[]>();
    141       if(tree0.Function != tree1.Function) return results;
     117      if(tree0.SubTrees.Count != tree1.SubTrees.Count) return results;
     118      // invariant arity - number of subtrees is equal in both trees
    142119
    143       int maxArity = Math.Min(tree0.SubTrees.Count, tree1.SubTrees.Count);
    144       for(int i = 0; i < maxArity; i++) {
     120      results.Add(new IFunctionTree[] { parent, tree0, tree1 });
     121      for(int i = 0; i < tree0.SubTrees.Count; i++) {
    145122        results.AddRange(GetCrossOverPoints(tree0, tree0.SubTrees[i], tree1.SubTrees[i]));
    146123      }
    147       if(results.Count == 0) results.Add(new IFunctionTree[] { parent, tree0, tree1 });
    148124      return results;
    149     }
    150 
    151     private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random) {
    152       if(random.NextDouble() < 0.5) return f; else return g;
    153125    }
    154126  }
Note: See TracChangeset for help on using the changeset viewer.