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 


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 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 2argument 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 noninteger 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  }

