source: branches/HeuristicLab.DataAnalysis.Symbolic.LinearInterpreter/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs @ 9732

Last change on this file since 9732 was 9732, checked in by bburlacu, 6 years ago

#2021: Merged trunk changes for HeuristicLab.Encodings.SymbolicExpressionTreeEncoding and HeuristicLab.Problems.DataAnalysis.Symbolic. Replaced prefix iteration of nodes in the linear interpretation with breadth iteration for simplified logic and extra performance. Reversed unnecessary changes to other projects.

File size: 10.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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("SubtreeSwappingCrossover", "An operator which performs subtree swapping crossover.")]
39  [StorableClass]
40  public class SubtreeCrossover : SymbolicExpressionTreeCrossover, ISymbolicExpressionTreeSizeConstraintOperator {
41    private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";
42    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
43    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
44
45    #region Parameter Properties
46    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
47      get { return (IValueLookupParameter<PercentValue>)Parameters[InternalCrossoverPointProbabilityParameterName]; }
48    }
49    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
50      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
51    }
52    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
53      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
54    }
55    #endregion
56    #region Properties
57    public PercentValue InternalCrossoverPointProbability {
58      get { return InternalCrossoverPointProbabilityParameter.ActualValue; }
59    }
60    public IntValue MaximumSymbolicExpressionTreeLength {
61      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
62    }
63    public IntValue MaximumSymbolicExpressionTreeDepth {
64      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
65    }
66    #endregion
67    [StorableConstructor]
68    protected SubtreeCrossover(bool deserializing) : base(deserializing) { }
69    protected SubtreeCrossover(SubtreeCrossover original, Cloner cloner) : base(original, cloner) { }
70    public SubtreeCrossover()
71      : base() {
72      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
73      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
74      Parameters.Add(new ValueLookupParameter<PercentValue>(InternalCrossoverPointProbabilityParameterName, "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
75    }
76
77    public override IDeepCloneable Clone(Cloner cloner) {
78      return new SubtreeCrossover(this, cloner);
79    }
80
81    public override ISymbolicExpressionTree Crossover(IRandom random,
82      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
83      return Cross(random, parent0, parent1, InternalCrossoverPointProbability.Value,
84        MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
85    }
86
87    public static ISymbolicExpressionTree Cross(IRandom random,
88      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
89      double internalCrossoverPointProbability, int maxTreeLength, int maxTreeDepth) {
90      // select a random crossover point in the first parent
91      CutPoint crossoverPoint0;
92      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeLength, maxTreeDepth, out crossoverPoint0);
93
94      int childLength = crossoverPoint0.Child != null ? crossoverPoint0.Child.GetLength() : 0;
95      // calculate the max length and depth that the inserted branch can have
96      int maxInsertedBranchLength = maxTreeLength - (parent0.Length - childLength);
97      int maxInsertedBranchDepth = maxTreeDepth - parent0.Root.GetBranchLevel(crossoverPoint0.Parent);
98
99      List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
100      parent1.Root.ForEachNodePostfix((n) => {
101        if (n.GetLength() <= maxInsertedBranchLength &&
102            n.GetDepth() <= maxInsertedBranchDepth && crossoverPoint0.IsMatchingPointType(n))
103          allowedBranches.Add(n);
104      });
105      // empty branch
106      if (crossoverPoint0.IsMatchingPointType(null)) allowedBranches.Add(null);
107
108      if (allowedBranches.Count == 0) {
109        return parent0;
110      } else {
111        var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
112
113        if (crossoverPoint0.Child != null) {
114          // manipulate the tree of parent0 in place
115          // replace the branch in tree0 with the selected branch from tree1
116          crossoverPoint0.Parent.RemoveSubtree(crossoverPoint0.ChildIndex);
117          if (selectedBranch != null) {
118            crossoverPoint0.Parent.InsertSubtree(crossoverPoint0.ChildIndex, selectedBranch);
119          }
120        } else {
121          // child is null (additional child should be added under the parent)
122          if (selectedBranch != null) {
123            crossoverPoint0.Parent.AddSubtree(selectedBranch);
124          }
125        }
126        return parent0;
127      }
128    }
129
130    private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchLength, int maxBranchDepth, out CutPoint crossoverPoint) {
131      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
132      List<CutPoint> internalCrossoverPoints = new List<CutPoint>();
133      List<CutPoint> leafCrossoverPoints = new List<CutPoint>();
134      parent0.Root.ForEachNodePostfix((n) => {
135        if (n.SubtreeCount > 0 && n != parent0.Root) {
136          foreach (var child in n.Subtrees) {
137            if (child.GetLength() <= maxBranchLength &&
138                child.GetDepth() <= maxBranchDepth) {
139              if (child.SubtreeCount > 0)
140                internalCrossoverPoints.Add(new CutPoint(n, child));
141              else
142                leafCrossoverPoints.Add(new CutPoint(n, child));
143            }
144          }
145
146          // add one additional extension point if the number of sub trees for the symbol is not full
147          if (n.SubtreeCount < n.Grammar.GetMaximumSubtreeCount(n.Symbol)) {
148            // empty extension point
149            internalCrossoverPoints.Add(new CutPoint(n, n.SubtreeCount));
150          }
151        }
152      }
153    );
154
155      if (random.NextDouble() < internalNodeProbability) {
156        // select from internal node if possible
157        if (internalCrossoverPoints.Count > 0) {
158          // select internal crossover point or leaf
159          crossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
160        } else {
161          // otherwise select external node
162          crossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
163        }
164      } else if (leafCrossoverPoints.Count > 0) {
165        // select from leaf crossover point if possible
166        crossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
167      } else {
168        // otherwise select internal crossover point
169        crossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
170      }
171    }
172
173    private static ISymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<ISymbolicExpressionTreeNode> branches, double internalNodeProbability) {
174      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
175      List<ISymbolicExpressionTreeNode> allowedInternalBranches;
176      List<ISymbolicExpressionTreeNode> allowedLeafBranches;
177      if (random.NextDouble() < internalNodeProbability) {
178        // select internal node if possible
179        allowedInternalBranches = (from branch in branches
180                                   where branch != null && branch.SubtreeCount > 0
181                                   select branch).ToList();
182        if (allowedInternalBranches.Count > 0) {
183          return allowedInternalBranches.SelectRandom(random);
184        } else {
185          // no internal nodes allowed => select leaf nodes
186          allowedLeafBranches = (from branch in branches
187                                 where branch == null || branch.SubtreeCount == 0
188                                 select branch).ToList();
189          return allowedLeafBranches.SelectRandom(random);
190        }
191      } else {
192        // select leaf node if possible
193        allowedLeafBranches = (from branch in branches
194                               where branch == null || branch.SubtreeCount == 0
195                               select branch).ToList();
196        if (allowedLeafBranches.Count > 0) {
197          return allowedLeafBranches.SelectRandom(random);
198        } else {
199          allowedInternalBranches = (from branch in branches
200                                     where branch != null && branch.SubtreeCount > 0
201                                     select branch).ToList();
202          return allowedInternalBranches.SelectRandom(random);
203        }
204      }
205    }
206  }
207}
Note: See TracBrowser for help on using the repository browser.