Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 7439 was 7439, checked in by bburlacu, 12 years ago

#1772: Created branch and solution.

File size: 14.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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      // remove all argument symbols from grammar except that one contained in cutpoints
142      var oldArgumentSymbols = selectedBody.Grammar.Symbols.OfType<Argument>().ToList();
143      foreach (var oldArgSymb in oldArgumentSymbols)
144        defunNode.Grammar.RemoveSymbol(oldArgSymb);
145      // find unique argument indexes and matching symbols in the function defining branch
146      var newArgumentIndexes = (from node in defunNode.IterateNodesPrefix().OfType<ArgumentTreeNode>()
147                                select node.Symbol.ArgumentIndex).Distinct();
148      // add argument symbols to grammar of function defining branch
149      GrammarModifier.AddArgumentSymbol(selectedBody.Grammar, defunNode.Grammar, newArgumentIndexes, argumentCutPoints);
150      defunNode.NumberOfArguments = newArgumentIndexes.Count();
151      if (defunNode.NumberOfArguments != argumentCutPoints.Count) throw new InvalidOperationException();
152      // add invoke symbol for newly defined function to the original branch
153      GrammarModifier.AddInvokeSymbol(selectedBody.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
154
155      // when the new function body was taken from another function definition
156      // add invoke symbol for newly defined function to all branches that are allowed to invoke the original branch
157      if (selectedBody.Symbol is Defun) {
158        var originalFunctionDefinition = selectedBody as DefunTreeNode;
159        foreach (var subtree in symbolicExpressionTree.Root.Subtrees) {
160          var originalBranchInvokeSymbol = (from symb in subtree.Grammar.Symbols.OfType<InvokeFunction>()
161                                            where symb.FunctionName == originalFunctionDefinition.FunctionName
162                                            select symb).SingleOrDefault();
163          // when the original branch can be invoked from the subtree then also allow invocation of the function
164          if (originalBranchInvokeSymbol != null) {
165            GrammarModifier.AddInvokeSymbol(subtree.Grammar, defunNode.FunctionName, defunNode.NumberOfArguments, selectedCutPoint, argumentCutPoints);
166          }
167        }
168      }
169      return true;
170    }
171
172    private static ISymbolicExpressionTreeNode DisconnectBranches(ISymbolicExpressionTreeNode node, List<CutPoint> argumentCutPoints) {
173      int argumentIndex = argumentCutPoints.FindIndex(x => x.Child == node);
174      if (argumentIndex != -1) {
175        var argSymbol = new Argument(argumentIndex);
176        return argSymbol.CreateTreeNode();
177      }
178      // remove the subtrees so that we can clone only the root node
179      List<ISymbolicExpressionTreeNode> subtrees = new List<ISymbolicExpressionTreeNode>(node.Subtrees);
180      while (node.Subtrees.Count() > 0) node.RemoveSubtree(0);
181      // recursively apply function for subtrees or append a argument terminal node
182      foreach (var subtree in subtrees) {
183        node.AddSubtree(DisconnectBranches(subtree, argumentCutPoints));
184      }
185      return node;
186    }
187
188    private static List<CutPoint> SelectRandomArgumentBranches(ISymbolicExpressionTreeNode selectedRoot,
189      IRandom random,
190      double cutProbability,
191      int maxArguments) {
192      // breadth first determination of argument cut-off points
193      // we must make sure that we cut off all original argument nodes and that the number of new argument is smaller than the limit
194      List<CutPoint> argumentBranches = new List<CutPoint>();
195      if (selectedRoot is ArgumentTreeNode) {
196        argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
197        return argumentBranches;
198      } else {
199        // get the number of argument nodes (which must be cut-off) in the sub-trees
200        var numberOfArgumentsInSubtrees = (from subtree in selectedRoot.Subtrees
201                                           let nArgumentsInTree = subtree.IterateNodesPrefix().OfType<ArgumentTreeNode>().Count()
202                                           select nArgumentsInTree).ToList();
203        // determine the minimal number of new argument nodes for each sub-tree
204        //if we exceed the maxArguments return the same cutpoint as the start cutpoint to create a ADF that returns only its argument
205        var minNewArgumentsForSubtrees = numberOfArgumentsInSubtrees.Select(x => x > 0 ? 1 : 0).ToList();
206        if (minNewArgumentsForSubtrees.Sum() > maxArguments) {
207          argumentBranches.Add(new CutPoint(selectedRoot.Parent, selectedRoot));
208          return argumentBranches;
209        }
210        // cut-off in the sub-trees in random order
211        var randomIndexes = (from index in Enumerable.Range(0, selectedRoot.Subtrees.Count())
212                             select new { Index = index, OrderValue = random.NextDouble() })
213                             .OrderBy(x => x.OrderValue)
214                             .Select(x => x.Index);
215        foreach (var subtreeIndex in randomIndexes) {
216          var subtree = selectedRoot.GetSubtree(subtreeIndex);
217          minNewArgumentsForSubtrees[subtreeIndex] = 0;
218          // => cut-off at 0..n points somewhere in the current sub-tree
219          // determine the maximum number of new arguments that should be created in the branch
220          // as the maximum for the whole branch minus already added arguments minus minimal number of arguments still left
221          int maxArgumentsFromBranch = maxArguments - argumentBranches.Count - minNewArgumentsForSubtrees.Sum();
222          // when no argument is allowed from the current branch then we have to include the whole branch into the function
223          // otherwise: choose randomly wether to cut off immediately or wether to extend the function body into the branch
224          if (maxArgumentsFromBranch == 0) {
225            // don't cut at all => the whole sub-tree branch is included in the function body
226            // (we already checked ahead of time that there are no arguments left over in the subtree)
227          } else if (random.NextDouble() >= cutProbability) {
228            argumentBranches.AddRange(SelectRandomArgumentBranches(subtree, random, cutProbability, maxArgumentsFromBranch));
229          } else {
230            // cut-off at current sub-tree
231            argumentBranches.Add(new CutPoint(subtree.Parent, subtree));
232          }
233        }
234        return argumentBranches;
235      }
236    }
237  }
238}
Note: See TracBrowser for help on using the repository browser.