Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/26/08 23:41:56 (16 years ago)
Author:
gkronber
Message:
  • added another abstract base class for GP crossover operators with maxsize and maxheight constraints
  • changed StandardCrossOver to inherit from SizeConstrictedGPCrossoverBase
  • changed SizeFairCrossOver to inherit from SizeConstrictedGPCrossoverBase
  • generally improved code of SizeFairCrossOver
  • changed LangdonHomologousCrossOver to inherit from SizeFairCrossOver and implemented only the method to finally select branches.

#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

    r833 r835  
    3838  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95-119, April 2000
    3939  /// </summary>
    40   public class SizeFairCrossOver : GPCrossoverBase {
     40  public class SizeFairCrossOver : SizeConstrictedGPCrossoverBase {
    4141    private const int MAX_RECOMBINATION_TRIES = 20;
    42     public override string Description {
    43       get {
    44         return @"";
    45       }
    46     }
    47     public SizeFairCrossOver()
    48       : base() {
    49       AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    50       AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
     42    // private data structure for crossover points
     43    protected class CrossoverPoint {
     44      public IFunctionTree tree;
     45      public int branchSize;
     46      public List<int> trail;
    5147    }
    5248
    53     internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
    54       int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    55       int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    56 
    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;
    64 
    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;
    69     }
    70 
    71     private IFunctionTree Cross(TreeGardener gardener, IFunctionTree tree0, IFunctionTree tree1, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
     49    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
    7250      int tries = 0;
    7351      IFunctionTree insertedBranch = null;
    74       IFunctionTree crossoverPoint = null;
     52      IFunctionTree parent = null;
    7553      int removedBranchIndex = 0;
    7654      do {
    7755        // 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);
     56        while (parent == null) parent = gardener.GetRandomParentNode(tree0);
     57        removedBranchIndex = random.Next(parent.SubTrees.Count);
     58        insertedBranch = GetReplacementBranch(random, gardener, tree0, parent, removedBranchIndex, tree1, maxTreeSize, maxTreeHeight);
     59      } while (insertedBranch == null && tries++ < MAX_RECOMBINATION_TRIES);
    8760
    88       if(insertedBranch != null) {
     61      if (insertedBranch != null) {
    8962        // replace the branch below the crossoverpoint with the selected branch from root1
    90         crossoverPoint.RemoveSubTree(removedBranchIndex);
    91         crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
     63        parent.RemoveSubTree(removedBranchIndex);
     64        parent.InsertSubTree(removedBranchIndex, insertedBranch);
    9265      }
    9366      return tree0;
    9467    }
    9568
    96     private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
    97       var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size <= maxBranchSize && t.Height <= maxBranchHeight)
    98         .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);
     69    private IFunctionTree GetReplacementBranch(MersenneTwister random, TreeGardener gardener, IFunctionTree intoTree, IFunctionTree parent, int replacedBranchIndex, IFunctionTree fromTree, int maxTreeSize, int maxTreeHeight) {
     70      IList<IFunction> allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, replacedBranchIndex);
     71      int removedBranchSize = parent.SubTrees[replacedBranchIndex].Size;
     72      int maxBranchSize = maxTreeSize - (intoTree.Size - removedBranchSize);
     73      int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(intoTree, parent);  // returns 1 if intoTree==parent and 2 if parent is a child of intoTree
     74      List<int> replacedTrail = GetTrail(intoTree, parent);
     75      replacedTrail.Add(replacedBranchIndex);
    9976
    100       var shorterBranches = branches.Where(t => t.Size < removedBranchSize);
    101       var longerBranches = branches.Where(t => t.Size > removedBranchSize);
    102       var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
     77      List<CrossoverPoint> shorterBranches = new List<CrossoverPoint>();
     78      List<CrossoverPoint> longerBranches = new List<CrossoverPoint>();
     79      List<CrossoverPoint> equalLengthBranches = new List<CrossoverPoint>();
    10380
    104       if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
    105         if(equalLengthBranches.Count() == 0) {
    106           return null;
    107         } else {
    108           return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
    109         }
    110       } else {
    111         // invariant: |shorterBranches| > 0  and |longerBranches| > 0
    112         double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;
    113         double pLonger = (1.0 - pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));
     81      FindPossibleBranches(fromTree, allowedFunctions, maxBranchSize, maxBranchHeight, removedBranchSize, shorterBranches, equalLengthBranches, longerBranches, new List<int>());
     82
     83      if (shorterBranches.Count > 0 && longerBranches.Count > 0) {
     84        double pEqualLength = equalLengthBranches.Count > 0 ? 1.0 / removedBranchSize : 0.0;
     85        double pLonger = (1.0 - pEqualLength) / (longerBranches.Count * (1.0 + longerBranches.Average(p => p.branchSize) / shorterBranches.Average(p => p.branchSize)));
    11486        double pShorter = (1.0 - pEqualLength - pLonger);
    11587
    11688        double r = random.NextDouble();
    117         if(r < pLonger) {
    118           return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
    119         } else if(r < pLonger + pShorter) {
    120           return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
     89        if (r < pLonger) {
     90          return SelectReplacement(random, replacedTrail, longerBranches);
     91        } else if (r < pLonger + pShorter) {
     92          return SelectReplacement(random, replacedTrail, shorterBranches);
    12193        } else {
    122           return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
     94          return SelectReplacement(random, replacedTrail, equalLengthBranches);
     95        }
     96      } else if (equalLengthBranches.Count > 0) {
     97        return SelectReplacement(random, replacedTrail, equalLengthBranches);
     98      } else {
     99        return null;
     100      }
     101    }
     102
     103    protected virtual IFunctionTree SelectReplacement(MersenneTwister random, List<int> replacedTrail, List<CrossoverPoint> crossoverPoints) {
     104      return crossoverPoints[random.Next(crossoverPoints.Count)].tree;
     105    }
     106
     107    private void FindPossibleBranches(IFunctionTree tree, IList<IFunction> allowedFunctions, int maxBranchSize, int maxBranchHeight, int removedBranchSize,
     108      List<CrossoverPoint> shorterBranches, List<CrossoverPoint> equalLengthBranches, List<CrossoverPoint> longerBranches, List<int> trail) {
     109      int treeSize = tree.Size;
     110      if (allowedFunctions.Contains(tree.Function) && treeSize <= maxBranchSize && tree.Height <= maxBranchHeight) {
     111        CrossoverPoint p = new CrossoverPoint();
     112        p.branchSize = treeSize;
     113        p.tree = tree;
     114        p.trail = new List<int>(trail);
     115        if (treeSize < removedBranchSize) shorterBranches.Add(p);
     116        else if (treeSize > removedBranchSize) longerBranches.Add(p);
     117        else equalLengthBranches.Add(p);
     118      }
     119      for (int i = 0; i < tree.SubTrees.Count; i++) {
     120        trail.Add(i);
     121        FindPossibleBranches(tree.SubTrees[i], allowedFunctions, maxBranchSize, maxBranchHeight, removedBranchSize, shorterBranches, equalLengthBranches, longerBranches, trail);
     122        trail.RemoveAt(trail.Count - 1);
     123      }
     124    }
     125
     126    private List<int> GetTrail(IFunctionTree root, IFunctionTree branch) {
     127      List<int> trail = new List<int>();
     128      GetTrail(root, branch, trail);
     129      trail.Reverse();
     130      trail.RemoveAt(trail.Count - 1);
     131      return trail;
     132    }
     133    private void GetTrail(IFunctionTree root, IFunctionTree branch, List<int> trail) {
     134      if (root == branch) {
     135        trail.Add(-1); // add flag that there was a match
     136        return;
     137      }
     138
     139      for (int i = 0; i < root.SubTrees.Count; i++) {
     140        GetTrail(root.SubTrees[i], branch, trail);
     141        if (trail.Count>0) {
     142          trail.Add(i);
     143          return;
    123144        }
    124145      }
Note: See TracChangeset for help on using the changeset viewer.