Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.DataAnalysis/3.3/Symbolic/SimpleArithmeticExpressionInterpreter.cs @ 5295

Last change on this file since 5295 was 5288, checked in by mkommend, 14 years ago

Implemented Power symbol for GP (ticket #1374).
File size: 13.1 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
22using System;
23using System.Collections.Generic;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Compiler;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Symbols;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  [StorableClass]
34  [Item("SimpleArithmeticExpressionInterpreter", "Interpreter for arithmetic symbolic expression trees including function calls.")]
35  public sealed class SimpleArithmeticExpressionInterpreter : NamedItem, ISymbolicExpressionTreeInterpreter {
36    private class OpCodes {
37      public const byte Add = 1;
38      public const byte Sub = 2;
39      public const byte Mul = 3;
40      public const byte Div = 4;
41
42      public const byte Sin = 5;
43      public const byte Cos = 6;
44      public const byte Tan = 7;
45
46      public const byte Log = 8;
47      public const byte Exp = 9;
48
49      public const byte IfThenElse = 10;
50
51      public const byte GT = 11;
52      public const byte LT = 12;
53
54      public const byte AND = 13;
55      public const byte OR = 14;
56      public const byte NOT = 15;
57
58
59      public const byte Average = 16;
60
61      public const byte Call = 17;
62
63      public const byte Variable = 18;
64      public const byte LagVariable = 19;
65      public const byte Constant = 20;
66      public const byte Arg = 21;
67
68      public const byte Power = 22;
69    }
70
71    private Dictionary<Type, byte> symbolToOpcode = new Dictionary<Type, byte>() {
72      { typeof(Addition), OpCodes.Add },
73      { typeof(Subtraction), OpCodes.Sub },
74      { typeof(Multiplication), OpCodes.Mul },
75      { typeof(Division), OpCodes.Div },
76      { typeof(Sine), OpCodes.Sin },
77      { typeof(Cosine), OpCodes.Cos },
78      { typeof(Tangent), OpCodes.Tan },
79      { typeof(Logarithm), OpCodes.Log },
80      { typeof(Exponential), OpCodes.Exp },
81      { typeof(IfThenElse), OpCodes.IfThenElse },
82      { typeof(GreaterThan), OpCodes.GT },
83      { typeof(LessThan), OpCodes.LT },
84      { typeof(And), OpCodes.AND },
85      { typeof(Or), OpCodes.OR },
86      { typeof(Not), OpCodes.NOT},
87      { typeof(Average), OpCodes.Average},
88      { typeof(InvokeFunction), OpCodes.Call },
89      { typeof(HeuristicLab.Problems.DataAnalysis.Symbolic.Symbols.Variable), OpCodes.Variable },
90      { typeof(LaggedVariable), OpCodes.LagVariable },
91      { typeof(Constant), OpCodes.Constant },
92      { typeof(Argument), OpCodes.Arg },
93      { typeof(Power),OpCodes.Power},
94    };
95    private const int ARGUMENT_STACK_SIZE = 1024;
96
97    public override bool CanChangeName {
98      get { return false; }
99    }
100    public override bool CanChangeDescription {
101      get { return false; }
102    }
103
104    [StorableConstructor]
105    private SimpleArithmeticExpressionInterpreter(bool deserializing) : base(deserializing) { }
106    private SimpleArithmeticExpressionInterpreter(SimpleArithmeticExpressionInterpreter original, Cloner cloner) : base(original, cloner) { }
107    public override IDeepCloneable Clone(Cloner cloner) {
108      return new SimpleArithmeticExpressionInterpreter(this, cloner);
109    }
110
111    public SimpleArithmeticExpressionInterpreter()
112      : base() {
113    }
114
115    public IEnumerable<double> GetSymbolicExpressionTreeValues(SymbolicExpressionTree tree, Dataset dataset, IEnumerable<int> rows) {
116      var compiler = new SymbolicExpressionTreeCompiler();
117      Instruction[] code = compiler.Compile(tree, MapSymbolToOpCode);
118
119      for (int i = 0; i < code.Length; i++) {
120        Instruction instr = code[i];
121        if (instr.opCode == OpCodes.Variable) {
122          var variableTreeNode = instr.dynamicNode as VariableTreeNode;
123          instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
124          code[i] = instr;
125        } else if (instr.opCode == OpCodes.LagVariable) {
126          var variableTreeNode = instr.dynamicNode as LaggedVariableTreeNode;
127          instr.iArg0 = (ushort)dataset.GetVariableIndex(variableTreeNode.VariableName);
128          code[i] = instr;
129        }
130      }
131
132      double[] argumentStack = new double[ARGUMENT_STACK_SIZE];
133      foreach (var rowEnum in rows) {
134        int row = rowEnum;
135        int pc = 0;
136        int argStackPointer = 0;
137        yield return Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
138      }
139    }
140
141    private double Evaluate(Dataset dataset, ref int row, Instruction[] code, ref int pc, double[] argumentStack, ref int argStackPointer) {
142      Instruction currentInstr = code[pc++];
143      switch (currentInstr.opCode) {
144        case OpCodes.Add: {
145            double s = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
146            for (int i = 1; i < currentInstr.nArguments; i++) {
147              s += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
148            }
149            return s;
150          }
151        case OpCodes.Sub: {
152            double s = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
153            for (int i = 1; i < currentInstr.nArguments; i++) {
154              s -= Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
155            }
156            if (currentInstr.nArguments == 1) s = -s;
157            return s;
158          }
159        case OpCodes.Mul: {
160            double p = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
161            for (int i = 1; i < currentInstr.nArguments; i++) {
162              p *= Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
163            }
164            return p;
165          }
166        case OpCodes.Div: {
167            double p = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
168            for (int i = 1; i < currentInstr.nArguments; i++) {
169              p /= Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
170            }
171            if (currentInstr.nArguments == 1) p = 1.0 / p;
172            return p;
173          }
174        case OpCodes.Average: {
175            double sum = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
176            for (int i = 1; i < currentInstr.nArguments; i++) {
177              sum += Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
178            }
179            return sum / currentInstr.nArguments;
180          }
181        case OpCodes.Cos: {
182            return Math.Cos(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));
183          }
184        case OpCodes.Sin: {
185            return Math.Sin(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));
186          }
187        case OpCodes.Tan: {
188            return Math.Tan(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));
189          }
190        case OpCodes.Power: {
191            double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
192            double y = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
193            return Math.Pow(x, y);
194          }
195        case OpCodes.Exp: {
196            return Math.Exp(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));
197          }
198        case OpCodes.Log: {
199            return Math.Log(Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer));
200          }
201        case OpCodes.IfThenElse: {
202            double condition = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
203            double result;
204            if (condition > 0.0) {
205              result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer); SkipBakedCode(code, ref pc);
206            } else {
207              SkipBakedCode(code, ref pc); result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
208            }
209            return result;
210          }
211        case OpCodes.AND: {
212            double result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
213            for (int i = 1; i < currentInstr.nArguments; i++) {
214              if (result <= 0.0) SkipBakedCode(code, ref pc);
215              else {
216                result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
217              }
218            }
219            return result <= 0.0 ? -1.0 : 1.0;
220          }
221        case OpCodes.OR: {
222            double result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
223            for (int i = 1; i < currentInstr.nArguments; i++) {
224              if (result > 0.0) SkipBakedCode(code, ref pc);
225              else {
226                result = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
227              }
228            }
229            return result > 0.0 ? 1.0 : -1.0;
230          }
231        case OpCodes.NOT: {
232            return -Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
233          }
234        case OpCodes.GT: {
235            double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
236            double y = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
237            if (x > y) return 1.0;
238            else return -1.0;
239          }
240        case OpCodes.LT: {
241            double x = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
242            double y = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
243            if (x < y) return 1.0;
244            else return -1.0;
245          }
246        case OpCodes.Call: {
247            // evaluate sub-trees
248            // push on argStack in reverse order
249            for (int i = 0; i < currentInstr.nArguments; i++) {
250              argumentStack[argStackPointer + currentInstr.nArguments - i] = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
251            }
252            argStackPointer += currentInstr.nArguments;
253
254            // save the pc
255            int nextPc = pc;
256            // set pc to start of function 
257            pc = currentInstr.iArg0;
258            // evaluate the function
259            double v = Evaluate(dataset, ref row, code, ref pc, argumentStack, ref argStackPointer);
260
261            // decrease the argument stack pointer by the number of arguments pushed
262            // to set the argStackPointer back to the original location
263            argStackPointer -= currentInstr.nArguments;
264
265            // restore the pc => evaluation will continue at point after my subtrees 
266            pc = nextPc;
267            return v;
268          }
269        case OpCodes.Arg: {
270            return argumentStack[argStackPointer - currentInstr.iArg0];
271          }
272        case OpCodes.Variable: {
273            var variableTreeNode = currentInstr.dynamicNode as VariableTreeNode;
274            return dataset[row, currentInstr.iArg0] * variableTreeNode.Weight;
275          }
276        case OpCodes.LagVariable: {
277            var laggedVariableTreeNode = currentInstr.dynamicNode as LaggedVariableTreeNode;
278            int actualRow = row + laggedVariableTreeNode.Lag;
279            if (actualRow < 0 || actualRow >= dataset.Rows) throw new ArgumentException("Out of range access to dataset row: " + row);
280            return dataset[actualRow, currentInstr.iArg0] * laggedVariableTreeNode.Weight;
281          }
282        case OpCodes.Constant: {
283            var constTreeNode = currentInstr.dynamicNode as ConstantTreeNode;
284            return constTreeNode.Value;
285          }
286        default: throw new NotSupportedException();
287      }
288    }
289
290    private byte MapSymbolToOpCode(SymbolicExpressionTreeNode treeNode) {
291      if (symbolToOpcode.ContainsKey(treeNode.Symbol.GetType()))
292        return symbolToOpcode[treeNode.Symbol.GetType()];
293      else
294        throw new NotSupportedException("Symbol: " + treeNode.Symbol);
295    }
296
297    // skips a whole branch
298    private void SkipBakedCode(Instruction[] code, ref int pc) {
299      int i = 1;
300      while (i > 0) {
301        i += code[pc++].nArguments;
302        i--;
303      }
304    }
305  }
306}
Note: See TracBrowser for help on using the repository browser.