Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/ArchitectureManipulators/SubroutineCreater.cs @ 15675

Last change on this file since 15675 was 15583, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers

File size: 14.8 KB
RevLine 
[3294]1#region License Information
2/* HeuristicLab
[15583]3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[3294]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;
[4068]23using System.Collections.Generic;
[3294]24using System.Linq;
[4068]25using System.Text;
[4722]26using HeuristicLab.Common;
[3294]27using HeuristicLab.Core;
28using HeuristicLab.Data;
[5686]29using HeuristicLab.Parameters;
[3294]30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[12422]31using HeuristicLab.Random;
[3294]32
[5499]33namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
[3294]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>
[5510]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")]
[3294]40  [StorableClass]
[5510]41  public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
[3360]42    private const double ARGUMENT_CUTOFF_PROBABILITY = 0.05;
[5510]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
[4722]61    [StorableConstructor]
62    private SubroutineCreater(bool deserializing) : base(deserializing) { }
63    private SubroutineCreater(SubroutineCreater original, Cloner cloner) : base(original, cloner) { }
[5686]64    public SubroutineCreater()
65      : base() {
[5510]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    }
[4722]69
70    public override IDeepCloneable Clone(Cloner cloner) {
71      return new SubroutineCreater(this, cloner);
72    }
73
[3294]74    public override sealed void ModifyArchitecture(
75      IRandom random,
[5510]76      ISymbolicExpressionTree symbolicExpressionTree,
77      IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
78      CreateSubroutine(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
[3294]79    }
80
81    public static bool CreateSubroutine(
82      IRandom random,
[5510]83      ISymbolicExpressionTree symbolicExpressionTree,
84      int maxTreeLength, int maxTreeDepth,
85      int maxFunctionDefinitions, int maxFunctionArguments) {
[3294]86      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
[5510]87      if (functionDefiningBranches.Count() >= maxFunctionDefinitions)
[3294]88        // allowed maximum number of ADF reached => abort
89        return false;
[5549]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
[3360]92        return false;
[5510]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)
[3294]95                                 select "ADF" + index.ToString(formatString);
[3360]96
97      // select a random body (either the result producing branch or an ADF branch)
[5733]98      var bodies = from node in symbolicExpressionTree.Root.Subtrees
[5549]99                   select new { Tree = node, Length = node.GetLength() };
100      var totalNumberOfBodyNodes = bodies.Select(x => x.Length).Sum();
[3294]101      int r = random.Next(totalNumberOfBodyNodes);
102      int aggregatedNumberOfBodyNodes = 0;
[5510]103      ISymbolicExpressionTreeNode selectedBody = null;
[3294]104      foreach (var body in bodies) {
[5549]105        aggregatedNumberOfBodyNodes += body.Length;
[3294]106        if (aggregatedNumberOfBodyNodes > r)
107          selectedBody = body.Tree;
108      }
109      // sanity check
110      if (selectedBody == null) throw new InvalidOperationException();
[3360]111
112      // select a random cut point in the selected branch
[5686]113      var allCutPoints = (from parent in selectedBody.IterateNodesPrefix()
[5733]114                          from subtree in parent.Subtrees
[5686]115                          select new CutPoint(parent, subtree)).ToList();
[12422]116      if (!allCutPoints.Any())
[3294]117        // no cut points => abort
118        return false;
[3360]119      string newFunctionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.FunctionName)).First();
[12422]120      var selectedCutPoint = allCutPoints.SampleRandom(random);
121
[3294]122      // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
[5686]123      List<CutPoint> argumentCutPoints = SelectRandomArgumentBranches(selectedCutPoint.Child, random, ARGUMENT_CUTOFF_PROBABILITY, maxFunctionArguments);
124      ISymbolicExpressionTreeNode functionBody = selectedCutPoint.Child;
[3294]125      // disconnect the function body from the tree
[5733]126      selectedCutPoint.Parent.RemoveSubtree(selectedCutPoint.ChildIndex);
[3294]127      // disconnect the argument branches from the function
[5686]128      functionBody = DisconnectBranches(functionBody, argumentCutPoints);
[3360]129      // insert a function invocation symbol instead
130      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction(newFunctionName)).CreateTreeNode();
[5733]131      selectedCutPoint.Parent.InsertSubtree(selectedCutPoint.ChildIndex, invokeNode);
[3360]132      // add the branches selected as argument as subtrees of the function invocation node
[5686]133      foreach (var argumentCutPoint in argumentCutPoints)
[5733]134        invokeNode.AddSubtree(argumentCutPoint.Child);
[3294]135
136      // insert a new function defining branch
137      var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
[3360]138      defunNode.FunctionName = newFunctionName;
[5733]139      defunNode.AddSubtree(functionBody);
140      symbolicExpressionTree.Root.AddSubtree(defunNode);
[3360]141      // the grammar in the newly defined function is a clone of the grammar of the originating branch
[5510]142      defunNode.SetGrammar((ISymbolicExpressionTreeGrammar)selectedBody.Grammar.Clone());
[8148]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
[5686]153      // remove all argument symbols from grammar except that one contained in cutpoints
154      var oldArgumentSymbols = selectedBody.Grammar.Symbols.OfType<Argument>().ToList();
[3360]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
[5686]161      GrammarModifier.AddArgumentSymbol(selectedBody.Grammar, defunNode.Grammar, newArgumentIndexes, argumentCutPoints);
[3360]162      defunNode.NumberOfArguments = newArgumentIndexes.Count();
[5686]163      if (defunNode.NumberOfArguments != argumentCutPoints.Count) throw new InvalidOperationException();
[3360]164      // add invoke symbol for newly defined function to the original branch
[5686]165      GrammarModifier.AddInvokeSymbol(selectedBody.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
[3360]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;
[5733]171        foreach (var subtree in symbolicExpressionTree.Root.Subtrees) {
[3360]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) {
[5686]177            GrammarModifier.AddInvokeSymbol(subtree.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
[3360]178          }
179        }
[3294]180      }
181      return true;
182    }
183
[5686]184    private static ISymbolicExpressionTreeNode DisconnectBranches(ISymbolicExpressionTreeNode node, List<CutPoint> argumentCutPoints) {
185      int argumentIndex = argumentCutPoints.FindIndex(x => x.Child == node);
186      if (argumentIndex != -1) {
[3360]187        var argSymbol = new Argument(argumentIndex);
188        return argSymbol.CreateTreeNode();
189      }
[3294]190      // remove the subtrees so that we can clone only the root node
[5733]191      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
192      while (node.Subtrees.Count() > 0) node.RemoveSubtree(0);
[3294]193      // recursively apply function for subtrees or append a argument terminal node
194      foreach (var subtree in subtrees) {
[5733]195        node.AddSubtree(DisconnectBranches(subtree, argumentCutPoints));
[3294]196      }
197      return node;
198    }
199
[5686]200    private static List<CutPoint> SelectRandomArgumentBranches(ISymbolicExpressionTreeNode selectedRoot,
[3294]201      IRandom random,
[3360]202      double cutProbability,
[3294]203      int maxArguments) {
[3360]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
[5686]206      List<CutPoint> argumentBranches = new List<CutPoint>();
[3360]207      if (selectedRoot is ArgumentTreeNode) {
[5686]208        argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
[3360]209        return argumentBranches;
210      } else {
211        // get the number of argument nodes (which must be cut-off) in the sub-trees
[5733]212        var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.Subtrees
[3360]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
[5686]216        //if we exceed the maxArguments return the same cutpoint as the start cutpoint to create a ADF that returns only its argument
[3360]217        var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
218        if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
[5686]219          argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
[3360]220          return argumentBranches;
[3294]221        }
[3360]222        // cut-off in the sub-trees in random order
[5733]223        var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.Subtrees.Count())
[5686]224                             select new { Index = index, OrderValue = random.NextDouble() })
225                             .OrderBy(x => x.OrderValue)
226                             .Select(x => x.Index);
[3360]227        foreach (var subtreeIndex in randomIndexes) {
[5733]228          var subtree = selectedRoot.GetSubtree(subtreeIndex);
[3360]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
[5686]243            argumentBranches.Add(new CutPoint(subtree.Parent, subtree));
[3360]244          }
245        }
246        return argumentBranches;
[3294]247      }
248    }
249  }
250}
Note: See TracBrowser for help on using the repository browser.