Free cookie consent management tool by TermsFeed Policy Generator

source: branches/symbreg-factors-2650/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs @ 14351

Last change on this file since 14351 was 14351, checked in by gkronber, 7 years ago

#2650: merged r14332:14350 from trunk to branch

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