1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2008 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 HeuristicLab.Core;
|
---|
23 | using HeuristicLab.Data;
|
---|
24 | using HeuristicLab.Random;
|
---|
25 | using System;
|
---|
26 | using System.Linq;
|
---|
27 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
28 | using System.Collections.Generic;
|
---|
29 | using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.GeneralSymbols;
|
---|
30 | using System.Text;
|
---|
31 |
|
---|
32 | namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
|
---|
33 | [StorableClass]
|
---|
34 | [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
|
---|
35 | public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {
|
---|
36 |
|
---|
37 | public ProbabilisticTreeCreator()
|
---|
38 | : base() {
|
---|
39 | }
|
---|
40 |
|
---|
41 | protected override SymbolicExpressionTree Create(
|
---|
42 | IRandom random,
|
---|
43 | ISymbolicExpressionGrammar grammar,
|
---|
44 | IntValue maxTreeSize, IntValue maxTreeHeight,
|
---|
45 | IntValue maxFunctionDefinitions, IntValue maxFunctionArguments) {
|
---|
46 | return Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value, maxFunctionDefinitions.Value, maxFunctionArguments.Value);
|
---|
47 | }
|
---|
48 |
|
---|
49 | public static SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar,
|
---|
50 | int maxTreeSize, int maxTreeHeight,
|
---|
51 | int maxFunctionDefinitions, int maxFunctionArguments
|
---|
52 | ) {
|
---|
53 | // tree size is limited by the grammar and by the explicit size constraints
|
---|
54 | int allowedMinSize = grammar.GetMinExpressionLength(grammar.StartSymbol);
|
---|
55 | int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(grammar.StartSymbol));
|
---|
56 | // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
|
---|
57 | int treeSize = random.Next(allowedMinSize, allowedMaxSize);
|
---|
58 | SymbolicExpressionTree tree = new SymbolicExpressionTree();
|
---|
59 | do {
|
---|
60 | try {
|
---|
61 | tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1, maxFunctionDefinitions, maxFunctionArguments);
|
---|
62 | }
|
---|
63 | catch (ArgumentException) {
|
---|
64 | // try a different size
|
---|
65 | treeSize = random.Next(allowedMinSize, allowedMaxSize);
|
---|
66 | }
|
---|
67 | } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
|
---|
68 | return tree;
|
---|
69 | }
|
---|
70 |
|
---|
71 | private class TreeExtensionPoint {
|
---|
72 | public SymbolicExpressionTreeNode Parent { get; set; }
|
---|
73 | public int ChildIndex { get; set; }
|
---|
74 | public int ExtensionPointDepth { get; set; }
|
---|
75 | }
|
---|
76 | public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol,
|
---|
77 | int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
|
---|
78 | SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
|
---|
79 | root.Grammar = grammar;
|
---|
80 | if (size <= 1 || maxDepth <= 1) return root;
|
---|
81 | CreateFullTreeFromSeed(random, root, size, maxDepth, maxFunctionDefinitions, maxFunctionArguments);
|
---|
82 | return root;
|
---|
83 | }
|
---|
84 |
|
---|
85 | private static void CreateFullTreeFromSeed(IRandom random, SymbolicExpressionTreeNode root, int size, int maxDepth, int maxFunctionDefinitions, int maxFunctionArguments) {
|
---|
86 | List<TreeExtensionPoint> extensionPoints = new List<TreeExtensionPoint>();
|
---|
87 | int currentSize = 1;
|
---|
88 | int totalListMinSize = root.Grammar.GetMinExpressionLength(root.Symbol) - 1;
|
---|
89 | int actualArity = SampleArity(random, root, size);
|
---|
90 | for (int i = 0; i < actualArity; i++) {
|
---|
91 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
92 | var dummy = new SymbolicExpressionTreeNode();
|
---|
93 | root.AddSubTree(dummy);
|
---|
94 | dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
|
---|
95 | extensionPoints.Add(new TreeExtensionPoint { Parent = root, ChildIndex = i, ExtensionPointDepth = 2 });
|
---|
96 | }
|
---|
97 | // while there are pending extension points and we have not reached the limit of adding new extension points
|
---|
98 | while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
|
---|
99 | int randomIndex = random.Next(extensionPoints.Count);
|
---|
100 | TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
|
---|
101 | extensionPoints.RemoveAt(randomIndex);
|
---|
102 | SymbolicExpressionTreeNode parent = nextExtension.Parent;
|
---|
103 | int argumentIndex = nextExtension.ChildIndex;
|
---|
104 | int extensionDepth = nextExtension.ExtensionPointDepth;
|
---|
105 | if (extensionDepth + parent.Grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
|
---|
106 | ReplaceWithMinimalTree(random, root, parent, argumentIndex, maxFunctionDefinitions, maxFunctionArguments);
|
---|
107 | //parent.RemoveSubTree(argumentIndex);
|
---|
108 | //var allowedSymbols = from s in parent.Grammar.Symbols
|
---|
109 | // where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
|
---|
110 | // select s;
|
---|
111 | //SymbolicExpressionTreeNode branch = CreateMinimalTree(random, parent, allowedSymbols);
|
---|
112 | //parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
|
---|
113 | //currentSize += branch.GetSize();
|
---|
114 | //totalListMinSize -= branch.GetSize();
|
---|
115 | } else {
|
---|
116 | var allowedSymbols = from s in parent.Grammar.Symbols
|
---|
117 | where parent.Grammar.IsAllowedChild(parent.Symbol, s, argumentIndex)
|
---|
118 | where parent.Grammar.GetMinExpressionDepth(s) + extensionDepth - 1 < maxDepth
|
---|
119 | where parent.Grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize
|
---|
120 | /*||
|
---|
121 | totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
|
---|
122 | // terminals or terminal-branches*/
|
---|
123 | // where !IsDynamicSymbol(s) || IsDynamicSymbolAllowed(grammar, root, parent, s)
|
---|
124 | select s;
|
---|
125 | Symbol selectedSymbol = SelectRandomSymbol(random, allowedSymbols);
|
---|
126 | SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
|
---|
127 | parent.RemoveSubTree(argumentIndex);
|
---|
128 | parent.InsertSubTree(argumentIndex, newTree);
|
---|
129 |
|
---|
130 | InitializeNewTreeNode(random, root, newTree, maxFunctionDefinitions, maxFunctionArguments);
|
---|
131 |
|
---|
132 | currentSize++;
|
---|
133 | totalListMinSize--;
|
---|
134 |
|
---|
135 | actualArity = SampleArity(random, newTree, size - currentSize);
|
---|
136 | for (int i = 0; i < actualArity; i++) {
|
---|
137 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
138 | var dummy = new SymbolicExpressionTreeNode();
|
---|
139 | newTree.AddSubTree(dummy);
|
---|
140 | if (IsTopLevelBranch(root, dummy))
|
---|
141 | dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
|
---|
142 | extensionPoints.Add(new TreeExtensionPoint { Parent = newTree, ChildIndex = i, ExtensionPointDepth = extensionDepth + 1 });
|
---|
143 | }
|
---|
144 | totalListMinSize += newTree.Grammar.GetMinExpressionLength(newTree.Symbol);
|
---|
145 | }
|
---|
146 | }
|
---|
147 | // fill all pending extension points
|
---|
148 | while (extensionPoints.Count > 0) {
|
---|
149 | int randomIndex = random.Next(extensionPoints.Count);
|
---|
150 | TreeExtensionPoint nextExtension = extensionPoints[randomIndex];
|
---|
151 | extensionPoints.RemoveAt(randomIndex);
|
---|
152 | SymbolicExpressionTreeNode parent = nextExtension.Parent;
|
---|
153 | int a = nextExtension.ChildIndex;
|
---|
154 | int d = nextExtension.ExtensionPointDepth;
|
---|
155 | ReplaceWithMinimalTree(random, root, parent, a, maxFunctionDefinitions, maxFunctionArguments);
|
---|
156 | }
|
---|
157 | }
|
---|
158 |
|
---|
159 | private static void ReplaceWithMinimalTree(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode parent, int argumentIndex, int maxFunctionDefinitions, int maxFunctionArguments) {
|
---|
160 | // determine possible symbols that will lead to the smallest possible tree
|
---|
161 | var possibleSymbols = (from s in parent.GetAllowedSymbols(argumentIndex)
|
---|
162 | group s by parent.Grammar.GetMinExpressionLength(s) into g
|
---|
163 | orderby g.Key
|
---|
164 | select g).First();
|
---|
165 | var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
|
---|
166 | var tree = selectedSymbol.CreateTreeNode();
|
---|
167 | parent.RemoveSubTree(argumentIndex);
|
---|
168 | parent.InsertSubTree(argumentIndex, tree);
|
---|
169 | InitializeNewTreeNode(random, root, tree, maxFunctionDefinitions, maxFunctionArguments);
|
---|
170 | for (int i = 0; i < tree.GetMinSubtreeCount(); i++) {
|
---|
171 | // insert a dummy sub-tree and add the pending extension to the list
|
---|
172 | var dummy = new SymbolicExpressionTreeNode();
|
---|
173 | tree.AddSubTree(dummy);
|
---|
174 | dummy.Grammar = (ISymbolicExpressionGrammar)dummy.Grammar.Clone();
|
---|
175 | // replace the just inserted dummy by recursive application
|
---|
176 | ReplaceWithMinimalTree(random, root, tree, i, maxFunctionDefinitions, maxFunctionArguments);
|
---|
177 | }
|
---|
178 | }
|
---|
179 |
|
---|
180 | private static void InitializeNewTreeNode(IRandom random, SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode newTree, int maxFunctionDefinitions, int maxFunctionArguments) {
|
---|
181 | // NB it is assumed that defuns are only allowed as children of root and nowhere else
|
---|
182 | // also assumes that newTree is already attached to root somewhere
|
---|
183 | if (IsTopLevelBranch(root, newTree))
|
---|
184 | newTree.Grammar = (ISymbolicExpressionGrammar)newTree.Grammar.Clone();
|
---|
185 | if (newTree.Symbol is Defun) {
|
---|
186 | var defunTree = newTree as DefunTreeNode;
|
---|
187 | string formatString = new StringBuilder().Append('0', (int)Math.Log10(maxFunctionDefinitions * 10 - 1)).ToString(); // >= 100 functions => ###
|
---|
188 | var allowedNames = from index in Enumerable.Range(0, maxFunctionDefinitions)
|
---|
189 | select "ADF" + index.ToString(formatString);
|
---|
190 | var takenNames = (from node in root.IterateNodesPrefix().OfType<DefunTreeNode>()
|
---|
191 | select node.FunctionName).Distinct();
|
---|
192 | var remainingNames = allowedNames.Except(takenNames).ToList();
|
---|
193 | string functionName = remainingNames[random.Next(remainingNames.Count)];
|
---|
194 | // set name and number of arguments of the ADF
|
---|
195 | int nArgs = random.Next(maxFunctionArguments);
|
---|
196 | defunTree.FunctionName = functionName;
|
---|
197 | defunTree.NumberOfArguments = nArgs;
|
---|
198 | if (nArgs > 0) {
|
---|
199 | AddDynamicArguments(defunTree.Grammar, nArgs);
|
---|
200 | }
|
---|
201 | int argIndex = root.SubTrees.IndexOf(newTree);
|
---|
202 | // allow invokes of ADFs with higher index
|
---|
203 | for (int i = argIndex + 1; i < root.SubTrees.Count; i++) {
|
---|
204 | var otherDefunNode = root.SubTrees[i] as DefunTreeNode;
|
---|
205 | if (otherDefunNode != null) {
|
---|
206 | var allowedParents = from sym in defunTree.Grammar.Symbols
|
---|
207 | where defunTree.Grammar.IsAllowedChild(defunTree.Symbol, sym, 0)
|
---|
208 | select sym;
|
---|
209 | var allowedChildren = allowedParents;
|
---|
210 | AddDynamicSymbol(defunTree.Grammar, allowedParents, allowedChildren, otherDefunNode.FunctionName, otherDefunNode.NumberOfArguments);
|
---|
211 | }
|
---|
212 | }
|
---|
213 | // make the ADF available as symbol for other branches (with smaller index to prevent recursions)
|
---|
214 | for (int i = 0; i < argIndex; i++) {
|
---|
215 | // if not dummy node
|
---|
216 | if (root.SubTrees[i].Symbol != null) {
|
---|
217 | var topLevelGrammar = root.SubTrees[i].Grammar;
|
---|
218 | var allowedParents = from sym in root.SubTrees[i].Grammar.Symbols
|
---|
219 | where root.SubTrees[i].Grammar.IsAllowedChild(root.SubTrees[i].Symbol, sym, 0)
|
---|
220 | select sym;
|
---|
221 | var allowedChildren = allowedParents;
|
---|
222 |
|
---|
223 | AddDynamicSymbol(topLevelGrammar, allowedParents, allowedChildren, functionName, nArgs);
|
---|
224 | }
|
---|
225 | }
|
---|
226 | }
|
---|
227 | }
|
---|
228 |
|
---|
229 | private static void AddDynamicSymbol(ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> allowedParents, IEnumerable<Symbol> allowedChildren, string symbolName, int nArgs) {
|
---|
230 | var invokeSym = new InvokeFunction(symbolName);
|
---|
231 | grammar.AddSymbol(invokeSym);
|
---|
232 | grammar.SetMinSubtreeCount(invokeSym, nArgs);
|
---|
233 | grammar.SetMaxSubtreeCount(invokeSym, nArgs);
|
---|
234 | foreach (var parent in allowedParents) {
|
---|
235 | for (int arg = 0; arg < grammar.GetMaxSubtreeCount(parent); arg++) {
|
---|
236 | grammar.SetAllowedChild(parent, invokeSym, arg);
|
---|
237 | }
|
---|
238 | }
|
---|
239 | foreach (var child in allowedChildren) {
|
---|
240 | for (int arg = 0; arg < grammar.GetMaxSubtreeCount(invokeSym); arg++) {
|
---|
241 | grammar.SetAllowedChild(invokeSym, child, arg);
|
---|
242 | }
|
---|
243 | }
|
---|
244 | }
|
---|
245 |
|
---|
246 | private static void AddDynamicArguments(ISymbolicExpressionGrammar grammar, int nArgs) {
|
---|
247 | for (int argIndex = 0; argIndex < nArgs; argIndex++) {
|
---|
248 | var argNode = new Argument(argIndex);
|
---|
249 | grammar.AddSymbol(argNode);
|
---|
250 | grammar.SetMinSubtreeCount(argNode, 0);
|
---|
251 | grammar.SetMaxSubtreeCount(argNode, 0);
|
---|
252 | // allow the argument as child of any other symbol
|
---|
253 | foreach (var symb in grammar.Symbols)
|
---|
254 | for (int i = 0; i < grammar.GetMaxSubtreeCount(symb); i++) {
|
---|
255 | grammar.SetAllowedChild(symb, argNode, i);
|
---|
256 | }
|
---|
257 | }
|
---|
258 | }
|
---|
259 |
|
---|
260 | private static bool IsTopLevelBranch(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode branch) {
|
---|
261 | return root.SubTrees.IndexOf(branch) > -1;
|
---|
262 | }
|
---|
263 |
|
---|
264 | private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
|
---|
265 | var symbolList = symbols.ToList();
|
---|
266 | var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
|
---|
267 | var r = random.NextDouble() * ticketsSum;
|
---|
268 | double aggregatedTickets = 0;
|
---|
269 | for (int i = 0; i < symbolList.Count; i++) {
|
---|
270 | aggregatedTickets += symbolList[i].InitialFrequency;
|
---|
271 | if (aggregatedTickets >= r) {
|
---|
272 | return symbolList[i];
|
---|
273 | }
|
---|
274 | }
|
---|
275 | // this should never happen
|
---|
276 | throw new ArgumentException();
|
---|
277 | }
|
---|
278 |
|
---|
279 | private static int SampleArity(IRandom random, SymbolicExpressionTreeNode node, int targetSize) {
|
---|
280 | // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
|
---|
281 | int minArity = node.GetMinSubtreeCount();
|
---|
282 | int maxArity = node.GetMaxSubtreeCount();
|
---|
283 | if (maxArity > targetSize) {
|
---|
284 | maxArity = targetSize;
|
---|
285 | }
|
---|
286 | // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree size
|
---|
287 | // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target size then minArity should be at least 2
|
---|
288 | long aggregatedLongestExpressionLength = 0;
|
---|
289 | for (int i = 0; i < maxArity; i++) {
|
---|
290 | aggregatedLongestExpressionLength += (from s in node.GetAllowedSymbols(i)
|
---|
291 | select node.Grammar.GetMaxExpressionLength(s)).Max();
|
---|
292 | if (aggregatedLongestExpressionLength < targetSize) minArity = i;
|
---|
293 | else break;
|
---|
294 | }
|
---|
295 |
|
---|
296 | // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree size
|
---|
297 | // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target size then maxArity should be at most 0
|
---|
298 | long aggregatedShortestExpressionLength = 0;
|
---|
299 | for (int i = 0; i < maxArity; i++) {
|
---|
300 | aggregatedShortestExpressionLength += (from s in node.GetAllowedSymbols(i)
|
---|
301 | select node.Grammar.GetMinExpressionLength(s)).Min();
|
---|
302 | if (aggregatedShortestExpressionLength > targetSize) {
|
---|
303 | maxArity = i;
|
---|
304 | break;
|
---|
305 | }
|
---|
306 | }
|
---|
307 | if (minArity > maxArity) throw new ArgumentException();
|
---|
308 | return random.Next(minArity, maxArity + 1);
|
---|
309 | }
|
---|
310 | }
|
---|
311 | } |
---|