#region License Information /* HeuristicLab * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.DataAnalysis.Symbolic { [Item("DepthConstrainedCrossover", "An operator which performs subtree swapping within a specific depth range. The range parameter controls the crossover behavior:\n" + "- HighLevel (upper 25% of the tree)\n" + "- Standard (mid 50% of the tree)\n" + "- LowLevel (lower 25% of the tree)")] public sealed class SymbolicDataAnalysisExpressionDepthConstrainedCrossover : SymbolicDataAnalysisExpressionCrossover where T : class, IDataAnalysisProblemData { private enum Ranges { HighLevel, Standard, LowLevel }; private const string DepthRangeParameterName = "DepthRange"; #region Parameter properties public ConstrainedValueParameter DepthRangeParameter { get { return (ConstrainedValueParameter)Parameters[DepthRangeParameterName]; } } #endregion #region Properties public StringValue DepthRange { get { return (StringValue)DepthRangeParameter.ActualValue; } } #endregion [StorableConstructor] private SymbolicDataAnalysisExpressionDepthConstrainedCrossover(bool deserializing) : base(deserializing) { } private SymbolicDataAnalysisExpressionDepthConstrainedCrossover(SymbolicDataAnalysisExpressionCrossover original, Cloner cloner) : base(original, cloner) { } public SymbolicDataAnalysisExpressionDepthConstrainedCrossover() : base() { Parameters.Add(new ConstrainedValueParameter(DepthRangeParameterName, "Depth range specifier")); DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.HighLevel)).AsReadOnly()); DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.Standard)).AsReadOnly()); DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.LowLevel)).AsReadOnly()); name = "DepthConstrainedCrossover"; } public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionDepthConstrainedCrossover(this, cloner); } public override ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) { return Cross(random, parent0, parent1, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value, DepthRange.Value); } /// /// Takes two parent individuals P0 and P1. /// Randomly choose nodes that fall within the specified depth range in both parents. /// /// Pseudo-random number generator. /// First parent. /// Second parent. /// Maximum allowed length depth. /// Maximum allowed tree length. /// Controls the crossover behavior: /// - HighLevel (upper 25% of the tree), /// - Standard (mid 50%) /// - LowLevel (low 25%) /// public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, int maxDepth, int maxLength, string mode) { int depth = parent0.Root.GetDepth() - 1; // substract 1 because the tree levels are counted from 0 var depthRange = new IntRange(); const int depthOffset = 2; // skip the first 2 levels (root + startNode) switch ((int)Enum.Parse(typeof(Ranges), mode)) { case (int)Ranges.HighLevel: depthRange.Start = depthOffset; // skip the first 2 levels (root + startNode) depthRange.End = depthRange.Start + (int)Math.Round(depth * 0.25); break; case (int)Ranges.Standard: depthRange.Start = depthOffset + (int)Math.Round(depth * 0.25); depthRange.End = depthRange.Start + (int)Math.Round(depth * 0.5); break; case (int)Ranges.LowLevel: depthRange.Start = depthOffset + (int)Math.Round(depth * 0.75); depthRange.End = Math.Max(depthRange.Start, depth); break; } // make sure that the depth range does not exceeded the actual depth of parent0 if (depthRange.Start > depth) depthRange.Start = depth; if (depthRange.End < depthRange.Start) depthRange.End = depthRange.Start; var crossoverPoints0 = (from node in GetNodesAtDepth(parent0, depthRange) select new CutPoint(node.Parent, node)).ToList(); if (crossoverPoints0.Count == 0) throw new Exception("No crossover points available in the first parent"); var crossoverPoint0 = crossoverPoints0.SelectRandom(random); int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child); int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength(); var allowedBranches = (from s in GetNodesAtDepth(parent1, depthRange) where s.GetDepth() + level <= maxDepth where s.GetLength() + length <= maxLength where crossoverPoint0.IsMatchingPointType(s) select s).ToList(); if (allowedBranches.Count == 0) return parent0; var selectedBranch = allowedBranches.SelectRandom(random); Swap(crossoverPoint0, selectedBranch); return parent0; } private static IEnumerable GetNodesAtDepth(ISymbolicExpressionTree tree, IntRange depthRange) { var treeDepth = tree.Root.GetDepth(); return from node in tree.Root.IterateNodesPostfix() let depth = treeDepth - node.GetDepth() where depthRange.Start <= depth where depth <= depthRange.End select node; } } }