source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/DerivativeCalculator.cs @ 17066

Last change on this file since 17066 was 17066, checked in by mkommend, 2 years ago

#2948: Merged 16206, 16207, 16213, 16216, 16294 to stable.

File size: 9.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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 Constant constantSy = new Constant();
44    private static readonly Addition addSy = new Addition();
45    private static readonly Subtraction subSy = new Subtraction();
46    private static readonly Multiplication mulSy = new Multiplication();
47    private static readonly Division divSy = new Division();
48    private static readonly Cosine cosSy = new Cosine();
49    private static readonly Square sqrSy = new Square();
50
51    public static ISymbolicExpressionTreeNode Derive(ISymbolicExpressionTreeNode branch, string variableName) {
52      if (branch.Symbol is Constant) {
53        return CreateConstant(0.0);
54      }
55      if (branch.Symbol is Variable) {
56        var varNode = branch as VariableTreeNode;
57        if (varNode.VariableName == variableName) {
58          return CreateConstant(varNode.Weight);
59        } else {
60          return CreateConstant(0.0);
61        }
62      }
63      if (branch.Symbol is Addition) {
64        var sum = addSy.CreateTreeNode();
65        foreach (var subTree in branch.Subtrees) {
66          sum.AddSubtree(Derive(subTree, variableName));
67        }
68        return sum;
69      }
70      if (branch.Symbol is Subtraction) {
71        var sum = subSy.CreateTreeNode();
72        foreach (var subTree in branch.Subtrees) {
73          sum.AddSubtree(Derive(subTree, variableName));
74        }
75        return sum;
76      }
77      if (branch.Symbol is Multiplication) {
78        // (f * g)' = f'*g + f*g'
79        // for multiple factors: (f * g * h)' = ((f*g) * h)' = (f*g)' * h + (f*g) * h'
80
81        if (branch.SubtreeCount >= 2) {
82          var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
83          var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone();
84          var fprime = Derive(f, variableName);
85          var gprime = Derive(g, variableName);
86          var fgPrime = Sum(Product(f, gprime), Product(fprime, g));
87          for (int i = 2; i < branch.SubtreeCount; i++) {
88            var fg = Product((ISymbolicExpressionTreeNode)f.Clone(), (ISymbolicExpressionTreeNode)g.Clone());
89            var h = (ISymbolicExpressionTreeNode)branch.GetSubtree(i).Clone();
90            var hPrime = Derive(h, variableName);
91            fgPrime = Sum(Product(fgPrime, h), Product(fg, hPrime));
92          }
93          return fgPrime;
94        } else
95          // multiplication with only one argument has no effect -> derive the argument
96          return Derive(branch.GetSubtree(0), variableName);
97      }
98      if (branch.Symbol is Division) {
99        // (f/g)' = (f'g - g'f) / g²
100        if (branch.SubtreeCount == 1) {
101          var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
102          var gPrime = Product(CreateConstant(-1.0), Derive(g, variableName));
103          var sqrNode = new Square().CreateTreeNode();
104          sqrNode.AddSubtree(g);
105          return Div(gPrime, sqrNode);
106        } else {
107          // for two subtrees:
108          // (f/g)' = (f'g - fg')/g²
109
110          // if there are more than 2 subtrees
111          // div(x,y,z) is interpretered as (x/y)/z
112          // which is the same as x / (y*z)
113
114          // --> make a product of all but the first subtree and differentiate as for the 2-argument case above
115          var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
116          var g = Product(branch.Subtrees.Skip(1).Select(n => (ISymbolicExpressionTreeNode)n.Clone()));
117          var fprime = Derive(f, variableName);
118          var gprime = Derive(g, variableName);
119          var gSqr = Square(g);
120          return Div(Subtract(Product(fprime, g), Product(f, gprime)), gSqr);
121        }
122      }
123      if (branch.Symbol is Logarithm) {
124        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
125        return Product(Div(CreateConstant(1.0), f), Derive(f, variableName));
126      }
127      if (branch.Symbol is Exponential) {
128        var f = (ISymbolicExpressionTreeNode)branch.Clone();
129        return Product(f, Derive(branch.GetSubtree(0), variableName));
130      }
131      if (branch.Symbol is Square) {
132        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
133        return Product(Product(CreateConstant(2.0), f), Derive(f, variableName));
134      }
135      if (branch.Symbol is SquareRoot) {
136        var f = (ISymbolicExpressionTreeNode)branch.Clone();
137        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
138        return Product(Div(CreateConstant(1.0), Product(CreateConstant(2.0), f)), Derive(u, variableName));
139      }
140      if (branch.Symbol is Sine) {
141        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
142        var cos = (new Cosine()).CreateTreeNode();
143        cos.AddSubtree(u);
144        return Product(cos, Derive(u, variableName));
145      }
146      if (branch.Symbol is Cosine) {
147        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
148        var sin = (new Sine()).CreateTreeNode();
149        sin.AddSubtree(u);
150        return Product(CreateConstant(-1.0), Product(sin, Derive(u, variableName)));
151      }
152      if (branch.Symbol is Tangent) {
153        // tan(x)' = 1 / cos²(x)
154        var fxp = Derive(branch.GetSubtree(0), variableName);
155        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
156        return Div(fxp, Square(Cosine(u)));
157      }
158      throw new NotSupportedException(string.Format("Symbol {0} is not supported.", branch.Symbol));
159    }
160
161
162    private static ISymbolicExpressionTreeNode Product(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
163      var product = mulSy.CreateTreeNode();
164      product.AddSubtree(f);
165      product.AddSubtree(g);
166      return product;
167    }
168    private static ISymbolicExpressionTreeNode Product(IEnumerable<ISymbolicExpressionTreeNode> fs) {
169      var product = mulSy.CreateTreeNode();
170      foreach (var f in fs) product.AddSubtree(f);
171      return product;
172    }
173    private static ISymbolicExpressionTreeNode Div(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
174      var div = divSy.CreateTreeNode();
175      div.AddSubtree(f);
176      div.AddSubtree(g);
177      return div;
178    }
179
180    private static ISymbolicExpressionTreeNode Sum(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
181      var sum = addSy.CreateTreeNode();
182      sum.AddSubtree(f);
183      sum.AddSubtree(g);
184      return sum;
185    }
186    private static ISymbolicExpressionTreeNode Subtract(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
187      var sum = subSy.CreateTreeNode();
188      sum.AddSubtree(f);
189      sum.AddSubtree(g);
190      return sum;
191    }
192    private static ISymbolicExpressionTreeNode Cosine(ISymbolicExpressionTreeNode f) {
193      var cos = cosSy.CreateTreeNode();
194      cos.AddSubtree(f);
195      return cos;
196    }
197    private static ISymbolicExpressionTreeNode Square(ISymbolicExpressionTreeNode f) {
198      var sqr = sqrSy.CreateTreeNode();
199      sqr.AddSubtree(f);
200      return sqr;
201    }
202
203    private static ISymbolicExpressionTreeNode CreateConstant(double v) {
204      var constNode = (ConstantTreeNode)constantSy.CreateTreeNode();
205      constNode.Value = v;
206      return constNode;
207    }
208
209    public static bool IsCompatible(ISymbolicExpressionTree tree) {
210      var containsUnknownSymbol = (
211        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
212        where
213          !(n.Symbol is Variable) &&
214          !(n.Symbol is Constant) &&
215          !(n.Symbol is Addition) &&
216          !(n.Symbol is Subtraction) &&
217          !(n.Symbol is Multiplication) &&
218          !(n.Symbol is Division) &&
219          !(n.Symbol is Logarithm) &&
220          !(n.Symbol is Exponential) &&
221          !(n.Symbol is Square) &&
222          !(n.Symbol is SquareRoot) &&
223          !(n.Symbol is Sine) &&
224          !(n.Symbol is Cosine) &&
225          !(n.Symbol is Tangent) &&
226          !(n.Symbol is StartSymbol)
227        select n).Any();
228      return !containsUnknownSymbol;
229    }
230  }
231}
Note: See TracBrowser for help on using the repository browser.