Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GpPluginsRefactoringBranch/HeuristicLab.GP/Recombination/SizeFairCrossOver.cs @ 645

Last change on this file since 645 was 645, checked in by gkronber, 15 years ago

moved all classes of HL.Functions and HL.StructureIdentification to new plugins HeuristicLab.GP... (#177)

File size: 13.7 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 : OperatorBase {
41    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("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      CompositeOperation initOperations = new CompositeOperation();
70
71      int children = scope.SubScopes.Count / 2;
72      for(int i = 0; i < children; i++) {
73        IScope parent1 = scope.SubScopes[0];
74        scope.RemoveSubScope(parent1);
75        IScope parent2 = scope.SubScopes[0];
76        scope.RemoveSubScope(parent2);
77        IScope child = new Scope(i.ToString());
78        IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
79        initOperations.AddOperation(childInitOperation);
80        scope.AddSubScope(child);
81      }
82
83      return initOperations;
84    }
85
86    private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
87      IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
88      List<IFunctionTree> newBranches;
89      IFunctionTree newTree = Cross(gardener, parent1, parent2,
90        random, maxTreeSize, maxTreeHeight, out newBranches);
91
92
93      int newTreeSize = newTree.Size;
94      int newTreeHeight = newTree.Height;
95      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
96      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
97      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
98
99      // check if the new tree is valid and if the height of is still in the allowed bounds (we are not so strict for the max-size)
100      Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
101      return gardener.CreateInitializationOperation(newBranches, child);
102    }
103
104
105    private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {
106      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
107      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
108      int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
109
110      IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
111      int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;
112      int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
113
114      if(tree0Size == 1 && tree1Size == 1) {
115        return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
116      } else {
117        newBranches = new List<IFunctionTree>();
118
119        // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
120        // in case both trees are higher than 1 we swap the trees with probability 50%
121        if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
122          IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
123          int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
124          int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
125        }
126
127        // select a random suboperator of the 'receiving' tree
128        IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
129        int removedBranchIndex;
130        IFunctionTree removedBranch;
131        IList<IFunction> allowedFunctions;
132        if(crossoverPoint == null) {
133          removedBranchIndex = 0;
134          removedBranch = tree0;
135          allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
136        } else {
137          removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
138          removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
139          allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
140        }
141        int removedBranchSize = removedBranch.Size;
142        int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
143        int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch);
144        IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
145
146        int tries = 0;
147        while(insertedBranch == null) {
148          if(tries++ > MAX_RECOMBINATION_TRIES) {
149            if(random.Next() > 0.5) return tree1;
150            else return tree0;
151          }
152
153          // retry with a different crossoverPoint       
154          crossoverPoint = gardener.GetRandomParentNode(tree0);
155          if(crossoverPoint == null) {
156            removedBranchIndex = 0;
157            removedBranch = tree0;
158            allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
159          } else {
160            removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
161            removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
162            allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
163          }
164          removedBranchSize = removedBranch.Size;
165          maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
166          maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
167          insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
168        }
169        if(crossoverPoint != null) {
170          // replace the branch below the crossoverpoint with the selected branch from root1
171          crossoverPoint.RemoveSubTree(removedBranchIndex);
172          crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
173          return tree0;
174        } else {
175          return insertedBranch;
176        }
177      }
178    }
179
180    private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
181      var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)
182        .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);
183
184      var shorterBranches = branches.Where(t => t.Size < removedBranchSize);
185      var longerBranches = branches.Where(t => t.Size > removedBranchSize);
186      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
187
188      if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
189        if(equalLengthBranches.Count() == 0) {
190          return null;
191        } else {
192          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
193        }
194      } else {
195        // invariant: |shorterBranches| > 0  and |longerBranches| > 0
196        double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;
197        double pLonger = (1.0 - pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));
198        double pShorter = (1.0 - pEqualLength - pLonger);
199
200        double r = random.NextDouble();
201        if(r < pLonger) {
202          return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
203        } else if(r < pLonger + pShorter) {
204          return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
205        } else {
206          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
207        }
208      }
209    }
210
211
212    // take f and g and create a tree that has f and g as sub-trees
213    // example
214    //       O
215    //      /|\
216    //     g 2 f
217    //
218    private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
219      newBranches = new List<IFunctionTree>();
220      // determine the set of possible parent functions
221      ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
222      if(possibleParents.Count == 0) throw new InvalidProgramException();
223      // and select a random one
224      IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();
225
226      int nSlots = Math.Max(2, parent.Function.MinArity);
227      // determine which slot can take which sub-trees
228      List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
229      for(int slot = 0; slot < nSlots; slot++) {
230        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
231        List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
232        if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
233        if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
234        slots[slot] = allowedTrees;
235      }
236      // fill the slots in the order of degrees of freedom
237      int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
238
239      // tmp arry to store the tree for each sub-tree slot of the parent
240      IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
241
242      // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
243      for(int i = 0; i < slotSequence.Length; i++) {
244        int slot = slotSequence[i];
245        List<IFunctionTree> allowedTrees = slots[slot];
246        // when neither f nor g fit into the slot => create a new random tree
247        if(allowedTrees.Count() == 0) {
248          var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
249          selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);
250          newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
251        } else {
252          // select randomly which tree to insert into this slot
253          IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
254          selectedFunctionTrees[slot] = selectedTree;
255          // remove the tree that we used in this slot from following function-sets
256          for(int j = i + 1; j < slotSequence.Length; j++) {
257            int otherSlot = slotSequence[j];
258            slots[otherSlot].Remove(selectedTree);
259          }
260        }
261      }
262      // actually append the sub-trees to the parent tree
263      for(int i = 0; i < selectedFunctionTrees.Length; i++) {
264        parent.InsertSubTree(i, selectedFunctionTrees[i]);
265      }
266
267      return parent;
268    }
269  }
270}
Note: See TracBrowser for help on using the repository browser.