Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Crossovers/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs @ 7477

Last change on this file since 7477 was 7477, checked in by bburlacu, 12 years ago

#1682: Added missing files (that were previously incorrectly referencing the old branch), added unit tests, recommitted lost changes.

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