source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs @ 17975

Last change on this file since 17975 was 17975, checked in by gkronber, 9 months ago

#3067: merged r17490:17492 and r17871:17872 from trunk to stable

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