Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/17/12 15:18:03 (13 years ago)
Author:
bburlacu
Message:

#1682: New branch format: removed unnecessary files, merged remaining.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDepthConstrainedCrossover.cs

    r7303 r7344  
    3535  public sealed class SymbolicDataAnalysisExpressionDepthConstrainedCrossover<T> :
    3636    SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
    37     private enum Ranges { HighLevel, Standard, Lowlevel };
     37    private enum Ranges { HighLevel, Standard, LowLevel };
    3838    private const string DepthRangeParameterName = "DepthRange";
    3939    #region Parameter properties
    … …  
    5959      DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.HighLevel)));
    6060      DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.Standard)));
    61       DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.Lowlevel)));
     61      DepthRangeParameter.ValidValues.Add(new StringValue(Enum.GetName(typeof(Ranges), Ranges.LowLevel)));
    6262      Name = "DepthConstrainedCrossover";
    6363    }
    … …  
    8787    /// <returns></returns>
    8888    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, int maxDepth, int maxLength, string mode) {
    89       int depth = parent0.Root.GetDepth();
    90       var depthRange = new DoubleRange();
     89      int depth = parent0.Root.GetDepth() - 1; // subtract 1 because the tree levels are counted from 0
     90      var depthRange = new IntRange();
    9191      const int depthOffset = 2; // skip the first 2 levels (root + startNode)
    9292      switch ((int)Enum.Parse(typeof(Ranges), mode)) {
    9393        case (int)Ranges.HighLevel:
    9494          depthRange.Start = depthOffset; // skip the first 2 levels (root + startNode)
    95           depthRange.End = depthRange.Start + Math.Round(depth * 0.25);
     95          depthRange.End = depthRange.Start + (int)Math.Round(depth * 0.25);
    9696          break;
    9797        case (int)Ranges.Standard:
    98           depthRange.Start = depthOffset + Math.Round(depth * 0.25);
    99           depthRange.End = depthRange.Start + Math.Round(depth * 0.5);
     98          depthRange.Start = depthOffset + (int)Math.Round(depth * 0.25);
     99          depthRange.End = depthRange.Start + (int)Math.Round(depth * 0.5);
    100100          break;
    101         case (int)Ranges.Lowlevel:
    102           depthRange.Start = depthOffset + Math.Round(depth * 0.75);
     101        case (int)Ranges.LowLevel:
     102          depthRange.Start = depthOffset + (int)Math.Round(depth * 0.75);
    103103          depthRange.End = Math.Max(depthRange.Start, depth);
    104104          break;
    105105      }
    106106
    107       var crossoverPoints0 = new List<CutPoint>();
    108       parent0.Root.ForEachNodePostfix((n) => {
    109         if (n.Subtrees.Any() && n != parent0.Root)
    110           crossoverPoints0.AddRange(from s in n.Subtrees
    111                                     where parent0.Root.GetBranchLevel(s) >= depthRange.Start && parent0.Root.GetBranchLevel(s) <= depthRange.End
    112                                     select new CutPoint(n, s));
    113       });
     107      // make sure that the depth range does not exceeded the actual depth of parent0
     108      if (depthRange.Start > depth)
     109        depthRange.Start = depth;
     110      if (depthRange.End < depthRange.Start)
     111        depthRange.End = depthRange.Start;
     112
     113      var crossoverPoints0 = (from node in GetNodesAtDepth(parent0.Root, depthRange) select new CutPoint(node.Parent, node)).ToList();
    114114
    115115      if (crossoverPoints0.Count == 0)
    116116        throw new Exception("No crossover points available in the first parent");
    117117
    118       CutPoint crossoverPoint0 = crossoverPoints0.SelectRandom(random);
     118      var crossoverPoint0 = crossoverPoints0.SelectRandom(random);
     119
    119120      int level = parent0.Root.GetBranchLevel(crossoverPoint0.Child);
    120121      int length = parent0.Root.GetLength() - crossoverPoint0.Child.GetLength();
    121122
    122       var allowedBranches = new List<ISymbolicExpressionTreeNode>();
    123       parent1.Root.ForEachNodePostfix((n) => {
    124         if (n.Subtrees.Any() && n != parent1.Root) {
    125           allowedBranches.AddRange(from s in n.Subtrees
    126                                    let branchLevel = parent1.Root.GetBranchLevel(s)
    127                                    where branchLevel >= depthRange.Start && branchLevel <= depthRange.End && s.GetDepth() + level <= maxDepth && s.GetLength() + length <= maxLength
    128                                    select s);
     123      var allowedBranches = (from s in GetNodesAtDepth(parent1.Root, depthRange)
     124                             where
     125                               crossoverPoint0.IsMatchingPointType(s) &&
     126                               s.GetDepth() + level <= maxDepth &&
     127                               s.GetLength() + length <= maxLength
     128                             select s).ToList();
     129      if (allowedBranches.Count == 0) return parent0;
     130      var selectedBranch = allowedBranches.SelectRandom(random);
     131      swap(crossoverPoint0, selectedBranch);
     132      return parent0;
     133    }
     134
     135    private static IEnumerable<ISymbolicExpressionTreeNode> GetNodesAtDepth(ISymbolicExpressionTreeNode root, IntRange range) {
     136      var list = new List<Tuple<ISymbolicExpressionTreeNode, int>> { new Tuple<ISymbolicExpressionTreeNode, int>(root, 0) };
     137      int offset = 0;
     138      int level = 0;
     139      while (level < range.End) {
     140        ++level;
     141        int count = list.Count;
     142        for (int i = offset; i != count; ++i) {
     143          if (list[i].Item1.Subtrees.Any())
     144            list.AddRange(from s in list[i].Item1.Subtrees select new Tuple<ISymbolicExpressionTreeNode, int>(s, level));
    129145        }
    130       });
    131 
    132       if (allowedBranches.Count == 0)
    133         return parent0;
    134 
    135       var selectedBranch = allowedBranches.SelectRandom(random);
    136 
    137       swap(crossoverPoint0, selectedBranch);
    138 
    139       return parent0;
     146        offset = count;
     147      }
     148      // taking advantage of the fact that the list is already sorted by level
     149      for (int i = list.Count - 1; i >= 0; --i) {
     150        if (list[i].Item2 >= range.Start)
     151          yield return list[i].Item1;
     152        else break;
     153      }
    140154    }
    141155
Note: See TracChangeset for help on using the changeset viewer.