Free cookie consent management tool by TermsFeed Policy Generator

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

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

Extracted view for artificial ant problem into a separate plugin/project. #952 (Artificial Ant Problem for 3.3)

File size: 9.2 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      return symbolList[random.Next(symbolList.Count)];
64    }
65
66
67    private SymbolicExpressionTreeNode PTC2(IRandom random, ISymbolicExpressionGrammar grammar, Symbol rootSymbol, int size, int maxDepth) {
68      SymbolicExpressionTreeNode root = rootSymbol.CreateTreeNode();
69      if (size <= 1 || maxDepth <= 1) return root;
70      List<object[]> list = new List<object[]>();
71      int currentSize = 1;
72      int totalListMinSize = grammar.MinimalExpressionLength(rootSymbol) - 1;
73
74      int actualArity = SampleArity(random, grammar, rootSymbol, size);
75      for (int i = 0; i < actualArity; i++) {
76        // insert a dummy sub-tree and add the pending extension to the list
77        root.AddSubTree(null);
78        list.Add(new object[] { root, i, 2 });
79      }
80
81      // while there are pending extension points and we have not reached the limit of adding new extension points
82      while (list.Count > 0 && totalListMinSize + currentSize < size) {
83        int randomIndex = random.Next(list.Count);
84        object[] nextExtension = list[randomIndex];
85        list.RemoveAt(randomIndex);
86        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
87        int argumentIndex = (int)nextExtension[1];
88        int extensionDepth = (int)nextExtension[2];
89        if (extensionDepth + grammar.MinimalExpressionDepth(parent.Symbol) >= maxDepth) {
90          parent.RemoveSubTree(argumentIndex);
91          SymbolicExpressionTreeNode branch = CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, argumentIndex));
92          parent.InsertSubTree(argumentIndex, branch); // insert a smallest possible tree
93          currentSize += branch.GetSize();
94          totalListMinSize -= branch.GetSize();
95        } else {
96          var allowedSubFunctions = from s in grammar.AllowedSymbols(parent.Symbol, argumentIndex)
97                                    where grammar.MinimalExpressionDepth(parent.Symbol) + extensionDepth - 1 < maxDepth
98                                    where grammar.MaximalExpressionLength(s) > size - totalListMinSize - currentSize ||
99                                          totalListMinSize + currentSize >= size * 0.9 // if the necessary size is almost reached then also allow
100                                    // terminals or terminal-branches
101                                    select s;
102          Symbol selectedSymbol = SelectRandomSymbol(random, allowedSubFunctions);
103          SymbolicExpressionTreeNode newTree = selectedSymbol.CreateTreeNode();
104          parent.RemoveSubTree(argumentIndex);
105          parent.InsertSubTree(argumentIndex, newTree);
106          currentSize++;
107          totalListMinSize--;
108
109          actualArity = SampleArity(random, grammar, selectedSymbol, size - currentSize);
110          for (int i = 0; i < actualArity; i++) {
111            // insert a dummy sub-tree and add the pending extension to the list
112            newTree.AddSubTree(null);
113            list.Add(new object[] { newTree, i, extensionDepth + 1 });
114          }
115          totalListMinSize += grammar.MinimalExpressionLength(selectedSymbol);
116        }
117      }
118      // fill all pending extension points
119      while (list.Count > 0) {
120        int randomIndex = random.Next(list.Count);
121        object[] nextExtension = list[randomIndex];
122        list.RemoveAt(randomIndex);
123        SymbolicExpressionTreeNode parent = (SymbolicExpressionTreeNode)nextExtension[0];
124        int a = (int)nextExtension[1];
125        int d = (int)nextExtension[2];
126        parent.RemoveSubTree(a);
127        parent.InsertSubTree(a,
128          CreateMinimalTree(random, grammar, grammar.AllowedSymbols(parent.Symbol, a))); // append a tree with minimal possible height
129      }
130      return root;
131    }
132
133    private int SampleArity(IRandom random, ISymbolicExpressionGrammar grammar, Symbol symbol, int targetSize) {
134      // select actualArity randomly with the constraint that the sub-trees in the minimal arity can become large enough
135      int minArity = grammar.MinSubTrees(symbol);
136      int maxArity = grammar.MaxSubTrees(symbol);
137      if (maxArity > targetSize) {
138        maxArity = targetSize;
139      }
140      // 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
141      // 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
142      long aggregatedLongestExpressionLength = 0;
143      for (int i = 0; i < maxArity; i++) {
144        aggregatedLongestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
145                                              select grammar.MaximalExpressionLength(s)).Max();
146        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
147        else break;
148      }
149
150      // 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
151      // 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
152      long aggregatedShortestExpressionLength = 0;
153      for (int i = 0; i < maxArity; i++) {
154        aggregatedShortestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
155                                               select grammar.MinimalExpressionLength(s)).Min();
156        if (aggregatedShortestExpressionLength > targetSize) {
157          maxArity = i;
158          break;
159        }
160      }
161      if (minArity > maxArity) throw new ArgumentException();
162      return random.Next(minArity, maxArity + 1);
163    }
164
165    private SymbolicExpressionTreeNode CreateMinimalTree(IRandom random, ISymbolicExpressionGrammar grammar, IEnumerable<Symbol> symbols) {
166      // determine possible symbols that will lead to the smallest possible tree
167      var possibleSymbols = (from s in symbols
168                             group s by grammar.MinimalExpressionLength(s) into g
169                             orderby g.Key
170                             select g).First();
171      var selectedSymbol = SelectRandomSymbol(random, possibleSymbols);
172      // build minimal tree by recursive application
173      var tree = selectedSymbol.CreateTreeNode();
174      for (int i = 0; i < grammar.MinSubTrees(selectedSymbol); i++)
175        tree.AddSubTree(CreateMinimalTree(random, grammar, grammar.AllowedSymbols(selectedSymbol, i)));
176      return tree;
177    }
178  }
179}
Note: See TracBrowser for help on using the repository browser.