1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Common;


26  using HeuristicLab.Core;


27  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


28  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


29  using HeuristicLab.Random;


30 


31  namespace 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  }

