Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8333


Ignore:
Timestamp:
07/26/12 14:12:26 (11 years ago)
Author:
mkommend
Message:

#1070: Added RemoveBranchManipulation to HL.Encodings.SymbolicExpressionTree.

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

    r6978 r8333  
    152152    <Compile Include="Manipulators\ChangeNodeTypeManipulation.cs" />
    153153    <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeManipulator.cs" />
     154    <Compile Include="Manipulators\RemoveBranchManipulation.cs" />
    154155    <Compile Include="Manipulators\ReplaceBranchManipulation.cs" />
    155156    <Compile Include="Manipulators\FullTreeShaker.cs" />
  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/RemoveBranchManipulation.cs

    r8330 r8333  
    2020#endregion
    2121
     22using System.Collections.Generic;
    2223using System.Linq;
    2324using HeuristicLab.Common;
     
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using System.Collections.Generic;
    2929
    3030namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3131  [StorableClass]
    32   [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
    33   public sealed class ReplaceBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
     32  [Item("RemoveBranchManipulation", "Removes a random sub-tree of the input tree and fixes the tree by generating random subtrees if necessary..")]
     33  public sealed class RemoveBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
    3434    private const int MAX_TRIES = 100;
    3535    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     
    5353
    5454    [StorableConstructor]
    55     private ReplaceBranchManipulation(bool deserializing) : base(deserializing) { }
    56     private ReplaceBranchManipulation(ReplaceBranchManipulation original, Cloner cloner) : base(original, cloner) { }
    57     public ReplaceBranchManipulation()
     55    private RemoveBranchManipulation(bool deserializing) : base(deserializing) { }
     56    private RemoveBranchManipulation(RemoveBranchManipulation original, Cloner cloner) : base(original, cloner) { }
     57    public RemoveBranchManipulation()
    5858      : base() {
    5959      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
     
    6262
    6363    public override IDeepCloneable Clone(Cloner cloner) {
    64       return new ReplaceBranchManipulation(this, cloner);
     64      return new RemoveBranchManipulation(this, cloner);
    6565    }
    6666
    6767    protected override void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
    68       ReplaceRandomBranch(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
     68      RemoveRandomBranch(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
    6969    }
    7070
    71     public static void ReplaceRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
     71    public static void RemoveRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
    7272      var allowedSymbols = new List<ISymbol>();
    7373      ISymbolicExpressionTreeNode parent;
     
    7777      // repeat until a fitting parent and child are found (MAX_TRIES times)
    7878      int tries = 0;
     79
     80      var nodes = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).ToList();
    7981      do {
    80         parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
     82        parent = nodes.SelectRandom(random);
    8183        childIndex = random.Next(parent.SubtreeCount);
    8284        var child = parent.GetSubtree(childIndex);
     
    9799      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
    98100
    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);
     101      if (tries >= MAX_TRIES) return;
     102      ReplaceWithMinimalTree(random, symbolicExpressionTree.Root, parent, childIndex);
     103    }
    106104
    107         parent.RemoveSubtree(childIndex);
    108         parent.InsertSubtree(childIndex, seedNode);
    109         ProbabilisticTreeCreator.PTC2(random, seedNode, maxLength, maxDepth);
     105    private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent, int childIndex) {
     106      // determine possible symbols that will lead to the smallest possible tree
     107      var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)
     108                             where s.InitialFrequency > 0.0
     109                             group s by parent.Grammar.GetMinimumExpressionLength(s) into g
     110                             orderby g.Key
     111                             select g).First().ToList();
     112      var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();
     113      var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
     114      var newTreeNode = selectedSymbol.CreateTreeNode();
     115      if (newTreeNode.HasLocalParameters) newTreeNode.ResetLocalParameters(random);
     116      parent.RemoveSubtree(childIndex);
     117      parent.InsertSubtree(childIndex, newTreeNode);
     118
     119      var topLevelNode = newTreeNode as SymbolicExpressionTreeTopLevelNode;
     120      if (topLevelNode != null)
     121        topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
     122
     123      for (int i = 0; i < newTreeNode.Grammar.GetMinimumSubtreeCount(newTreeNode.Symbol); i++) {
     124        // insert a dummy sub-tree and add the pending extension to the list
     125        var dummy = new SymbolicExpressionTreeNode();
     126        newTreeNode.AddSubtree(dummy);
     127        // replace the just inserted dummy by recursive application
     128        ReplaceWithMinimalTree(random, root, newTreeNode, i);
    110129      }
    111130    }
Note: See TracChangeset for help on using the changeset viewer.