Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.GP/Recombination/LangdonHomologousCrossOver.cs @ 833

Last change on this file since 833 was 814, checked in by gkronber, 15 years ago
  • removed combination of two terminals to a tree and with this the initialization routine for new branches.
  • fixed an 'off-by-one' bug in the calculation of maximal branch heights.

#391 (Review and improve implementation of SizeFair and LangdonHomologous crossover operators)

File size: 11.0 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 homologous 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 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;
194        }
195      }
196    }
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;
201      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;
219    }
220  }
221}
Note: See TracBrowser for help on using the repository browser.