Free cookie consent management tool by TermsFeed Policy Generator

Changeset 835


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)

Location:
trunk/sources/HeuristicLab.GP
Files:
1 added
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.GP/HeuristicLab.GP.csproj

    r815 r835  
    7171    <Compile Include="Logging\TreeArityAnalyser.cs" />
    7272    <Compile Include="OffspringEqualiser.cs" />
     73    <Compile Include="Recombination\SizeConstrictedGPCrossoverBase.cs" />
    7374    <Compile Include="Recombination\GPCrossoverBase.cs" />
    7475    <Compile Include="Recombination\UniformCrossover.cs" />

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

    r832 r835  
    3333namespace HeuristicLab.GP {
    3434  public abstract class GPCrossoverBase : OperatorBase {
    35     private const int MAX_RECOMBINATION_TRIES = 100;
    36 
    3735    public GPCrossoverBase()
    3836      : base() {

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

    r814 r835  
    3838  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95-119, April 2000
    3939  /// </summary>
    40   public class LangdonHomologousCrossOver : OperatorBase {
    41     private const int MAX_RECOMBINATION_TRIES = 20;
    42     public override string Description {
    43       get {
    44         return @"";
    45       }
    46     }
    47     public LangdonHomologousCrossOver()
    48       : 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));
    51       AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    52       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));
    56     }
    57 
    58     public override IOperation Apply(IScope scope) {
    59       MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
    60       GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
    61       int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    62       int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    63 
    64       TreeGardener gardener = new TreeGardener(random, opLibrary);
    65 
    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;
    81     }
    82 
    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);
    87 
    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 if the size and height are still in the allowed bounds
    93       Debug.Assert(gardener.IsValidTree(newTree) && newTree.Height <= maxTreeHeight && newTree.Size <= maxTreeSize);
    94     }
    95 
    96     private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
    97       IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
    98       int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
    99       int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
    100 
    101       IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
    102       int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;
    103       int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
    104 
    105       // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
    106       // in case both trees are higher than 1 we swap the trees with probability 50%
    107       if (tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
    108         IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
    109         int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
    110         int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
    111       }
    112 
    113       // select a random suboperator of the 'receiving' tree
    114       IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
    115       int removedBranchIndex;
    116       IFunctionTree removedBranch;
    117       IList<IFunction> allowedFunctions;
    118       if (crossoverPoint == null) {
    119         removedBranchIndex = 0;
    120         removedBranch = tree0;
    121         allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
    122       } else {
    123         removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
    124         removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
    125         allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    126       }
    127       int removedBranchSize = removedBranch.Size;
    128       int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
    129       int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
    130       List<int> removedBranchThread = GetThread(removedBranch, tree0);
    131       IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchThread, 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         removedBranchThread = GetThread(removedBranch, tree0);
    155         insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchThread, removedBranchSize, maxBranchSize, maxBranchHeight);
    156       }
    157       if (crossoverPoint != null) {
    158         // replace the branch below the crossoverpoint with the selected branch from root1
    159         crossoverPoint.RemoveSubTree(removedBranchIndex);
    160         crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
    161         return tree0;
    162       } else {
    163         return insertedBranch;
    164       }
    165     }
    166 
    167     private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, List<int> removedBranchThread, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
    168       var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)
    169         .Select(t => new { Tree = t, Size = t.Size, Thread = GetThread(t, tree) }).Where(s => s.Size < 2 * removedBranchSize + 1);
    170 
    171       var shorterBranches = branches.Where(t => t.Size < removedBranchSize);
    172       var longerBranches = branches.Where(t => t.Size > removedBranchSize);
    173       var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
    174 
    175       if (shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
    176         if (equalLengthBranches.Count() == 0) {
    177           return null;
    178         } else {
    179           return equalLengthBranches.OrderBy(t => MatchingSteps(removedBranchThread, t.Thread)).Last().Tree;
    180         }
    181       } else {
    182         // invariant: |shorterBranches| > 0  and |longerBranches| > 0
    183         double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;
    184         double pLonger = (1.0 - pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));
    185         double pShorter = (1.0 - pEqualLength - pLonger);
    186 
    187         double r = random.NextDouble();
    188         if (r < pLonger) {
    189           return longerBranches.OrderBy(t => MatchingSteps(removedBranchThread, t.Thread)).Last().Tree;
    190         } else if (r < pLonger + pShorter) {
    191           return shorterBranches.OrderBy(t => MatchingSteps(removedBranchThread, t.Thread)).Last().Tree;
    192         } else {
    193           return equalLengthBranches.OrderBy(t => MatchingSteps(removedBranchThread, t.Thread)).Last().Tree;
     40  public class LangdonHomologousCrossOver : SizeFairCrossOver {
     41    protected override IFunctionTree SelectReplacement(MersenneTwister random, List<int> replacedTrail, List<CrossoverPoint> crossoverPoints) {
     42      List<CrossoverPoint> bestPoints = new List<CrossoverPoint> { crossoverPoints[0] };
     43      int bestMatchLength = MatchingSteps(replacedTrail, crossoverPoints[0].trail);
     44      for (int i = 1; i < crossoverPoints.Count; i++) {
     45        int currentMatchLength = MatchingSteps(replacedTrail, crossoverPoints[i].trail);
     46        if (currentMatchLength > bestMatchLength) {
     47          bestMatchLength = currentMatchLength;
     48          bestPoints.Clear();
     49          bestPoints.Add(crossoverPoints[i]);
     50        } else if (currentMatchLength == bestMatchLength) {
     51          bestPoints.Add(crossoverPoints[i]);
    19452        }
    19553      }
     54      return bestPoints[random.Next(bestPoints.Count)].tree;
    19655    }
    197 
    198     private int MatchingSteps(List<int> removedBranchThread, List<int> list) {
    199       int n = Math.Min(removedBranchThread.Count, list.Count);
    200       for (int i = 0; i < n; i++) if (removedBranchThread[i] != list[i]) return i;
     56    private int MatchingSteps(List<int> t1, List<int> t2) {
     57      int n = Math.Min(t1.Count, t2.Count);
     58      for (int i = 0; i < n; i++) if (t1[i] != t2[i]) return i;
    20159      return n;
    202     }
    203 
    204     private List<int> GetThread(IFunctionTree t, IFunctionTree tree) {
    205       List<int> thread = new List<int>();
    206       for (int i = 0; i < tree.SubTrees.Count; i++) {
    207         if (t == tree.SubTrees[i]) {
    208           thread.Add(i);
    209           return thread;
    210         } else {
    211           thread.AddRange(GetThread(t, tree.SubTrees[i]));
    212           if (thread.Count > 0) {
    213             thread.Insert(0, i);
    214             return thread;
    215           }
    216         }
    217       }
    218       return thread;
    21960    }
    22061  }

  • 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      }

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

    r833 r835  
    3232
    3333namespace HeuristicLab.GP {
    34   public class StandardCrossOver : GPCrossoverBase {
    35     private const int MAX_RECOMBINATION_TRIES = 100;
     34  public class StandardCrossOver : SizeConstrictedGPCrossoverBase {
     35    private const int MAX_RECOMBINATION_TRIES = 20;
    3636
    3737    public override string Description {
    … …  
    4343      }
    4444    }
    45     public StandardCrossOver()
    46       : base() {
    47       AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
    48       AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
    49     }
    5045
    51     internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
    52       int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
    53       int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
    54 
    55       // when tree0 is terminal then try to cross into tree1, when tree1 is also terminal just return tree0 unchanged.
    56       IFunctionTree newTree;
    57       if(tree0.SubTrees.Count > 0) {
    58         newTree = Cross(gardener, tree0, tree1, random, maxTreeSize, maxTreeHeight);
    59       } else if(tree1.SubTrees.Count > 0) {
    60         newTree = Cross(gardener, tree1, tree0, random, maxTreeSize, maxTreeHeight);
    61       } else newTree = tree0;
    62 
    63       // check if the size and height of the new tree are still within the allowed bounds
    64       Debug.Assert(newTree.Height <= maxTreeHeight);
    65       Debug.Assert(newTree.Size <= maxTreeSize);
    66       return newTree;
    67     }
    68 
    69 
    70     private IFunctionTree Cross(TreeGardener gardener, IFunctionTree tree0, IFunctionTree tree1, MersenneTwister random, int maxTreeSize, int maxTreeHeight) {
     46    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
    7147      int tries = 0;
    7248      List<IFunctionTree> allowedCrossoverPoints = null;
Note: See TracChangeset for help on using the changeset viewer.