source: trunk/sources/HeuristicLab.GP/Recombination/OnePointCrossOver.cs @ 832

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

simplified StandardCrossOver to a simple sub-tree swapping crossover with max size and height constraints.
The old version should probably be revived as HL2StandardCrossover.

#393 (Refactor GP crossover operators to extract common code into the abstract base class GPCrossoverBase)

File size: 3.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 one point crossover operator as described in:
36  /// W. B. Langdon and R. Poli.  Foundations of Genetic Programming. Springer-Verlag, 2002.
37  /// </summary>
38  public class OnePointCrossOver : GPCrossoverBase {
39    // internal data structure to represent crossover points
40    private class CrossoverPoint {
41      public IFunctionTree parent0;
42      public IFunctionTree parent1;
43      public int childIndex;
44    }
45    public override string Description {
46      get {
47        return @"";
48      }
49    }
50
51    internal override IFunctionTree Cross(IScope scope, TreeGardener gardener, MersenneTwister random, IFunctionTree tree0, IFunctionTree tree1) {
52      List<CrossoverPoint> allowedCrossOverPoints = new List<CrossoverPoint>();
53      GetCrossOverPoints(gardener, tree0, tree1, allowedCrossOverPoints);
54      if (allowedCrossOverPoints.Count > 0) {
55        CrossoverPoint crossOverPoint = allowedCrossOverPoints[random.Next(allowedCrossOverPoints.Count)];
56        IFunctionTree parent0 = crossOverPoint.parent0;
57        IFunctionTree branch1 = crossOverPoint.parent1.SubTrees[crossOverPoint.childIndex];
58        parent0.RemoveSubTree(crossOverPoint.childIndex);
59        parent0.InsertSubTree(crossOverPoint.childIndex, branch1);
60      }
61      return tree0;
62    }
63
64    private void GetCrossOverPoints(TreeGardener gardener, IFunctionTree branch0, IFunctionTree branch1, List<CrossoverPoint> crossoverPoints) {
65      if (branch0.SubTrees.Count != branch1.SubTrees.Count) return;
66
67      for (int i = 0; i < branch0.SubTrees.Count; i++) {
68        // if the current branch can be attached as a sub-tree to branch0
69        if (gardener.GetAllowedSubFunctions(branch0.Function, i).Contains(branch1.SubTrees[i].Function)) {
70          CrossoverPoint p = new CrossoverPoint();
71          p.childIndex = i;
72          p.parent0 = branch0;
73          p.parent1 = branch1;
74          crossoverPoints.Add(p);
75        }
76        GetCrossOverPoints(gardener, branch0.SubTrees[i], branch1.SubTrees[i], crossoverPoints);
77      }
78    }
79  }
80}
Note: See TracBrowser for help on using the repository browser.