Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineCreater.cs @ 9834

Last change on this file since 9834 was 9456, checked in by swagner, 12 years ago

Updated copyright year and added some missing license headers (#1889)

File size: 14.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
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()
64      : base() {
65      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
66      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
67    }
68
69    public override IDeepCloneable Clone(Cloner cloner) {
70      return new SubroutineCreater(this, cloner);
71    }
72
73    public override sealed void ModifyArchitecture(
74      IRandom random,
75      ISymbolicExpressionTree symbolicExpressionTree,
76      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
77      CreateSubroutine(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
78    }
79
80    public static bool CreateSubroutine(
81      IRandom random,
82      ISymbolicExpressionTree symbolicExpressionTree,
83      int maxTreeLength, int maxTreeDepth,
84      int maxFunctionDefinitions, int maxFunctionArguments) {
85      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
86      if (functionDefiningBranches.Count() >= maxFunctionDefinitions)
87        // allowed maximum number of ADF reached => abort
88        return false;
89      if (symbolicExpressionTree.Length + 4 > maxTreeLength)
90        // defining a new function causes an length increase by 4 nodes (max) if the max tree length is reached => abort
91        return false;
92      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
93      var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
94                                 select "ADF" + index.ToString(formatString);
95
96      // select a random body (either the result producing branch or an ADF branch)
97      var bodies = from node in symbolicExpressionTree.Root.Subtrees
98                   select new { Tree = node, Length = node.GetLength() };
99      var totalNumberOfBodyNodes = bodies.Select(x => x.Length).Sum();
100      int r = random.Next(totalNumberOfBodyNodes);
101      int aggregatedNumberOfBodyNodes = 0;
102      ISymbolicExpressionTreeNode selectedBody = null;
103      foreach (var body in bodies) {
104        aggregatedNumberOfBodyNodes += body.Length;
105        if (aggregatedNumberOfBodyNodes > r)
106          selectedBody = body.Tree;
107      }
108      // sanity check
109      if (selectedBody == null) throw new InvalidOperationException();
110
111      // select a random cut point in the selected branch
112      var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
113                          from subtree in parent.Subtrees
114                          select new CutPoint(parent, subtree)).ToList();
115      if (allCutPoints.Count() == 0)
116        // no cut points => abort
117        return false;
118      string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First();
119      var selectedCutPoint = allCutPoints.SelectRandom(random);
120      // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
121      List<CutPoint> argumentCutPoints = SelectRandomArgumentBranches(selectedCutPoint.Child, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments);
122      ISymbolicExpressionTreeNode functionBody = selectedCutPoint.Child;
123      // disconnect the function body from the tree
124      selectedCutPoint.Parent.RemoveSubtree(selectedCutPoint.ChildIndex);
125      // disconnect the argument branches from the function
126      functionBody = DisconnectBranches(functionBody, argumentCutPoints);
127      // insert a function invocation symbol instead
128      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode();
129      selectedCutPoint.Parent.InsertSubtree(selectedCutPoint.ChildIndex, invokeNode);
130      // add the branches selected as argument as subtrees of the function invocation node
131      foreach (var argumentCutPoint in argumentCutPoints)
132        invokeNode.AddSubtree(argumentCutPoint.Child);
133
134      // insert a new function defining branch
135      var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
136      defunNode.FunctionName = newFunctionName;
137      defunNode.AddSubtree(functionBody);
138      symbolicExpressionTree.Root.AddSubtree(defunNode);
139      // the grammar in the newly defined function is a clone of the grammar of the originating branch
140      defunNode.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBody.Grammar.Clone());
141
142      var allowedChildSymbols = selectedBody.Grammar.GetAllowedChildSymbols(selectedBody.Symbol);
143      foreach (var allowedChildSymbol in allowedChildSymbols)
144        defunNode.Grammar.AddAllowedChildSymbol(defunNode.Symbol, allowedChildSymbol);
145      var maxSubtrees = selectedBody.Grammar.GetMaximumSubtreeCount(selectedBody.Symbol);
146      for (int i = 0; i < maxSubtrees; i++) {
147        foreach (var allowedChildSymbol in selectedBody.Grammar.GetAllowedChildSymbols(selectedBody.Symbol, i))
148          defunNode.Grammar.AddAllowedChildSymbol(defunNode.Symbol, allowedChildSymbol);
149      }
150
151      // remove all argument symbols from grammar except that one contained in cutpoints
152      var oldArgumentSymbols = selectedBody.Grammar.Symbols.OfType<Argument>().ToList();
153      foreach (var oldArgSymb in oldArgumentSymbols)
154        defunNode.Grammar.RemoveSymbol(oldArgSymb);
155      // find unique argument indexes and matching symbols in the function defining branch
156      var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()
157                                select node.Symbol.ArgumentIndex).Distinct();
158      // add argument symbols to grammar of function defining branch
159      GrammarModifier.AddArgumentSymbol(selectedBody.Grammar, defunNode.Grammar, newArgumentIndexes, argumentCutPoints);
160      defunNode.NumberOfArguments = newArgumentIndexes.Count();
161      if (defunNode.NumberOfArguments != argumentCutPoints.Count) throw new InvalidOperationException();
162      // add invoke symbol for newly defined function to the original branch
163      GrammarModifier.AddInvokeSymbol(selectedBody.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
164
165      // when the new function body was taken from another function definition
166      // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch
167      if (selectedBody.Symbol is Defun) {
168        var originalFunctionDefinition = selectedBody as DefunTreeNode;
169        foreach (var subtree in symbolicExpressionTree.Root.Subtrees) {
170          var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
171                                            where symb.FunctionName == originalFunctionDefinition.FunctionName
172                                            select symb).SingleOrDefault();
173          // when the original branch can be invoked from the subtree then also allow invocation of the function
174          if (originalBranchInvokeSymbol != null) {
175            GrammarModifier.AddInvokeSymbol(subtree.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
176          }
177        }
178      }
179      return true;
180    }
181
182    private static ISymbolicExpressionTreeNode DisconnectBranches(ISymbolicExpressionTreeNode node, List<CutPoint> argumentCutPoints) {
183      int argumentIndex = argumentCutPoints.FindIndex(x => x.Child == node);
184      if (argumentIndex != -1) {
185        var argSymbol = new Argument(argumentIndex);
186        return argSymbol.CreateTreeNode();
187      }
188      // remove the subtrees so that we can clone only the root node
189      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
190      while (node.Subtrees.Count() > 0) node.RemoveSubtree(0);
191      // recursively apply function for subtrees or append a argument terminal node
192      foreach (var subtree in subtrees) {
193        node.AddSubtree(DisconnectBranches(subtree, argumentCutPoints));
194      }
195      return node;
196    }
197
198    private static List<CutPoint> SelectRandomArgumentBranches(ISymbolicExpressionTreeNode selectedRoot,
199      IRandom random,
200      double cutProbability,
201      int maxArguments) {
202      // breadth first determination of argument cut-off points
203      // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit
204      List<CutPoint> argumentBranches = new List<CutPoint>();
205      if (selectedRoot is ArgumentTreeNode) {
206        argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
207        return argumentBranches;
208      } else {
209        // get the number of argument nodes (which must be cut-off) in the sub-trees
210        var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.Subtrees
211                                           let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count()
212                                           select nArgumentsInTree).ToList();
213        // determine the minimal number of new argument nodes for each sub-tree
214        //if we exceed the maxArguments return the same cutpoint as the start cutpoint to create a ADF that returns only its argument
215        var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
216        if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
217          argumentBranches.Add(new CutPoint(selectedRoot.Parent, 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() })
223                             .OrderBy(x => x.OrderValue)
224                             .Select(x => x.Index);
225        foreach (var subtreeIndex in randomIndexes) {
226          var subtree = selectedRoot.GetSubtree(subtreeIndex);
227          minNewArgumentsForSubtrees[subtreeIndex] = 0;
228          // => cut-off at 0..n points somewhere in the current sub-tree
229          // determine the maximum number of new arguments that should be created in the branch
230          // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left
231          int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum();
232          // when no argument is allowed from the current branch then we have to include the whole branch into the function
233          // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch
234          if (maxArgumentsFromBranch == 0) {
235            // don't cut at all => the whole sub-tree branch is included in the function body
236            // (we already checked ahead of time that there are no arguments left over in the subtree)
237          } else if (random.NextDouble() >= cutProbability) {
238            argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch));
239          } else {
240            // cut-off at current sub-tree
241            argumentBranches.Add(new CutPoint(subtree.Parent, subtree));
242          }
243        }
244        return argumentBranches;
245      }
246    }
247  }
248}
Note: See TracBrowser for help on using the repository browser.