Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis.Extensions/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureManipulators/SubroutineCreater.cs @ 8812

Last change on this file since 8812 was 4803, checked in by swinkler, 14 years ago

Created branch for implementing Smalltalk representation of formulas. (#1270)

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