Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 7227 was 7076, checked in by mkommend, 13 years ago

#1654: Corrected tree creators for symbolic expression encoding.

File size: 20.3 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      cachedMaxExpressionDepth = new Dictionary<string, int>();
85
86      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
87      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
88
89      suppressEvents = false;
90    }
91
92    protected SymbolicExpressionGrammarBase(SymbolicExpressionGrammarBase original, Cloner cloner)
93      : base(original, cloner) {
94      cachedMinExpressionLength = new Dictionary<string, int>();
95      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
96      cachedMinExpressionDepth = new Dictionary<string, int>();
97      cachedMaxExpressionDepth = new Dictionary<string, int>();
98
99      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
100      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
101
102      symbols = original.symbols.ToDictionary(x => x.Key, y => cloner.Clone(y.Value));
103      symbolSubtreeCount = new Dictionary<string, Tuple<int, int>>(original.symbolSubtreeCount);
104
105      allowedChildSymbols = new Dictionary<string, List<string>>();
106      foreach (var element in original.allowedChildSymbols)
107        allowedChildSymbols.Add(element.Key, new List<string>(element.Value));
108
109      allowedChildSymbolsPerIndex = new Dictionary<Tuple<string, int>, List<string>>();
110      foreach (var element in original.allowedChildSymbolsPerIndex)
111        allowedChildSymbolsPerIndex.Add(element.Key, new List<string>(element.Value));
112
113      suppressEvents = false;
114    }
115
116    protected SymbolicExpressionGrammarBase(string name, string description)
117      : base(name, description) {
118      cachedMinExpressionLength = new Dictionary<string, int>();
119      cachedMaxExpressionLength = new Dictionary<Tuple<string, int>, int>();
120      cachedMinExpressionDepth = new Dictionary<string, int>();
121      cachedMaxExpressionDepth = new Dictionary<string, int>();
122
123      cachedIsAllowedChildSymbol = new Dictionary<Tuple<string, string>, bool>();
124      cachedIsAllowedChildSymbolIndex = new Dictionary<Tuple<string, string, int>, bool>();
125
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    protected 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    protected 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    protected 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    protected 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    protected 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    protected 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    protected 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;
317    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child) {
318      if (!child.Enabled) return false;
319
320      bool result;
321      if (cachedIsAllowedChildSymbol.TryGetValue(Tuple.Create(parent.Name, child.Name), out result)) return result;
322      List<string> temp;
323      if (allowedChildSymbols.TryGetValue(parent.Name, out temp)) {
324        //if (temp.Contains(child.Name)) return true;
325        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
326          cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), true);
327          return true;
328        }
329      }
330      cachedIsAllowedChildSymbol.Add(Tuple.Create(parent.Name, child.Name), false);
331      return false;
332    }
333
334    private readonly Dictionary<Tuple<string, string, int>, bool> cachedIsAllowedChildSymbolIndex;
335    public virtual bool IsAllowedChildSymbol(ISymbol parent, ISymbol child, int argumentIndex) {
336      if (!child.Enabled) return false;
337      if (IsAllowedChildSymbol(parent, child)) return true;
338
339      bool result;
340      if (cachedIsAllowedChildSymbolIndex.TryGetValue(Tuple.Create(parent.Name, child.Name, argumentIndex), out result)) return result;
341      List<string> temp;
342      var key = Tuple.Create(parent.Name, argumentIndex);
343      if (allowedChildSymbolsPerIndex.TryGetValue(key, out temp)) {
344        //if (temp.Contains(child.Name)) return true;
345        if (temp.SelectMany(s => GetSymbol(s).Flatten()).Where(s => s.Name == child.Name).Any()) {
346          cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), true);
347          return true;
348        }
349      }
350      cachedIsAllowedChildSymbolIndex.Add(Tuple.Create(parent.Name, child.Name, argumentIndex), false);
351      return false;
352    }
353
354    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent) {
355      return from child in AllowedSymbols
356             where IsAllowedChildSymbol(parent, child)
357             select child;
358    }
359
360    public IEnumerable<ISymbol> GetAllowedChildSymbols(ISymbol parent, int argumentIndex) {
361      return from child in AllowedSymbols
362             where IsAllowedChildSymbol(parent, child, argumentIndex)
363             select child;
364    }
365
366    public virtual int GetMinimumSubtreeCount(ISymbol symbol) {
367      return symbolSubtreeCount[symbol.Name].Item1;
368    }
369    public virtual int GetMaximumSubtreeCount(ISymbol symbol) {
370      return symbolSubtreeCount[symbol.Name].Item2;
371    }
372
373    protected void ClearCaches() {
374      cachedMinExpressionLength.Clear();
375      cachedMaxExpressionLength.Clear();
376      cachedMinExpressionDepth.Clear();
377      cachedMaxExpressionDepth.Clear();
378
379      cachedIsAllowedChildSymbol.Clear();
380      cachedIsAllowedChildSymbolIndex.Clear();
381    }
382
383    private readonly Dictionary<string, int> cachedMinExpressionLength;
384    public int GetMinimumExpressionLength(ISymbol symbol) {
385      int temp;
386      if (!cachedMinExpressionLength.TryGetValue(symbol.Name, out temp)) {
387        cachedMinExpressionLength[symbol.Name] = int.MaxValue; // prevent infinite recursion
388        long sumOfMinExpressionLengths = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
389                                              let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
390                                                                      where s.InitialFrequency > 0.0
391                                                                      select GetMinimumExpressionLength(s)).DefaultIfEmpty(0).Min()
392                                              select minForSlot).DefaultIfEmpty(0).Sum();
393
394        cachedMinExpressionLength[symbol.Name] = (int)Math.Min(sumOfMinExpressionLengths, int.MaxValue);
395        return cachedMinExpressionLength[symbol.Name];
396      }
397      return temp;
398    }
399
400    private readonly Dictionary<Tuple<string, int>, int> cachedMaxExpressionLength;
401    public int GetMaximumExpressionLength(ISymbol symbol, int maxDepth) {
402      int temp;
403      var key = Tuple.Create(symbol.Name, maxDepth);
404      if (!cachedMaxExpressionLength.TryGetValue(key, out temp)) {
405        cachedMaxExpressionLength[key] = int.MaxValue; // prevent infinite recursion
406        long sumOfMaxTrees = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
407                                  let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
408                                                          where s.InitialFrequency > 0.0
409                                                          where GetMinimumExpressionDepth(s) < maxDepth
410                                                          select GetMaximumExpressionLength(s, maxDepth - 1)).DefaultIfEmpty(0).Max()
411                                  select maxForSlot).DefaultIfEmpty(0).Sum();
412        cachedMaxExpressionLength[key] = (int)Math.Min(sumOfMaxTrees, int.MaxValue);
413        return cachedMaxExpressionLength[key];
414      }
415      return temp;
416    }
417
418    private readonly Dictionary<string, int> cachedMinExpressionDepth;
419    public int GetMinimumExpressionDepth(ISymbol symbol) {
420      int temp;
421      if (!cachedMinExpressionDepth.TryGetValue(symbol.Name, out temp)) {
422        cachedMinExpressionDepth[symbol.Name] = int.MaxValue; // prevent infinite recursion
423        long minDepth = 1 + (from argIndex in Enumerable.Range(0, GetMinimumSubtreeCount(symbol))
424                             let minForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
425                                                     where s.InitialFrequency > 0.0
426                                                     select GetMinimumExpressionDepth(s)).DefaultIfEmpty(0).Min()
427                             select minForSlot).DefaultIfEmpty(0).Max();
428        cachedMinExpressionDepth[symbol.Name] = (int)Math.Min(minDepth, int.MaxValue);
429        return cachedMinExpressionDepth[symbol.Name];
430      }
431      return temp;
432    }
433
434    private readonly Dictionary<string, int> cachedMaxExpressionDepth;
435    public int GetMaximumExpressionDepth(ISymbol symbol) {
436      int temp;
437      if (!cachedMaxExpressionDepth.TryGetValue(symbol.Name, out temp)) {
438        cachedMaxExpressionDepth[symbol.Name] = int.MaxValue;
439        long maxDepth = 1 + (from argIndex in Enumerable.Range(0, GetMaximumSubtreeCount(symbol))
440                             let maxForSlot = (long)(from s in GetAllowedChildSymbols(symbol, argIndex)
441                                                     where s.InitialFrequency > 0.0
442                                                     select GetMaximumExpressionDepth(s)).DefaultIfEmpty(0).Max()
443                             select maxForSlot).DefaultIfEmpty(0).Max();
444        cachedMaxExpressionDepth[symbol.Name] = (int)Math.Min(maxDepth, int.MaxValue);
445        return cachedMaxExpressionDepth[symbol.Name];
446      }
447      return temp;
448    }
449
450    public event EventHandler Changed;
451    protected virtual void OnChanged() {
452      if (suppressEvents) return;
453      var handler = Changed;
454      if (handler != null) Changed(this, EventArgs.Empty);
455    }
456  }
457}
Note: See TracBrowser for help on using the repository browser.