Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/ArchitectureAlteringOperators/SubroutineCreater.cs @ 3534

Last change on this file since 3534 was 3534, checked in by gkronber, 14 years ago

Added interfaces for symbolic expression tree operators and added multi manipulation operators. #937 (Data types and operators for symbolic expression tree encoding)

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