Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs @ 3270

Last change on this file since 3270 was 3270, checked in by gkronber, 13 years ago

Changed PTC2 initialization operator for symbolic expression tree encoding to select symbols based on the number of tickets. #937 (Data types and operators for symbolic expression tree encoding)

File size: 9.6 KB
Line 
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
22using HeuristicLab.Core;
23using HeuristicLab.Data;
24using HeuristicLab.Random;
25using System;
26using System.Linq;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using System.Collections.Generic;
29
30namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
31  [StorableClass]
32  [Item("ProbabilisticTreeCreator", "An operator that creates new symbolic expression trees with uniformly distributed size")]
33  public class ProbabilisticTreeCreator : SymbolicExpressionTreeCreator {
34    public ProbabilisticTreeCreator()
35      : base() {
36    }
37
38    protected override SymbolicExpressionTree Create(IRandom random, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight) {
39      return Apply(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);
40    }
41
42    public SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar, int maxTreeSize, int maxTreeHeight) {
43      // tree size is limited by the grammar and by the explicit size constraints
44      int allowedMinSize = grammar.MinimalExpressionLength(grammar.StartSymbol);
45      int allowedMaxSize = Math.Min(maxTreeSize, grammar.MaximalExpressionLength(grammar.StartSymbol));
46      // select a target tree size uniformly in the possible range (as determined by explicit limits and limits of the grammar)
47      int treeSize = random.Next(allowedMinSize, allowedMaxSize);
48      SymbolicExpressionTree tree = new SymbolicExpressionTree();
49      do {
50        try {
51          tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1);
52        }
53        catch (ArgumentException) {
54          // try a different size
55          treeSize = random.Next(allowedMinSize, allowedMaxSize);
56        }
57      } while (tree.Root == null || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
58      return tree;
59    }
60
61    private Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
62      var symbolList = symbols.ToList();
63      var ticketsSum = symbolList.Select(x => x.Tickets.Value).Sum();
64      var r = random.NextDouble() * ticketsSum;
65      double aggregatedTickets = 0;
66      for (int i = 0; i < symbolList.Count; i++) {
67        aggregatedTickets += symbolList[i].Tickets.Value;
68        if (aggregatedTickets >= r) {
69          return symbolList[i];
70        }
71      }
72      // this should never happen
73      throw new ArgumentException();
74    }
75
76
77    private SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
78      SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
79      if (size <= 1 || maxDepth <= 1) return root;
80      List<object[]> list = new List<object[]>();
81      int currentSize = 1;
82      int totalListMinSize = grammar.MinimalExpressionLength(rootSymbol) - 1;
83
84      int actualArity = SampleArity(random, grammar, rootSymbol, size);
85      for (int i = 0; i < actualArity; i++) {
86        // insert a dummy sub-tree and add the pending extension to the list
87        root.AddSubTree(null);
88        list.Add(new object[] { root, i, 2 });
89      }
90
91      // while there are pending extension points and we have not reached the limit of adding new extension points
92      while (list.Count > 0 && totalListMinSize + currentSize < size) {
93        int randomIndex = random.Next(list.Count);
94        object[] nextExtension = list[randomIndex];
95        list.RemoveAt(randomIndex);
96        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
97        int argumentIndex = (int)nextExtension[1];
98        int extensionDepth = (int)nextExtension[2];
99        if (extensionDepth + grammar.MinimalExpressionDepth(parent.Symbol) >= maxDepth) {
100          parent.RemoveSubTree(argumentIndex);
101          SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, argumentIndex));
102          parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
103          currentSize += branch.GetSize();
104          totalListMinSize -= branch.GetSize();
105        } else {
106          var allowedSubFunctions = from s in grammar.AllowedSymbols(parent.Symbol, argumentIndex)
107                                    where grammar.MinimalExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
108                                    where grammar.MaximalExpressionLength(s) > size - totalListMinSize - currentSize ||
109                                          totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
110                                    // terminals or terminal-branches
111                                    select s;
112          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSubFunctions);
113          SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
114          parent.RemoveSubTree(argumentIndex);
115          parent.InsertSubTree(argumentIndex, newTree);
116          currentSize++;
117          totalListMinSize--;
118
119          actualArity = SampleArity(random, grammar, selectedSymbol, size - currentSize);
120          for (int i = 0; i < actualArity; i++) {
121            // insert a dummy sub-tree and add the pending extension to the list
122            newTree.AddSubTree(null);
123            list.Add(new object[] { newTree, i, extensionDepth + 1 });
124          }
125          totalListMinSize += grammar.MinimalExpressionLength(selectedSymbol);
126        }
127      }
128      // fill all pending extension points
129      while (list.Count > 0) {
130        int randomIndex = random.Next(list.Count);
131        object[] nextExtension = list[randomIndex];
132        list.RemoveAt(randomIndex);
133        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
134        int a = (int)nextExtension[1];
135        int d = (int)nextExtension[2];
136        parent.RemoveSubTree(a);
137        parent.InsertSubTree(a,
138          CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
139      }
140      return root;
141    }
142
143    private int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
144      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
145      int minArity = grammar.MinSubTrees(symbol);
146      int maxArity = grammar.MaxSubTrees(symbol);
147      if (maxArity > targetSize) {
148        maxArity = targetSize;
149      }
150      // 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
151      // 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
152      long aggregatedLongestExpressionLength = 0;
153      for (int i = 0; i < maxArity; i++) {
154        aggregatedLongestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
155                                              select grammar.MaximalExpressionLength(s)).Max();
156        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
157        else break;
158      }
159
160      // 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
161      // 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
162      long aggregatedShortestExpressionLength = 0;
163      for (int i = 0; i < maxArity; i++) {
164        aggregatedShortestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
165                                               select grammar.MinimalExpressionLength(s)).Min();
166        if (aggregatedShortestExpressionLength > targetSize) {
167          maxArity = i;
168          break;
169        }
170      }
171      if (minArity > maxArity) throw new ArgumentException();
172      return random.Next(minArity, maxArity + 1);
173    }
174
175    private SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
176      // determine possible symbols that will lead to the smallest possible tree
177      var possibleSymbols = (from s in symbols
178                             group s by grammar.MinimalExpressionLength(s) into g
179                             orderby g.Key
180                             select g).First();
181      var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
182      // build minimal tree by recursive application
183      var tree = selectedSymbol.CreateTreeNode();
184      for (int i = 0; i < grammar.MinSubTrees(selectedSymbol); i++)
185        tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.AllowedSymbols(selectedSymbol, i)));
186      return tree;
187    }
188  }
189}
Note: See TracBrowser for help on using the repository browser.