Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
03/28/12 15:47:26 (13 years ago)
Author:
spimming
Message:

#1680: merged changes from trunk into branch

Location:
branches/HeuristicLab.Hive.Azure
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.Hive.Azure

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

    • Property svn:mergeinfo set to (toggle deleted branches)
      /branches/GP.Symbols (TimeLag, Diff, Integral)/HeuristicLab.Encodings.SymbolicExpressionTreeEncodingmergedeligible
      /trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncodingmergedeligible
      /branches/Benchmarking/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6917-7005
      /branches/CloningRefactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding4656-4721
      /branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5471-5808
      /branches/DataAnalysis SolutionEnsembles/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5815-6180
      /branches/DataAnalysis/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding4458-4459,​4462,​4464
      /branches/GP.Grammar.Editor/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6284-6795
      /branches/HeuristicLab.Crossovers/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding7343-7503
      /branches/NET40/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5138-5162
      /branches/ParallelEngine/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5175-5192
      /branches/QAPAlgorithms/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6350-6627
      /branches/Restructure trunk solution/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6828
      /branches/SuccessProgressAnalysis/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5370-5682
      /branches/Trunk/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding6829-6865
      /branches/VNS/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5594-5752
      /branches/histogram/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding5959-6341

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Analyzers/MinAverageMaxSymbolicExpressionTreeLengthAnalyzer.cs

    r7270 r7669  
    7373    private MinAverageMaxSymbolicExpressionTreeLengthAnalyzer(MinAverageMaxSymbolicExpressionTreeLengthAnalyzer original, Cloner cloner)
    7474      : base(original, cloner) {
     75      valueAnalyzer = cloner.Clone(original.valueAnalyzer);
     76      subScopesProcessor = cloner.Clone(original.subScopesProcessor);
    7577      AfterDeserialization();
    7678    }

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Analyzers/SymbolicExpressionTreeLengthAnalyzer.cs

    r7270 r7669  
    121121        Parameters.Add(new ValueParameter<IntValue>(UpdateIntervalParameterName, "The interval in which the tree length analysis should be applied.", new IntValue(1)));
    122122      }
     123      //necessary code to correct UpdateCounterParameter - type was changed from LookupParameter to ValueParameter
     124      if (Parameters.ContainsKey(UpdateCounterParameterName) && (Parameters[UpdateCounterParameterName] is LookupParameter<IntValue>))
     125        Parameters.Remove(UpdateCounterParameterName);
    123126      if (!Parameters.ContainsKey(UpdateCounterParameterName)) {
    124127        Parameters.Add(new ValueParameter<IntValue>(UpdateCounterParameterName, "The value which counts how many times the operator was called since the last update", new IntValue(0)));

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers

    • Property svn:ignore set to
      *.bak

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SubtreeCrossover.cs

    r7270 r7669  
    3636  /// until a valid configuration is found.
    3737  /// </summary> 
    38   [Item("SubtreeCrossover", "An operator which performs subtree swapping crossover.")]
     38  [Item("SubtreeSwappingCrossover", "An operator which performs subtree swapping crossover.")]
    3939  [StorableClass]
    40   public sealed class SubtreeCrossover : SymbolicExpressionTreeCrossover, ISymbolicExpressionTreeSizeConstraintOperator {
     40  public class SubtreeCrossover : SymbolicExpressionTreeCrossover, ISymbolicExpressionTreeSizeConstraintOperator {
    4141    private const string InternalCrossoverPointProbabilityParameterName = "InternalCrossoverPointProbability";
    4242    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
    4343    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
     44
    4445    #region Parameter Properties
    4546    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
    … …  
    6566    #endregion
    6667    [StorableConstructor]
    67     private SubtreeCrossover(bool deserializing) : base(deserializing) { }
    68     private SubtreeCrossover(SubtreeCrossover original, Cloner cloner) : base(original, cloner) { }
     68    protected SubtreeCrossover(bool deserializing) : base(deserializing) { }
     69    protected SubtreeCrossover(SubtreeCrossover original, Cloner cloner) : base(original, cloner) { }
    6970    public SubtreeCrossover()
    7071      : base() {
    … …  
    7879    }
    7980
    80     protected override ISymbolicExpressionTree Cross(IRandom random,
     81    public override ISymbolicExpressionTree Crossover(IRandom random,
    8182      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
    8283      return Cross(random, parent0, parent1, InternalCrossoverPointProbability.Value,
    … …  
    9495      // calculate the max length and depth that the inserted branch can have
    9596      int maxInsertedBranchLength = maxTreeLength - (parent0.Length - childLength);
    96       int maxInsertedBranchDepth = maxTreeDepth - GetBranchLevel(parent0.Root, crossoverPoint0.Parent);
     97      int maxInsertedBranchDepth = maxTreeDepth - parent0.Root.GetBranchLevel(crossoverPoint0.Parent);
    9798
    9899      List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
    99100      parent1.Root.ForEachNodePostfix((n) => {
    100101        if (n.GetLength() <= maxInsertedBranchLength &&
    101             n.GetDepth() <= maxInsertedBranchDepth &&
    102             IsMatchingPointType(crossoverPoint0, n))
     102            n.GetDepth() <= maxInsertedBranchDepth && crossoverPoint0.IsMatchingPointType(n))
    103103          allowedBranches.Add(n);
    104104      });
    105105      // empty branch
    106       if (IsMatchingPointType(crossoverPoint0, null)) allowedBranches.Add(null);
     106      if (crossoverPoint0.IsMatchingPointType(null)) allowedBranches.Add(null);
    107107
    108108      if (allowedBranches.Count == 0) {
    … …  
    128128    }
    129129
    130     private static bool IsMatchingPointType(CutPoint cutPoint, ISymbolicExpressionTreeNode newChild) {
    131       var parent = cutPoint.Parent;
    132       if (newChild == null) {
    133         // make sure that one subtree can be removed and that only the last subtree is removed
    134         return parent.Grammar.GetMinimumSubtreeCount(parent.Symbol) < parent.SubtreeCount &&
    135           cutPoint.ChildIndex == parent.SubtreeCount - 1;
    136       } else {
    137         // check syntax constraints of direct parent - child relation
    138         if (!parent.Grammar.ContainsSymbol(newChild.Symbol) ||
    139             !parent.Grammar.IsAllowedChildSymbol(parent.Symbol, newChild.Symbol, cutPoint.ChildIndex)) return false;
    140 
    141         bool result = true;
    142         // check point type for the whole branch
    143         newChild.ForEachNodePostfix((n) => {
    144           result =
    145             result &&
    146             parent.Grammar.ContainsSymbol(n.Symbol) &&
    147             n.SubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(n.Symbol) &&
    148             n.SubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(n.Symbol);
    149         });
    150         return result;
    151       }
    152     }
    153 
    154130    private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0, double internalNodeProbability, int maxBranchLength, int maxBranchDepth, out CutPoint crossoverPoint) {
    155131      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
    … …  
    157133      List<CutPoint> leafCrossoverPoints = new List<CutPoint>();
    158134      parent0.Root.ForEachNodePostfix((n) => {
    159         if (n.Subtrees.Any() && n != parent0.Root) {
     135        if (n.SubtreeCount > 0 && n != parent0.Root) {
    160136          foreach (var child in n.Subtrees) {
    161137            if (child.GetLength() <= maxBranchLength &&
    162138                child.GetDepth() <= maxBranchDepth) {
    163               if (child.Subtrees.Any())
     139              if (child.SubtreeCount > 0)
    164140                internalCrossoverPoints.Add(new CutPoint(n, child));
    165141              else
    … …  
    167143            }
    168144          }
     145
    169146          // add one additional extension point if the number of sub trees for the symbol is not full
    170147          if (n.SubtreeCount < n.Grammar.GetMaximumSubtreeCount(n.Symbol)) {
    … …  
    173150          }
    174151        }
    175       });
     152      }
     153    );
    176154
    177155      if (random.NextDouble() < internalNodeProbability) {
    … …  
    200178        // select internal node if possible
    201179        allowedInternalBranches = (from branch in branches
    202                                    where branch != null && branch.Subtrees.Any()
     180                                   where branch != null && branch.SubtreeCount > 0
    203181                                   select branch).ToList();
    204182        if (allowedInternalBranches.Count > 0) {
    … …  
    207185          // no internal nodes allowed => select leaf nodes
    208186          allowedLeafBranches = (from branch in branches
    209                                  where branch == null || !branch.Subtrees.Any()
     187                                 where branch == null || branch.SubtreeCount == 0
    210188                                 select branch).ToList();
    211189          return allowedLeafBranches.SelectRandom(random);
    … …  
    214192        // select leaf node if possible
    215193        allowedLeafBranches = (from branch in branches
    216                                where branch == null || !branch.Subtrees.Any()
     194                               where branch == null || branch.SubtreeCount == 0
    217195                               select branch).ToList();
    218196        if (allowedLeafBranches.Count > 0) {
    … …  
    220198        } else {
    221199          allowedInternalBranches = (from branch in branches
    222                                      where branch != null && branch.Subtrees.Any()
     200                                     where branch != null && branch.SubtreeCount > 0
    223201                                     select branch).ToList();
    224202          return allowedInternalBranches.SelectRandom(random);
    … …  
    226204      }
    227205    }
    228 
    229     private static int GetBranchLevel(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode point) {
    230       if (root == point) return 0;
    231       foreach (var subtree in root.Subtrees) {
    232         int branchLevel = GetBranchLevel(subtree, point);
    233         if (branchLevel < int.MaxValue) return 1 + branchLevel;
    234       }
    235       return int.MaxValue;
    236     }
    237206  }
    238207}

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Crossovers/SymbolicExpressionTreeCrossover.cs

    r7270 r7669  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
    25 using HeuristicLab.Data;
    2625using HeuristicLab.Parameters;
    2726using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    6665        throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
    6766
    68       ISymbolicExpressionTree result = Cross(Random, Parents[0], Parents[1]);
     67      ISymbolicExpressionTree result = Crossover(Random, Parents[0], Parents[1]);
    6968
    7069      Child = result;
    … …  
    7271    }
    7372
    74     protected abstract ISymbolicExpressionTree Cross(IRandom random,
    75       ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1);
     73    public abstract ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1);
    7674  }
    7775}

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/CutPoint.cs

    r7270 r7669  
    2222
    2323namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    24   internal class CutPoint {
     24  public class CutPoint {
    2525    public ISymbolicExpressionTreeNode Parent { get; set; }
    2626    public ISymbolicExpressionTreeNode Child { get; set; }
    … …  
    3939      this.Child = null;
    4040    }
     41
     42    public bool IsMatchingPointType(ISymbolicExpressionTreeNode newChild) {
     43      var parent = this.Parent;
     44      if (newChild == null) {
     45        // make sure that one subtree can be removed and that only the last subtree is removed
     46        return parent.Grammar.GetMinimumSubtreeCount(parent.Symbol) < parent.SubtreeCount &&
     47          this.ChildIndex == parent.SubtreeCount - 1;
     48      } else {
     49        // check syntax constraints of direct parent - child relation
     50        if (!parent.Grammar.ContainsSymbol(newChild.Symbol) ||
     51            !parent.Grammar.IsAllowedChildSymbol(parent.Symbol, newChild.Symbol, this.ChildIndex))
     52          return false;
     53
     54        bool result = true;
     55        // check point type for the whole branch
     56        newChild.ForEachNodePostfix((n) => {
     57          result =
     58            result &&
     59            parent.Grammar.ContainsSymbol(n.Symbol) &&
     60            n.SubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(n.Symbol) &&
     61            n.SubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(n.Symbol);
     62        });
     63        return result;
     64      }
     65    }
    4166  }
    4267}

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/ISymbolicExpressionTreeNode.cs

    r7270 r7669  
    3232    int GetDepth();
    3333    int GetLength();
     34    int GetBranchLevel(ISymbolicExpressionTreeNode child);
    3435
    3536    IEnumerable<ISymbolicExpressionTreeNode> IterateNodesPostfix();

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Interfaces/Operators/ISymbolicExpressionTreeCrossover.cs

    r7270 r7669  
    3030    ILookupParameter<ItemArray<ISymbolicExpressionTree>> ParentsParameter { get; }
    3131    ILookupParameter<ISymbolicExpressionTree> ChildParameter { get; }
     32    ISymbolicExpressionTree Crossover(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1);
    3233  }
    3334}

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs

    r7270 r7669  
    2424using HeuristicLab.Core;
    2525using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     26using System.Collections.Generic;
    2627
    2728namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    2930  [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]
    3031  public sealed class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator {
     32    private const int MAX_TRIES = 100;
     33
    3134    [StorableConstructor]
    3235    private ChangeNodeTypeManipulation(bool deserializing) : base(deserializing) { }
    … …  
    4346
    4447    public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
    45       // select any node as parent (except the root node)
    46       var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
    47                                 let subtreeCount = parent.Subtrees.Count()
    48                                 from subtreeIndex in Enumerable.Range(0, subtreeCount)
    49                                 let subtree = parent.GetSubtree(subtreeIndex)
    50                                 let existingSubtreeCount = subtree.Subtrees.Count()
    51                                 // find possible symbols for the node (also considering the existing branches below it)
    52                                 let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
    53                                                       // do not replace the existing symbol with itself
    54                                                       where symbol.Name != subtree.Symbol.Name
    55                                                       where symbol.InitialFrequency > 0
    56                                                       where existingSubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(symbol)
    57                                                       where existingSubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(symbol)
    58                                                       // keep only symbols that are still possible considering the existing sub-trees
    59                                                       where (from existingSubtreeIndex in Enumerable.Range(0, existingSubtreeCount)
    60                                                              let existingSubtree = subtree.GetSubtree(existingSubtreeIndex)
    61                                                              select parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex))
    62                                                              .All(x => x == true)
    63                                                       select symbol)
    64                                                       .ToList()
    65                                 where allowedSymbols.Count() > 0
    66                                 select new { Parent = parent, Child = subtree, Index = subtreeIndex, AllowedSymbols = allowedSymbols })
    67                                .ToList();
    68       if (manipulationPoints.Count == 0) { return; }
    69       var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
     48      List<ISymbol> allowedSymbols = new List<ISymbol>();
     49      ISymbolicExpressionTreeNode parent;
     50      int childIndex;
     51      ISymbolicExpressionTreeNode child;
     52      // repeat until a fitting parent and child are found (MAX_TRIES times)
     53      int tries = 0;
     54      do {
     55        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
     56        childIndex = random.Next(parent.SubtreeCount);
    7057
    71       var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
    72       var newSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
     58        child = parent.GetSubtree(childIndex);
     59        int existingSubtreeCount = child.SubtreeCount;
     60        allowedSymbols.Clear();
     61        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
     62          // check basic properties that the new symbol must have
     63          if (symbol.Name != child.Symbol.Name &&
     64            symbol.InitialFrequency > 0 &&
     65            existingSubtreeCount <= parent.Grammar.GetMinimumSubtreeCount(symbol) &&
     66            existingSubtreeCount >= parent.Grammar.GetMaximumSubtreeCount(symbol)) {
     67            // check that all existing subtrees are also allowed for the new symbol
     68            bool allExistingSubtreesAllowed = true;
     69            for (int existingSubtreeIndex = 0; existingSubtreeIndex < existingSubtreeCount && allExistingSubtreesAllowed; existingSubtreeIndex++) {
     70              var existingSubtree = child.GetSubtree(existingSubtreeIndex);
     71              allExistingSubtreesAllowed &= parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex);
     72            }
     73            if (allExistingSubtreesAllowed) {
     74              allowedSymbols.Add(symbol);
     75            }
     76          }
     77        }
     78        tries++;
     79      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
    7380
    74       // replace the old node with the new node
    75       var newNode = newSymbol.CreateTreeNode();
    76       if (newNode.HasLocalParameters)
    77         newNode.ResetLocalParameters(random);
    78       foreach (var subtree in selectedManipulationPoint.Child.Subtrees)
    79         newNode.AddSubtree(subtree);
    80       selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
    81       selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, newNode);
     81      if (tries < MAX_TRIES) {
     82        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
     83        var newSymbol = allowedSymbols.SelectRandom(weights, random);
     84
     85        // replace the old node with the new node
     86        var newNode = newSymbol.CreateTreeNode();
     87        if (newNode.HasLocalParameters)
     88          newNode.ResetLocalParameters(random);
     89        foreach (var subtree in child.Subtrees)
     90          newNode.AddSubtree(subtree);
     91        parent.RemoveSubtree(childIndex);
     92        parent.InsertSubtree(childIndex, newNode);
     93      }
    8294    }
    8395  }

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ReplaceBranchManipulation.cs

    r7270 r7669  
    2626using HeuristicLab.Parameters;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using System.Collections.Generic;
    2829
    2930namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    … …  
    3132  [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
    3233  public sealed class ReplaceBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
     34    private const int MAX_TRIES = 100;
    3335    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
    3436    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
    … …  
    6870
    6971    public static void ReplaceRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
    70       // select any node as parent (except the root node)
    71       var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
    72                                 from subtree in parent.Subtrees
    73                                 let subtreeIndex = parent.IndexOfSubtree(subtree)
    74                                 let maxLength = maxTreeLength - symbolicExpressionTree.Length + subtree.GetLength()
    75                                 let maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + subtree.GetDepth()
    76                                 // find possible symbols for the node (also considering the existing branches below it)
    77                                 let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
    78                                                       // do not replace symbol with the same symbol
    79                                                       where symbol.Name != subtree.Symbol.Name
    80                                                       where symbol.InitialFrequency > 0
    81                                                       where parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth
    82                                                       where parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength
    83                                                       select symbol)
    84                                                       .ToList()
    85                                 where allowedSymbols.Count > 0
    86                                 select new {
    87                                   Parent = parent,
    88                                   Child = subtree,
    89                                   Index = subtreeIndex,
    90                                   AllowedSymbols = allowedSymbols,
    91                                   MaxLength = maxLength,
    92                                   MaxDepth = maxDepth
    93                                 })
    94                                .ToList();
     72      var allowedSymbols = new List<ISymbol>();
     73      ISymbolicExpressionTreeNode parent;
     74      int childIndex;
     75      int maxLength;
     76      int maxDepth;
     77      // repeat until a fitting parent and child are found (MAX_TRIES times)
     78      int tries = 0;
     79      do {
     80        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
     81        childIndex = random.Next(parent.SubtreeCount);
     82        var child = parent.GetSubtree(childIndex);
     83        maxLength = maxTreeLength - symbolicExpressionTree.Length + child.GetLength();
     84        maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + child.GetDepth();
    9585
    96       if (manipulationPoints.Count == 0) return;
    97       var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
     86        allowedSymbols.Clear();
     87        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
     88          // check basic properties that the new symbol must have
     89          if (symbol.Name != child.Symbol.Name &&
     90            symbol.InitialFrequency > 0 &&
     91            parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth &&
     92            parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength) {
     93            allowedSymbols.Add(symbol);
     94          }
     95        }
     96        tries++;
     97      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
    9898
    99       var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
    100       var seedSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
    101       // replace the old node with the new node
    102       var seedNode = seedSymbol.CreateTreeNode();
    103       if (seedNode.HasLocalParameters)
    104         seedNode.ResetLocalParameters(random);
     99      if (tries < MAX_TRIES) {
     100        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
     101        var seedSymbol = allowedSymbols.SelectRandom(weights, random);
     102        // replace the old node with the new node
     103        var seedNode = seedSymbol.CreateTreeNode();
     104        if (seedNode.HasLocalParameters)
     105          seedNode.ResetLocalParameters(random);
    105106
    106       selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
    107       selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, seedNode);
    108       ProbabilisticTreeCreator.PTC2(random, seedNode, selectedManipulationPoint.MaxLength, selectedManipulationPoint.MaxDepth);
     107        parent.RemoveSubtree(childIndex);
     108        parent.InsertSubtree(childIndex, seedNode);
     109        ProbabilisticTreeCreator.PTC2(random, seedNode, maxLength, maxDepth);
     110      }
    109111    }
    110112  }

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs

    r7270 r7669  
    308308    }
    309309    public virtual IEnumerable<ISymbol> AllowedSymbols {
    310       get { return Symbols.Where(s => s.Enabled); }
     310      get { foreach (var s in Symbols) if (s.Enabled) yield return s; }
    311311    }
    312312    public virtual bool ContainsSymbol(ISymbol symbol) {
    … …  
    316316    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
    317317    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
     318      if (allowedChildSymbols.Count == 0) return false;
    318319      if (!child.Enabled) return false;
    319320
    320321      bool result;
    321       if (cachedIsAllowedChildSymbol.TryGetValue(Tuple.Create(parent.Name, child.Name), out result)) return result;
     322      var key = Tuple.Create(parent.Name, child.Name);
     323      if (cachedIsAllowedChildSymbol.TryGetValue(key, out result)) return result;
     324
    322325      List<string> temp;
    323326      if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
    324327        //if (temp.Contains(child.Name)) return true;
    325         if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
    326           cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), true);
     328        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
     329          cachedIsAllowedChildSymbol.Add(key, true);
    327330          return true;
    328331        }
    329332      }
    330       cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), false);
     333      cachedIsAllowedChildSymbol.Add(key, false);
    331334      return false;
    332335    }
    … …  
    336339      if (!child.Enabled) return false;
    337340      if (IsAllowedChildSymbol(parent, child)) return true;
     341      if (allowedChildSymbolsPerIndex.Count == 0) return false;
    338342
    339343      bool result;
    340       if (cachedIsAllowedChildSymbolIndex.TryGetValue(Tuple.Create(parent.Name, child.Name, argumentIndex), out result)) return result;
     344      var key = Tuple.Create(parent.Name, child.Name, argumentIndex);
     345      if (cachedIsAllowedChildSymbolIndex.TryGetValue(key, out result)) return result;
     346
    341347      List<string> temp;
    342       var key = Tuple.Create(parent.Name, argumentIndex);
    343       if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp)) {
    344         //if (temp.Contains(child.Name)) return true;
    345         if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
    346           cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), true);
     348      if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, argumentIndex), out temp)) {
     349        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Any(s => s.Name == child.Name)) {
     350          cachedIsAllowedChildSymbolIndex.Add(key, true);
    347351          return true;
    348352        }
    349353      }
    350       cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), false);
     354      cachedIsAllowedChildSymbolIndex.Add(key, false);
    351355      return false;
    352356    }
    353357
    354358    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
    355       return from child in AllowedSymbols
    356              where IsAllowedChildSymbol(parent, child)
    357              select child;
     359      foreach (ISymbol child in AllowedSymbols) {
     360        if (IsAllowedChildSymbol(parent, child)) yield return child;
     361      }
    358362    }
    359363
    360364    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
    361       return from child in AllowedSymbols
    362              where IsAllowedChildSymbol(parent, child, argumentIndex)
    363              select child;
     365      foreach (ISymbol child in AllowedSymbols) {
     366        if (IsAllowedChildSymbol(parent, child, argumentIndex)) yield return child;
     367      }
    364368    }
    365369

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeGrammar.cs

    r7270 r7669  
    2222using System;
    2323using System.Collections.Generic;
    24 using System.Linq;
    2524using HeuristicLab.Common;
    2625using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    5150
    5251    public override IEnumerable<ISymbol> Symbols {
    53       get { return grammar.Symbols.Union(base.Symbols); }
     52      get {
     53        foreach (var s in grammar.Symbols) yield return s;
     54        foreach (var s in base.symbols.Values) yield return s;
     55      }
    5456    }
    5557    public override IEnumerable<ISymbol> AllowedSymbols {

  • branches/HeuristicLab.Hive.Azure/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionTreeNode.cs

    r7270 r7669  
    5555      : base() {
    5656      symbol = original.symbol; // symbols are reused
     57      length = original.length;
     58      depth = original.depth;
    5759      if (original.subtrees != null) {
    5860        subtrees = new List<ISymbolicExpressionTreeNode>(original.subtrees.Count);
    … …  
    125127    }
    126128
     129    public int GetBranchLevel(ISymbolicExpressionTreeNode child) {
     130      return GetBranchLevel(this, child);
     131    }
     132
     133    private static int GetBranchLevel(ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode point) {
     134      if (root == point)
     135        return 0;
     136      foreach (var subtree in root.Subtrees) {
     137        int branchLevel = GetBranchLevel(subtree, point);
     138        if (branchLevel < int.MaxValue)
     139          return 1 + branchLevel;
     140      }
     141      return int.MaxValue;
     142    }
     143
    127144    public virtual void ResetLocalParameters(IRandom random) { }
    128145    public virtual void ShakeLocalParameters(IRandom random, double shakingFactor) { }
Note: See TracChangeset for help on using the changeset viewer.