1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022019 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  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;


26 


27  namespace 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 multivariate 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  private static readonly Absolute absSy = new Absolute();


51  private static readonly SquareRoot sqrtSy = new SquareRoot();


52 


53  public static ISymbolicExpressionTreeNode Derive(ISymbolicExpressionTreeNode branch, string variableName) {


54  if (branch.Symbol is Constant) {


55  return CreateConstant(0.0);


56  }


57  if (branch.Symbol is Variable) {


58  var varNode = branch as VariableTreeNode;


59  if (varNode.VariableName == variableName) {


60  return CreateConstant(varNode.Weight);


61  } else {


62  return CreateConstant(0.0);


63  }


64  }


65  if (branch.Symbol is Addition) {


66  var sum = addSy.CreateTreeNode();


67  foreach (var subTree in branch.Subtrees) {


68  sum.AddSubtree(Derive(subTree, variableName));


69  }


70  return sum;


71  }


72  if (branch.Symbol is Subtraction) {


73  var sum = subSy.CreateTreeNode();


74  foreach (var subTree in branch.Subtrees) {


75  sum.AddSubtree(Derive(subTree, variableName));


76  }


77  return sum;


78  }


79  if (branch.Symbol is Multiplication) {


80  // (f * g)' = f'*g + f*g'


81  // for multiple factors: (f * g * h)' = ((f*g) * h)' = (f*g)' * h + (f*g) * h'


82 


83  if (branch.SubtreeCount >= 2) {


84  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


85  var fprime = Derive(f, variableName);


86  for (int i = 1; i < branch.SubtreeCount; i++) {


87  var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(i).Clone();


88  var fg = Product((ISymbolicExpressionTreeNode)f.Clone(), (ISymbolicExpressionTreeNode)g.Clone());


89  var gPrime = Derive(g, variableName);


90  var fgPrime = Sum(Product(fprime, g), Product(gPrime, f));


91  // prepare for next iteration


92  f = fg;


93  fprime = fgPrime;


94  }


95  return fprime;


96  } else


97  // multiplication with only one argument has no effect > derive the argument


98  return Derive(branch.GetSubtree(0), variableName);


99  }


100  if (branch.Symbol is Division) {


101  // (f/g)' = (f'g  g'f) / g²


102  if (branch.SubtreeCount == 1) {


103  var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


104  var gPrime = Product(CreateConstant(1.0), Derive(g, variableName));


105  var sqrNode = new Square().CreateTreeNode();


106  sqrNode.AddSubtree(g);


107  return Div(gPrime, sqrNode);


108  } else {


109  // for two subtrees:


110  // (f/g)' = (f'g  fg')/g²


111 


112  // if there are more than 2 subtrees


113  // div(x,y,z) is interpretered as (x/y)/z


114  // which is the same as x / (y*z)


115 


116  // > make a product of all but the first subtree and differentiate as for the 2argument case above


117  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


118  var g = Product(branch.Subtrees.Skip(1).Select(n => (ISymbolicExpressionTreeNode)n.Clone()));


119  var fprime = Derive(f, variableName);


120  var gprime = Derive(g, variableName);


121  var gSqr = Square(g);


122  return Div(Subtract(Product(fprime, g), Product(f, gprime)), gSqr);


123  }


124  }


125  if (branch.Symbol is Logarithm) {


126  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


127  return Product(Div(CreateConstant(1.0), f), Derive(f, variableName));


128  }


129  if (branch.Symbol is Exponential) {


130  var f = (ISymbolicExpressionTreeNode)branch.Clone();


131  return Product(f, Derive(branch.GetSubtree(0), variableName));


132  }


133  if (branch.Symbol is Square) {


134  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


135  return Product(Product(CreateConstant(2.0), f), Derive(f, variableName));


136  }


137  if (branch.Symbol is SquareRoot) {


138  var f = (ISymbolicExpressionTreeNode)branch.Clone();


139  var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


140  return Product(Div(CreateConstant(1.0), Product(CreateConstant(2.0), f)), Derive(u, variableName));


141  }


142  if (branch.Symbol is CubeRoot) {


143  var f = (ISymbolicExpressionTreeNode)branch.Clone();


144  var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


145  return Product(Div(CreateConstant(1.0), Product(CreateConstant(3.0), Square(f))), Derive(u, variableName)); // 1/3 1/cbrt(f(x))^2 d/dx f(x)


146  }


147  if (branch.Symbol is Cube) {


148  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


149  return Product(Product(CreateConstant(3.0), Square(f)), Derive(f, variableName));


150  }


151  if (branch.Symbol is Absolute) {


152  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


153  var absf = Abs((ISymbolicExpressionTreeNode)f.Clone());


154  return Product(Div(f, absf), Derive(f, variableName));


155  }


156  if (branch.Symbol is AnalyticQuotient) {


157  // aq(a(x), b(x)) = a(x) / sqrt(b(x)²+1)


158  var a = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


159  var b = (ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone();


160 


161  var definition = Div(a, SquareRoot(Sum(Square(b), CreateConstant(1.0))));


162  return Derive(definition, variableName);


163  }


164  if (branch.Symbol is Sine) {


165  var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


166  var cos = (new Cosine()).CreateTreeNode();


167  cos.AddSubtree(u);


168  return Product(cos, Derive(u, variableName));


169  }


170  if (branch.Symbol is Cosine) {


171  var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


172  var sin = (new Sine()).CreateTreeNode();


173  sin.AddSubtree(u);


174  return Product(CreateConstant(1.0), Product(sin, Derive(u, variableName)));


175  }


176  if (branch.Symbol is Tangent) {


177  // tan(x)' = 1 / cos²(x)


178  var fxp = Derive(branch.GetSubtree(0), variableName);


179  var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


180  return Div(fxp, Square(Cosine(u)));


181  }


182  if (branch.Symbol is HyperbolicTangent) {


183  // tanh(f(x))' = f(x)'sech²(f(x)) = f(x)'(1  tanh²(f(x)))


184  var fxp = Derive(branch.GetSubtree(0), variableName);


185  var tanh = (ISymbolicExpressionTreeNode)branch.Clone();


186  return Product(fxp, Subtract(CreateConstant(1.0), Square(tanh)));


187  }


188  throw new NotSupportedException(string.Format("Symbol {0} is not supported.", branch.Symbol));


189  }


190 


191 


192  private static ISymbolicExpressionTreeNode Product(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {


193  var product = mulSy.CreateTreeNode();


194  product.AddSubtree(f);


195  product.AddSubtree(g);


196  return product;


197  }


198  private static ISymbolicExpressionTreeNode Product(IEnumerable<ISymbolicExpressionTreeNode> fs) {


199  var product = mulSy.CreateTreeNode();


200  foreach (var f in fs) product.AddSubtree(f);


201  return product;


202  }


203  private static ISymbolicExpressionTreeNode Div(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {


204  var div = divSy.CreateTreeNode();


205  div.AddSubtree(f);


206  div.AddSubtree(g);


207  return div;


208  }


209 


210  private static ISymbolicExpressionTreeNode Sum(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {


211  var sum = addSy.CreateTreeNode();


212  sum.AddSubtree(f);


213  sum.AddSubtree(g);


214  return sum;


215  }


216  private static ISymbolicExpressionTreeNode Subtract(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {


217  var sum = subSy.CreateTreeNode();


218  sum.AddSubtree(f);


219  sum.AddSubtree(g);


220  return sum;


221  }


222  private static ISymbolicExpressionTreeNode Cosine(ISymbolicExpressionTreeNode f) {


223  var cos = cosSy.CreateTreeNode();


224  cos.AddSubtree(f);


225  return cos;


226  }


227  private static ISymbolicExpressionTreeNode Abs(ISymbolicExpressionTreeNode f) {


228  var abs = absSy.CreateTreeNode();


229  abs.AddSubtree(f);


230  return abs;


231  }


232  private static ISymbolicExpressionTreeNode Square(ISymbolicExpressionTreeNode f) {


233  var sqr = sqrSy.CreateTreeNode();


234  sqr.AddSubtree(f);


235  return sqr;


236  }


237  private static ISymbolicExpressionTreeNode SquareRoot(ISymbolicExpressionTreeNode f) {


238  var sqrt = sqrtSy.CreateTreeNode();


239  sqrt.AddSubtree(f);


240  return sqrt;


241  }


242 


243  private static ISymbolicExpressionTreeNode CreateConstant(double v) {


244  var constNode = (ConstantTreeNode)constantSy.CreateTreeNode();


245  constNode.Value = v;


246  return constNode;


247  }


248 


249  public static bool IsCompatible(ISymbolicExpressionTree tree) {


250  var containsUnknownSymbol = (


251  from n in tree.Root.GetSubtree(0).IterateNodesPrefix()


252  where


253  !(n.Symbol is Variable) &&


254  !(n.Symbol is Constant) &&


255  !(n.Symbol is Addition) &&


256  !(n.Symbol is Subtraction) &&


257  !(n.Symbol is Multiplication) &&


258  !(n.Symbol is Division) &&


259  !(n.Symbol is Logarithm) &&


260  !(n.Symbol is Exponential) &&


261  !(n.Symbol is Square) &&


262  !(n.Symbol is SquareRoot) &&


263  !(n.Symbol is Cube) &&


264  !(n.Symbol is CubeRoot) &&


265  !(n.Symbol is Absolute) &&


266  !(n.Symbol is AnalyticQuotient) &&


267  !(n.Symbol is Sine) &&


268  !(n.Symbol is Cosine) &&


269  !(n.Symbol is Tangent) &&


270  !(n.Symbol is StartSymbol)


271  select n).Any();


272  return !containsUnknownSymbol;


273  }


274  }


275  }

