Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Grammars/SymbolicExpressionGrammarBase.cs @ 17106

Last change on this file since 17106 was 17105, checked in by mkommend, 5 years ago

#2520: Merged 16584, 16585,16594,16595, 16625, 16658, 16659, 16672, 16707, 16729, 16792, 16796, 16797, 16799, 16819, 16906, 16907, 16908, 16933, 16945, 16992, 16994, 16995, 16996, 16997, 17014, 17015, 17017, 17020, 17021, 17022, 17023, 17024, 17029, 17086, 17087, 17088, 17089 into stable.

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