Free cookie consent management tool by TermsFeed Policy Generator

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

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

Added test classes for crossover and subroutine creater. #290 (Implement ADFs)

File size: 9.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.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
31using System.Collections.Generic;
32using System.Text;
33using System.Diagnostics;
34
35namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureAlteringOperators {
36  /// <summary>
37  /// Manipulates a symbolic expression by adding one new function-defining branch containing
38  /// a proportion of a preexisting branch and by creating a reference to the new branch.
39  /// As described in Koza, Bennett, Andre, Keane, Genetic Programming III - Darwinian Invention and Problem Solving, 1999, pp. 97
40  /// </summary>
41  [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.")]
42  [StorableClass]
43  public sealed class SubroutineCreater : SymbolicExpressionTreeArchitectureAlteringOperator {
44    public override sealed void ModifyArchitecture(
45      IRandom random,
46      SymbolicExpressionTree symbolicExpressionTree,
47      ISymbolicExpressionGrammar grammar,
48      IntValue maxTreeSize, IntValue maxTreeHeight,
49      IntValue maxFunctionDefiningBranches, IntValue maxFunctionArguments,
50      out bool success) {
51      success = CreateSubroutine(random, symbolicExpressionTree, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefiningBranches.Value, maxFunctionArguments.Value);
52    }
53
54    public static bool CreateSubroutine(
55      IRandom random,
56      SymbolicExpressionTree symbolicExpressionTree,
57      ISymbolicExpressionGrammar grammar,
58      int maxTreeSize, int maxTreeHeight,
59      int maxFunctionDefiningBranches, int maxFunctionArguments) {
60      var functionDefiningBranches = symbolicExpressionTree.IterateNodesPrefix().OfType<DefunTreeNode>();
61      if (functionDefiningBranches.Count() >= maxFunctionDefiningBranches)
62        // allowed maximum number of ADF reached => abort
63        return false;
64      string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefiningBranches) + 1).ToString(); // >= 100 functions => ###
65      var allowedFunctionNames = from index in Enumerable.Range(0, maxFunctionDefiningBranches)
66                                 select "ADF" + index.ToString(formatString);
67      // find all body branches
68      var bodies = from node in symbolicExpressionTree.IterateNodesPrefix()
69                   where node.Symbol is Defun || node.Symbol is StartSymbol
70                   select new { Tree = node, Size = node.GetSize() };
71      var totalNumberOfBodyNodes = bodies.Select(x => x.Size).Sum();
72      // select a random body
73      int r = random.Next(totalNumberOfBodyNodes);
74      int aggregatedNumberOfBodyNodes = 0;
75      SymbolicExpressionTreeNode selectedBody = null;
76      foreach (var body in bodies) {
77        aggregatedNumberOfBodyNodes += body.Size;
78        if (aggregatedNumberOfBodyNodes > r)
79          selectedBody = body.Tree;
80      }
81      // sanity check
82      if (selectedBody == null) throw new InvalidOperationException();
83      // select a random node in the selected branch
84      var allCutPoints = (from parent in IterateNodesPrefix(selectedBody)
85                          from subtree in parent.SubTrees
86                          select new { Parent = parent, ReplacedBranchIndex = parent.SubTrees.IndexOf(subtree), ReplacedBranch = subtree }).ToList();
87      if (allCutPoints.Count == 0)
88        // no cut points => abort
89        return false;
90      var selectedCutPoint = allCutPoints[random.Next(allCutPoints.Count)];
91      // select random branches as argument cut-off points (replaced by argument terminal nodes in the function)
92      List<SymbolicExpressionTreeNode> argumentBranches = SelectRandomArgumentBranches(selectedCutPoint.ReplacedBranch, random, 0.25, maxFunctionArguments);
93      string functionName = allowedFunctionNames.Except(functionDefiningBranches.Select(x => x.Name)).First();
94      SymbolicExpressionTreeNode functionBody = selectedCutPoint.ReplacedBranch;
95      // disconnect the function body from the tree
96      selectedCutPoint.Parent.RemoveSubTree(selectedCutPoint.ReplacedBranchIndex);
97      // disconnect the argument branches from the function
98      DisconnectBranches(functionBody, argumentBranches);
99      // and insert a function invocation symbol instead
100      var invokeNode = (InvokeFunctionTreeNode)(new InvokeFunction()).CreateTreeNode();
101      invokeNode.InvokedFunctionName = functionName;
102      selectedCutPoint.Parent.InsertSubTree(selectedCutPoint.ReplacedBranchIndex, invokeNode);
103      foreach (var argumentBranch in argumentBranches)
104        invokeNode.AddSubTree(argumentBranch);
105
106      // insert a new function defining branch
107      var defunNode = (DefunTreeNode)(new Defun()).CreateTreeNode();
108      defunNode.Name = functionName;
109      defunNode.AddSubTree(functionBody);
110      symbolicExpressionTree.Root.AddSubTree(defunNode);
111      // copy known symbols from originating branch into new branch
112      foreach (var knownSymbol in selectedBody.DynamicSymbols) {
113        defunNode.AddDynamicSymbol(knownSymbol, selectedBody.GetDynamicSymbolArgumentCount(knownSymbol));
114      }
115      // add function arguments as known symbols to new branch
116      for (int i = 0; i < argumentBranches.Count; i++) {
117        defunNode.AddDynamicSymbol("ARG" + i);
118      }
119      // add new function name to original branch
120      selectedBody.AddDynamicSymbol(functionName, argumentBranches.Count);
121      return true;
122    }
123
124    private static void DisconnectBranches(SymbolicExpressionTreeNode node, List<SymbolicExpressionTreeNode> argumentBranches) {
125      // remove the subtrees so that we can clone only the root node
126      List<SymbolicExpressionTreeNode> subtrees = new List<SymbolicExpressionTreeNode>(node.SubTrees);
127      while (node.SubTrees.Count > 0) node.SubTrees.RemoveAt(0);
128      // recursively apply function for subtrees or append a argument terminal node
129      foreach (var subtree in subtrees) {
130        if (argumentBranches.Contains(subtree)) {
131          node.AddSubTree(MakeArgumentNode(argumentBranches.IndexOf(subtree)));
132        } else {
133          DisconnectBranches(subtree, argumentBranches);
134          node.AddSubTree(subtree);
135        }
136      }
137    }
138
139    private static SymbolicExpressionTreeNode MakeArgumentNode(int argIndex) {
140      var node = (ArgumentTreeNode)(new Argument()).CreateTreeNode();
141      node.ArgumentIndex = argIndex;
142      return node;
143    }
144
145    private static List<SymbolicExpressionTreeNode> SelectRandomArgumentBranches(SymbolicExpressionTreeNode selectedRoot,
146      IRandom random,
147      double argumentProbability,
148      int maxArguments) {
149      List<SymbolicExpressionTreeNode> argumentBranches = new List<SymbolicExpressionTreeNode>();
150      foreach (var subTree in selectedRoot.SubTrees) {
151        if (random.NextDouble() < argumentProbability) {
152          if (argumentBranches.Count < maxArguments)
153            argumentBranches.Add(subTree);
154        } else {
155          foreach (var argBranch in SelectRandomArgumentBranches(subTree, random, argumentProbability, maxArguments))
156            if (argumentBranches.Count < maxArguments)
157              argumentBranches.Add(argBranch);
158        }
159      }
160      return argumentBranches;
161    }
162
163    private static IEnumerable<SymbolicExpressionTreeNode> IterateNodesPrefix(SymbolicExpressionTreeNode tree) {
164      yield return tree;
165      foreach (var subTree in tree.SubTrees) {
166        foreach (var node in IterateNodesPrefix(subTree)) {
167          yield return node;
168        }
169      }
170    }
171
172    private static IEnumerable<string> UsedFunctionNames(SymbolicExpressionTree symbolicExpressionTree) {
173      return from node in symbolicExpressionTree.IterateNodesPrefix()
174             where node.Symbol is Defun
175             select ((DefunTreeNode)node).Name;
176    }
177
178    private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<DefunTreeNode> branches) {
179      var list = branches.ToList();
180      return list[random.Next(list.Count)];
181    }
182  }
183}
Note: See TracBrowser for help on using the repository browser.