Free cookie consent management tool by TermsFeed Policy Generator

source: branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs @ 7303

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

#1682: Override of the CanChangeName property, added friendly names for the crossover operators.

File size: 6.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
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    protected override ISymbolicExpressionTree Cross(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    public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
57      return Cross(random, parent0, parent1);
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.Subtrees.Any() && n != parent0.Root)
70          possibleChildren.AddRange(n.Subtrees);
71      });
72      var selectedChild = possibleChildren.SelectRandom(random);
73      var crossoverPoints = new List<CutPoint>();
74      var qualities = new List<Tuple<CutPoint, double>>();
75
76      parent0.Root.ForEachNodePostfix((n) => {
77        if (n.Subtrees.Any() && n != parent0.Root)
78          crossoverPoints.AddRange(from s in n.Subtrees
79                                   let crossoverPoint = new CutPoint(n, s)
80                                   let totalDepth = parent0.Root.GetBranchLevel(s) + selectedChild.GetDepth()
81                                   let totalLength = parent0.Root.GetLength() - s.GetLength() + selectedChild.GetLength()
82                                   where crossoverPoint.IsMatchingPointType(selectedChild) && totalDepth <= maxDepth && totalLength <= maxLength
83                                   select crossoverPoint);
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          double quality = evaluator.Evaluate(context, parent0, problemData, rows);
94          qualities.Add(new Tuple<CutPoint, double>(crossoverPoint, quality));
95          // restore the correct parent
96          selectedChild.Parent = parent;
97          // swap the replaced subtree back into the tree so that the structure is preserved
98          swap(crossoverPoint, crossoverPoint.Child);
99        }
100
101        qualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
102        var crossoverPoint0 = evaluator.Maximization ? qualities.Last().Item1 : qualities.First().Item1;
103        // swap the node that would create the best offspring
104        // this last swap makes a total of (2 * crossoverPoints.Count() + 1) swap operations.
105        swap(crossoverPoint0, selectedChild);
106      }
107
108      return parent0;
109    }
110
111    private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
112      if (crossoverPoint.Child != null) {
113        // manipulate the tree of parent0 in place
114        // replace the branch in tree0 with the selected branch from tree1
115        crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);
116        if (selectedBranch != null) {
117          crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);
118        }
119      } else {
120        // child is null (additional child should be added under the parent)
121        if (selectedBranch != null) {
122          crossoverPoint.Parent.AddSubtree(selectedBranch);
123        }
124      }
125    }
126  }
127}
Note: See TracBrowser for help on using the repository browser.