Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Crossovers/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs @ 7489

Last change on this file since 7489 was 7481, checked in by mkommend, 12 years ago

#1682: Corrected gp-crossover code.

  • Changed ISymbolicExpressionTreeCrossover
  • Corrected SubtreeCrossover
  • Updated MultiSymbolicDataAnalysisCrossover
File size: 6.3 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.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
31
32  [Item("ContextAwareCrossover", "An operator which deterministically choses the best insertion point for a randomly selected node.")]
33  public sealed class SymbolicDataAnalysisExpressionContextAwareCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
34    [StorableConstructor]
35    private SymbolicDataAnalysisExpressionContextAwareCrossover(bool deserializing) : base(deserializing) { }
36    private SymbolicDataAnalysisExpressionContextAwareCrossover(SymbolicDataAnalysisExpressionCrossover<T> original, Cloner cloner)
37      : base(original, cloner) {
38    }
39    public SymbolicDataAnalysisExpressionContextAwareCrossover()
40      : base() {
41      Name = "ContextAwareCrossover";
42    }
43    public override IDeepCloneable Clone(Cloner cloner) {
44      return new SymbolicDataAnalysisExpressionContextAwareCrossover<T>(this, cloner);
45    }
46    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
47      if (this.ExecutionContext == null)
48        throw new InvalidOperationException("ExecutionContext not set.");
49      List<int> rows = GenerateRowsToEvaluate().ToList();
50      T problemData = ProblemDataParameter.ActualValue;
51      ISymbolicDataAnalysisSingleObjectiveEvaluator<T> evaluator = EvaluatorParameter.ActualValue;
52
53      return Cross(random, parent0, parent1, this.ExecutionContext, evaluator, problemData, rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value);
54    }
55
56    /// <summary>
57    /// Takes two parent individuals P0 and P1.
58    /// Randomly choose a node i from the second parent, then test all possible crossover points from the first parent to determine the best location for i to be inserted.
59    /// </summary>
60    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, IExecutionContext context,
61                                                ISymbolicDataAnalysisSingleObjectiveEvaluator<T> evaluator, T problemData, List<int> rows, int maxDepth, int maxLength) {
62      // randomly choose a node from the second parent
63      var possibleChildren = new List<ISymbolicExpressionTreeNode>();
64      parent1.Root.ForEachNodePostfix((n) => {
65        if (n.Subtrees.Any() && n != parent0.Root)
66          possibleChildren.AddRange(n.Subtrees);
67      });
68      var selectedChild = possibleChildren.SelectRandom(random);
69      var crossoverPoints = new List<CutPoint>();
70      var qualities = new List<Tuple<CutPoint, double>>();
71
72      parent0.Root.ForEachNodePostfix((n) => {
73        if (n.Subtrees.Any() && n != parent0.Root)
74          crossoverPoints.AddRange(from s in n.Subtrees
75                                   let crossoverPoint = new CutPoint(n, s)
76                                   let totalDepth = parent0.Root.GetBranchLevel(s) + selectedChild.GetDepth()
77                                   let totalLength = parent0.Root.GetLength() - s.GetLength() + selectedChild.GetLength()
78                                   where crossoverPoint.IsMatchingPointType(selectedChild) && totalDepth <= maxDepth && totalLength <= maxLength
79                                   select crossoverPoint);
80      });
81
82      if (crossoverPoints.Any()) {
83        // this loop will perform two swap operations per each crossover point
84        foreach (var crossoverPoint in crossoverPoints) {
85          // save the old parent so we can restore it later
86          var parent = selectedChild.Parent;
87          // perform a swap and check the quality of the solution
88          swap(crossoverPoint, selectedChild);
89          double quality = evaluator.Evaluate(context, parent0, problemData, rows);
90          qualities.Add(new Tuple<CutPoint, double>(crossoverPoint, quality));
91          // restore the correct parent
92          selectedChild.Parent = parent;
93          // swap the replaced subtree back into the tree so that the structure is preserved
94          swap(crossoverPoint, crossoverPoint.Child);
95        }
96
97        qualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
98        var crossoverPoint0 = evaluator.Maximization ? qualities.Last().Item1 : qualities.First().Item1;
99        // swap the node that would create the best offspring
100        // this last swap makes a total of (2 * crossoverPoints.Count() + 1) swap operations.
101        swap(crossoverPoint0, selectedChild);
102      }
103
104      return parent0;
105    }
106
107    private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
108      if (crossoverPoint.Child != null) {
109        // manipulate the tree of parent0 in place
110        // replace the branch in tree0 with the selected branch from tree1
111        crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);
112        if (selectedBranch != null) {
113          crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);
114        }
115      } else {
116        // child is null (additional child should be added under the parent)
117        if (selectedBranch != null) {
118          crossoverPoint.Parent.AddSubtree(selectedBranch);
119        }
120      }
121    }
122  }
123}
Note: See TracBrowser for help on using the repository browser.