Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs @ 12706

Last change on this file since 12706 was 12706, checked in by mkommend, 9 years ago

#2320: Merged r12422, r12423, r12424, r12480, r12481 and r12482 into stable.

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