source: trunk/sources/HeuristicLab.GP/Recombination/UniformCrossover.cs @ 1197

Last change on this file since 1197 was 1197, checked in by gkronber, 13 years ago

merged fix for #479 (Crossover operators create trees that are larger than the allowed max size) (r1196) to trunk

File size: 7.2 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 uniform crossover operator as described in:
36  /// R. Poli and W. B. Langdon.  On the Search Properties of Different Crossover Operators in Genetic Programming.
37  /// In Proceedings of Genetic Programming '98, Madison, Wisconsin, 1998.
38  /// </summary>
39  public class UniformCrossover : SizeConstrictedGPCrossoverBase {
40    // internal datastructure to represent crossover points
41    private class CrossoverPoint {
42      public IFunctionTree Parent0;
43      public IFunctionTree Parent1;
44      public int ChildIndex;
45      public bool IsInternal;
46    }
47
48    public override string Description {
49      get {
50        return @"Uniform crossover as defined by Poli and Langdon";
51      }
52    }
53
54    internal override IFunctionTree Cross(TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
55      List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
56      GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);
57      // iterate through the list of crossover points and swap nodes with p=0.5
58      foreach (CrossoverPoint crossoverPoint in allowedCrossOverPoints) {
59        if (random.NextDouble() < 0.5) {
60          if (crossoverPoint.IsInternal) {
61            ExchangeNodes(crossoverPoint);
62          } else {
63            SwapSubtrees(crossoverPoint);
64          }
65        }
66      }
67      return tree0;
68    }
69
70    private void GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1, List<CrossoverPoint> crossoverPoints) {
71      if (branch0.SubTrees.Count != branch1.SubTrees.Count) return; // branches have to have same number of sub-trees to be valid crossover points
72      // iterate over all sub-trees
73      for (int i = 0; i < branch0.SubTrees.Count; i++) {
74        IFunctionTree currentSubTree0 = branch0.SubTrees[i];
75        IFunctionTree currentSubTree1 = branch1.SubTrees[i];
76        // when the current sub-tree in branch1 can be attached as a child of branch0
77        // and the sub-tree of branch0 can be attached as child of branch1.
78        // note: we have to check both cases because either branch0 or branch1 can end up in the result tree
79        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(currentSubTree1.Function) &&
80          gardener.GetAllowedSubFunctions(branch1.Function, i).Contains(currentSubTree0.Function)) {
81          // and the sub-tree is at the border of the common region
82          if (currentSubTree0.SubTrees.Count != currentSubTree1.SubTrees.Count) {
83            // then we have found a valid crossover point
84            CrossoverPoint p = new CrossoverPoint();
85            p.ChildIndex = i;
86            p.Parent0 = branch0;
87            p.Parent1 = branch1;
88            p.IsInternal = false;
89            crossoverPoints.Add(p);
90          } else {
91            // when the sub-trees are not on the border of the common region
92            // we also have to check if the children of the current sub-trees of branch0 and branch1 can be exchanged
93            if (CanHaveSubTrees(gardener, currentSubTree0, currentSubTree1.SubTrees) &&
94              CanHaveSubTrees(gardener, currentSubTree1, currentSubTree0.SubTrees)) {
95              CrossoverPoint p = new CrossoverPoint();
96              p.ChildIndex = i;
97              p.Parent0 = branch0;
98              p.Parent1 = branch1;
99              p.IsInternal = true;
100              crossoverPoints.Add(p);
101            }
102          }
103        }
104        GetCrossOverPoints(gardener, currentSubTree0, currentSubTree1, crossoverPoints);
105      }
106    }
107
108    private bool CanHaveSubTrees(TreeGardener gardener, IFunctionTree parent, IList<IFunctionTree> subTrees) {
109      for (int i = 0; i < subTrees.Count; i++) {
110        if (!gardener.GetAllowedSubFunctions(parent.Function, i).Contains(subTrees[i].Function)) return false;
111      }
112      return true;
113    }
114
115    private void ExchangeNodes(CrossoverPoint crossoverPoint) {
116      IFunctionTree parent0 = crossoverPoint.Parent0;
117      IFunctionTree parent1 = crossoverPoint.Parent1;
118      int childIndex = crossoverPoint.ChildIndex;
119      IFunctionTree branch0 = crossoverPoint.Parent0.SubTrees[childIndex];
120      IFunctionTree branch1 = crossoverPoint.Parent1.SubTrees[childIndex];
121      // exchange the branches in the parent
122      parent0.RemoveSubTree(childIndex);
123      parent0.InsertSubTree(childIndex, branch1);
124      parent1.RemoveSubTree(childIndex);
125      parent1.InsertSubTree(childIndex, branch0);
126
127      ExchangeChildren(branch0, branch1);
128    }
129
130    private void SwapSubtrees(CrossoverPoint crossoverPoint) {
131      IFunctionTree parent0 = crossoverPoint.Parent0;
132      IFunctionTree parent1 = crossoverPoint.Parent1;
133      int childIndex = crossoverPoint.ChildIndex;
134      IFunctionTree branch0 = crossoverPoint.Parent0.SubTrees[childIndex];
135      IFunctionTree branch1 = crossoverPoint.Parent1.SubTrees[childIndex];
136      // insert branch1 into parent0 replacing branch0
137      parent0.RemoveSubTree(childIndex);
138      parent0.InsertSubTree(childIndex, branch1);
139      // insert branch0 into parent1 replacing branch1
140      parent1.RemoveSubTree(childIndex);
141      parent1.InsertSubTree(childIndex, branch0);
142    }
143
144    private void ExchangeChildren(IFunctionTree branch0, IFunctionTree branch1) {
145      List<IFunctionTree> branch0Children = new List<IFunctionTree>(branch0.SubTrees); // lists to backup subtrees
146      List<IFunctionTree> branch1Children = new List<IFunctionTree>(branch1.SubTrees);
147
148      // remove children of branch0 and branch1
149      while (branch1.SubTrees.Count > 0) branch1.RemoveSubTree(0);
150      while (branch0.SubTrees.Count > 0) branch0.RemoveSubTree(0);
151
152      // add original children of branch0 to branch1
153      foreach (IFunctionTree subTree in branch0Children) {
154        branch1.AddSubTree(subTree);
155      }
156      // add original children of branch1 to branch0
157      foreach (IFunctionTree subTree in branch1Children) {
158        branch0.AddSubTree(subTree);
159      }
160    }
161  }
162}
Note: See TracBrowser for help on using the repository browser.