Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 644 was 618, checked in by gkronber, 16 years ago
  • improved SizeFairCrossOver
  • implemented very simple and strict form of a homologous crossover operator

(ticket #108)

File size: 13.8 KB
RevLine 
[2]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;
[155]31using HeuristicLab.Functions;
[238]32using System.Diagnostics;
[2]33
34namespace HeuristicLab.StructureIdentification {
[617]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>
[158]41  public class SizeFairCrossOver : OperatorBase {
[442]42    private const int MAX_RECOMBINATION_TRIES = 20;
[2]43    public override string Description {
44      get {
[617]45        return @"";
[2]46      }
47    }
[158]48    public SizeFairCrossOver()
[2]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));
[155]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));
[2]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) {
[155]89      List<IFunctionTree> newBranches;
90      IFunctionTree newTree = Cross(gardener, parent1, parent2,
91        random, maxTreeSize, maxTreeHeight, out newBranches);
[2]92
93
[324]94      int newTreeSize = newTree.Size;
95      int newTreeHeight = newTree.Height;
[155]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)));
[2]99
[442]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)
[444]101      Debug.Assert(gardener.IsValidTree(newTree) && newTreeHeight <= maxTreeHeight && newTreeSize <= maxTreeSize);
[155]102      return gardener.CreateInitializationOperation(newBranches, child);
[2]103    }
104
105
[155]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);
[2]108      int tree0Height = f.GetVariableValue<IntData>("TreeHeight", false).Data;
109      int tree0Size = f.GetVariableValue<IntData>("TreeSize", false).Data;
110
[155]111      IFunctionTree tree1 = g.GetVariableValue<IFunctionTree>("FunctionTree", false);
[2]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) {
[155]116        return CombineTerminals(gardener, tree0, tree1, random, maxTreeHeight, out newBranches);
[2]117      } else {
[442]118        newBranches = new List<IFunctionTree>();
119
[2]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)) {
[155]123          IFunctionTree tmp = tree0; tree0 = tree1; tree1 = tmp;
[2]124          int tmpHeight = tree0Height; tree0Height = tree1Height; tree1Height = tmpHeight;
125          int tmpSize = tree0Size; tree0Size = tree1Size; tree1Size = tmpSize;
126        }
127
[617]128        // select a random suboperator of the 'receiving' tree
[618]129        IFunctionTree crossoverPoint = gardener.GetRandomParentNode(tree0);
[617]130        int removedBranchIndex;
131        IFunctionTree removedBranch;
132        IList<IFunction> allowedFunctions;
133        if(crossoverPoint == null) {
134          removedBranchIndex = 0;
[618]135          removedBranch = tree0;
[617]136          allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
137        } else {
138          removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
139          removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
140          allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
141        }
142        int removedBranchSize = removedBranch.Size;
[618]143        int maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
144        int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch);
145        IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
[2]146
[442]147        int tries = 0;
[617]148        while(insertedBranch == null) {
[442]149          if(tries++ > MAX_RECOMBINATION_TRIES) {
[618]150            if(random.Next() > 0.5) return tree1;
151            else return tree0;
[442]152          }
[2]153
[617]154          // retry with a different crossoverPoint       
[618]155          crossoverPoint = gardener.GetRandomParentNode(tree0);
[617]156          if(crossoverPoint == null) {
157            removedBranchIndex = 0;
[618]158            removedBranch = tree0;
[617]159            allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
160          } else {
161            removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
162            removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
163            allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
164          }
165          removedBranchSize = removedBranch.Size;
[618]166          maxBranchSize = maxTreeSize - (tree0.Size - removedBranchSize);
167          maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, removedBranch) + 1;
168          insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, tree1, removedBranchSize, maxBranchSize, maxBranchHeight);
[617]169        }
170        if(crossoverPoint != null) {
171          // replace the branch below the crossoverpoint with the selected branch from root1
172          crossoverPoint.RemoveSubTree(removedBranchIndex);
173          crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
[618]174          return tree0;
[617]175        } else {
176          return insertedBranch;
177        }
178      }
179    }
[437]180
[617]181    private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
182      var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)
183        .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);
[2]184
[617]185      var shorterBranches = branches.Where(t => t.Size < removedBranchSize);
186      var longerBranches = branches.Where(t => t.Size > removedBranchSize);
187      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
188
189      if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
190        if(equalLengthBranches.Count() == 0) {
191          return null;
192        } else {
193          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
[2]194        }
[617]195      } else {
196        // invariant: |shorterBranches| > 0  and |longerBranches| > 0
197        double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;
198        double pLonger = (1.0 - pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));
199        double pShorter = (1.0 - pEqualLength - pLonger);
200
201        double r = random.NextDouble();
202        if(r < pLonger) {
203          return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
204        } else if(r < pLonger + pShorter) {
205          return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
206        } else {
207          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
208        }
[2]209      }
210    }
211
212
[155]213    // take f and g and create a tree that has f and g as sub-trees
214    // example
215    //       O
216    //      /|\
217    //     g 2 f
218    //
219    private IFunctionTree CombineTerminals(TreeGardener gardener, IFunctionTree f, IFunctionTree g, MersenneTwister random, int maxTreeHeight, out List<IFunctionTree> newBranches) {
220      newBranches = new List<IFunctionTree>();
221      // determine the set of possible parent functions
222      ICollection<IFunction> possibleParents = gardener.GetPossibleParents(new List<IFunction>() { f.Function, g.Function });
[2]223      if(possibleParents.Count == 0) throw new InvalidProgramException();
[155]224      // and select a random one
[189]225      IFunctionTree parent = possibleParents.ElementAt(random.Next(possibleParents.Count())).GetTreeNode();
[2]226
[526]227      int nSlots = Math.Max(2, parent.Function.MinArity);
[155]228      // determine which slot can take which sub-trees
229      List<IFunctionTree>[] slots = new List<IFunctionTree>[nSlots];
[2]230      for(int slot = 0; slot < nSlots; slot++) {
[155]231        ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
232        List<IFunctionTree> allowedTrees = new List<IFunctionTree>();
233        if(allowedSubFunctions.Contains(f.Function)) allowedTrees.Add(f);
234        if(allowedSubFunctions.Contains(g.Function)) allowedTrees.Add(g);
235        slots[slot] = allowedTrees;
[2]236      }
[155]237      // fill the slots in the order of degrees of freedom
238      int[] slotSequence = Enumerable.Range(0, slots.Count()).OrderBy(slot => slots[slot].Count()).ToArray();
[2]239
[155]240      // tmp arry to store the tree for each sub-tree slot of the parent
241      IFunctionTree[] selectedFunctionTrees = new IFunctionTree[nSlots];
[2]242
[155]243      // fill the sub-tree slots of the parent starting with the slots that can take potentially both functions (f and g)
[2]244      for(int i = 0; i < slotSequence.Length; i++) {
245        int slot = slotSequence[i];
[155]246        List<IFunctionTree> allowedTrees = slots[slot];
247        // when neither f nor g fit into the slot => create a new random tree
248        if(allowedTrees.Count() == 0) {
249          var allowedFunctions = gardener.GetAllowedSubFunctions(parent.Function, slot);
[450]250          selectedFunctionTrees[slot] = gardener.CreateRandomTree(allowedFunctions, 1, 1);
[155]251          newBranches.AddRange(gardener.GetAllSubTrees(selectedFunctionTrees[slot]));
[2]252        } else {
[155]253          // select randomly which tree to insert into this slot
254          IFunctionTree selectedTree = allowedTrees[random.Next(allowedTrees.Count())];
255          selectedFunctionTrees[slot] = selectedTree;
256          // remove the tree that we used in this slot from following function-sets
[2]257          for(int j = i + 1; j < slotSequence.Length; j++) {
258            int otherSlot = slotSequence[j];
[155]259            slots[otherSlot].Remove(selectedTree);
[2]260          }
261        }
262      }
[155]263      // actually append the sub-trees to the parent tree
264      for(int i = 0; i < selectedFunctionTrees.Length; i++) {
265        parent.InsertSubTree(i, selectedFunctionTrees[i]);
[2]266      }
267
268      return parent;
269    }
270  }
271}
Note: See TracBrowser for help on using the repository browser.