Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/ArithmeticExpressionGrammar.cs @ 3253

Last change on this file since 3253 was 3253, checked in by gkronber, 13 years ago

Implemented basic framework for symbolic regression problems for HL 3.3. #938 (Data types and operators for regression problems)

File size: 5.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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
22
23using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
24using System.Collections.Generic;
25using System;
26using System.Linq;
27using HeuristicLab.Core;
28using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
31  [StorableClass]
32  public class ArithmeticExpressionGrammar : Item, ISymbolicExpressionGrammar {
33
34    private class EmptySymbol : Symbol {
35      public EmptySymbol() {
36        Name = "Start";
37      }
38    }
39
40    public ArithmeticExpressionGrammar()
41      : base() {
42    }
43    #region ISymbolicExpressionGrammar Members
44    [Storable]
45    private EmptySymbol startSymbol = new EmptySymbol();
46    public Symbol StartSymbol {
47      get { return startSymbol; }
48    }
49
50    [Storable]
51    private static List<Symbol> allSymbols = new List<Symbol>() {
52      new Addition(),
53      new Subtraction(),
54      new Multiplication(),
55      new Division(),
56      new Constant(),
57      new HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable()
58    };
59    [Storable]
60    private Dictionary<Type, Dictionary<int, IEnumerable<Symbol>>> allowedSymbols = new Dictionary<Type, Dictionary<int, IEnumerable<Symbol>>>() {
61      {
62        typeof(EmptySymbol),
63        new Dictionary<int, IEnumerable<Symbol>>()
64        {
65          { 0, allSymbols},
66        }
67      },      {
68        typeof(Addition),
69        new Dictionary<int, IEnumerable<Symbol>>()
70        {
71          { 0, allSymbols},
72          { 1, allSymbols}
73        }
74      },
75      {
76        typeof(Subtraction),
77        new Dictionary<int, IEnumerable<Symbol>>()
78        {
79          { 0, allSymbols},
80          { 1, allSymbols}
81        }
82      },
83      {
84        typeof(Multiplication),
85        new Dictionary<int, IEnumerable<Symbol>>()
86        {
87          { 0, allSymbols},
88          { 1, allSymbols}
89        }
90      },
91      {
92        typeof(Division),
93        new Dictionary<int, IEnumerable<Symbol>>()
94        {
95          { 0, allSymbols},
96          { 1, allSymbols}
97        }
98      },
99    };
100    public IEnumerable<Symbol> AllowedSymbols(Symbol parent, int argumentIndex) {
101      return allowedSymbols[parent.GetType()][argumentIndex];
102    }
103
104    [Storable]
105    private Dictionary<Type, int> minLength = new Dictionary<Type, int>() {
106      {typeof(EmptySymbol), 1},
107      {typeof(Addition), 3},
108      {typeof(Subtraction), 3},
109      {typeof(Multiplication), 4},
110      {typeof(Division), 4},
111      {typeof(Constant), 1},
112      {typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), 1},
113    };
114    public int MinimalExpressionLength(Symbol start) {
115      return minLength[start.GetType()];
116    }
117
118    [Storable]
119    private Dictionary<Type, int> maxLength = new Dictionary<Type, int>() {
120      {typeof(EmptySymbol), int.MaxValue},
121      {typeof(Addition), int.MaxValue},
122      {typeof(Subtraction), int.MaxValue},
123      {typeof(Multiplication), int.MaxValue},
124      {typeof(Division), int.MaxValue},
125      {typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), 1},
126      {typeof(Constant), 1},
127    };
128    public int MaximalExpressionLength(Symbol start) {
129      return maxLength[start.GetType()];
130    }
131
132    [Storable]
133    private Dictionary<Type, int> minDepth = new Dictionary<Type, int>() {
134      {typeof(EmptySymbol), 1},
135      {typeof(Addition), 1},
136      {typeof(Subtraction), 1},
137      {typeof(Multiplication), 1},
138      {typeof(Division), 1},
139      {typeof(Constant), 0},
140      {typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), 0}
141    };
142    public int MinimalExpressionDepth(Symbol start) {
143      return minDepth[start.GetType()];
144    }
145
146    [Storable]
147    private Dictionary<Type, int> subTrees = new Dictionary<Type, int>() {
148      {typeof(EmptySymbol), 1},
149      {typeof(Addition), 2},
150      {typeof(Subtraction), 2},
151      {typeof(Multiplication), 2},
152      {typeof(Division), 2},
153      {typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), 0},
154      {typeof(Constant), 0},
155    };
156    public int MinSubTrees(Symbol start) {
157      return subTrees[start.GetType()];
158    }
159    public int MaxSubTrees(Symbol start) {
160      return subTrees[start.GetType()];
161    }
162
163    #endregion
164
165    #region ISymbolicExpressionGrammar Members
166
167
168    public bool IsValidExpression(SymbolicExpressionTree expression) {
169      if (expression.Root.Symbol != StartSymbol) return false;
170      return IsValidExpression(expression.Root);
171    }
172
173    #endregion
174
175    private bool IsValidExpression(SymbolicExpressionTreeNode root) {
176      if (root.SubTrees.Count < MinSubTrees(root.Symbol)) return false;
177      if (root.SubTrees.Count > MaxSubTrees(root.Symbol)) return false;
178      for (int i = 0; i < root.SubTrees.Count; i++) {
179        if (!AllowedSymbols(root.Symbol, i).Contains(root.SubTrees[i].Symbol)) return false;
180        if (!IsValidExpression(root.SubTrees[i])) return false;
181      }
182      return true;
183    }
184  }
185}
Note: See TracBrowser for help on using the repository browser.