source: trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs @ 7521

Last change on this file since 7521 was 7521, checked in by mkommend, 8 years ago

#1682: Forbid name changes in new gp crossovers

File size: 5.9 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  [Item("ContextAwareCrossover", "An operator which deterministically choses the best insertion point for a randomly selected node:\n" +
32                                 "- Take two parent individuals P0 and P1\n" +
33                                 "- Randomly choose a node N from P1\n" +
34                                 "- Test all crossover points from P0 to determine the best location for N to be inserted")]
35  public sealed class SymbolicDataAnalysisExpressionContextAwareCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
36    [StorableConstructor]
37    private SymbolicDataAnalysisExpressionContextAwareCrossover(bool deserializing) : base(deserializing) { }
38    private SymbolicDataAnalysisExpressionContextAwareCrossover(SymbolicDataAnalysisExpressionCrossover<T> original, Cloner cloner)
39      : base(original, cloner) {
40    }
41    public SymbolicDataAnalysisExpressionContextAwareCrossover()
42      : base() {
43      name = "ContextAwareCrossover";
44    }
45    public override IDeepCloneable Clone(Cloner cloner) {
46      return new SymbolicDataAnalysisExpressionContextAwareCrossover<T>(this, cloner);
47    }
48    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
49      if (this.ExecutionContext == null)
50        throw new InvalidOperationException("ExecutionContext not set.");
51      List<int> rows = GenerateRowsToEvaluate().ToList();
52      T problemData = ProblemDataParameter.ActualValue;
53      ISymbolicDataAnalysisSingleObjectiveEvaluator<T> evaluator = EvaluatorParameter.ActualValue;
54
55      return Cross(random, parent0, parent1, this.ExecutionContext, evaluator, problemData, rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value);
56    }
57
58    /// <summary>
59    /// Takes two parent individuals P0 and P1.
60    /// 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.
61    /// </summary>
62    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, IExecutionContext context,
63                                                ISymbolicDataAnalysisSingleObjectiveEvaluator<T> evaluator, T problemData, List<int> rows, int maxDepth, int maxLength) {
64      // randomly choose a node from the second parent
65      var possibleChildren = new List<ISymbolicExpressionTreeNode>();
66      parent1.Root.ForEachNodePostfix((n) => {
67        if (n.Parent != null && n.Parent != parent1.Root)
68          possibleChildren.Add(n);
69      });
70      var selectedChild = possibleChildren.SelectRandom(random);
71      var crossoverPoints = new List<CutPoint>();
72      var qualities = new List<Tuple<CutPoint, double>>();
73
74      parent0.Root.ForEachNodePostfix((n) => {
75        if (n.Parent != null && n.Parent != parent0.Root) {
76          var totalDepth = parent0.Root.GetBranchLevel(n) + selectedChild.GetDepth();
77          var totalLength = parent0.Root.GetLength() - n.GetLength() + selectedChild.GetLength();
78          if (totalDepth <= maxDepth && totalLength <= maxLength) {
79            var crossoverPoint = new CutPoint(n.Parent, n);
80            if (crossoverPoint.IsMatchingPointType(selectedChild))
81              crossoverPoints.Add(crossoverPoint);
82          }
83        }
84      });
85
86      if (crossoverPoints.Any()) {
87        // this loop will perform two swap operations per each crossover point
88        foreach (var crossoverPoint in crossoverPoints) {
89          // save the old parent so we can restore it later
90          var parent = selectedChild.Parent;
91          // perform a swap and check the quality of the solution
92          Swap(crossoverPoint, selectedChild);
93          IExecutionContext childContext = new ExecutionContext(context, evaluator, context.Scope);
94          double quality = evaluator.Evaluate(childContext, parent0, problemData, rows);
95          qualities.Add(new Tuple<CutPoint, double>(crossoverPoint, quality));
96          // restore the correct parent
97          selectedChild.Parent = parent;
98          // swap the replaced subtree back into the tree so that the structure is preserved
99          Swap(crossoverPoint, crossoverPoint.Child);
100        }
101
102        qualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
103        var crossoverPoint0 = evaluator.Maximization ? qualities.Last().Item1 : qualities.First().Item1;
104        // swap the node that would create the best offspring
105        // this last swap makes a total of (2 * crossoverPoints.Count() + 1) swap operations.
106        Swap(crossoverPoint0, selectedChild);
107      }
108
109      return parent0;
110    }
111  }
112}
Note: See TracBrowser for help on using the repository browser.