source: trunk/sources/HeuristicLab.GP/Recombination/SizeFairCrossOver.cs @ 835

Last change on this file since 835 was 835, checked in by gkronber, 13 years ago
  • 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 size: 6.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Core;
27using HeuristicLab.Operators;
28using HeuristicLab.Random;
29using HeuristicLab.Data;
30using HeuristicLab.Constraints;
31using System.Diagnostics;
32
33namespace HeuristicLab.GP {
34  /// <summary>
35  /// Implementation of a size fair crossover operator as described in:
36  /// William B. Langdon
37  /// Size Fair and Homologous Tree Genetic Programming Crossovers,
38  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95-119, April 2000
39  /// </summary>
40  public class SizeFairCrossOver : SizeConstrictedGPCrossoverBase {
41    private const int MAX_RECOMBINATION_TRIES = 20;
42    // private data structure for crossover points
43    protected class CrossoverPoint {
44      public IFunctionTree tree;
45      public int branchSize;
46      public List<int> trail;
47    }
48
49    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
50      int tries = 0;
51      IFunctionTree insertedBranch = null;
52      IFunctionTree parent = null;
53      int removedBranchIndex = 0;
54      do {
55        // select a random suboperator of the 'receiving' tree
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);
60
61      if (insertedBranch != null) {
62        // replace the branch below the crossoverpoint with the selected branch from root1
63        parent.RemoveSubTree(removedBranchIndex);
64        parent.InsertSubTree(removedBranchIndex, insertedBranch);
65      }
66      return tree0;
67    }
68
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);
76
77      List<CrossoverPoint> shorterBranches = new List<CrossoverPoint>();
78      List<CrossoverPoint> longerBranches = new List<CrossoverPoint>();
79      List<CrossoverPoint> equalLengthBranches = new List<CrossoverPoint>();
80
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)));
86        double pShorter = (1.0 - pEqualLength - pLonger);
87
88        double r = random.NextDouble();
89        if (r < pLonger) {
90          return SelectReplacement(random, replacedTrail, longerBranches);
91        } else if (r < pLonger + pShorter) {
92          return SelectReplacement(random, replacedTrail, shorterBranches);
93        } else {
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;
144        }
145      }
146    }
147  }
148}
Note: See TracBrowser for help on using the repository browser.