[4189] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[12395] | 3 | * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[4189] | 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
[8333] | 22 | using System.Collections.Generic;
|
---|
[4189] | 23 | using System.Linq;
|
---|
[4722] | 24 | using HeuristicLab.Common;
|
---|
[4189] | 25 | using HeuristicLab.Core;
|
---|
| 26 | using HeuristicLab.Data;
|
---|
[5686] | 27 | using HeuristicLab.Parameters;
|
---|
[4189] | 28 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 29 |
|
---|
[5499] | 30 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
[4189] | 31 | [StorableClass]
|
---|
[8333] | 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 {
|
---|
[7662] | 34 | private const int MAX_TRIES = 100;
|
---|
[5499] | 35 | private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
|
---|
| 36 | private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
|
---|
| 37 | #region Parameter Properties
|
---|
| 38 | public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
|
---|
| 39 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
|
---|
| 40 | }
|
---|
| 41 | public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
|
---|
| 42 | get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
|
---|
| 43 | }
|
---|
| 44 | #endregion
|
---|
| 45 | #region Properties
|
---|
| 46 | public IntValue MaximumSymbolicExpressionTreeLength {
|
---|
| 47 | get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
|
---|
| 48 | }
|
---|
| 49 | public IntValue MaximumSymbolicExpressionTreeDepth {
|
---|
| 50 | get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
|
---|
| 51 | }
|
---|
| 52 | #endregion
|
---|
| 53 |
|
---|
[4722] | 54 | [StorableConstructor]
|
---|
[8333] | 55 | private RemoveBranchManipulation(bool deserializing) : base(deserializing) { }
|
---|
| 56 | private RemoveBranchManipulation(RemoveBranchManipulation original, Cloner cloner) : base(original, cloner) { }
|
---|
| 57 | public RemoveBranchManipulation()
|
---|
[5499] | 58 | : base() {
|
---|
| 59 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
|
---|
| 60 | Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
|
---|
| 61 | }
|
---|
[4189] | 62 |
|
---|
[4722] | 63 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
[8333] | 64 | return new RemoveBranchManipulation(this, cloner);
|
---|
[4189] | 65 | }
|
---|
| 66 |
|
---|
[5499] | 67 | protected override void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
|
---|
[8333] | 68 | RemoveRandomBranch(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
|
---|
[4189] | 69 | }
|
---|
| 70 |
|
---|
[8333] | 71 | public static void RemoveRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
|
---|
[7662] | 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;
|
---|
[8333] | 79 |
|
---|
| 80 | var nodes = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).ToList();
|
---|
[7662] | 81 | do {
|
---|
[8333] | 82 | parent = nodes.SelectRandom(random);
|
---|
[7662] | 83 | childIndex = random.Next(parent.SubtreeCount);
|
---|
| 84 | var child = parent.GetSubtree(childIndex);
|
---|
| 85 | maxLength = maxTreeLength - symbolicExpressionTree.Length + child.GetLength();
|
---|
| 86 | maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + child.GetDepth();
|
---|
[5014] | 87 |
|
---|
[7662] | 88 | allowedSymbols.Clear();
|
---|
| 89 | foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
|
---|
| 90 | // check basic properties that the new symbol must have
|
---|
| 91 | if (symbol.Name != child.Symbol.Name &&
|
---|
| 92 | symbol.InitialFrequency > 0 &&
|
---|
| 93 | parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth &&
|
---|
| 94 | parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength) {
|
---|
| 95 | allowedSymbols.Add(symbol);
|
---|
| 96 | }
|
---|
| 97 | }
|
---|
| 98 | tries++;
|
---|
| 99 | } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
|
---|
[5569] | 100 |
|
---|
[8333] | 101 | if (tries >= MAX_TRIES) return;
|
---|
| 102 | ReplaceWithMinimalTree(random, symbolicExpressionTree.Root, parent, childIndex);
|
---|
| 103 | }
|
---|
[4189] | 104 |
|
---|
[8333] | 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);
|
---|
[7662] | 129 | }
|
---|
[4189] | 130 | }
|
---|
| 131 | }
|
---|
| 132 | }
|
---|