1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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 


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

