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

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

#1657: Corrected and adapted implementation of !PTC2 to handle symbol frequencies correctly and to always create trees of the target size. Additionally the performance of the grammars have been improved and a unit test was added.

File size: 19.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
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        symbolSubtreeCount.Add(s.Name, Tuple.Create(s.MinimumArity, s.MaximumArity));
137      }
138      ClearCaches();
139    }
140
141    protected virtual void RemoveSymbol(ISymbol symbol) {
142      foreach (var s in symbol.Flatten()) {
143        symbols.Remove(s.Name);
144        allowedChildSymbols.Remove(s.Name);
145        for (int i = 0; i < GetMaximumSubtreeCount(s); i++)
146          allowedChildSymbolsPerIndex.Remove(Tuple.Create(s.Name, i));
147        symbolSubtreeCount.Remove(s.Name);
148
149        foreach (var parent in Symbols) {
150          List<string> allowedChilds;
151          if (allowedChildSymbols.TryGetValue(parent.Name, out allowedChilds))
152            allowedChilds.Remove(s.Name);
153
154          for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
155            if (allowedChildSymbolsPerIndex.TryGetValue(Tuple.Create(parent.Name, i), out allowedChilds))
156              allowedChilds.Remove(s.Name);
157          }
158        }
159        suppressEvents = true;
160        foreach (var groupSymbol in Symbols.OfType<GroupSymbol>())
161          groupSymbol.SymbolsCollection.Remove(symbol);
162        suppressEvents = false;
163      }
164      ClearCaches();
165    }
166
167    public virtual ISymbol GetSymbol(string symbolName) {
168      ISymbol symbol;
169      if (symbols.TryGetValue(symbolName, out symbol)) return symbol;
170      return null;
171    }
172
173    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child) {
174      bool changed = false;
175
176      foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
177        changed |= AddAllowedChildSymbolToDictionaries(p, child);
178
179      if (changed) {
180        ClearCaches();
181        OnChanged();
182      }
183    }
184
185    private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child) {
186      List<string> childSymbols;
187      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
188        childSymbols = new List<string>();
189        allowedChildSymbols.Add(parent.Name, childSymbols);
190      }
191      if (childSymbols.Contains(child.Name)) return false;
192
193      suppressEvents = true;
194      for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++)
195        RemoveAllowedChildSymbol(parent, child, argumentIndex);
196      suppressEvents = false;
197
198      childSymbols.Add(child.Name);
199      return true;
200    }
201
202    protected void AddAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
203      bool changed = false;
204
205      foreach (ISymbol p in parent.Flatten().Where(p => !(p is GroupSymbol)))
206        changed |= AddAllowedChildSymbolToDictionaries(p, child, argumentIndex);
207
208      if (changed) {
209        ClearCaches();
210        OnChanged();
211      }
212    }
213
214
215    private bool AddAllowedChildSymbolToDictionaries(ISymbol parent, ISymbol child, int argumentIndex) {
216      List<string> childSymbols;
217      if (!allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
218        childSymbols = new List<string>();
219        allowedChildSymbols.Add(parent.Name, childSymbols);
220      }
221      if (childSymbols.Contains(child.Name)) return false;
222
223
224      var key = Tuple.Create(parent.Name, argumentIndex);
225      if (!allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols)) {
226        childSymbols = new List<string>();
227        allowedChildSymbolsPerIndex.Add(key, childSymbols);
228      }
229
230      if (childSymbols.Contains(child.Name)) return false;
231
232      childSymbols.Add(child.Name);
233      return true;
234    }
235
236    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child) {
237      bool changed = false;
238      List<string> childSymbols;
239      if (allowedChildSymbols.TryGetValue(child.Name, out childSymbols)) {
240        changed |= childSymbols.Remove(child.Name);
241      }
242
243      for (int argumentIndex = 0; argumentIndex < GetMaximumSubtreeCount(parent); argumentIndex++) {
244        var key = Tuple.Create(parent.Name, argumentIndex);
245        if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
246          changed |= childSymbols.Remove(child.Name);
247      }
248
249      if (changed) {
250        ClearCaches();
251        OnChanged();
252      }
253    }
254
255    protected void RemoveAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
256      bool changed = false;
257
258      suppressEvents = true;
259      List<string> childSymbols;
260      if (allowedChildSymbols.TryGetValue(parent.Name, out childSymbols)) {
261        if (childSymbols.Remove(child.Name)) {
262          for (int i = 0; i < GetMaximumSubtreeCount(parent); i++) {
263            if (i != argumentIndex) AddAllowedChildSymbol(parent, child, i);
264          }
265          changed = true;
266        }
267      }
268      suppressEvents = false;
269
270      var key = Tuple.Create(parent.Name, argumentIndex);
271      if (allowedChildSymbolsPerIndex.TryGetValue(key, out childSymbols))
272        changed |= childSymbols.Remove(child.Name);
273
274      if (changed) {
275        ClearCaches();
276        OnChanged();
277      }
278    }
279
280    protected void SetSubtreeCount(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
281      var symbols = symbol.Flatten().Where(s => !(s is GroupSymbol));
282      if (symbols.Any(s => s.MinimumArity > minimumSubtreeCount)) throw new ArgumentException("Invalid minimum subtree count " + minimumSubtreeCount + " for " + symbol);
283      if (symbols.Any(s => s.MaximumArity < maximumSubtreeCount)) throw new ArgumentException("Invalid maximum subtree count " + maximumSubtreeCount + " for " + symbol);
284
285      foreach (ISymbol s in symbols)
286        SetSubTreeCountInDictionaries(s, minimumSubtreeCount, maximumSubtreeCount);
287
288      ClearCaches();
289      OnChanged();
290    }
291
292    private void SetSubTreeCountInDictionaries(ISymbol symbol, int minimumSubtreeCount, int maximumSubtreeCount) {
293      for (int i = maximumSubtreeCount; i < GetMaximumSubtreeCount(symbol); i++) {
294        var key = Tuple.Create(symbol.Name, i);
295        allowedChildSymbolsPerIndex.Remove(key);
296      }
297
298      symbolSubtreeCount[symbol.Name] = Tuple.Create(minimumSubtreeCount, maximumSubtreeCount);
299    }
300    #endregion
301
302    public virtual IEnumerable<ISymbol> Symbols {
303      get { return symbols.Values; }
304    }
305    public virtual IEnumerable<ISymbol> AllowedSymbols {
306      get { return Symbols.Where(s => s.Enabled); }
307    }
308    public virtual bool ContainsSymbol(ISymbol symbol) {
309      return symbols.ContainsKey(symbol.Name);
310    }
311
312    private readonly Dictionary<Tuple<string, string>, bool> cachedIsAllowedChildSymbol;
313    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
314      if (!child.Enabled) return false;
315
316      bool result;
317      if (cachedIsAllowedChildSymbol.TryGetValue(Tuple.Create(parent.Name, child.Name), out result)) return result;
318      List<string> temp;
319      if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
320        //if (temp.Contains(child.Name)) return true;
321        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
322          cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), true);
323          return true;
324        }
325      }
326      cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), false);
327      return false;
328    }
329
330    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
331    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
332      if (!child.Enabled) return false;
333      if (IsAllowedChildSymbol(parent, child)) return true;
334
335      bool result;
336      if (cachedIsAllowedChildSymbolIndex.TryGetValue(Tuple.Create(parent.Name, child.Name, argumentIndex), out result)) return result;
337      List<string> temp;
338      var key = Tuple.Create(parent.Name, argumentIndex);
339      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp)) {
340        //if (temp.Contains(child.Name)) return true;
341        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
342          cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), true);
343          return true;
344        }
345      }
346      cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), false);
347      return false;
348    }
349
350    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
351      return from child in AllowedSymbols
352             where IsAllowedChildSymbol(parent, child)
353             select child;
354    }
355
356    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
357      return from child in AllowedSymbols
358             where IsAllowedChildSymbol(parent, child, argumentIndex)
359             select child;
360    }
361
362    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
363      return symbolSubtreeCount[symbol.Name].Item1;
364    }
365    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
366      return symbolSubtreeCount[symbol.Name].Item2;
367    }
368
369    protected void ClearCaches() {
370      cachedMinExpressionLength.Clear();
371      cachedMaxExpressionLength.Clear();
372      cachedMinExpressionDepth.Clear();
373
374      cachedIsAllowedChildSymbol.Clear();
375      cachedIsAllowedChildSymbolIndex.Clear();
376    }
377
378    private readonly Dictionary<string, int> cachedMinExpressionLength;
379    public int GetMinimumExpressionLength(ISymbol symbol) {
380      int temp;
381      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
382        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
383        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
384                                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
385                                                                      where s.InitialFrequency > 0.0
386                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
387                                              select minForSlot).DefaultIfEmpty(0).Sum();
388
389        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
390        return cachedMinExpressionLength[symbol.Name];
391      }
392      return temp;
393    }
394
395    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
396    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
397      int temp;
398      var key = Tuple.Create(symbol.Name, maxDepth);
399      if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
400        cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
401        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
402                                  let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
403                                                          where s.InitialFrequency > 0.0
404                                                          where GetMinimumExpressionDepth(s) < maxDepth
405                                                          select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
406                                  select maxForSlot).DefaultIfEmpty(0).Sum();
407        cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
408        return cachedMaxExpressionLength[key];
409      }
410      return temp;
411    }
412
413    private readonly Dictionary<string, int> cachedMinExpressionDepth;
414    public int GetMinimumExpressionDepth(ISymbol symbol) {
415      int temp;
416      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
417        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
418        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
419                             let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
420                                                     where s.InitialFrequency > 0.0
421                                                     select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
422                             select minForSlot).DefaultIfEmpty(0).Max();
423        cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
424        return cachedMinExpressionDepth[symbol.Name];
425      }
426      return temp;
427    }
428
429    public event EventHandler Changed;
430    protected virtual void OnChanged() {
431      if (suppressEvents) return;
432      var handler = Changed;
433      if (handler != null) Changed(this, EventArgs.Empty);
434    }
435  }
436}
Note: See TracBrowser for help on using the repository browser.