Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GP.Grammar.Editor/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs @ 6934

Last change on this file since 6934 was 6387, checked in by mkommend, 14 years ago

#1540: Added min and max arity to symbols and renamed SymbolicExpressionTreeNode.SubtreesCount to SymbolicExpressionTreeNode.SubtreeCount.

File size: 12.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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 HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
32  /// <summary>
33  /// Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
34  /// And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
35  /// When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1
36  /// until a valid configuration is found.
37  /// </summary> 
38  [Item("SubtreeCrossover", "An operator which performs subtree swapping crossover.")]
39  [StorableClass]
40  public sealed class SubtreeCrossover : SymbolicExpressionTreeCrossover, ISymbolicExpressionTreeSizeConstraintOperator {
41    private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";
42    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
43    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
44    #region Parameter Properties
45    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
46      get { return (IValueLookupParameter<PercentValue>)Parameters[InternalCrossoverPointProbabilityParameterName]; }
47    }
48    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
49      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
50    }
51    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
52      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
53    }
54    #endregion
55    #region Properties
56    public PercentValue InternalCrossoverPointProbability {
57      get { return InternalCrossoverPointProbabilityParameter.ActualValue; }
58    }
59    public IntValue MaximumSymbolicExpressionTreeLength {
60      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
61    }
62    public IntValue MaximumSymbolicExpressionTreeDepth {
63      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
64    }
65    #endregion
66    [StorableConstructor]
67    private SubtreeCrossover(bool deserializing) : base(deserializing) { }
68    private SubtreeCrossover(SubtreeCrossover original, Cloner cloner) : base(original, cloner) { }
69    public SubtreeCrossover()
70      : base() {
71      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
72      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
73      Parameters.Add(new ValueLookupParameter<PercentValue>(InternalCrossoverPointProbabilityParameterName, "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
74    }
75
76    public override IDeepCloneable Clone(Cloner cloner) {
77      return new SubtreeCrossover(this, cloner);
78    }
79
80    protected override ISymbolicExpressionTree Cross(IRandom random,
81      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
82      return Cross(random, parent0, parent1, InternalCrossoverPointProbability.Value,
83        MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
84    }
85
86    public static ISymbolicExpressionTree Cross(IRandom random,
87      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
88      double internalCrossoverPointProbability, int maxTreeLength, int maxTreeDepth) {
89      // select a random crossover point in the first parent
90      CutPoint crossoverPoint0;
91      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeLength, maxTreeDepth, out crossoverPoint0);
92
93      int childLength = crossoverPoint0.Child != null ? crossoverPoint0.Child.GetLength() : 0;
94      // calculate the max length and depth that the inserted branch can have
95      int maxInsertedBranchLength = maxTreeLength - (parent0.Length - childLength);
96      int maxInsertedBranchDepth = maxTreeDepth - GetBranchLevel(parent0.Root, crossoverPoint0.Parent);
97
98      List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
99      parent1.Root.ForEachNodePostfix((n) => {
100        if (!n.Symbol.Fixed &&
101            n.GetLength() <= maxInsertedBranchLength &&
102            n.GetDepth() <= maxInsertedBranchDepth &&
103            IsMatchingPointType(crossoverPoint0, n))
104          allowedBranches.Add(n);
105      });
106      // empty branch
107      if (IsMatchingPointType(crossoverPoint0, null)) allowedBranches.Add(null);
108
109      if (allowedBranches.Count == 0) {
110        return parent0;
111      } else {
112        var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
113
114        if (crossoverPoint0.Child != null) {
115          // manipulate the tree of parent0 in place
116          // replace the branch in tree0 with the selected branch from tree1
117          crossoverPoint0.Parent.RemoveSubtree(crossoverPoint0.ChildIndex);
118          if (selectedBranch != null) {
119            crossoverPoint0.Parent.InsertSubtree(crossoverPoint0.ChildIndex, selectedBranch);
120          }
121        } else {
122          // child is null (additional child should be added under the parent)
123          if (selectedBranch != null) {
124            crossoverPoint0.Parent.AddSubtree(selectedBranch);
125          }
126        }
127        return parent0;
128      }
129    }
130
131    private static bool IsMatchingPointType(CutPoint cutPoint, ISymbolicExpressionTreeNode newChild) {
132      var parent = cutPoint.Parent;
133      if (newChild == null) {
134        // make sure that one subtree can be removed and that only the last subtree is removed
135        return parent.Grammar.GetMinimumSubtreeCount(parent.Symbol) < parent.SubtreeCount &&
136          cutPoint.ChildIndex == parent.SubtreeCount - 1;
137      } else {
138        // check syntax constraints of direct parent - child relation
139        if (!parent.Grammar.ContainsSymbol(newChild.Symbol) ||
140            !parent.Grammar.IsAllowedChildSymbol(parent.Symbol, newChild.Symbol, cutPoint.ChildIndex)) return false;
141
142        bool result = true;
143        // check point type for the whole branch
144        newChild.ForEachNodePostfix((n) => {
145          result =
146            result &&
147            parent.Grammar.ContainsSymbol(n.Symbol) &&
148            n.SubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(n.Symbol) &&
149            n.SubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(n.Symbol);
150        });
151        return result;
152      }
153    }
154
155    private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchLength, int maxBranchDepth, out CutPoint crossoverPoint) {
156      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
157      List<CutPoint> internalCrossoverPoints = new List<CutPoint>();
158      List<CutPoint> leafCrossoverPoints = new List<CutPoint>();
159      parent0.Root.ForEachNodePostfix((n) => {
160        if (!n.Symbol.Fixed && n.Subtrees.Any() && n != parent0.Root) {
161          foreach (var child in n.Subtrees) {
162            if (child.GetLength() <= maxBranchLength &&
163                child.GetDepth() <= maxBranchDepth) {
164              if (child.Subtrees.Any())
165                internalCrossoverPoints.Add(new CutPoint(n, child));
166              else
167                leafCrossoverPoints.Add(new CutPoint(n, child));
168            }
169          }
170          // add one additional extension point if the number of sub trees for the symbol is not full
171          if (n.SubtreeCount < n.Grammar.GetMaximumSubtreeCount(n.Symbol)) {
172            // empty extension point
173            internalCrossoverPoints.Add(new CutPoint(n, n.SubtreeCount));
174          }
175        }
176      });
177
178      if (random.NextDouble() < internalNodeProbability) {
179        // select from internal node if possible
180        if (internalCrossoverPoints.Count > 0) {
181          // select internal crossover point or leaf
182          crossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
183        } else {
184          // otherwise select external node
185          crossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
186        }
187      } else if (leafCrossoverPoints.Count > 0) {
188        // select from leaf crossover point if possible
189        crossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
190      } else {
191        // otherwise select internal crossover point
192        crossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
193      }
194    }
195
196    private static ISymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<ISymbolicExpressionTreeNode> branches, double internalNodeProbability) {
197      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
198      List<ISymbolicExpressionTreeNode> allowedInternalBranches;
199      List<ISymbolicExpressionTreeNode> allowedLeafBranches;
200      if (random.NextDouble() < internalNodeProbability) {
201        // select internal node if possible
202        allowedInternalBranches = (from branch in branches
203                                   where branch != null && branch.Subtrees.Any()
204                                   select branch).ToList();
205        if (allowedInternalBranches.Count > 0) {
206          return allowedInternalBranches.SelectRandom(random);
207        } else {
208          // no internal nodes allowed => select leaf nodes
209          allowedLeafBranches = (from branch in branches
210                                 where branch == null || !branch.Subtrees.Any()
211                                 select branch).ToList();
212          return allowedLeafBranches.SelectRandom(random);
213        }
214      } else {
215        // select leaf node if possible
216        allowedLeafBranches = (from branch in branches
217                               where branch == null || !branch.Subtrees.Any()
218                               select branch).ToList();
219        if (allowedLeafBranches.Count > 0) {
220          return allowedLeafBranches.SelectRandom(random);
221        } else {
222          allowedInternalBranches = (from branch in branches
223                                     where branch != null && branch.Subtrees.Any()
224                                     select branch).ToList();
225          return allowedInternalBranches.SelectRandom(random);
226        }
227      }
228    }
229
230    private static int GetBranchLevel(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode point) {
231      if (root == point) return 0;
232      foreach (var subtree in root.Subtrees) {
233        int branchLevel = GetBranchLevel(subtree, point);
234        if (branchLevel < int.MaxValue) return 1 + branchLevel;
235      }
236      return int.MaxValue;
237    }
238  }
239}
Note: See TracBrowser for help on using the repository browser.