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/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  }
Note: See TracChangeset for help on using the changeset viewer.