source: branches/2520_PersistenceReintegration/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineCreater.cs @ 16453

Last change on this file since 16453 was 16453, checked in by jkarder, 12 months ago

#2520: updated year of copyrights

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