Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis Refactoring/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineCreater.cs @ 5549

Last change on this file since 5549 was 5549, checked in by gkronber, 12 years ago

#1418 unified size/height vs. length/depth terminology and adapted unit tests for symbolic expression tree encoding version 3.4

File size: 14.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Parameters;
31
32namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
33  /// <summary>
34  /// Manipulates a symbolic expression by adding one new function-defining branch containing
35  /// a proportion of a preexisting branch and by creating a reference to the new branch.
36  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 97
37  /// </summary>
38  [Item("SubroutineCreater", "Manipulates a symbolic expression by adding one new function-defining branch containing a proportion of a preexisting branch and by creating a reference to the new branch. As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 97")]
39  [StorableClass]
40  public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
41    private const double ARGUMENT_CUTOFF_PROBABILITY = 0.05;
42    private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
43    private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
44    #region Parameter Properties
45    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
46      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
47    }
48    public IValueLookupParameter<IntValue> MaximumSymbolicExpressionTreeDepthParameter {
49      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeDepthParameterName]; }
50    }
51    #endregion
52    #region Properties
53    public IntValue MaximumSymbolicExpressionTreeLength {
54      get { return MaximumSymbolicExpressionTreeLengthParameter.ActualValue; }
55    }
56    public IntValue MaximumSymbolicExpressionTreeDepth {
57      get { return MaximumSymbolicExpressionTreeDepthParameter.ActualValue; }
58    }
59    #endregion
60    [StorableConstructor]
61    private SubroutineCreater(bool deserializing) : base(deserializing) { }
62    private SubroutineCreater(SubroutineCreater original, Cloner cloner) : base(original, cloner) { }
63    public SubroutineCreater() : base() {
64      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
65      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
66    }
67
68    public override IDeepCloneable Clone(Cloner cloner) {
69      return new SubroutineCreater(this, cloner);
70    }
71
72    public override sealed void ModifyArchitecture(
73      IRandom random,
74      ISymbolicExpressionTree symbolicExpressionTree,
75      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
76      CreateSubroutine(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
77    }
78
79    public static bool CreateSubroutine(
80      IRandom random,
81      ISymbolicExpressionTree symbolicExpressionTree,
82      int maxTreeLength, int maxTreeDepth,
83      int maxFunctionDefinitions, int maxFunctionArguments) {
84      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
85      if (functionDefiningBranches.Count() >= maxFunctionDefinitions)
86        // allowed maximum number of ADF reached => abort
87        return false;
88      if (symbolicExpressionTree.Length + 4 > maxTreeLength)
89        // defining a new function causes an length increase by 4 nodes (max) if the max tree length is reached => abort
90        return false;
91      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
92      var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
93                                 select "ADF" + index.ToString(formatString);
94
95      // select a random body (either the result producing branch or an ADF branch)
96      var bodies = from node in symbolicExpressionTree.Root.SubTrees
97                   select new { Tree = node, Length = node.GetLength() };
98      var totalNumberOfBodyNodes = bodies.Select(x => x.Length).Sum();
99      int r = random.Next(totalNumberOfBodyNodes);
100      int aggregatedNumberOfBodyNodes = 0;
101      ISymbolicExpressionTreeNode selectedBody = null;
102      foreach (var body in bodies) {
103        aggregatedNumberOfBodyNodes += body.Length;
104        if (aggregatedNumberOfBodyNodes > r)
105          selectedBody = body.Tree;
106      }
107      // sanity check
108      if (selectedBody == null) throw new InvalidOperationException();
109
110      // select a random cut point in the selected branch
111      var allCutPoints = from parent in selectedBody.IterateNodesPrefix()
112                         from subtree in parent.SubTrees
113                         select new { Parent = parent, ReplacedBranchIndex = parent.IndexOfSubTree(subtree), ReplacedBranch = subtree };
114      if (allCutPoints.Count() == 0)
115        // no cut points => abort
116        return false;
117      string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First();
118      var selectedCutPoint = allCutPoints.SelectRandom(random);
119      // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
120      List<ISymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments);
121      ISymbolicExpressionTreeNode functionBody = selectedCutPoint.ReplacedBranch;
122      // disconnect the function body from the tree
123      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedBranchIndex);
124      // disconnect the argument branches from the function
125      functionBody = DisconnectBranches(functionBody, argumentBranches);
126      // insert a function invocation symbol instead
127      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode();
128      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedBranchIndex, invokeNode);
129      // add the branches selected as argument as subtrees of the function invocation node
130      foreach (var argumentBranch in argumentBranches)
131        invokeNode.AddSubTree(argumentBranch);
132
133      // insert a new function defining branch
134      var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
135      defunNode.FunctionName = newFunctionName;
136      defunNode.AddSubTree(functionBody);
137      symbolicExpressionTree.Root.AddSubTree(defunNode);
138      // the grammar in the newly defined function is a clone of the grammar of the originating branch
139      defunNode.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBody.Grammar.Clone());
140      // remove all argument symbols from grammar
141      var oldArgumentSymbols = defunNode.Grammar.Symbols.OfType<Argument>().ToList();
142      foreach (var oldArgSymb in oldArgumentSymbols)
143        defunNode.Grammar.RemoveSymbol(oldArgSymb);
144      // find unique argument indexes and matching symbols in the function defining branch
145      var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()
146                                select node.Symbol.ArgumentIndex).Distinct();
147      // add argument symbols to grammar of function defining branch
148      GrammarModifier.AddDynamicArguments(defunNode.Grammar, defunNode.Symbol, newArgumentIndexes);
149      defunNode.NumberOfArguments = newArgumentIndexes.Count();
150      if (defunNode.NumberOfArguments != argumentBranches.Count) throw new InvalidOperationException();
151      // add invoke symbol for newly defined function to the original branch
152      var allowedParents = from symb in selectedBody.Grammar.Symbols
153                           where !(symb is ProgramRootSymbol)
154                           select symb;
155      var allowedChildren = from symb in selectedBody.Grammar.Symbols
156                            where selectedBody.Grammar.IsAllowedChild(selectedBody.Symbol, symb, 0)
157                            select symb;
158      GrammarModifier.AddDynamicSymbol(selectedBody.Grammar, selectedBody.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments);
159
160      // when the new function body was taken from another function definition
161      // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch
162      if (selectedBody.Symbol is Defun) {
163        var originalFunctionDefinition = selectedBody as DefunTreeNode;
164        foreach (var subtree in symbolicExpressionTree.Root.SubTrees) {
165          var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
166                                            where symb.FunctionName == originalFunctionDefinition.FunctionName
167                                            select symb).SingleOrDefault();
168          // when the original branch can be invoked from the subtree then also allow invocation of the function
169          if (originalBranchInvokeSymbol != null) {
170            allowedParents = from symb in subtree.Grammar.Symbols
171                             where !(symb is ProgramRootSymbol)
172                             select symb;
173            allowedChildren = from symb in subtree.Grammar.Symbols
174                              where subtree.Grammar.IsAllowedChild(subtree.Symbol, symb, 0)
175                              select symb;
176            GrammarModifier.AddDynamicSymbol(subtree.Grammar, subtree.Symbol, defunNode.FunctionName, defunNode.NumberOfArguments);
177          }
178        }
179      }
180      return true;
181    }
182
183    private static ISymbolicExpressionTreeNode DisconnectBranches(ISymbolicExpressionTreeNode node, List<ISymbolicExpressionTreeNode> argumentBranches) {
184      if (argumentBranches.Contains(node)) {
185        var argumentIndex = argumentBranches.IndexOf(node);
186        var argSymbol = new Argument(argumentIndex);
187        return argSymbol.CreateTreeNode();
188      }
189      // remove the subtrees so that we can clone only the root node
190      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.SubTrees);
191      while (node.SubTrees.Count() > 0) node.RemoveSubTree(0);
192      // recursively apply function for subtrees or append a argument terminal node
193      foreach (var subtree in subtrees) {
194        node.AddSubTree(DisconnectBranches(subtree, argumentBranches));
195      }
196      return node;
197    }
198
199    private static List<ISymbolicExpressionTreeNode> SelectRandomArgumentBranches(ISymbolicExpressionTreeNode selectedRoot,
200      IRandom random,
201      double cutProbability,
202      int maxArguments) {
203      // breadth first determination of argument cut-off points
204      // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit
205      List<ISymbolicExpressionTreeNode> argumentBranches = new List<ISymbolicExpressionTreeNode>();
206      if (selectedRoot is ArgumentTreeNode) {
207        argumentBranches.Add(selectedRoot);
208        return argumentBranches;
209      } else {
210        // get the number of argument nodes (which must be cut-off) in the sub-trees
211        var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.SubTrees
212                                           let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count()
213                                           select nArgumentsInTree).ToList();
214        // determine the minimal number of new argument nodes for each sub-tree
215        var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
216        if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
217          argumentBranches.Add(selectedRoot);
218          return argumentBranches;
219        }
220        // cut-off in the sub-trees in random order
221        var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.SubTrees.Count())
222                             select new { Index = index, OrderValue = random.NextDouble() }).OrderBy(x => x.OrderValue).Select(x => x.Index);
223        foreach (var subtreeIndex in randomIndexes) {
224          var subtree = selectedRoot.GetSubTree(subtreeIndex);
225          minNewArgumentsForSubtrees[subtreeIndex] = 0;
226          // => cut-off at 0..n points somewhere in the current sub-tree
227          // determine the maximum number of new arguments that should be created in the branch
228          // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left
229          int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum();
230          // when no argument is allowed from the current branch then we have to include the whole branch into the function
231          // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch
232          if (maxArgumentsFromBranch == 0) {
233            // don't cut at all => the whole sub-tree branch is included in the function body
234            // (we already checked ahead of time that there are no arguments left over in the subtree)
235          } else if (random.NextDouble() >= cutProbability) {
236            argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch));
237          } else {
238            // cut-off at current sub-tree
239            argumentBranches.Add(subtree);
240          }
241        }
242        return argumentBranches;
243      }
244    }
245  }
246}
Note: See TracBrowser for help on using the repository browser.