Changeset 7109


Ignore:
Timestamp:
12/01/11 17:15:28 (8 years ago)
Author:
bburlacu
Message:

#1693: Implemented the context-aware crossover.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs

    r7089 r7109  
    3232namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3333
    34   [Item("ContextAwareCrossover", "An operator which performs subtree swapping in a deterministic way: it checks all possible cross points in the second parent with the aim of creating the best possible offspring.")]
     34  [Item("ContextAwareCrossover", "A crossover operator which deterministically choses the best insertion point for a randomly selected node.")]
    3535  public sealed class SymbolicDataAnalysisExpressionContextAwareCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
    3636    [StorableConstructor]
     
    5656    /// <summary>
    5757    /// Takes two parent individuals P0 and P1.
    58     /// Randomly choose a node i from the first parent, then test all nodes j from the second parent to determine the best child that would be obtained by swapping i for j.
     58    /// 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.
    5959    /// </summary>
    6060    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, IExecutionContext context,
    6161                                                ISymbolicDataAnalysisSingleObjectiveEvaluator<T> evaluator, T problemData, IEnumerable<int> rows, int maxDepth, int maxLength) {
    62       List<CutPoint> crossoverPoints0 = new List<CutPoint>();
     62      // randomly choose a node from the second parent
     63      var possibleChildren = new List<ISymbolicExpressionTreeNode>();
     64      parent1.Root.ForEachNodePostfix((n) => {
     65        if (n.Subtrees.Any() && n != parent0.Root)
     66          foreach (var child in n.Subtrees)
     67            possibleChildren.Add(child);
     68      });
     69      var selectedChild = possibleChildren[random.Next(possibleChildren.Count)];
     70      var crossoverPoints = new List<CutPoint>();
     71      var qualities = new List<Tuple<CutPoint, double>>();
     72
    6373      parent0.Root.ForEachNodePostfix((n) => {
    6474        if (n.Subtrees.Any() && n != parent0.Root)
    65           foreach (var child in n.Subtrees)
    66             crossoverPoints0.Add(new CutPoint(n, child));
    67       });
    68       CutPoint crossoverPoint0 = crossoverPoints0[random.Next(crossoverPoints0.Count)];
    69       int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
    70       int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
    71 
    72       List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
    73       parent1.Root.ForEachNodePostfix((n) => {
    74         if (n.Subtrees.Any() && n != parent1.Root)
    75           foreach (var child in n.Subtrees)
    76             if (crossoverPoint0.IsMatchingPointType(child) && (child.GetDepth() + level <= maxDepth) && (child.GetLength() + length <= maxLength))
    77               allowedBranches.Add(child);
     75          foreach (var child in n.Subtrees) {
     76            var crossoverPoint = new CutPoint(n, child);
     77            int totalDepth = parent0.Root.GetBranchLevel(child) + selectedChild.GetDepth();
     78            int totalLength = parent0.Root.GetLength() - child.GetLength() + selectedChild.GetLength();
     79            if (crossoverPoint.IsMatchingPointType(selectedChild) && totalDepth <= maxDepth && totalLength <= maxLength) {
     80              crossoverPoints.Add(crossoverPoint);
     81            }
     82          }
    7883      });
    7984
    80       // check if empty branch is allowed
    81       if (crossoverPoint0.IsMatchingPointType(null)) allowedBranches.Add(null);
     85      if (crossoverPoints.Any()) {
     86        // this loop will perform two swap operations per each crossover point
     87        foreach (var crossoverPoint in crossoverPoints) {
     88          // save the old parent so we can restore it later
     89          var parent = selectedChild.Parent;
     90          // perform a swap and check the quality of the solution
     91          swap(crossoverPoint, selectedChild);
     92          double quality = evaluator.Evaluate(context, parent0, problemData, rows);
     93          qualities.Add(new Tuple<CutPoint, double>(crossoverPoint, quality));
     94          // restore the correct parent
     95          selectedChild.Parent = parent;
     96          // swap the replaced subtree back into the tree so that the structure is preserved
     97          swap(crossoverPoint, crossoverPoint.Child);
     98        }
    8299
    83       if (allowedBranches.Count == 0)
    84         return parent0;
    85 
    86       var dataset = problemData.Dataset;
    87 
    88       // create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
    89       ISymbolicExpressionTreeNode selectedBranch = null;
    90 
    91       var nodeQualities = new List<Tuple<ISymbolicExpressionTreeNode, double>>();
    92 
    93       foreach (var node in allowedBranches) {
    94         swap(crossoverPoint0, node);
    95         double quality = evaluator.Evaluate(context, parent0, problemData, rows);
    96         nodeQualities.Add(new Tuple<ISymbolicExpressionTreeNode, double>(node, quality));
     100        qualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
     101        var crossoverPoint0 = evaluator.Maximization ? qualities.Last().Item1 : qualities.First().Item1;
     102        // swap the node that would create the best offspring
     103        // this last swap makes a total of (2 * crossoverPoints.Count() + 1) swap operations.
     104        swap(crossoverPoint0, selectedChild);
    97105      }
    98 
    99       nodeQualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order
    100 
    101       if (evaluator.Maximization)
    102         selectedBranch = nodeQualities.Last().Item1;
    103       else
    104         selectedBranch = nodeQualities.First().Item1;
    105 
    106       // swap the node that would create the best offspring
    107       swap(crossoverPoint0, selectedBranch);
    108106
    109107      return parent0;
Note: See TracChangeset for help on using the changeset viewer.