Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/26/08 18:57:58 (15 years ago)
Author:
gkronber
Message:

improved sizefair crossover operator. #393 (Refactor GP crossover operators to extract common code into the abstract base class GPCrossoverBase)

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r814 r833  
    3838  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95-119, April 2000
    3939  /// </summary>
    40   public class SizeFairCrossOver : OperatorBase {
     40  public class SizeFairCrossOver : GPCrossoverBase {
    4141    private const int MAX_RECOMBINATION_TRIES = 20;
    4242    public override string Description {
    … …  
    4747    public SizeFairCrossOver()
    4848      : base() {
    49       AddVariableInfo(new VariableInfo("Random", "Pseudo random number generator", typeof(MersenneTwister), VariableKind.In));
    50       AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
    5149      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    5250      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    53       AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.New));
    54       AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));
    55       AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));
    5651    }
    5752
    58     public override IOperation Apply(IScope scope) {
    59       MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    60       GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
     53    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
    6154      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    6255      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    6356
    64       TreeGardener gardener = new TreeGardener(random, opLibrary);
     57      // when tree0 is terminal then try to cross into tree1, when tree1 is also terminal just return tree0 unchanged.
     58      IFunctionTree newTree;
     59      if(tree0.SubTrees.Count > 0) {
     60        newTree = Cross(gardener, tree0, tree1, random, maxTreeSize, maxTreeHeight);
     61      } else if(tree1.SubTrees.Count > 0) {
     62        newTree = Cross(gardener, tree1, tree0, random, maxTreeSize, maxTreeHeight);
     63      } else newTree = tree0;
    6564
    66       if ((scope.SubScopes.Count % 2) != 0)
    67         throw new InvalidOperationException("Number of parents is not even");
    68 
    69       int children = scope.SubScopes.Count / 2;
    70       for (int i = 0; i < children; i++) {
    71         IScope parent1 = scope.SubScopes[0];
    72         scope.RemoveSubScope(parent1);
    73         IScope parent2 = scope.SubScopes[0];
    74         scope.RemoveSubScope(parent2);
    75         IScope child = new Scope(i.ToString());
    76         Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
    77         scope.AddSubScope(child);
    78       }
    79 
    80       return null;
     65      // check if the height and size of the new tree are still in the allowed bounds
     66      Debug.Assert(newTree.Height <= maxTreeHeight);
     67      Debug.Assert(newTree.Size <= maxTreeSize);
     68      return newTree;
    8169    }
    8270
    83     private void 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);
     71    private IFunctionTree Cross(TreeGardener gardener, IFunctionTree tree0, IFunctionTree tree1, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
     72      int tries = 0;
     73      IFunctionTree insertedBranch = null;
     74      IFunctionTree crossoverPoint = null;
     75      int removedBranchIndex = 0;
     76      do {
     77        // select a random suboperator of the 'receiving' tree
     78        while(crossoverPoint == null) crossoverPoint = gardener.GetRandomParentNode(tree0);
     79        removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
     80        IFunctionTree removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
     81        IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
     82        int removedBranchSize = removedBranch.Size;
     83        int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
     84        int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, crossoverPoint);
     85        insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
     86      } while(insertedBranch == null && tries++ < MAX_RECOMBINATION_TRIES);
    8787
    88       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
    89       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTree.Size)));
    90       child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTree.Height)));
    91 
    92       // check if the new tree is valid and the height and size are still in the allowed bounds
    93       Debug.Assert(gardener.IsValidTree(newTree) && newTree.Height <= maxTreeHeight && newTree.Size <= maxTreeSize);
    94     }
    95 
    96 
    97     private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
    98       IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    99       int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
    100       int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
    101 
    102       IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
    103       int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;
    104       int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
    105 
    106       // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
    107       // in case both trees are higher than 1 we swap the trees with probability 50%
    108       if (tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
    109         IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
    110         int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
    111         int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
    112       }
    113 
    114       // select a random suboperator of the 'receiving' tree
    115       IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
    116       int removedBranchIndex;
    117       IFunctionTree removedBranch;
    118       IList<IFunction> allowedFunctions;
    119       if (crossoverPoint == null) {
    120         removedBranchIndex = 0;
    121         removedBranch = tree0;
    122         allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    123       } else {
    124         removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
    125         removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
    126         allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    127       }
    128       int removedBranchSize = removedBranch.Size;
    129       int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
    130       int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
    131       IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
    132 
    133       int tries = 0;
    134       while (insertedBranch == null) {
    135         if (tries++ > MAX_RECOMBINATION_TRIES) {
    136           if (random.Next() > 0.5) return tree1;
    137           else return tree0;
    138         }
    139 
    140         // retry with a different crossoverPoint       
    141         crossoverPoint = gardener.GetRandomParentNode(tree0);
    142         if (crossoverPoint == null) {
    143           removedBranchIndex = 0;
    144           removedBranch = tree0;
    145           allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    146         } else {
    147           removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
    148           removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
    149           allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    150         }
    151         removedBranchSize = removedBranch.Size;
    152         maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
    153         maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
    154         insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
    155       }
    156       if (crossoverPoint != null) {
     88      if(insertedBranch != null) {
    15789        // replace the branch below the crossoverpoint with the selected branch from root1
    15890        crossoverPoint.RemoveSubTree(removedBranchIndex);
    15991        crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
    160         return tree0;
    161       } else {
    162         return insertedBranch;
    16392      }
     93      return tree0;
    16494    }
    16595
    16696    private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
    167       var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)
     97      var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size <= maxBranchSize && t.Height <= maxBranchHeight)
    16898        .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);
    16999
    … …  
    172102      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
    173103
    174       if (shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
    175         if (equalLengthBranches.Count() == 0) {
     104      if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
     105        if(equalLengthBranches.Count() == 0) {
    176106          return null;
    177107        } else {
    … …  
    185115
    186116        double r = random.NextDouble();
    187         if (r < pLonger) {
     117        if(r < pLonger) {
    188118          return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
    189         } else if (r < pLonger + pShorter) {
     119        } else if(r < pLonger + pShorter) {
    190120          return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
    191121        } else {
Note: See TracChangeset for help on using the changeset viewer.