source: branches/2839_HiveProjectManagement/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs @ 16057

Last change on this file since 16057 was 16057, checked in by jkarder, 4 years ago

#2839:

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