Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs @ 617

Last change on this file since 617 was 617, checked in by gkronber, 16 years ago

renamed the crossover operator that we used as default in HL2 and HL3 to StandardCrossOver and implemented SizeFairCrossOver (#108)

File size: 14.1 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 HeuristicLab.Functions;
32using System.Diagnostics;
33
34namespace HeuristicLab.StructureIdentification {
35  /// <summary>
36  /// Implementation of a size fair crossover operator as described in:
37  /// William B. Langdon
38  /// Size Fair and Homologous Tree Genetic Programming Crossovers,
39  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95-119, April 2000
40  /// </summary>
41  public class SizeFairCrossOver : OperatorBase {
42    private const int MAX_RECOMBINATION_TRIES = 20;
43    public override string Description {
44      get {
45        return @"";
46      }
47    }
48    public SizeFairCrossOver()
49      : base() {
50      AddVariableInfo(new VariableInfo("Random", "Pseudo random number generator", typeof(MersenneTwister), VariableKind.In));
51      AddVariableInfo(new VariableInfo("OperatorLibrary", "The operator library containing all available operators", typeof(GPOperatorLibrary), VariableKind.In));
52      AddVariableInfo(new VariableInfo("MaxTreeHeight", "The maximal allowed height of the tree", typeof(IntData), VariableKind.In));
53      AddVariableInfo(new VariableInfo("MaxTreeSize", "The maximal allowed size (number of nodes) of the tree", typeof(IntData), VariableKind.In));
54      AddVariableInfo(new VariableInfo("FunctionTree", "The tree to mutate", typeof(IFunctionTree), VariableKind.In | VariableKind.New));
55      AddVariableInfo(new VariableInfo("TreeSize", "The size (number of nodes) of the tree", typeof(IntData), VariableKind.New));
56      AddVariableInfo(new VariableInfo("TreeHeight", "The height of the tree", typeof(IntData), VariableKind.New));
57    }
58
59    public override IOperation Apply(IScope scope) {
60      MersenneTwister random = GetVariableValue<MersenneTwister>("Random", scope, true);
61      GPOperatorLibrary opLibrary = GetVariableValue<GPOperatorLibrary>("OperatorLibrary", scope, true);
62      int maxTreeHeight = GetVariableValue<IntData>("MaxTreeHeight", scope, true).Data;
63      int maxTreeSize = GetVariableValue<IntData>("MaxTreeSize", scope, true).Data;
64
65      TreeGardener gardener = new TreeGardener(random, opLibrary);
66
67      if((scope.SubScopes.Count % 2) != 0)
68        throw new InvalidOperationException("Number of parents is not even");
69
70      CompositeOperation initOperations = new CompositeOperation();
71
72      int children = scope.SubScopes.Count / 2;
73      for(int i = 0; i < children; i++) {
74        IScope parent1 = scope.SubScopes[0];
75        scope.RemoveSubScope(parent1);
76        IScope parent2 = scope.SubScopes[0];
77        scope.RemoveSubScope(parent2);
78        IScope child = new Scope(i.ToString());
79        IOperation childInitOperation = Cross(gardener, maxTreeSize, maxTreeHeight, scope, random, parent1, parent2, child);
80        initOperations.AddOperation(childInitOperation);
81        scope.AddSubScope(child);
82      }
83
84      return initOperations;
85    }
86
87    private IOperation Cross(TreeGardener gardener, int maxTreeSize, int maxTreeHeight,
88      IScope scope, MersenneTwister random, IScope parent1, IScope parent2, IScope child) {
89      List<IFunctionTree> newBranches;
90      IFunctionTree newTree = Cross(gardener, parent1, parent2,
91        random, maxTreeSize, maxTreeHeight, out newBranches);
92
93
94      int newTreeSize = newTree.Size;
95      int newTreeHeight = newTree.Height;
96      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("FunctionTree"), newTree));
97      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeSize"), new IntData(newTreeSize)));
98      child.AddVariable(new HeuristicLab.Core.Variable(scope.TranslateName("TreeHeight"), new IntData(newTreeHeight)));
99
100      // 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)
101      Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
102      return gardener.CreateInitializationOperation(newBranches, child);
103    }
104
105
106    private IFunctionTree Cross(TreeGardener gardener, IScope f, IScope g, MersenneTwister random, int maxTreeSize, int maxTreeHeight, out List<IFunctionTree> newBranches) {
107      IFunctionTree tree0 = f.GetVariableValue<IFunctionTree>("FunctionTree", false);
108      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
109      int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
110
111      IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
112      int tree1Height = g.GetVariableValue<IntData>("TreeHeight", false).Data;
113      int tree1Size = g.GetVariableValue<IntData>("TreeSize", false).Data;
114
115      if(tree0Size == 1 && tree1Size == 1) {
116        return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
117      } else {
118        newBranches = new List<IFunctionTree>();
119
120        // we are going to insert tree1 into tree0 at a random place so we have to make sure that tree0 is not a terminal
121        // in case both trees are higher than 1 we swap the trees with probability 50%
122        if(tree0Height == 1 || (tree1Height > 1 && random.Next(2) == 0)) {
123          IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
124          int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
125          int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
126        }
127
128        // save the roots because later on we change tree0 and tree1 while searching a valid tree configuration
129        IFunctionTree root0 = tree0;
130        IFunctionTree root1 = tree1;
131        int root0Height = tree0Height;
132        int root1Height = tree1Height;
133        int rootSize = tree0Size;
134
135        // select a random suboperator of the 'receiving' tree
136        IFunctionTree crossoverPoint = gardener.GetRandomParentNode(root0);
137        int removedBranchIndex;
138        IFunctionTree removedBranch;
139        IList<IFunction> allowedFunctions;
140        if(crossoverPoint == null) {
141          removedBranchIndex = 0;
142          removedBranch = root0;
143          allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
144        } else {
145          removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
146          removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
147          allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
148        }
149        int removedBranchSize = removedBranch.Size;
150        int maxBranchSize = maxTreeSize - (root0.Size - removedBranchSize);
151        int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(root0, removedBranch);
152        IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, root1, removedBranchSize, maxBranchSize, maxBranchHeight);
153
154        int tries = 0;
155        while(insertedBranch == null) {
156          if(tries++ > MAX_RECOMBINATION_TRIES) {
157            if(random.Next() > 0.5) return root1;
158            else return root0;
159          }
160
161          // retry with a different crossoverPoint       
162          crossoverPoint = gardener.GetRandomParentNode(root0);
163          if(crossoverPoint == null) {
164            removedBranchIndex = 0;
165            removedBranch = root0;
166            allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
167          } else {
168            removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
169            removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
170            allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
171          }
172          removedBranchSize = removedBranch.Size;
173          maxBranchSize = maxTreeSize - (root0.Size - removedBranchSize);
174          maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(root0, removedBranch) + 1;
175          insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, root1, removedBranchSize, maxBranchSize, maxBranchHeight);
176        }
177        if(crossoverPoint != null) {
178          // replace the branch below the crossoverpoint with the selected branch from root1
179          crossoverPoint.RemoveSubTree(removedBranchIndex);
180          crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
181          return root0;
182        } else {
183          return insertedBranch;
184        }
185      }
186    }
187
188    private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
189      var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)
190        .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);
191
192      var shorterBranches = branches.Where(t => t.Size < removedBranchSize);
193      var longerBranches = branches.Where(t => t.Size > removedBranchSize);
194      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
195
196      if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
197        if(equalLengthBranches.Count() == 0) {
198          return null;
199        } else {
200          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
201        }
202      } else {
203        // invariant: |shorterBranches| > 0  and |longerBranches| > 0
204        double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;
205        double pLonger = (1.0 - pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));
206        double pShorter = (1.0 - pEqualLength - pLonger);
207
208        double r = random.NextDouble();
209        if(r < pLonger) {
210          return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
211        } else if(r < pLonger + pShorter) {
212          return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
213        } else {
214          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
215        }
216      }
217    }
218
219
220    // take f and g and create a tree that has f and g as sub-trees
221    // example
222    //       O
223    //      /|\
224    //     g 2 f
225    //
226    private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
227      newBranches = new List<IFunctionTree>();
228      // determine the set of possible parent functions
229      ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
230      if(possibleParents.Count == 0) throw new InvalidProgramException();
231      // and select a random one
232      IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();
233
234      int nSlots = Math.Max(2, parent.Function.MinArity);
235      // determine which slot can take which sub-trees
236      List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
237      for(int slot = 0; slot < nSlots; slot++) {
238        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
239        List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
240        if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
241        if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
242        slots[slot] = allowedTrees;
243      }
244      // fill the slots in the order of degrees of freedom
245      int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
246
247      // tmp arry to store the tree for each sub-tree slot of the parent
248      IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
249
250      // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
251      for(int i = 0; i < slotSequence.Length; i++) {
252        int slot = slotSequence[i];
253        List<IFunctionTree> allowedTrees = slots[slot];
254        // when neither f nor g fit into the slot => create a new random tree
255        if(allowedTrees.Count() == 0) {
256          var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
257          selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);
258          newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
259        } else {
260          // select randomly which tree to insert into this slot
261          IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
262          selectedFunctionTrees[slot] = selectedTree;
263          // remove the tree that we used in this slot from following function-sets
264          for(int j = i + 1; j < slotSequence.Length; j++) {
265            int otherSlot = slotSequence[j];
266            slots[otherSlot].Remove(selectedTree);
267          }
268        }
269      }
270      // actually append the sub-trees to the parent tree
271      for(int i = 0; i < selectedFunctionTrees.Length; i++) {
272        parent.InsertSubTree(i, selectedFunctionTrees[i]);
273      }
274
275      return parent;
276    }
277  }
278}
Note: See TracBrowser for help on using the repository browser.