[16206]  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;


[17066]  23  using System.Collections.Generic;


[16206]  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) {


[17066]  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");


[16206]  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));


[17066]  38  //var dTree = Derive(mainBranch, variableName);


[16206]  39  root.GetSubtree(0).AddSubtree(dTree);


 40  return new SymbolicExpressionTree(root);


 41  }


 42 


[17066]  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();


[16206]  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;


[17066]  94  } else


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


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


[16206]  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);


[17066]  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


[16206]  115  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


[17066]  116  var g = Product(branch.Subtrees.Skip(1).Select(n => (ISymbolicExpressionTreeNode)n.Clone()));


[16206]  117  var fprime = Derive(f, variableName);


 118  var gprime = Derive(g, variableName);


[17066]  119  var gSqr = Square(g);


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


 121  }


[16206]  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  }


[17066]  131  if (branch.Symbol is Square) {


[16206]  132  var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();


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


[17066]  134  }


 135  if (branch.Symbol is SquareRoot) {


[16206]  136  var f = (ISymbolicExpressionTreeNode)branch.Clone();


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


[17066]  138  return Product(Div(CreateConstant(1.0), Product(CreateConstant(2.0), f)), Derive(u, variableName));


[16206]  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  }


[17066]  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));


[16206]  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  }


[17066]  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  }


[16206]  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  }


[17066]  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 


[16206]  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) &&


[17066]  225  !(n.Symbol is Tangent) &&


[16206]  226  !(n.Symbol is StartSymbol)


 227  select n).Any();


 228  return !containsUnknownSymbol;


 229  }


 230  }


 231  }

