Free cookie consent management tool by TermsFeed Policy Generator

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

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

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

File size: 9.9 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 Create(random, grammar, maxTreeSize.Value, maxTreeHeight.Value);
40    }
41
42    public static SymbolicExpressionTree Create(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.GetMinExpressionLength(grammar.StartSymbol);
45      int allowedMaxSize = Math.Min(maxTreeSize, grammar.GetMaxExpressionLength(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 = grammar.ProgramRootSymbol.CreateTreeNode();
52          tree.Root.AddSubTree(PTC2(random, grammar, grammar.StartSymbol, treeSize + 1, maxTreeHeight + 1));
53        }
54        catch (ArgumentException) {
55          // try a different size
56          treeSize = random.Next(allowedMinSize, allowedMaxSize);
57        }
58      } while (tree.Root.SubTrees.Count == 0 || tree.Size > maxTreeSize || tree.Height > maxTreeHeight);
59      return tree;
60    }
61
62    private static Symbol SelectRandomSymbol(IRandom random, IEnumerable<Symbol> symbols) {
63      var symbolList = symbols.ToList();
64      var ticketsSum = symbolList.Select(x => x.InitialFrequency).Sum();
65      var r = random.NextDouble() * ticketsSum;
66      double aggregatedTickets = 0;
67      for (int i = 0; i < symbolList.Count; i++) {
68        aggregatedTickets += symbolList[i].InitialFrequency;
69        if (aggregatedTickets >= r) {
70          return symbolList[i];
71        }
72      }
73      // this should never happen
74      throw new ArgumentException();
75    }
76
77
78    public static SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
79      SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
80      if (size <= 1 || maxDepth <= 1) return root;
81      List<object[]> extensionPoints = new List<object[]>();
82      int currentSize = 1;
83      int totalListMinSize = grammar.GetMinExpressionLength(rootSymbol) - 1;
84
85      int actualArity = SampleArity(random, grammar, rootSymbol, size);
86      for (int i = 0; i < actualArity; i++) {
87        // insert a dummy sub-tree and add the pending extension to the list
88        root.AddSubTree(null);
89        extensionPoints.Add(new object[] { root, i, 2 });
90      }
91
92      // while there are pending extension points and we have not reached the limit of adding new extension points
93      while (extensionPoints.Count > 0 && totalListMinSize + currentSize < size) {
94        int randomIndex = random.Next(extensionPoints.Count);
95        object[] nextExtension = extensionPoints[randomIndex];
96        extensionPoints.RemoveAt(randomIndex);
97        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
98        int argumentIndex = (int)nextExtension[1];
99        int extensionDepth = (int)nextExtension[2];
100        if (extensionDepth + grammar.GetMinExpressionDepth(parent.Symbol) >= maxDepth) {
101          parent.RemoveSubTree(argumentIndex);
102          SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(parent.Symbol, argumentIndex));
103          parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
104          currentSize += branch.GetSize();
105          totalListMinSize -= branch.GetSize();
106        } else {
107          var allowedSubFunctions = from s in grammar.GetAllowedSymbols(parent.Symbol, argumentIndex)
108                                    where grammar.GetMinExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
109                                    where grammar.GetMaxExpressionLength(s) > size - totalListMinSize - currentSize ||
110                                          totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
111                                    // terminals or terminal-branches
112                                    select s;
113          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSubFunctions);
114          SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
115          parent.RemoveSubTree(argumentIndex);
116          parent.InsertSubTree(argumentIndex, newTree);
117          currentSize++;
118          totalListMinSize--;
119
120          actualArity = SampleArity(random, grammar, selectedSymbol, size - currentSize);
121          for (int i = 0; i < actualArity; i++) {
122            // insert a dummy sub-tree and add the pending extension to the list
123            newTree.AddSubTree(null);
124            extensionPoints.Add(new object[] { newTree, i, extensionDepth + 1 });
125          }
126          totalListMinSize += grammar.GetMinExpressionLength(selectedSymbol);
127        }
128      }
129      // fill all pending extension points
130      while (extensionPoints.Count > 0) {
131        int randomIndex = random.Next(extensionPoints.Count);
132        object[] nextExtension = extensionPoints[randomIndex];
133        extensionPoints.RemoveAt(randomIndex);
134        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
135        int a = (int)nextExtension[1];
136        int d = (int)nextExtension[2];
137        parent.RemoveSubTree(a);
138        parent.InsertSubTree(a,
139          CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
140      }
141      return root;
142    }
143
144    private static int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
145      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
146      int minArity = grammar.GetMinSubTreeCount(symbol);
147      int maxArity = grammar.GetMaxSubTreeCount(symbol);
148      if (maxArity > targetSize) {
149        maxArity = targetSize;
150      }
151      // 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
152      // 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
153      long aggregatedLongestExpressionLength = 0;
154      for (int i = 0; i < maxArity; i++) {
155        aggregatedLongestExpressionLength += (from s in grammar.GetAllowedSymbols(symbol, i)
156                                              select grammar.GetMaxExpressionLength(s)).Max();
157        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
158        else break;
159      }
160
161      // 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
162      // 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
163      long aggregatedShortestExpressionLength = 0;
164      for (int i = 0; i < maxArity; i++) {
165        aggregatedShortestExpressionLength += (from s in grammar.GetAllowedSymbols(symbol, i)
166                                               select grammar.GetMinExpressionLength(s)).Min();
167        if (aggregatedShortestExpressionLength > targetSize) {
168          maxArity = i;
169          break;
170        }
171      }
172      if (minArity > maxArity) throw new ArgumentException();
173      return random.Next(minArity, maxArity + 1);
174    }
175
176    private static SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
177      // determine possible symbols that will lead to the smallest possible tree
178      var possibleSymbols = (from s in symbols
179                             group s by grammar.GetMinExpressionLength(s) into g
180                             orderby g.Key
181                             select g).First();
182      var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
183      // build minimal tree by recursive application
184      var tree = selectedSymbol.CreateTreeNode();
185      for (int i = 0; i < grammar.GetMinSubTreeCount(selectedSymbol); i++)
186        tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.GetAllowedSymbols(selectedSymbol, i)));
187      return tree;
188    }
189  }
190}
Note: See TracBrowser for help on using the repository browser.