source: branches/3140_NumberSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/DerivativeCalculator.cs @ 18113

Last change on this file since 18113 was 18113, checked in by chaider, 8 months ago

#3140

  • Refactored ConstantOptimization ==> ParameterOptimization
File size: 12.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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.Encodings.SymbolicExpressionTreeEncoding;
26
27namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
28  public static class DerivativeCalculator {
29    public static ISymbolicExpressionTree Derive(ISymbolicExpressionTree tree, string variableName) {
30      if (tree.Root.SubtreeCount != 1)
31        throw new NotImplementedException("Derive is not implemented for symbolic expressions with automatically defined functions (ADF)");
32      if (tree.Root.GetSubtree(0).SubtreeCount != 1)
33        throw new NotImplementedException("Derive is not implemented for multi-variate symbolic expressions");
34      var mainBranch = tree.Root.GetSubtree(0).GetSubtree(0);
35      var root = new ProgramRootSymbol().CreateTreeNode();
36      root.AddSubtree(new StartSymbol().CreateTreeNode());
37      var dTree = TreeSimplifier.GetSimplifiedTree(Derive(mainBranch, variableName));
38      //var dTree = Derive(mainBranch, variableName);
39      root.GetSubtree(0).AddSubtree(dTree);
40      return new SymbolicExpressionTree(root);
41    }
42
43    private static readonly Number numberSy = new Number();
44    private static readonly Constant constSy = new Constant();
45    private static readonly Addition addSy = new Addition();
46    private static readonly Subtraction subSy = new Subtraction();
47    private static readonly Multiplication mulSy = new Multiplication();
48    private static readonly Division divSy = new Division();
49    private static readonly Cosine cosSy = new Cosine();
50    private static readonly Square sqrSy = new Square();
51    private static readonly Absolute absSy = new Absolute();
52    private static readonly SquareRoot sqrtSy = new SquareRoot();
53
54    public static ISymbolicExpressionTreeNode Derive(ISymbolicExpressionTreeNode branch, string variableName) {
55      if (branch.Symbol is INumericSymbol) {
56        return CreateNumber(0.0);
57      }
58      if (branch.Symbol is Variable) {
59        var varNode = branch as VariableTreeNode;
60        if (varNode.VariableName == variableName) {
61          return CreateNumber(varNode.Weight);
62        } else {
63          return CreateNumber(0.0);
64        }
65      }
66      if (branch.Symbol is Addition) {
67        var sum = addSy.CreateTreeNode();
68        foreach (var subTree in branch.Subtrees) {
69          sum.AddSubtree(Derive(subTree, variableName));
70        }
71        return sum;
72      }
73      if (branch.Symbol is Subtraction) {
74        var sum = subSy.CreateTreeNode();
75        foreach (var subTree in branch.Subtrees) {
76          sum.AddSubtree(Derive(subTree, variableName));
77        }
78        return sum;
79      }
80      if (branch.Symbol is Multiplication) {
81        // (f * g)' = f'*g + f*g'
82        // for multiple factors: (f * g * h)' = ((f*g) * h)' = (f*g)' * h + (f*g) * h'
83
84        if (branch.SubtreeCount >= 2) {
85          var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
86          var fprime = Derive(f, variableName);
87          for (int i = 1; i < branch.SubtreeCount; i++) {
88            var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(i).Clone();
89            var fg = Product((ISymbolicExpressionTreeNode)f.Clone(), (ISymbolicExpressionTreeNode)g.Clone());
90            var gPrime = Derive(g, variableName);
91            var fgPrime = Sum(Product(fprime, g), Product(gPrime, f));
92            // prepare for next iteration
93            f = fg;
94            fprime = fgPrime;
95          }
96          return fprime;
97        } else
98          // multiplication with only one argument has no effect -> derive the argument
99          return Derive(branch.GetSubtree(0), variableName);
100      }
101      if (branch.Symbol is Division) {
102        // (f/g)' = (f'g - g'f) / g²
103        if (branch.SubtreeCount == 1) {
104          var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
105          var gPrime = Product(CreateNumber(-1.0), Derive(g, variableName));
106          var sqrNode = new Square().CreateTreeNode();
107          sqrNode.AddSubtree(g);
108          return Div(gPrime, sqrNode);
109        } else {
110          // for two subtrees:
111          // (f/g)' = (f'g - fg')/g²
112
113          // if there are more than 2 subtrees
114          // div(x,y,z) is interpretered as (x/y)/z
115          // which is the same as x / (y*z)
116
117          // --> make a product of all but the first subtree and differentiate as for the 2-argument case above
118          var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
119          var g = Product(branch.Subtrees.Skip(1).Select(n => (ISymbolicExpressionTreeNode)n.Clone()));
120          var fprime = Derive(f, variableName);
121          var gprime = Derive(g, variableName);
122          var gSqr = Square(g);
123          return Div(Subtract(Product(fprime, g), Product(f, gprime)), gSqr);
124        }
125      }
126      if (branch.Symbol is Logarithm) {
127        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
128        return Product(Div(CreateNumber(1.0), f), Derive(f, variableName));
129      }
130      if (branch.Symbol is Exponential) {
131        var f = (ISymbolicExpressionTreeNode)branch.Clone();
132        return Product(f, Derive(branch.GetSubtree(0), variableName));
133      }
134      if (branch.Symbol is Square) {
135        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
136        return Product(Product(CreateNumber(2.0), f), Derive(f, variableName));
137      }
138      if (branch.Symbol is SquareRoot) {
139        var f = (ISymbolicExpressionTreeNode)branch.Clone();
140        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
141        return Product(Div(CreateNumber(1.0), Product(CreateNumber(2.0), f)), Derive(u, variableName));
142      }
143      if (branch.Symbol is CubeRoot) {
144        var f = (ISymbolicExpressionTreeNode)branch.Clone();
145        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
146        return Product(Div(CreateNumber(1.0), Product(CreateNumber(3.0), Square(f))), Derive(u, variableName));  // 1/3 1/cbrt(f(x))^2 d/dx f(x)
147      }
148      if (branch.Symbol is Cube) {
149        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
150        return Product(Product(CreateNumber(3.0), Square(f)), Derive(f, variableName));
151      }
152      if (branch.Symbol is Power) {
153        // HL evaluators handle power strangely (exponent is rounded to an integer)
154        // here we only support the case when the exponent is a constant integer
155        var exponent = branch.GetSubtree(1) as INumericTreeNode;
156        if (exponent != null && Math.Truncate(exponent.Value) == exponent.Value) {
157          var newPower = (ISymbolicExpressionTreeNode)branch.Clone();
158          var f = (ISymbolicExpressionTreeNode)newPower.GetSubtree(0).Clone();
159          var newExponent = (INumericTreeNode)newPower.GetSubtree(1);
160          newExponent.Value -= 1;
161          return Product(Product(CreateNumber(exponent.Value), newPower), Derive(f, variableName));
162        } else throw new NotSupportedException("Cannot derive non-integer powers");
163      }
164      if (branch.Symbol is Absolute) {
165        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
166        var absf = Abs((ISymbolicExpressionTreeNode)f.Clone());
167        return Product(Div(f, absf), Derive(f, variableName));
168      }
169      if (branch.Symbol is AnalyticQuotient) {
170        // aq(a(x), b(x)) = a(x) / sqrt(b(x)²+1)
171        var a = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
172        var b = (ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone();
173
174        var definition = Div(a, SquareRoot(Sum(Square(b), CreateNumber(1.0))));
175        return Derive(definition, variableName);
176      }
177      if (branch.Symbol is Sine) {
178        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
179        var cos = (new Cosine()).CreateTreeNode();
180        cos.AddSubtree(u);
181        return Product(cos, Derive(u, variableName));
182      }
183      if (branch.Symbol is Cosine) {
184        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
185        var sin = (new Sine()).CreateTreeNode();
186        sin.AddSubtree(u);
187        return Product(CreateNumber(-1.0), Product(sin, Derive(u, variableName)));
188      }
189      if (branch.Symbol is Tangent) {
190        // tan(x)' = 1 / cos²(x)
191        var fxp = Derive(branch.GetSubtree(0), variableName);
192        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
193        return Div(fxp, Square(Cosine(u)));
194      }
195      if (branch.Symbol is HyperbolicTangent) {
196        // tanh(f(x))' = f(x)'sech²(f(x)) = f(x)'(1 - tanh²(f(x)))
197        var fxp = Derive(branch.GetSubtree(0), variableName);
198        var tanh = (ISymbolicExpressionTreeNode)branch.Clone();
199        return Product(fxp, Subtract(CreateNumber(1.0), Square(tanh)));
200      }
201      throw new NotSupportedException(string.Format("Symbol {0} is not supported.", branch.Symbol));
202    }
203
204
205    private static ISymbolicExpressionTreeNode Product(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
206      var product = mulSy.CreateTreeNode();
207      product.AddSubtree(f);
208      product.AddSubtree(g);
209      return product;
210    }
211    private static ISymbolicExpressionTreeNode Product(IEnumerable<ISymbolicExpressionTreeNode> fs) {
212      var product = mulSy.CreateTreeNode();
213      foreach (var f in fs) product.AddSubtree(f);
214      return product;
215    }
216    private static ISymbolicExpressionTreeNode Div(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
217      var div = divSy.CreateTreeNode();
218      div.AddSubtree(f);
219      div.AddSubtree(g);
220      return div;
221    }
222
223    private static ISymbolicExpressionTreeNode Sum(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
224      var sum = addSy.CreateTreeNode();
225      sum.AddSubtree(f);
226      sum.AddSubtree(g);
227      return sum;
228    }
229    private static ISymbolicExpressionTreeNode Subtract(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
230      var sum = subSy.CreateTreeNode();
231      sum.AddSubtree(f);
232      sum.AddSubtree(g);
233      return sum;
234    }
235    private static ISymbolicExpressionTreeNode Cosine(ISymbolicExpressionTreeNode f) {
236      var cos = cosSy.CreateTreeNode();
237      cos.AddSubtree(f);
238      return cos;
239    }
240    private static ISymbolicExpressionTreeNode Abs(ISymbolicExpressionTreeNode f) {
241      var abs = absSy.CreateTreeNode();
242      abs.AddSubtree(f);
243      return abs;
244    }
245    private static ISymbolicExpressionTreeNode Square(ISymbolicExpressionTreeNode f) {
246      var sqr = sqrSy.CreateTreeNode();
247      sqr.AddSubtree(f);
248      return sqr;
249    }
250    private static ISymbolicExpressionTreeNode SquareRoot(ISymbolicExpressionTreeNode f) {
251      var sqrt = sqrtSy.CreateTreeNode();
252      sqrt.AddSubtree(f);
253      return sqrt;
254    }
255
256    private static ISymbolicExpressionTreeNode CreateNumber(double v) {
257      var numberNode = (NumberTreeNode)numberSy.CreateTreeNode();
258      numberNode.Value = v;
259      return numberNode;
260    }
261
262    public static bool IsCompatible(ISymbolicExpressionTree tree) {
263      var containsUnknownSymbol = (
264        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
265        where
266          !(n.Symbol is Variable) &&
267          !(n.Symbol is Number) &&
268          !(n.Symbol is Constant) &&
269          !(n.Symbol is Addition) &&
270          !(n.Symbol is Subtraction) &&
271          !(n.Symbol is Multiplication) &&
272          !(n.Symbol is Division) &&
273          !(n.Symbol is Logarithm) &&
274          !(n.Symbol is Exponential) &&
275          !(n.Symbol is Square) &&
276          !(n.Symbol is SquareRoot) &&
277          !(n.Symbol is Cube) &&
278          !(n.Symbol is CubeRoot) &&
279          !(n.Symbol is Power) &&
280          !(n.Symbol is Absolute) &&
281          !(n.Symbol is AnalyticQuotient) &&
282          !(n.Symbol is HyperbolicTangent) &&
283          !(n.Symbol is Sine) &&
284          !(n.Symbol is Cosine) &&
285          !(n.Symbol is Tangent) &&
286          !(n.Symbol is StartSymbol)
287        select n).Any();
288      return !containsUnknownSymbol;
289    }
290  }
291}
Note: See TracBrowser for help on using the repository browser.