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 |
|
---|
22 | using System;
|
---|
23 | using System.Linq;
|
---|
24 | using HeuristicLab.Common;
|
---|
25 | using HeuristicLab.Core;
|
---|
26 | using HeuristicLab.Data;
|
---|
27 | using HeuristicLab.Operators;
|
---|
28 | using HeuristicLab.Optimization;
|
---|
29 | using HeuristicLab.Parameters;
|
---|
30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
31 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
|
---|
32 | using System.Collections.Generic;
|
---|
33 | using System.Text;
|
---|
34 | using System.Diagnostics;
|
---|
35 |
|
---|
36 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ArchitectureManipulators {
|
---|
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.RemoveSubTree(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 | }
|
---|