Changeset 7109
- Timestamp:
- 12/01/11 17:15:28 (13 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs
r7089 r7109 32 32 namespace HeuristicLab.Problems.DataAnalysis.Symbolic { 33 33 34 [Item("ContextAwareCrossover", "A n 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.")] 35 35 public sealed class SymbolicDataAnalysisExpressionContextAwareCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData { 36 36 [StorableConstructor] … … 56 56 /// <summary> 57 57 /// 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. 59 59 /// </summary> 60 60 public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, IExecutionContext context, 61 61 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 63 73 parent0.Root.ForEachNodePostfix((n) => { 64 74 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 } 78 83 }); 79 84 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 } 82 99 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); 97 105 } 98 99 nodeQualities.Sort((a, b) => a.Item2.CompareTo(b.Item2)); // assuming this sorts the list in ascending order100 101 if (evaluator.Maximization)102 selectedBranch = nodeQualities.Last().Item1;103 else104 selectedBranch = nodeQualities.First().Item1;105 106 // swap the node that would create the best offspring107 swap(crossoverPoint0, selectedBranch);108 106 109 107 return parent0;
Note: See TracChangeset
for help on using the changeset viewer.