Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/SymbolicExpressionGrammarBase.cs @ 6009

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

#1472 implemented a check in PTC2 operator, fixed bugs in SymbolicExpressionGrammarBase and made some small changes in both classes to prevent numeric overflow exceptions.

File size: 14.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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 System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28
29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
30  /// <summary>
31  /// The default symbolic expression grammar stores symbols and syntactic constraints for symbols.
32  /// Symbols are treated as equvivalent if they have the same name.
33  /// Syntactic constraints limit the number of allowed sub trees for a node with a symbol and which symbols are allowed
34  /// in the sub-trees of a symbol (can be specified for each sub-tree index separately).
35  /// </summary>
36  [StorableClass]
37  public abstract class SymbolicExpressionGrammarBase : NamedItem, ISymbolicExpressionGrammarBase {
38    #region properties for separation between implementation and persistence
39    [Storable(Name = "Symbols")]
40    private IEnumerable<ISymbol> StorableSymbols {
41      get { return symbols.Values.ToArray(); }
42      set { symbols = value.ToDictionary(sym => sym.Name); }
43    }
44
45    [Storable(Name = "SymbolSubtreeCount")]
46    private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
47      get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
48      set { symbolSubtreeCount = value.ToDictionary(x => x.Key.Name, x => x.Value); }
49    }
50
51    [Storable(Name = "AllowedChildSymbols")]
52    private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
53      get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(y => GetSymbol(y)).ToArray())).ToArray(); }
54      set { allowedChildSymbols = value.ToDictionary(x => x.Key.Name, x => x.Value.Select(y => y.Name).ToList()); }
55    }
56
57    [Storable(Name = "AllowedChildSymbolsPerIndex")]
58    private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
59      get { return allowedChildSymbolsPerIndex.Select(x => new KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>(Tuple.Create<ISymbol, int>(GetSymbol(x.Key.Item1), x.Key.Item2), x.Value.Select(y => GetSymbol(y)).ToArray())).ToArray(); }
60      set { allowedChildSymbolsPerIndex = value.ToDictionary(x => Tuple.Create(x.Key.Item1.Name, x.Key.Item2), x => x.Value.Select(y => y.Name).ToList()); }
61    }
62    #endregion
63
64    protected Dictionary<string, ISymbol> symbols;
65    protected Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
66    protected Dictionary<string, List<string>> allowedChildSymbols;
67    protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
68
69    public override bool CanChangeName {
70      get { return false; }
71    }
72    public override bool CanChangeDescription {
73      get { return false; }
74    }
75
76    [StorableConstructor]
77    protected SymbolicExpressionGrammarBase(bool deserializing)
78      : base(deserializing) {
79      cachedMinExpressionLength = new Dictionary<string, int>();
80      cachedMaxExpressionLength = new Dictionary<string, int>();
81      cachedMinExpressionDepth = new Dictionary<string, int>();
82    }
83    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
84      : base(original, cloner) {
85      cachedMinExpressionLength = new Dictionary<string, int>();
86      cachedMaxExpressionLength = new Dictionary<string, int>();
87      cachedMinExpressionDepth = new Dictionary<string, int>();
88
89      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
90      symbols = new Dictionary<string, ISymbol>(original.symbols);
91
92      allowedChildSymbols = new Dictionary<string, List<string>>();
93      foreach (var element in original.allowedChildSymbols)
94        allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
95
96      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
97      foreach (var element in original.allowedChildSymbolsPerIndex)
98        allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
99    }
100
101    protected SymbolicExpressionGrammarBase(string name, string description)
102      : base(name, description) {
103      cachedMinExpressionLength = new Dictionary<string, int>();
104      cachedMaxExpressionLength = new Dictionary<string, int>();
105      cachedMinExpressionDepth = new Dictionary<string, int>();
106
107      symbols = new Dictionary<string, ISymbol>();
108      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
109      allowedChildSymbols = new Dictionary<string, List<string>>();
110      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
111    }
112
113    #region protected grammar manipulation methods
114    protected void AddSymbol(ISymbol symbol) {
115      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
116      symbols.Add(symbol.Name, symbol);
117      symbolSubtreeCount.Add(symbol.Name, Tuple.Create(0, 0));
118      ClearCaches();
119    }
120
121    protected void RemoveSymbol(ISymbol symbol) {
122      symbols.Remove(symbol.Name);
123      allowedChildSymbols.Remove(symbol.Name);
124      for (int i = 0; i < GetMaximumSubtreeCount(symbol); i++)
125        allowedChildSymbolsPerIndex.Remove(Tuple.Create(symbol.Name, i));
126      symbolSubtreeCount.Remove(symbol.Name);
127
128
129      foreach (var parent in Symbols) {
130        List<string> allowedChilds;
131        if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
132          allowedChilds.Remove(symbol.Name);
133
134        for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
135          if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
136            allowedChilds.Remove(symbol.Name);
137        }
138      }
139      ClearCaches();
140    }
141
142    public virtual ISymbol GetSymbol(string symbolName) {
143      ISymbol symbol;
144      if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
145      return null;
146    }
147
148    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
149      List<string> childSymbols;
150      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
151        childSymbols = new List<string>();
152        allowedChildSymbols.Add(parent.Name, childSymbols);
153      }
154      if (childSymbols.Contains(child.Name)) throw new ArgumentException();
155      childSymbols.Add(child.Name);
156      ClearCaches();
157    }
158
159    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
160      var key = Tuple.Create(parent.Name, argumentIndex);
161      List<string> childSymbols;
162      if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
163        childSymbols = new List<string>();
164        allowedChildSymbolsPerIndex.Add(key, childSymbols);
165      }
166
167      if (IsAllowedChildSymbol(parent, child)) throw new ArgumentException();
168      if (childSymbols.Contains(child.Name)) throw new ArgumentException();
169      childSymbols.Add(child.Name);
170      ClearCaches();
171    }
172
173    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
174      List<string> childSymbols;
175      if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
176        if (allowedChildSymbols[parent.Name].Remove(child.Name))
177          ClearCaches();
178      }
179    }
180
181    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
182      var key = Tuple.Create(parent.Name, argumentIndex);
183      List<string> childSymbols;
184      if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
185        if (allowedChildSymbolsPerIndex[key].Remove(child.Name))
186          ClearCaches();
187      }
188    }
189
190    protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
191      for (int i = GetMaximumSubtreeCount(symbol) - 1; i >= maximumSubtreeCount; i--) {
192        var key = Tuple.Create(symbol.Name, i);
193        allowedChildSymbolsPerIndex.Remove(key);
194      }
195
196      symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
197      ClearCaches();
198    }
199    #endregion
200
201    #region ISymbolicExpressionGrammarBase Members
202    public virtual IEnumerable<ISymbol> Symbols {
203      get { return symbols.Values; }
204    }
205    public virtual IEnumerable<ISymbol> AllowedSymbols {
206      get { return Symbols.Where(s => !s.InitialFrequency.IsAlmost(0.0)); }
207    }
208    public virtual bool ContainsSymbol(ISymbol symbol) {
209      return symbols.ContainsKey(symbol.Name);
210    }
211
212    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
213      List<string> temp;
214      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
215        if (temp.Contains(child.Name)) return true;
216      return false;
217    }
218
219    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
220      List<string> temp;
221      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
222        if (temp.Contains(child.Name)) return true;
223
224      var key = Tuple.Create(parent.Name, argumentIndex);
225      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
226        return temp.Contains(child.Name);
227      return false;
228    }
229
230    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
231      return from s in AllowedSymbols where IsAllowedChildSymbol(parent, s) select s;
232    }
233
234    public virtual IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
235      var result = Enumerable.Empty<string>();
236
237      List<string> temp;
238      if (allowedChildSymbols.TryGetValue(parent.Name, out temp))
239        result = result.Union(temp);
240      var key = Tuple.Create(parent.Name, argumentIndex);
241      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp))
242        result = result.Union(temp);
243
244      return result.Select(x => GetSymbol(x));
245    }
246
247    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
248      return symbolSubtreeCount[symbol.Name].Item1;
249    }
250    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
251      return symbolSubtreeCount[symbol.Name].Item2;
252    }
253
254
255    private void ClearCaches() {
256      cachedMinExpressionLength.Clear();
257      cachedMaxExpressionLength.Clear();
258      cachedMinExpressionDepth.Clear();
259    }
260
261    private Dictionary<string, int> cachedMinExpressionLength;
262    public int GetMinimumExpressionLength(ISymbol symbol) {
263      int temp;
264      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
265        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
266        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
267                                              let minForSlot = (long)(from s in AllowedSymbols
268                                                                      where IsAllowedChildSymbol(symbol, s, argIndex)
269                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
270                                              select minForSlot).DefaultIfEmpty(0).Sum();
271
272        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
273        return cachedMinExpressionLength[symbol.Name];
274      }
275      return temp;
276    }
277
278    private Dictionary<string, int> cachedMaxExpressionLength;
279    public int GetMaximumExpressionLength(ISymbol symbol) {
280      int temp;
281      if (!cachedMaxExpressionLength.TryGetValue(symbol.Name, out temp)) {
282        cachedMaxExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
283        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
284                                  let maxForSlot = (long)(from s in AllowedSymbols
285                                                          where IsAllowedChildSymbol(symbol, s, argIndex)
286                                                          select GetMaximumExpressionLength(s)).DefaultIfEmpty(0).Max()
287                                  select maxForSlot).DefaultIfEmpty(0).Sum();
288        cachedMaxExpressionLength[symbol.Name] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
289        return cachedMaxExpressionLength[symbol.Name];
290      }
291      return temp;
292    }
293
294    private Dictionary<string, int> cachedMinExpressionDepth;
295    public int GetMinimumExpressionDepth(ISymbol symbol) {
296      int temp;
297      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
298        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
299        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
300                             let minForSlot = (long)(from s in AllowedSymbols
301                                                     where IsAllowedChildSymbol(symbol, s, argIndex)
302                                                     select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
303                             select minForSlot).DefaultIfEmpty(0).Max();
304        cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
305        return cachedMinExpressionDepth[symbol.Name];
306      }
307      return temp;
308    }
309    #endregion
310  }
311}
Note: See TracBrowser for help on using the repository browser.