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

Last change on this file since 7001 was 7001, checked in by mkommend, 11 years ago

#1479: Changed default value of maximum subtree count for newly added symbols.

File size: 19.2 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
39    #region properties for separation between implementation and persistence
40    [Storable(Name = "Symbols")]
41    private IEnumerable<ISymbol> StorableSymbols {
42      get { return symbols.Values.ToArray(); }
43      set { symbols = value.ToDictionary(sym => sym.Name); }
44    }
45
46    [Storable(Name = "SymbolSubtreeCount")]
47    private IEnumerable<KeyValuePair<ISymbol, Tuple<int, int>>> StorableSymbolSubtreeCount {
48      get { return symbolSubtreeCount.Select(x => new KeyValuePair<ISymbol, Tuple<int, int>>(GetSymbol(x.Key), x.Value)).ToArray(); }
49      set { symbolSubtreeCount = value.ToDictionary(x => x.Key.Name, x => x.Value); }
50    }
51
52    [Storable(Name = "AllowedChildSymbols")]
53    private IEnumerable<KeyValuePair<ISymbol, IEnumerable<ISymbol>>> StorableAllowedChildSymbols {
54      get { return allowedChildSymbols.Select(x => new KeyValuePair<ISymbol, IEnumerable<ISymbol>>(GetSymbol(x.Key), x.Value.Select(GetSymbol).ToArray())).ToArray(); }
55      set { allowedChildSymbols = value.ToDictionary(x => x.Key.Name, x => x.Value.Select(y => y.Name).ToList()); }
56    }
57
58    [Storable(Name = "AllowedChildSymbolsPerIndex")]
59    private IEnumerable<KeyValuePair<Tuple<ISymbol, int>, IEnumerable<ISymbol>>> StorableAllowedChildSymbolsPerIndex {
60      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(); }
61      set { allowedChildSymbolsPerIndex = value.ToDictionary(x => Tuple.Create(x.Key.Item1.Name, x.Key.Item2), x => x.Value.Select(y => y.Name).ToList()); }
62    }
63    #endregion
64
65    private bool suppressEvents;
66    protected Dictionary<string, ISymbol> symbols;
67    protected Dictionary<string, Tuple<int, int>> symbolSubtreeCount;
68    protected Dictionary<string, List<string>> allowedChildSymbols;
69    protected Dictionary<Tuple<string, int>, List<string>> allowedChildSymbolsPerIndex;
70
71    public override bool CanChangeName {
72      get { return false; }
73    }
74    public override bool CanChangeDescription {
75      get { return false; }
76    }
77
78    [StorableConstructor]
79    protected SymbolicExpressionGrammarBase(bool deserializing)
80      : base(deserializing) {
81      cachedMinExpressionLength = new Dictionary<string, int>();
82      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
83      cachedMinExpressionDepth = new Dictionary<string, int>();
84
85      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
86      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
87
88      suppressEvents = false;
89    }
90
91    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
92      : base(original, cloner) {
93      cachedMinExpressionLength = new Dictionary<string, int>();
94      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
95      cachedMinExpressionDepth = new Dictionary<string, int>();
96
97      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
98      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
99
100      symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
101      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
102
103      allowedChildSymbols = new Dictionary<string, List<string>>();
104      foreach (var element in original.allowedChildSymbols)
105        allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
106
107      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
108      foreach (var element in original.allowedChildSymbolsPerIndex)
109        allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
110
111      suppressEvents = false;
112    }
113
114    protected SymbolicExpressionGrammarBase(string name, string description)
115      : base(name, description) {
116      cachedMinExpressionLength = new Dictionary<string, int>();
117      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
118      cachedMinExpressionDepth = new Dictionary<string, int>();
119
120      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
121      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
122
123      symbols = new Dictionary<string, ISymbol>();
124      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>();
125      allowedChildSymbols = new Dictionary<string, List<string>>();
126      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
127
128      suppressEvents = false;
129    }
130
131    #region protected grammar manipulation methods
132    protected virtual void AddSymbol(ISymbol symbol) {
133      if (ContainsSymbol(symbol)) throw new ArgumentException("Symbol " + symbol + " is already defined.");
134      foreach (var s in symbol.Flatten()) {
135        symbols.Add(s.Name, s);
136        int maxSubTreeCount = Math.Min(s.MinimumArity + 1, s.MaximumArity);
137        symbolSubtreeCount.Add(s.Name, Tuple.Create(s.MinimumArity, maxSubTreeCount));
138      }
139      ClearCaches();
140    }
141
142    protected virtual void RemoveSymbol(ISymbol symbol) {
143      foreach (var s in symbol.Flatten()) {
144        symbols.Remove(s.Name);
145        allowedChildSymbols.Remove(s.Name);
146        for (int i = 0; i < GetMaximumSubtreeCount(s); i++)
147          allowedChildSymbolsPerIndex.Remove(Tuple.Create(s.Name, i));
148        symbolSubtreeCount.Remove(s.Name);
149
150        foreach (var parent in Symbols) {
151          List<string> allowedChilds;
152          if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
153            allowedChilds.Remove(s.Name);
154
155          for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
156            if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
157              allowedChilds.Remove(s.Name);
158          }
159        }
160        suppressEvents = true;
161        foreach (var groupSymbol in Symbols.OfType<GroupSymbol>())
162          groupSymbol.SymbolsCollection.Remove(symbol);
163        suppressEvents = false;
164      }
165      ClearCaches();
166    }
167
168    public virtual ISymbol GetSymbol(string symbolName) {
169      ISymbol symbol;
170      if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
171      return null;
172    }
173
174    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
175      bool changed = false;
176
177      foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
178        changed |= AddAllowedChildSymbolToDictionaries(p, child);
179
180      if (changed) {
181        ClearCaches();
182        OnChanged();
183      }
184    }
185
186    private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child) {
187      List<string> childSymbols;
188      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
189        childSymbols = new List<string>();
190        allowedChildSymbols.Add(parent.Name, childSymbols);
191      }
192      if (childSymbols.Contains(child.Name)) return false;
193
194      suppressEvents = true;
195      for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++)
196        RemoveAllowedChildSymbol(parent, child, argumentIndex);
197      suppressEvents = false;
198
199      childSymbols.Add(child.Name);
200      return true;
201    }
202
203    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
204      bool changed = false;
205
206      foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
207        changed |= AddAllowedChildSymbolToDictionaries(p, child, argumentIndex);
208
209      if (changed) {
210        ClearCaches();
211        OnChanged();
212      }
213    }
214
215
216    private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child, int argumentIndex) {
217      List<string> childSymbols;
218      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
219        childSymbols = new List<string>();
220        allowedChildSymbols.Add(parent.Name, childSymbols);
221      }
222      if (childSymbols.Contains(child.Name)) return false;
223
224
225      var key = Tuple.Create(parent.Name, argumentIndex);
226      if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
227        childSymbols = new List<string>();
228        allowedChildSymbolsPerIndex.Add(key, childSymbols);
229      }
230
231      if (childSymbols.Contains(child.Name)) return false;
232
233      childSymbols.Add(child.Name);
234      return true;
235    }
236
237    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
238      bool changed = false;
239      List<string> childSymbols;
240      if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
241        changed |= childSymbols.Remove(child.Name);
242      }
243
244      for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++) {
245        var key = Tuple.Create(parent.Name, argumentIndex);
246        if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
247          changed |= childSymbols.Remove(child.Name);
248      }
249
250      if (changed) {
251        ClearCaches();
252        OnChanged();
253      }
254    }
255
256    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
257      bool changed = false;
258
259      suppressEvents = true;
260      List<string> childSymbols;
261      if (allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
262        if (childSymbols.Remove(child.Name)) {
263          for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
264            if (i != argumentIndex) AddAllowedChildSymbol(parent, child, i);
265          }
266          changed = true;
267        }
268      }
269      suppressEvents = false;
270
271      var key = Tuple.Create(parent.Name, argumentIndex);
272      if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
273        changed |= childSymbols.Remove(child.Name);
274
275      if (changed) {
276        ClearCaches();
277        OnChanged();
278      }
279    }
280
281    protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
282      var symbols = symbol.Flatten().Where(s => !(s is GroupSymbol));
283      if (symbols.Any(s => s.MinimumArity > minimumSubtreeCount)) throw new ArgumentException("Invalid minimum subtree count " + minimumSubtreeCount + " for " + symbol);
284      if (symbols.Any(s => s.MaximumArity < maximumSubtreeCount)) throw new ArgumentException("Invalid maximum subtree count " + maximumSubtreeCount + " for " + symbol);
285
286      foreach (ISymbol s in symbols)
287        SetSubTreeCountInDictionaries(s, minimumSubtreeCount, maximumSubtreeCount);
288
289      ClearCaches();
290      OnChanged();
291    }
292
293    private void SetSubTreeCountInDictionaries(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
294      for (int i = maximumSubtreeCount; i < GetMaximumSubtreeCount(symbol); i++) {
295        var key = Tuple.Create(symbol.Name, i);
296        allowedChildSymbolsPerIndex.Remove(key);
297      }
298
299      symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
300    }
301    #endregion
302
303    public virtual IEnumerable<ISymbol> Symbols {
304      get { return symbols.Values; }
305    }
306    public virtual IEnumerable<ISymbol> AllowedSymbols {
307      get { return Symbols.Where(s => s.Enabled); }
308    }
309    public virtual bool ContainsSymbol(ISymbol symbol) {
310      return symbols.ContainsKey(symbol.Name);
311    }
312
313    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
314    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
315      if (!child.Enabled) return false;
316
317      bool result;
318      if (cachedIsAllowedChildSymbol.TryGetValue(Tuple.Create(parent.Name, child.Name), out result)) return result;
319      List<string> temp;
320      if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
321        //if (temp.Contains(child.Name)) return true;
322        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
323          cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), true);
324          return true;
325        }
326      }
327      cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), false);
328      return false;
329    }
330
331    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
332    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
333      if (!child.Enabled) return false;
334      if (IsAllowedChildSymbol(parent, child)) return true;
335
336      bool result;
337      if (cachedIsAllowedChildSymbolIndex.TryGetValue(Tuple.Create(parent.Name, child.Name, argumentIndex), out result)) return result;
338      List<string> temp;
339      var key = Tuple.Create(parent.Name, argumentIndex);
340      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp)) {
341        //if (temp.Contains(child.Name)) return true;
342        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
343          cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), true);
344          return true;
345        }
346      }
347      cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), false);
348      return false;
349    }
350
351    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
352      return from child in AllowedSymbols
353             where IsAllowedChildSymbol(parent, child)
354             select child;
355    }
356
357    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
358      return from child in AllowedSymbols
359             where IsAllowedChildSymbol(parent, child, argumentIndex)
360             select child;
361    }
362
363    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
364      return symbolSubtreeCount[symbol.Name].Item1;
365    }
366    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
367      return symbolSubtreeCount[symbol.Name].Item2;
368    }
369
370    protected void ClearCaches() {
371      cachedMinExpressionLength.Clear();
372      cachedMaxExpressionLength.Clear();
373      cachedMinExpressionDepth.Clear();
374
375      cachedIsAllowedChildSymbol.Clear();
376      cachedIsAllowedChildSymbolIndex.Clear();
377    }
378
379    private readonly Dictionary<string, int> cachedMinExpressionLength;
380    public int GetMinimumExpressionLength(ISymbol symbol) {
381      int temp;
382      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
383        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
384        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
385                                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
386                                                                      where s.InitialFrequency > 0.0
387                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
388                                              select minForSlot).DefaultIfEmpty(0).Sum();
389
390        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
391        return cachedMinExpressionLength[symbol.Name];
392      }
393      return temp;
394    }
395
396    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
397    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
398      int temp;
399      var key = Tuple.Create(symbol.Name, maxDepth);
400      if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
401        cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
402        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
403                                  let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
404                                                          where s.InitialFrequency > 0.0
405                                                          where GetMinimumExpressionDepth(s) < maxDepth
406                                                          select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
407                                  select maxForSlot).DefaultIfEmpty(0).Sum();
408        cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
409        return cachedMaxExpressionLength[key];
410      }
411      return temp;
412    }
413
414    private readonly Dictionary<string, int> cachedMinExpressionDepth;
415    public int GetMinimumExpressionDepth(ISymbol symbol) {
416      int temp;
417      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
418        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
419        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
420                             let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
421                                                     where s.InitialFrequency > 0.0
422                                                     select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
423                             select minForSlot).DefaultIfEmpty(0).Max();
424        cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
425        return cachedMinExpressionDepth[symbol.Name];
426      }
427      return temp;
428    }
429
430    public event EventHandler Changed;
431    protected virtual void OnChanged() {
432      if (suppressEvents) return;
433      var handler = Changed;
434      if (handler != null) Changed(this, EventArgs.Empty);
435    }
436  }
437}
Note: See TracBrowser for help on using the repository browser.